2 ms·
Yes. But you don't need to keep the whole tree in memory.
by eterevsky 3y ago
Yes. 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.