MinMax in practice: think backwards, assume the worst opponent, shortcut where possible.
Concepts 8 min Intermediate April 26, 2026
In 1997, IBM’s Deep Blue defeated reigning world chess champion Garry Kasparov. The machine did not understand chess — it evaluated 200 million positions per second using an idea that traces back to Ernst Zermelo (1913) and John von Neumann (1928). This idea is the MinMax algorithm, and it remains the foundation of classical game AI to this day.
1997 Competitions
Deep Blue Defeats Kasparov
The first match victory of a machine over a reigning world chess champion under tournament conditions. On May 11, 1997, Deep Blue made history when the IBM supercomputer defeated Garry Kasparov in the rematch in New York with a score of 3.5 to 2.5. Following the 1996 defeat, IBM had fundamentally overhauled the system: new chess chips doubled the speed to 200 million positions per second, improved endgame databases and grandmaster consultation refined its playing strength. The decisive sixth game lasted just one hour — after a knight sacrifice, Kasparov quickly found himself in an objectively lost position and resigned as early as move 19, an unprecedented moment in his career. The victory demonstrated for the first time the superiority of computers in complex strategic thinking and marked a turning point in public perception of AI. The prize money of 00,000 for Deep Blue underscored the historic significance of this triumph of machine intelligence.
In this article, you will learn how a computer systematically thinks through all possible moves, finds the optimal move against a perfect opponent, and skips entire subtrees without changing the result.
The Game Tree — Thinking Through All Possibilities
Game Tree
AnalogyDefinition
Imagine two chess players thinking ahead: "If I play move A, she will play move B, then I could play move C..." This mental chain of moves and counter-moves IS the game tree — the algorithm just builds it systematically instead of intuitively.
Analogy:
Imagine two chess players thinking ahead: "If I play move A, she will play move B, then I could play move C..." This mental chain of moves and counter-moves IS the game tree — the algorithm just builds it systematically instead of intuitively.
Definition:
A game tree is a directed graph where each node represents a game state and each edge represents a legal move. Players alternate turns: MAX nodes (the maximizing player) and MIN nodes (the minimizing player). Leaf nodes carry evaluation values.
The comparison has an important limit: humans intuitively skip variations and only think through promising moves. The algorithm builds the tree systematically and completely — it "forgets" nothing.
A concrete example: In Tic-Tac-Toe, MAX initially has 9 possible moves. For each of these, MIN has 8 responses. After just two half-moves, the tree already contains 72 nodes. In chess, with a branching factor of about 35 and a depth of roughly 80 half-moves, there are more possible positions than atoms in the universe.
~35
Chess Branching Factor Average legal moves per position
10⁴⁷
Possible Chess Positions More than atoms in the observable universe
Misconception: The computer plays every game to the end
In practice, this is impossible. Instead, a depth limit and a heuristic evaluation function are used. In chess, this might count the material value of pieces. The tree is never fully built — the evaluation function estimates the quality of a position without actually playing the game to completion.
The MinMax Algorithm — Optimal Against the Perfect Opponent
MinMax Algorithm
AnalogyDefinition
The principle of "expect the worst": in a zero-sum game, your loss is your opponent's gain — so they will always choose the most painful move against you. You plan a strategy under exactly this assumption and pick the option where this worst-case scenario is the least bad.
Analogy:
The principle of "expect the worst": in a zero-sum game, your loss is your opponent's gain — so they will always choose the most painful move against you. You plan a strategy under exactly this assumption and pick the option where this worst-case scenario is the least bad.
Definition:
MinMax is a recursive algorithm that propagates evaluations from the leaves of the game tree upward. At MAX nodes, the highest child value is chosen; at MIN nodes, the lowest. The result is the optimal move under the assumption of a perfectly playing opponent.
The analogy is correct: MinMax thinks pessimistically. But against weaker opponents, this caution can cause exploitable weaknesses to be overlooked.
MinMax Calculation: Step by Step
1
At the bottom of the tree are the results: [3, 5], [6, 9], [1, 2], [0, -1]. These are the evaluations when the game is played to completion.
2
At the lower nodes, it is our turn (MAX). We pick the better option each time: max(3,5) = 5, max(6,9) = 9, max(1,2) = 2, max(0,-1) = 0.
3
Now the opponent's turn (MIN). They want to hurt us and always pick the worst for us: Left they choose min(5,9) = 5, right min(2,0) = 0. Going right would give us only 0 points.
4
Back to us (MAX): Left guarantees 5 points, right only 0. max(5, 0) = 5 — we go left.
The algorithm chooses the left subtree with a guaranteed value of 5. No matter how the opponent plays — it cannot get worse than 5 for MAX.
O(bᵈ)
MinMax Runtime b = branching factor, d = search depth. Exponential growth makes pure MinMax impractical for complex games.
Misconception: MinMax always finds the best move
MinMax guarantees the optimal move only under three conditions: (1) the opponent plays perfectly, (2) it is a zero-sum game with complete information (one player's gain is the other's loss, and both players see all information — like chess, but not poker), and (3) the tree is searched to sufficient depth. Against imperfect opponents, more aggressive strategies may perform better. With insufficient search depth, the quality depends on the heuristic evaluation function.
Interactive: MinMax Game Tree
The article describes how MinMax propagates evaluations from the leaves upward. Here you can step through the algorithm and see how MAX and MIN make their decisions.
Step 1 / 8
The leaf nodes show the game outcomes. These are the evaluation values when the game is played to completion.
Alpha-Beta Pruning — Smart Cutting
Alpha-Beta Pruning
AnalogyDefinition
Imagine you are comparing job offers by total salary. Offer A guarantees you 5,000 EUR per month (your Alpha). For Offer B, you learn that the employer pays a maximum of 3,000 EUR for this position. You stop negotiating immediately — Offer B cannot beat Offer A. You have "pruned" the rest.
Analogy:
Imagine you are comparing job offers by total salary. Offer A guarantees you 5,000 EUR per month (your Alpha). For Offer B, you learn that the employer pays a maximum of 3,000 EUR for this position. You stop negotiating immediately — Offer B cannot beat Offer A. You have "pruned" the rest.
Definition:
Alpha-Beta Pruning extends MinMax with two bounds: Alpha (the best value MAX can guarantee so far) and Beta (the best value for MIN). As soon as Alpha >= Beta (a so-called beta cutoff), the remaining children of the current node are skipped — they provably cannot change the result.
The job analogy shows a simple comparison. In the game tree, evaluations are nested — but the core principle of "stop when it provably gets worse" is identical.
Back to our example: After evaluating the left subtree, the root has Alpha = 5. In the right subtree, the first MAX node yields max(1,2) = 2. The MIN node now has candidate 2, which is already less than Alpha = 5 (beta cutoff). The second MAX node [0, -1] is never evaluated at all. Result: identical (move left, value 5), but with fewer calculations.
Pure MinMax
Evaluates all 8 leaf nodes. Computes every single path in the tree. Guarantees optimal result, but maximum computational effort.
MinMax with Alpha-Beta
Skips provably irrelevant branches. In our example: 6 instead of 8 nodes evaluated. Exactly the same result, less work.
O(bᵈᐟ²)
Alpha-Beta Best Case Effectively twice the search depth in the same time. Achieved through optimal move ordering.
200M/s
Deep Blue (1997) Positions per second. MinMax with Alpha-Beta on specialized hardware.
Misconception: Pruning produces a different or approximate result
Alpha-Beta Pruning produces exactly the same result as pure MinMax. It is not an approximation — it is a mathematical proof that certain subtrees cannot influence the result. The chosen move is identical.
Deep Dive: From Shannon to Deep Blue
In 1950, Claude Shannon published his landmark paper on chess programming — one of the first formal descriptions of computer-based game strategy. In 1953, Alan Turing wrote a chess program that he executed by hand for lack of a computer. Over the following decades, MinMax and Alpha-Beta Pruning (formally analyzed by Knuth and Moore, 1975) became the standard approach. The pinnacle: in 1997, Deep Blue, an IBM supercomputer with specialized chess chips, defeated Garry Kasparov. Nearly two decades later came the next breakthrough: in 2016, AlphaGo marked the next paradigm shift with Monte Carlo Tree Search and neural networks.
Deep Dive: Move Ordering — The Key to Efficient Pruning
The efficiency of Alpha-Beta Pruning depends heavily on the order in which moves are evaluated. When the best moves are examined first, the algorithm prunes the maximum number of branches — in the best case reducing complexity to the square root of the original runtime — effectively doubling search depth in the same time. When the worst moves are examined first, nothing is pruned and Alpha-Beta behaves like pure MinMax. In practice, chess programs use the "killer move heuristic": moves that have already caused cutoffs in parallel variations are examined first.
Key Takeaways
A game tree maps all possible move sequences. MAX nodes choose the highest value, MIN nodes the lowest — this models the worst-case opponent.
MinMax guarantees the optimal move against a perfect opponent, but its exponential runtime makes it impractical for complex games without optimization.
Alpha-Beta Pruning produces exactly the same result as MinMax, but prunes provably irrelevant branches — effectively enabling twice the search depth in the same time.
Quiz: MinMax & Pruning
Question 1 / 4
Not completed
What does a MIN node do in a MinMax tree?
1. What does a MIN node do in a MinMax tree?
☐ A) It chooses the child with the highest value
☐ B) It chooses the child with the lowest value
☐ C) It chooses a random child
☐ D) It calculates the average of all child values
2. A MinMax tree has a root (MAX) with two children (MIN nodes). The left MIN node has children with values [4, 7]. The right MIN node has children with values [2, 9]. What is the value at the root?
☐ A) 9
☐ B) 7
☐ C) 4
☐ D) 2
3. During Alpha-Beta Pruning, Alpha is currently 6 at a MAX node. A child MIN node evaluates its first child and gets 3. What happens?
☐ A) The MIN node continues evaluating its remaining children
☐ B) The remaining children of this MIN node are pruned (beta cutoff), because 3 < 6
☐ C) Alpha is updated to 3
☐ D) The entire subtree is restarted
4. Deep Blue defeated Kasparov in 1997 using MinMax and Alpha-Beta Pruning. A developer argues that simply increasing search depth always produces a stronger chess program. What critical factor does this argument overlook?
☐ A) Beyond a certain point, the quality of the heuristic evaluation function matters more than raw search depth
☐ B) MinMax does not work for chess
☐ C) Alpha-Beta Pruning only works with shallow trees
☐ D) Chess has too few possible moves to benefit from deeper search
Answer Key: 1) B · 2) C · 3) B · 4) A
Checkpoint: MinMax & Pruning
A chess computer cannot calculate all positions to the end of the game. How does it solve this problem — and what weakness does this solution introduce?
Why is it essential in the MinMax algorithm to always assume the opponent will choose the worst move for us?
Alpha-Beta Pruning cuts off and ignores entire branches of the game tree. Why does it still guarantee finding the same best move as without pruning?