I was reading about bounded 2-player games in chapter 6.1 of Games, Puzzles, and Computation. "Bounded" here means theres some finite resource of the game which imposes a limit on the number of player moves.
Where it says that,
Deciding such games can be no harder than PSPACE, because a Turing machine using space polynomial in board size can perform a depth-first search of the entire game tree..."
I do not fully understand why. Polynomial in the size of the game tree makes sense, since depth-first search is polynomial time $O(V + E)$, but why is it necessarily true that a depth-first search of the game tree is polynomial to the size of the board?
As an example to illustrate what I mean, suppose we have a board of size $n$, and initially there are $n$ moves available; 1 per location. On each turn, a player takes $1$ of the locations, reducing the available moves by 1. So the game tree has a size of about $n(n-1)(n-2)...(1) = n!$. The board is size $O(n)$, but the game tree is $O(n!)$ which does not look to me like a depth-first search that is polynomial to the size of the board. What am I missing here?
You seem to be ignoring the distinction between time and space. The depth-first search will usually take considerably more than polynomial time (relative to the board size), but it will take only polynomial space. The reason is that space can be re-used. After computing what happens along one branch of the game tree, you can back up and change your last choice (i.e., follow the next path in the depth-first search) without needing to remember the end part of the previous path. At any time, all that the computer needs to record is (1) the board position currently under consideration and (2) how it got there in the game tree (e.g., "at the root, use option 3; at the next node option 82" etc.). Both of these require only polynomially much storage space.