Alpha-Beta Pruning
Same minimax answer, fewer nodes touched. Track the best each side has guaranteed so far, and cut whole subtrees the parent will never pick.
What you'll learn
- Alpha tracks MAX's best-guaranteed value along the path; beta tracks MIN's
- Prune a node's remaining children when its outcome cannot affect the parent's choice
- Pruning depends on left-to-right evaluation order — node ordering changes how much gets pruned
- The root value is unchanged from plain minimax — alpha-beta is an efficiency, not an approximation
Before you start
Plain minimax visits every leaf. That feels wasteful — once you’ve found a decent line, why keep exploring branches the opponent will obviously block? Alpha-beta is that intuition turned into a precise rule. It returns the same minimax value while skipping subtrees that can no longer change the answer.
The savings can be huge. With perfectly ordered moves, alpha-beta explores
about the square root of minimax’s nodes — turning a depth-d search with
branching b from b^d into roughly b^(d/2). That square-root cut is what let
classic chess engines search twice as deep in the same time, and the same
prune-what-can’t-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. The
pruning rule is one 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.
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 — based on real 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. The second leaf of B never gets evaluated. MIN B’s
value is reported as <= 2 (it does not matter what exactly).
Root value: max(3, anything <= 2) = 3. Identical to plain minimax, and we
saved one leaf evaluation. On a real game tree those savings compound across
many subtrees.
A useful 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 β).
Quick check
Quick check
Practice this in an interview
All questionsPruning removes splits that do not improve generalisation. Pre-pruning stops growth early via hyperparameters like max_depth or min_samples_leaf. Post-pruning (cost-complexity pruning) grows the full tree then collapses nodes whose removal does not hurt held-out accuracy enough.
At each node the algorithm iterates over every feature and every candidate threshold, scores each candidate split by the weighted impurity of the two child nodes, and selects the pair that gives the largest impurity reduction. It then recurses on each child until a stopping criterion is met.
At each step of a recursive walk through the input, you make a binary choice: include the current element or skip it. Recording the current path at every node of the recursion tree (not just the leaves) collects all 2^n subsets. A `start` index prevents duplicates by ensuring elements are only considered left-to-right.
Use backtracking with a running total. At each step, try adding a candidate to the current path. If the total equals the target, record the path. If it exceeds the target, prune. Passing the same start index (not i+1) back into the recursion allows unlimited reuse of the same element.