Alpha-Beta Pruning

Last lesson ended on a glimmer: minimax must, as written, visit every leaf — hopeless for chess, whose tree has more leaves than the universe has atoms. Yet once MIN has found a reply bad enough, the rest of that branch cannot change MAX’s mind, so why look? Alpha-beta turns that glimmer into a precise rule. It returns the exact same minimax value while skipping every subtree that can no longer change the answer.

The savings can be enormous. A game tree that offers b moves at each of d levels has b^d leaves, and plain minimax visits every one. With perfectly ordered moves, alpha-beta explores about the square root of that — roughly b^(d/2). That square-root cut is what let classic chess engines search twice as deep in the same time. The same prune-what-cannot-matter idea reappears in branch-and-bound optimisers. GATE will not test the asymptotics, but it will absolutely test whether you can hand-trace which branches survive.

Alpha and beta, in one sentence each

• α (alpha) — the best (largest) value MAX is currently guaranteed along the path from the root. Starts at -infinity. Only MAX raises α.
• β (beta) — the best (smallest) value MIN is currently guaranteed along the path from the root. Starts at +infinity. Only MIN lowers β.

At every node you carry the pair (α, β) inherited from the parent, and the pruning rule is a single line:

If at any point α >= β, stop exploring this node's remaining children — prune.

The intuition: if MAX has already secured at least α, and the current subtree can offer MIN no more than β <= α, then MAX’s parent will never choose this subtree — so finishing it is wasted work.

What trips people here is ownership versus use. α is MAX’s number and β is MIN’s, but every node tests both. A MIN node never raises α — it inherits α from the MAX ancestor above it and uses it purely as a cutoff, asking “has my value already sunk to what MAX can get elsewhere?” So keep two habits apart when you trace: updating is one-sided (only MAX touches α, only MIN touches β), while testing α >= β happens at every node.

A small tree with one cut

How GATE asks this

A reliable MCQ/MSQ pattern: a small game tree drawn with leaves labelled, plus a question like “which leaves are pruned under left-to-right alpha-beta?” or “what range of x at this leaf causes pruning?”. Sometimes it asks the root value (always identical to plain minimax) as a sanity check. This pattern appeared in both GATE DA 2024 and 2025.

Worked example — GATE DA 2024

A MAX root has two children, MIN A (left) and MIN B (right). MIN A’s leaves: [3, 8]. MIN B’s leaves: [2, ?]. Evaluating left-to-right, what does alpha-beta do with MIN B’s second leaf?

Start at the root with α = -infinity, β = +infinity.

Visit MIN A with (α=-inf, β=+inf).

• First leaf of A returns 3. MIN updates its best: β = min(+inf, 3) = 3. Check: α < β still, so keep going.
• Second leaf of A returns 8. MIN updates: β = min(3, 8) = 3 (no change). No more children — MIN A’s value is 3.

Back at the root (MAX), update α = max(-inf, 3) = 3. Now (α=3, β=+inf).

Visit MIN B with (α=3, β=+inf).

• First leaf of B returns 2. MIN updates: β = min(+inf, 2) = 2. Check the pruning condition: α (=3) >= β (=2). Prune.

MIN B cannot return more than 2, and MAX already has 3 in hand. MAX will never pick this branch, so the second leaf of B is never evaluated. MIN B’s value is reported as <= 2 (it does not matter what exactly).

Root value: max(3, anything <= 2) = 3. It is identical to plain minimax, and we saved one leaf evaluation. Those savings compound across many subtrees on a real game tree.

A handy framing: at a MIN node, prune when its running value drops to <= α (further children can only lower it more, and MAX already has α). At a MAX node, prune when its running value climbs to >= β (further children can only raise it, and MIN already has β).

In one breath

Alpha-beta returns the identical minimax value while skipping subtrees that cannot change it. It carries (α, β) down the tree: α is the best MAX has guaranteed so far, and β is the best MIN has. It prunes the moment α >= β: a MIN node cuts once its value falls to <= α, and a MAX node once it climbs to >= β. The root value never changes, but how much gets pruned depends entirely on left-to-right move order. With best-move-first ordering, the search explores only about b^(d/2) of minimax’s b^d nodes.

Practice

A question to carry forward

Step back across the whole chapter so far and notice what every method shared — BFS, A*, minimax, this. Each treated thinking as searching: lay out a tree of possibilities and walk it cleverly. The intelligence was all in the order of exploration.

But a great deal of reasoning is not search at all. A doctor weighing a diagnosis, an engineer verifying a circuit, an access-control system deciding whether to admit a user — none of them walks a maze. They deduce: given these facts and these rules, what must necessarily be true?

That demands something search never needed — a precise language for stating facts, and an exact, mechanical notion of one statement following from others. Here is the thread onward into a new sub-topic:

• how do you write true/false facts and glue them with connectives,
• when is a formula merely satisfiable versus valid, and
• what does it rigorously mean to say one set of statements entails another?