Minimax and Alpha–Beta Pruning

Worked Example

Consider a zero-sum game tree of depth 3 with 8 terminal leaves. The root node is a MAX player. Depth 1 nodes belong to the MIN player, and depth 2 nodes belong to MAX. Let the leaf scores from left to right be: 3, 5, 6, 9, 1, 2, 0, -1.

With standard Minimax:

1. The left MAX node at depth 2 sees leaves 3, 5. It chooses the maximum: 5.
2. The second MAX node at depth 2 sees leaves 6, 9. It chooses the maximum: 9.
3. The MIN node at depth 1 (left child of root) sees options 5, 9 from its children. It chooses the minimum: 5.
4. The third MAX node at depth 2 sees leaves 1, 2. It chooses 2.
5. The fourth MAX node at depth 2 sees leaves 0, -1. It chooses 0.
6. The MIN node at depth 1 (right child of root) sees options 2, 0. It chooses 0.
7. The MAX root node sees options 5, 0. It chooses 5.

With Alpha-Beta pruning, we track bounds [α, β] for each node:

1. The search explores the left side of the tree. The left MIN node receives its first child value 5, and sets its upper bound β = 5.
2. The next MAX node at depth 2 evaluates its first leaf, 6. This updates its lower bound α = 6.
3. Since α (6) ≥ β (5), the MIN node will never choose this MAX node. The algorithm prunes the remaining leaf (9) and skips evaluating it.
4. Similarly, on the right half of the tree, the right MIN node evaluates its first child (which returns 2), setting its β = 2.
5. The MAX root has a lower bound α = 5 (from the left side). Since α (5) ≥ β (2), it prunes the rest of the right subtree.

Experiment

You can try this interactive simulation at Minimax and Alpha-Beta Pruning. Use the Leaf scores input to test different scenarios.

1. Enter comma-separated integers such as -1,0,2,1,9,6,5,3 in the Leaf scores input.
2. Toggle the Pruning checkbox on or off to compare the evaluated leaves.
3. Click Finish: with pruning on this input gives root 5, seven evaluated leaves and one pruned leaf. With Pruning off, Finish gives the same root 5 from eight evaluated leaves. Reset rewinds without changing the input.
4. Use the Step button to watch the depth-first search traverse the tree, and note that when Pruning is enabled, branches are marked with an "X" once α ≥ β is met.

Limitations

This visualization uses a fixed, complete binary tree of depth 3 and synthetic terminal utility values. This view also cuts at equal bounds: a tied alternative cannot improve the root utility, and the root keeps its left choice. A returned cutoff bound is not an exact value for that skipped subtree. Real game-playing AI (like those for Chess or Go) would not reach terminal states so quickly; instead, they use depth-limited search and heuristic static evaluation functions for non-terminal leaves. Additionally, modern engines enhance Alpha-Beta pruning with techniques like move ordering, iterative deepening, and transposition tables, which are not depicted here.

References

This algorithm and the theoretical basis for bounds are detailed here:

• Minimax search and Alpha-Beta Pruning (CS312 Recitation 21, Cornell University)