3 ms·
If a tree's branching factor (i.e. the number of possible actions per turn) is N, and the depth of the tree (i.e. the length of the game) is N, the size of the
by kevinwang 3y ago
If a tree's branching factor (i.e. the number of possible actions per turn) is N, and the depth of the tree (i.e. the length of the game) is N, the size of the tree is N^N, not N^2.
- eterevsky 3y agoYes. But you don't need to keep the whole tree in memory.
- kevinwang 3y agoAhh sorry, I see what you're saying now. Yeah I guess it's in PSPACE if the length of each game is polynomial in n, and EXPTIME if games can go on for longer. I guess chess (without the 50-move rule), checkers, and go (with a certain ruleset) can go on for longer.