5 ms·
I meant optimal perfect strategy, either via a proof or a game tree search (alpha-beta pruning). With 3^81 game states (most not attainable), it should be sear
by fsk 13y ago
I meant optimal perfect strategy, either via a proof or a game tree search (alpha-beta pruning). With 3^81 game states (most not attainable), it should be searchable.
More precisely, the game has a finite # of states, and cannot end in a draw. It's always a win for P1 or P2. If both people play perfectly, who wins and what is the optimal strategy? (Note: It is possible that this game is a P2 win, because your move restricts your opponent's choice.) (For the person with the guaranteed win, what strategy forces the win? For the person who can't guaranteed win, what strategy gives your opponent the most opportunity to make a mistake?)
- gibybo 13y agoI'm not so sure that it's searchable. 3^81 is quite a lot. I don't know of any solved game with that many. Tic-tac-toe, connect 4, checkers, etc all have less. I think 3^81 is comparable to 9x9-Go and Chess which are both unsolved. I suppose it depends how aggressive you can prune (which, admittedly, is probably pretty aggressively).
- fsk 13y agoTo (perfectly) solve 9x9 go, you need to consider almost every move at every turn. That's a branching factor of 40+. In this game, there are (usually) at most 9 legal moves per turn. The branching factor is a lot less. (Giving your opponent free choice to play anywhere is frequently a mistake.)
- Retric 13y agoIt's no where near 3^81 as there are winning strategy's that don't fill the board. Optimal play is really about delaying how long it takes to force a win.