Alpha-beta pruning

◈ 3 cards

Track alpha (MAX best-so-far) and beta (MIN best-so-far) to skip subtrees that cannot change the minimax value — same answer, far fewer nodes.

Same answer, less work

Alpha-beta pruning computes the exact same backed-up value as full minimax but skips subtrees that cannot possibly affect the result. It carries two bounds down the tree:

$α$ — the best value MAX is already assured of somewhere above. It can only ever increase.
$β$ — the best value MIN is already assured of somewhere above. It can only ever decrease.

### The two cutoff rules

$β$ -cutoff — stop exploring below a MIN node once its value $\leq α$ of some MAX ancestor. MAX already has a line at least this good, so it will never enter this MIN node.
$α$ -cutoff — stop exploring below a MAX node once its value $\geq β$ of some MIN ancestor. MIN already has a line at least this good, so it will never allow this MAX node.

In code: at a MAX node update $α = max (α, best)$ and break when $α \geq β$ ; at a MIN node update $β = min (β, best)$ and break when $α \geq β$ .

Why it matters

With good move ordering (try the strongest moves first), alpha-beta prunes whole subtrees and can effectively double the search depth reachable in a fixed time budget compared with plain minimax. With the worst ordering it prunes nothing and degrades to minimax. This is why chess engines invest in move ordering (e.g. iterative deepening to order the next level).

Worked example: alpha-beta vs minimax

Run both on the same tic-tac-toe position from the previous lesson, counting the nodes each visits. Both return move (2,2), value +1 — identical, as guaranteed. But plain minimax visits 258 nodes while alpha-beta visits 176: it pruned roughly a third of the tree without changing the answer. That is the entire point — alpha-beta is a speedup, never a change of result.

The identical sub-tree from the previous lesson, with bounds carried in. MAX has already secured 0 from earlier root children, so this node is entered with α = 0, β = 2. The first reply backs up +1 and lowers β to 1; the second backs up 0 and lowers β to 0, which meets α — a <strong>β-cutoff</strong>. MIN can no longer produce anything MAX would prefer to the 0 it already holds, so the last two replies are never generated. The node still returns 0, exactly as unpruned minimax did.

The two rules are mirror images, and both reduce to the same test — α ≥ β. α is a floor that only ever rises and β a ceiling that only ever falls; once they cross, whatever is left below the node is provably unreachable in optimal play, so it is skipped. The value returned is unchanged; only the node count moves.