Why is the result of minimax of tic-tac-toe always a draw?

user_13154187 0
Viewed 270

I found the below text from here, saying that the result for minimax for games like tic-tac-toe and chess will always be a draw. I also saw minimax algorithms for unbeatable tic-tac-toe. But I don't quite understand the reason why minimax results in a draw. Is it because there is no guaranteed winning or losing move and thus the best possible option for both players is a draw?

a computer running a minimax algorithm without any sort of enhancements will discover that, if both it and its opponent play optimally, the game will end in a draw no matter where it starts, and thus have no clue as to which opening play is the "best." Even in more interesting win-or-lose games like chess, even if a computer could play out every possible game situation (a hopelessly impossible task), this information alone would still lead it to the conclusion that the best it can ever do is draw (which would in fact be true, if both players had absolutely perfect knowledge of all possible results of each move).

minimax artificial-intelligence
1 Answers

The information from the site you’ve linked is slightly incorrect.

We know from a brute-force exploration of the game that with perfect play tic-tac-toe will always end in a draw. That is, if both players play the game according to the best possible strategy, then the game ends in a draw. There’s a wonderful xkcd graphic that details how to play perfectly.

If you were to run a minimax search over the game all the way to the end, it isn’t necessarily the case that minimax won’t know what option to pick. Rather, minimax would select any move that leads to a forced draw, since it always picks a move that leads to the best possible result for the player. It’s “unbeatable” in the sense that a perfect minimax player will never lose and, if you play against it with a suboptimal strategy, it may be able to find a forced win and beat you.

As for chess - as of now (December 2021) no one knows whether chess ends in a draw with perfect play or whether one of the players has a forced win. We simply aren’t able to explore the game tree in that much depth. It’s entirely possible that white has a forced win, for example, in which case a minimax search given sufficient time and resources playing as white will always outplay you.

user_5015570
Related