3 ms·
Under these conditions if you are doing a DFS over positions then you need to store O(n^2) positions in memory, considering that a position takes O(n) memory, y
by eterevsky 3y ago
Under these conditions if you are doing a DFS over positions then you need to store O(n^2) positions in memory, considering that a position takes O(n) memory, you are using O(n^3) memory in total.
- kevinwang 3y agoIf 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.