Alpha-Beta Pruning

The Simplest Explanation

Minimax wastes effort on branches that could never influence the final decision. Alpha-beta's insight:

"While backing up values, keep track of the best already-guaranteed options for both sides. If a branch turns out worse than something already guaranteed — stop looking. Cut it off."

Two values travel down the tree:

• α (alpha): the best value MAX is already assured of somewhere else (lower bound). Starts at $-\infty$.
• β (beta): the best value MIN is already assured of (upper bound). Starts at $+\infty$.

The cutoff rule: whenever $\alpha \geq \beta$, stop expanding the current node and return. Nothing below can change the outcome.

The Rules (memorize these four lines)

1. At a MAX node: update $\alpha \leftarrow \max(\alpha, \text{child value})$
2. At a MIN node: update $\beta \leftarrow \min(\beta, \text{child value})$
3. Children inherit the current $(\alpha, \beta)$ window
4. If at any point $\alpha \geq \beta$: prune remaining children of this node and back up immediately
   • If cut off at a MAX node → called a β-cutoff
   • If cut off at a MIN node → called an α-cutoff

Interactive Demo

Same idea as minimax — but watch two leaves escape evaluation entirely:

What Just Happened

• After B backs up 3, the root knows: whatever else happens, MAX gets ≥ 3 ($\alpha = 3$).
• Inside C, the first child returns 2. C is a MIN node, so C ≤ 2 < 3. MAX would never pick C.
• Therefore C's remaining children (4, 6) are irrelevant — pruned without being read.

Result: minimax value 3, optimal move A→B, only 7 of 9 leaves examined.

Worked Exam-Style Trace (by hand)

Tree: Root MAX with three MIN children; leaves left-to-right: B(3, 12, 8), C(2, 4, 6), D(14, 5, 2).

Root value: $\max(3, 2, 2) = 3$. Leaves evaluated: 7 of 9.

How to Count Cuts in Exams

A cut fires the moment a node's provisional value becomes ≤ α (at MIN nodes) or ≥ β (at MAX nodes), using the inherited window. Count every sibling after the firing child as pruned — even if the firing child was last, some papers still ask "was there a cutoff?" (answer: the condition held).

Inverse Design Problems (2026 trend!)

Recent exams flip the question: "Assign evaluation values to maximize the number of cuts."

Strategy:

• To force an early α-cutoff at a MIN node under window $(\alpha, \beta)$: make its first leaf ≤ α (e.g., very negative)
• To force an early β-cutoff at a MAX node: make its first leaf ≥ β (e.g., very large)
• Left-to-right order matters: cuts only fire on children examined after the window tightened, so put extreme values early in promising subtrees and let later siblings be cut

Effectiveness

With perfect move ordering alpha-beta searches roughly twice as deep as minimax in the same time — why it powers every chess engine.

Inspected vs Pruned — Two Sides of One Trace

Papers flip between asking which leaves were pruned (skipped) and which were inspected (evaluated). They're complements:

$\text{inspected} \cup \text{pruned} = \text{all horizon leaves}, \qquad \text{inspected} \cap \text{pruned} = \emptyset$

The chronological variant matters when several cuts fire: order them by when the cutoff occurred during the left-to-right traversal, then sort alphabetically only within simultaneous cuts.

Cutoff Taxonomy

When a forced eval triggers a stop, name it correctly:

25T3 papers ask this directly: give a leaf eval that induces a cutoff at a named node, then classify it. Recipe: check whether the node is MIN or MAX; that fixes α-cut vs β-cut; solve the inequality for the leaf's smallest/largest feasible value.