How a Computer Plays Perfect Tic Tac Toe
Our Tic Tac Toe game plays perfectly. It will never lose to you, ever, no matter how clever you think you are. How does it do that? The answer is an algorithm called minimax, one of the simplest and most beautiful ideas in computer science. Understanding it does not require any math beyond arithmetic, and once you see it you will never look at game-playing AI the same way.
The core idea
Minimax assumes two players take turns, and that each player always makes the move that is best for them. On your turn you want the outcome that is best for you, the human. On the computer's turn it wants the outcome that is best for it. Both players are playing at their maximum ability. No luck, no mistakes.
If you can enumerate every possible future move from a given position, and you know how each one ends (win, lose, or draw), then you can work backward from the end of the game to the present and pick the move that guarantees the best outcome you can force.
Why Tic Tac Toe is easy to solve
Tic Tac Toe has only 255,168 possible games after accounting for symmetries. A modern computer can enumerate all of them in a few milliseconds. For each one, the outcome is known: X wins, O wins, or draw. Minimax just traces these outcomes backward from the end of each line to choose the optimal next move.
Tic Tac Toe has 255,168 possible games. A laptop can walk through all of them before you finish reading this sentence. That is why our AI never loses.
A walk-through
Imagine the computer is evaluating its next move. It tries each of the nine possible squares in turn. For each, it asks: "If I play here, what does the human do next?" The human (in the computer's model) tries every response and picks the one that leads to the worst outcome for the computer. Then the computer, seeing that worst outcome, picks the square that still leads to the best possible result under the assumption of perfect human play.
This sounds recursive because it is. The computer's evaluation at each step depends on the human's response, which depends on the computer's next move, which depends on the human's next move. In code, this is just a function that calls itself until the game ends.
Minimax beyond Tic Tac Toe
For Tic Tac Toe, minimax is trivial because the game tree is small. For chess, the tree is about 10120 positions, which no computer can ever enumerate. Modern chess engines use variations of minimax (notably alpha-beta pruning, which skips branches that cannot possibly affect the answer) plus heuristic evaluation that estimates positions without looking to the end.
AlphaGo, the 2016 program that beat world-champion Lee Sedol at Go, replaces classical minimax with a Monte Carlo tree search guided by a deep neural network — but the core intuition of "trace outcomes backward and pick the best forced line" is still present.
Try to force a draw
Against a perfect minimax player, the human can at best draw. Any suboptimal move hands the computer a win. The best opening for the human is a corner; center gives the AI more winning lines; edges almost always lose. Play our game and see how quickly you can get to draws consistently.