Minimax is a search method for two-player, turn-taking games in which each side is assumed to pick its best available move. One player tries to maximize a position's score and the other tries to minimize it, so the program can work backward from the end of the game to the current move. In tic-tac-toe the complete game tree has 549,946 positions, and alpha-beta pruning reaches the same verdict, a draw, after examining 18,297 of them.
Key takeaways
- Minimax scores every position from one player's point of view: the maximizing player takes the highest child value, the minimizing player takes the lowest.
- Claude Shannon described a minimax procedure with a numeric evaluation function for chess in a paper first presented on March 9, 1949.
- Alpha-beta pruning returns exactly the value minimax would, but skips branches that cannot change the result.
- How many positions get skipped depends on move ordering. In a computed tic-tac-toe run, 18,297 of 549,946 positions were examined.
- The method needs perfect information and strictly opposed goals, so it does not fit games with hidden cards or cooperative aims.
What the two players are assumed to do
A game tree starts with the current position at the root. Every legal move leads to a child position, and the tree keeps branching until a position ends the game or the search stops for another reason. Minimax gives each end position a number, for example +1 for a win by the maximizing player, 0 for a draw, and -1 for a loss. Values then travel upward. At a position where the maximizing player moves, the value is the largest value among the children. Where the minimizing player moves, it is the smallest.
The assumption behind this is that the opponent never errs. That makes minimax a worst-case planner: the move it picks guarantees at least the computed value against any reply. In his 1950 paper in the Philosophical Magazine, first presented on March 9, 1949, Claude Shannon wrote out the chess case in these terms, with White choosing the move that maximizes the value Black can then hold down by minimizing.
A worked example with a three-move tree
The tree below is an illustrative example, not taken from a real game. The maximizing player has three moves, A, B, and C. After each, the minimizing player chooses among three replies, and the leaf numbers are scores for the maximizing player.
| First move | Leaf scores after each reply | Minimizing player picks | Value of the move |
|---|---|---|---|
| A | 3, 5, 9 | 3 | 3 |
| B | 2, 8, 1 | 1 | 1 |
| C | 4, 6, 7 | 4 | 4 |
The maximizing player takes the largest of 3, 1, and 4, so move C is chosen and the position is worth 4. Now add pruning. After move A is scored at 3, the maximizer already has a guaranteed 3. Under move B the first leaf is 2. Whatever the other two leaves hold, the minimizer can hold B to 2 or less, which is already worse than 3, so those two leaves never need to be read. Under C the three leaves must all be read, because 4 beats the current best. Seven of the nine leaves were examined and the answer is the same.
Alpha-beta pruning and what it saves
Alpha-beta keeps two running bounds while it searches: alpha, the best value the maximizing player is already assured of, and beta, the best the minimizing player is assured of. When a branch's value falls outside those bounds it cannot matter, and the rest of that branch is skipped. Donald Knuth and Ronald Moore published an analysis of the procedure in the journal Artificial Intelligence in 1975, and the technique is a standard topic in the adversarial search chapter of the textbook Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig.
The saving depends on the order in which moves are tried. The counts below come from a short program written for this article that plays out every legal tic-tac-toe game from an empty board, trying cells in fixed order from the top left.
| Measure | Plain minimax | Alpha-beta |
|---|---|---|
| Positions visited, counting repeats | 549,946 | 18,297 |
| Value of the empty board | 0 (draw) | 0 (draw) |
| Complete games reached by plain search | 255,168 | not applicable |
Only 5,478 distinct board arrangements can occur in a legal game, so most of the 549,946 visits repeat a position reached by a different move order. Programs that store results for positions already seen cut the work further, but that is a separate technique from pruning. A different move order would change the 18,297 figure, which is why game programs try promising moves first.
Why real games need a depth limit
Tic-tac-toe can be searched to the end. Chess cannot. Shannon estimated roughly 10^43 possible positions and about 10^120 variations from the starting position, and concluded that a machine could not examine them all. His answer was to search a few moves ahead and then score the position with an evaluation function. His illustrative function counted material with a queen worth about nine, a rook five, a bishop or knight three, and a pawn one, then subtracted small penalties for doubled, backward, and isolated pawns.
Depth-limited minimax is therefore only as good as its evaluation function and its speed. IBM's Deep Blue defeated Garry Kasparov 3.5 to 2.5 in May 1997 and, according to IBM's history page, evaluated about 200 million chess positions per second. That machine paired fast search with hand-built evaluation, an approach that differs from systems that learn their evaluation from data.
Checklist for reading a minimax tree
- Mark whose turn it is at each level, since the choice rule alternates between highest and lowest.
- Score the leaves from one fixed player's perspective and keep that perspective throughout.
- At a minimizing level, write the smallest child value. At a maximizing level, write the largest.
- When pruning, compare each new value with the bounds already held by the parent levels.
- Check that the result is the same with and without pruning. A difference points to an error.
Where minimax does not apply
Minimax needs a game in which both players see the whole position, moves alternate, and one side's gain is the other's loss. Card games with hidden hands, games with dice, and settings where players can cooperate break at least one of those conditions. The method also treats the opponent as flawless, so against a weaker opponent it may pass up chances that a riskier move would offer. It says nothing about how to learn an evaluation function; it only uses one.
FAQ
What does minimax mean?
The name describes the two alternating rules: the maximizing player picks the highest value available and the minimizing player picks the lowest. Together they assume that each side plays its best moves.
Does alpha-beta ever give a different answer from minimax?
No. With the same search depth and the same evaluation, it returns the same value. It only avoids work on branches that cannot change that value.
Why is tic-tac-toe always a draw under minimax?
The search shows that neither player can force a win against correct replies, so the value of the empty board is 0. In the computed run described above, both plain minimax and alpha-beta returned that value.
Is this how modern game-playing AI works?
Search with pruning is still a core idea in game programs, but many systems combine it with learned evaluation instead of hand-written rules. How any specific program is built has to be checked in its own documentation.
Related reading
- Heuristic problems and how estimates guide search
- How problems are formulated for AI search
- Where AI problem solving fits
- Why the size of a problem space matters
More in AI Basics.
Last verified: October 2026
Sources
- Programming a Computer for Playing Chess, Shannon C E, Philosophical Magazine, Series 7, Vol. 41, No. 314, March 1950
- An analysis of alpha-beta pruning, Knuth D E and Moore R W, Artificial Intelligence 6(4), 1975
- Artificial Intelligence: A Modern Approach, 4th US edition, Russell S and Norvig P, chapter 5 Adversarial Search and Games, UC Berkeley course site
- Deep Blue, IBM History, 2026 page
- Tic-tac-toe node counts: computed for this article, October 27, 2026, by exhaustive search