Minimax Algorithm and Alpha-Beta Pruning Explained (with Tic Tac Toe)
A plain-English explanation of the minimax algorithm, evaluation functions and alpha-beta pruning: the ideas behind our Tic-Tac-Toe and Four in a Row opponents.
When you play our Tic-Tac-Toe or Four in a Row against the computer, there's no huge database of games behind it and no machine learning. The opponent uses a few classic ideas from computer science that have powered game-playing programs since the 1950s. They're surprisingly easy to understand, and knowing how they work can even help you beat the computer.
The game tree
Imagine writing down the current board position at the top of a page. Below it, draw every possible move you could make, each as a new board. Below each of those, draw every reply your opponent could make, and so on. The result is a game tree: a branching diagram of every way the game could continue.
At the very bottom of the tree are finished games: wins, losses and draws. If a computer could see the whole tree, it could pick a path that leads to a win whenever one exists. The question is how to choose, given that your opponent is also choosing.
Minimax: assume the opponent is smart
The answer is an idea called minimax. Score every finished game from the computer's point of view, say +1 for a computer win, −1 for a loss and 0 for a draw. Now work upward from the bottom of the tree:
- On the computer's turn, it will choose the move with the highest score.
- On the opponent's turn, assume they'll choose the move with the lowest score, the one that's worst for the computer.
Alternating "max" and "min" all the way up gives every move at the top a score. The computer plays the move with the best one. That's the whole algorithm. Its name comes from this alternation: maximise your result, assuming the opponent minimises it.
The idea goes back to mathematician John von Neumann, who proved a "minimax theorem" about two-player games in 1928, long before computers existed to use it.
Why Tic-Tac-Toe is easy for a computer
Tic-tac-toe is tiny. There are only 255,168 possible complete games, and far fewer distinct positions. A modern computer can explore the entire tree in a fraction of a second. That's why our Unbeatable setting really is unbeatable: it doesn't guess, it knows the outcome of every possible move. With perfect play on both sides the result is always a draw, so the best you can do is match it.
One small refinement makes it feel more natural: it prefers to win sooner rather than later, and to lose later rather than sooner. It does this by giving slightly higher scores to quicker wins.
Four in a Row is too big
Four in a Row's 7 × 6 board has an astronomically larger tree, with trillions of possible positions. The game was solved in 1988, but that took clever mathematics and a lot of computing. A browser game can't search to the end on every move.
So the computer looks only a limited number of moves ahead (one, three or six on our Easy, Medium and Hard settings) and then estimates how good the position is, using an evaluation function.
Evaluation functions: educated guesses
An evaluation function turns a board that isn't finished into a number. Ours looks at every possible line of four squares on the board and scores it:
- Three of my discs and one empty square: a big plus.
- Two of my discs and two empty squares: a small plus.
- Three of the opponent's discs and one empty square: a big minus.
- Discs in the centre column: a small bonus, because central discs take part in more lines.
Adding these up gives a rough sense of who's ahead. The deeper the computer searches before using this estimate, the less the estimate's mistakes matter. That's why Hard is so much stronger than Medium: three extra moves of look-ahead lets it see traps that a static score would miss.
Alpha-beta pruning: skipping what doesn't matter
Searching six moves deep means looking at up to 7 × 7 × 7 × 7 × 7 × 7 = 117,649 positions. That's manageable, but each extra move multiplies the work by seven. Alpha-beta pruning is the trick that makes deeper search practical.
The idea: suppose the computer has already found a move that guarantees it a score of at least 5. While examining another move, it discovers that the opponent has a reply leading to a score of 2. There's no need to look at the rest of the replies to that move. Whatever they are, the opponent can already hold the computer to 2 or less, which is worse than the 5 it has. That whole branch can be "pruned" without changing the final answer.
With good move ordering, alpha-beta can roughly double how deep a program searches in the same time. Our Four in a Row checks the centre columns first for exactly this reason: strong moves found early lead to more pruning.
Alpha-beta was developed by several researchers in the 1950s and 60s, and versions of it powered the strongest chess programs for decades, including Deep Blue, the IBM machine that beat world champion Garry Kasparov in 1997.
Using this to beat the computer
Knowing how the opponent thinks reveals its weaknesses:
- The horizon: a computer searching three moves deep can't see a trap that springs on move four. Long-term plans, like building a threat that only becomes playable much later, are exactly what lower levels miss.
- The evaluation is simple: it doesn't understand subtle ideas like which row a threat is on (see our Four in a Row strategy guide). Positional play beats it more often than tactics do.
- On Easy, it sometimes plays randomly on purpose, so punish loose moves immediately.
Beyond minimax
Modern top programs for games like Go and chess have added new techniques such as Monte Carlo tree search and neural-network evaluation functions that learn from millions of games. But the basic shape is still there: look ahead, assume the opponent plays well, estimate positions you can't search to the end, and don't waste time on branches that can't matter.