4 ms·
Consider a game like go, where board size is n. This means the game tree's branching factor is O(n). Let's say the game tree's depth is O(n) too. Then what is t
by kevinwang 3y ago
Consider a game like go, where board size is n. This means the game tree's branching factor is O(n). Let's say the game tree's depth is O(n) too. Then what is the size of the tree?
- eterevsky 3y agoUnder 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.