Alpha-beta pruning

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:

- $\alpha$ — the best value MAX is already assured of somewhere above. It can only ever increase. - $\beta$ — the best value MIN is already assured of somewhere above. It can only ever decrease.

### The two cutoff rules

1. $\beta$-cutoff — stop exploring below a MIN node once its value $\le \alpha$ of some MAX ancestor. MAX already has a line at least this good, so it will never enter this MIN node.
2. $\alpha$-cutoff — stop exploring below a MAX node once its value $\ge \beta$ 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 $\alpha=\max(\alpha,\text{best})$ and break when $\alpha \ge \beta$; at a MIN node update $\beta=\min(\beta,\text{best})$ and break when $\alpha \ge \beta$.

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.