Alpha-beta pruning
Imagine you're a chess program. To decide your move you build a
minimax
game tree: you (MAX) try to reach the highest-scoring position, your opponent
(MIN) tries to force you into the lowest. Plain minimax explores every
leaf of that tree — and the tree is monstrous. At a branching factor of about 35 legal moves, looking
just 8 moves ahead means roughly 35^{8} \approx 2 \times 10^{12} positions.
No engine can afford that.
But here's the thing: a lot of that work is provably pointless. Think about how you
shop. You're comparing two flats. The first is lovely — bright, quiet, a fair price. You start viewing
the second and the very first room is a windowless box over a nightclub. Do you tour the rest of the
flat? Of course not. You already have a better option, and nothing in the remaining rooms can rescue
this one. You prune the viewing and move on.
Alpha-beta pruning is exactly this instinct, made precise and applied to a game tree.
It computes the same answer as full minimax — the identical value and the identical best move
— but skips branches it can prove cannot possibly influence that answer. This one page is about that
single idea: stop exploring a branch the moment it can no longer change the decision.
The key insight
Picture yourself as MAX, part-way through the tree. You have already fully explored one line of play
and found it guarantees you a score of 3. Now you start examining a second line. It's
a MIN node, so your opponent will pick the smallest value among its children — and the first
child you look at already scores 2.
That single number is enough to abandon the whole branch. MIN gets to choose, and MIN will never pick
something bigger than 2 — the value here can only stay at 2 or drop lower. So this line is
worth at most 2 to you, which is worse than the 3 you already have in
your pocket. Whatever the remaining, unexplored children of this MIN node turn out to be, you were
never going to choose this line. Reading them changes nothing. Cut them off.
That is the entire trick. Formalising "the best I already have" and "the best my opponent already has"
into two travelling numbers — \alpha and \beta —
turns this instinct into an algorithm.
Alpha and beta: two bounds that travel down the tree
As the search walks up and down the tree it carries two values along the current path:
- \alpha — the best (highest) score MAX can already guarantee
somewhere along this path. It only ever rises. Think: "MAX has a fallback worth at least
\alpha."
- \beta — the best (lowest) score MIN can already guarantee
along this path. It only ever falls. Think: "MIN has a fallback worth at most
\beta."
The window [\alpha, \beta] is the range of scores still "in play". The
moment it snaps shut — \alpha \ge \beta — the current node can no longer
matter, and we stop expanding its remaining children.
- At a MIN node we keep lowering \beta as we see
smaller children. As soon as \beta \le \alpha, MAX already has a
better option above, so we prune the remaining children — a
β-cut.
- At a MAX node we keep raising \alpha as we see
larger children. As soon as \alpha \ge \beta, MIN already has a
better option above, so we prune the remaining children — an
α-cut.
- Correctness. Alpha-beta returns exactly the minimax value of the root,
and hence the same optimal move. Pruning removes only children that provably cannot change that
value — it is a pure speed-up, never an approximation.
Watch it happen
Here is a small tree: MAX on top, two levels down to nine already-scored leaf positions, with MIN in
the middle. Step through the search left-to-right and watch a whole branch get pruned once
\beta falls to or below \alpha.
The left branch backs up to \min(3, 12, 8) = 3, so
\alpha = 3. The middle branch opens with a leaf of
2; since that MIN node can only go lower,
\beta = 2 \le \alpha = 3 and its other two leaves are cut. The right branch
finishes normally, and MAX backs up \max(3, 2, 2) = 3 — precisely what full
minimax gives, but with two leaves never touched. On this toy tree that's a small saving; on a real
one it is the difference between playable and hopeless.
Same answer, far less work
Talk is cheap, so let's prove it. Below we run plain minimax and
alpha-beta over the same game tree, each counting how many leaf positions it
actually evaluates (the expensive part in a real engine). Press Run: the values match
to the digit, yet alpha-beta looks at a fraction of the leaves.
type Tree = number | Tree[];
// A game tree: root is MAX, then MIN, then MAX, then scored leaves.
const game: Tree =
[ [[3, 12, 8], [2, 4, 6], [14, 5, 2]],
[[1, 5, 6], [7, 7, 7], [8, 8, 8]],
[[6, 2, 1], [9, 9, 9], [4, 4, 4]] ];
let mmLeaves = 0;
function minimax(node: Tree, isMax: boolean): number {
if (typeof node === "number") { mmLeaves++; return node; }
let best = isMax ? -Infinity : Infinity;
for (const c of node)
best = isMax ? Math.max(best, minimax(c, false)) : Math.min(best, minimax(c, true));
return best;
}
let abLeaves = 0;
function alphabeta(node: Tree, a: number, b: number, isMax: boolean): number {
if (typeof node === "number") { abLeaves++; return node; }
if (isMax) {
let best = -Infinity;
for (const c of node) {
best = Math.max(best, alphabeta(c, a, b, false));
a = Math.max(a, best);
if (a >= b) break; // α-cut: MIN above already has a better option
}
return best;
}
let best = Infinity;
for (const c of node) {
best = Math.min(best, alphabeta(c, a, b, true));
b = Math.min(b, best);
if (a >= b) break; // β-cut: MAX above already has a better option
}
return best;
}
const mm = minimax(game, true);
const ab = alphabeta(game, -Infinity, Infinity, true);
console.log("minimax value =", mm, " — leaves evaluated:", mmLeaves);
console.log("alpha-beta value =", ab, " — leaves evaluated:", abLeaves);
console.log("same answer?", mm === ab, "— alpha-beta skipped", mmLeaves - abLeaves, "leaves");
console.log("that's about", Math.round((mmLeaves / abLeaves) * 10) / 10, "x fewer leaf evaluations");
Identical values, a big cut in leaves examined — and the gap widens the deeper the tree goes. Notice
the code differs from minimax by only a few lines: carry \alpha and
\beta, and break out of the loop the instant the window closes.
Why it matters: doubling how far you can see
How much you save is not fixed — it depends entirely on the order you examine moves
in. With the worst possible ordering, alpha-beta prunes nothing and degenerates into plain
minimax at O(b^{d}) (branching factor b, depth
d). But with perfect ordering — always trying the best move first —
the effect is dramatic.
- With optimal move ordering, alpha-beta examines only
O\!\left(b^{d/2}\right) leaves instead of
O\!\left(b^{d}\right).
- Equivalently, the effective branching factor drops from
b to \sqrt{b}.
- In the same amount of time, that lets you search to roughly twice the depth.
Doubling your look-ahead is enormous. It is why serious chess engines, layered on top of alpha-beta,
can search far deeper than raw minimax ever could on the same hardware — and it is why real engines
pour so much effort into move ordering heuristics (try captures first, remember the
moves that caused cuts last time), because good ordering is what unlocks the
\sqrt{b} speed-up in practice.
Alpha-beta can't prune out of thin air — the very first cut needs an \alpha
or \beta to compare against, and those start at
-\infty and +\infty. So the search must walk one
complete path from root to a leaf and back up a real value before any bound is meaningful.
That first full descent is what establishes the initial \alpha; every
prune afterwards is measured against a bound some earlier, fully-explored line paid for. Explore your
most promising line first and that early bound is tight, so it prunes aggressively — which is, once
more, exactly why move ordering matters so much.
Two things students routinely get wrong about pruning:
- Pruning is not an approximation. It never changes the minimax value and never
changes the chosen move. It is a pure speed-up: it removes only work that provably cannot affect
the result. If your "alpha-beta" ever returns a different move from full minimax, it has a bug —
that is not what pruning does.
- The savings depend entirely on move ordering. Best-case
O(b^{d/2}) assumes you examine the strongest move first at every node.
With the worst ordering (weakest move first) alpha-beta prunes nothing
and costs the full O(b^{d}) — the same as plain minimax, just with extra
bookkeeping. So "alpha-beta is faster" is a statement about good ordering, not a
guarantee.