THE OBSERVATION: it is possible to compute the correct minimax decision WITHOUT LOOKING AT EVERY NODE. Once you know enough about a branch to be sure it cannot affect the decision, you can stop examining it — PRUNE it. TWO VALUES ARE CARRIED DOWN THE TREE during the search: α (alpha) the value of the BEST (highest) choice found so far at any choice point along the path for MAX. "MAX can already guarantee at least α." β (beta) the value of the BEST (lowest) choice found so far along the path for MIN. "MIN can already hold MAX to at most β." ALPHA-BETA UPDATES α AND β AS IT GOES AND PRUNES A BRANCH AS SOON AS THE VALUE OF THE CURRENT NODE IS KNOWN TO BE WORSE THAN THE CURRENT α (for MAX) OR β (for MIN). THE PRUNING CONDITION, in one line: PRUNE WHEN α ≥ β WHY IT IS SOUND — the reasoning that must be reproduced in an exam: At a MIN node, suppose MIN has already found a child worth 2, so β = 2. MAX, higher up, has already secured α = 3 elsewhere. Whatever remains under this MIN node, MIN will choose something ≤ 2, which is worse for MAX than the 3 already guaranteed. SO MAX WILL NEVER COME HERE, and the remaining children are irrelevant — their values cannot change the decision. Prune them. NOTE WHAT IS AND IS NOT CLAIMED: the pruned nodes might contain excellent values. They are irrelevant because THE PATH TO THEM WILL NOT BE TAKEN, not because they are bad. THE ALGORITHM: function ALPHA-BETA-SEARCH(state) returns an action v ← MAX-VALUE(state, −∞, +∞) return the action in ACTIONS(state) with value v function MAX-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← −∞ for each a in ACTIONS(state) do v ← MAX(v, MIN-VALUE(RESULT(state,a), α, β)) if v ≥ β then return v ← β-CUTOFF α ← MAX(α, v) return v function MIN-VALUE(state, α, β) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← +∞ for each a in ACTIONS(state) do v ← MIN(v, MAX-VALUE(RESULT(state,a), α, β)) if v ≤ α then return v ← α-CUTOFF β ← MIN(β, v) return v THE KEY PROPERTY: ALPHA-BETA RETURNS THE SAME VALUE AND THE SAME MOVE AS MINIMAX. It is not an approximation, not a heuristic, and loses nothing. It is pure computational saving.

THE STANDARD TREE from the minimax topic: branch A: 3, 12, 8 · branch B: 2, 4, 6 · branch C: 14, 5, 2 Root is MAX; each branch node is MIN. Search left to right. START: root MAX, α = −∞, β = +∞ ── BRANCH A (a MIN node, inherits α=−∞, β=+∞) ─────────────── leaf 3 → v = min(+∞, 3) = 3. Is 3 ≤ α(−∞)? No. β ← min(+∞, 3) = 3 leaf 12 → v = min(3, 12) = 3. β stays 3 leaf 8 → v = min(3, 8) = 3 MIN(A) returns 3. ALL THREE LEAVES EXAMINED. Back at the root: v = 3, α ← max(−∞, 3) = 3 ── BRANCH B (MIN node, inherits α=3, β=+∞) ────────────────── leaf 2 → v = min(+∞, 2) = 2. IS v ≤ α? 2 ≤ 3 → YES. α-CUTOFF. RETURN 2 IMMEDIATELY. LEAVES 4 AND 6 ARE NEVER EXAMINED — 2 PRUNED. WHY IT IS SAFE: MIN already has a 2 available here, so this node's value is at most 2. MAX already has 3 from branch A. MAX will never choose branch B, so its exact value does not matter. Back at the root: v = max(3, 2) = 3, α stays 3 ── BRANCH C (MIN node, inherits α=3, β=+∞) ────────────────── leaf 14 → v = 14. Is 14 ≤ 3? No. β ← 14 leaf 5 → v = min(14, 5) = 5. Is 5 ≤ 3? No. β ← 5 leaf 2 → v = min(5, 2) = 2. Is 2 ≤ 3? YES — but it is the last child anyway, so nothing remains to prune. MIN(C) returns 2. ALL THREE LEAVES EXAMINED. Back at the root: v = max(3, 2) = 3 RESULT: value 3, move A — IDENTICAL TO MINIMAX. LEAVES EXAMINED: 7 of 9. Two pruned. A SMALL SAVING ON A TINY TREE, and that is the honest point: the saving grows explosively with depth, because a prune near the root removes an entire subtree rather than two leaves. THE EFFECT OF MOVE ORDERING — the decisive factor: Suppose branch C had been searched FIRST, with its leaves ordered 2, 5, 14: MIN(C) sees 2 first, β = 2, and returns 2 after examining all three (nothing to prune, since α is still −∞). α at the root becomes 2. Then branch A: leaf 3 → 3 > 2, no cutoff; 12, 8 → returns 3. α becomes 3. Then branch B: leaf 2 ≤ 3 → prune. A DIFFERENT NUMBER OF NODES for the same tree and the same answer. THE ORDER IN WHICH SUCCESSORS ARE CONSIDERED DETERMINES HOW MUCH IS PRUNED. IF WE COULD ORDER MOVES PERFECTLY — best first at every node — alpha-beta examines only O(b^(d/2)) nodes instead of O(b^d). THAT MEANS THE EFFECTIVE BRANCHING FACTOR BECOMES √b, WHICH DOUBLES THE SEARCHABLE DEPTH FOR THE SAME COST. THE ARITHMETIC, for chess with b = 35: depth 8: full tree 35^8 ≈ 2.25 × 10^12 perfect order 35^4 ≈ 1.50 × 10^6 → a factor of about 1.5 million depth 12: full tree 35^12 ≈ 3.38 × 10^18 perfect order 35^6 ≈ 1.84 × 10^9 RANDOM ORDERING gives about O(b^(3d/4)): depth 8, random-ish 35^6 ≈ 1.84 × 10^9 So even mediocre ordering is worth roughly a thousandfold at depth 8, and good ordering another thousandfold on top. IN PRACTICE, with reasonable ordering, chess programs come fairly close to the b^(d/2) ideal — which is why alpha-beta plus ordering, rather than raw hardware, is what made deep search possible. HOW MOVE ORDERING IS ACHIEVED — the standard techniques: · try CAPTURES first, then threats, then forward moves · the KILLER HEURISTIC: a move that caused a cutoff at the same depth elsewhere is likely to cause one again · ITERATIVE DEEPENING: the best move from the depth-(d−1) search is tried first at depth d. This is the most effective method in practice, and it means the repeated work of iterative deepening more than pays for itself through better ordering. · a TRANSPOSITION TABLE: cache the value of positions already evaluated. Different move orders reach the same position, and in chess the saving is very large.

PROPERTIES OF ALPHA-BETA: CORRECTNESS returns exactly the minimax value and move COMPLETENESS same as minimax TIME O(b^(d/2)) with perfect ordering O(b^(3d/4)) with random ordering O(b^d) worst case (worst possible ordering) SPACE O(bd) — unchanged; it is still depth-first THE WORST CASE IS NO WORSE THAN MINIMAX, so alpha-beta is never a loss. That is an unusually clean property for an optimisation. TWO POINTS THAT ARE FREQUENTLY MISUNDERSTOOD: 1. PRUNING DEPENDS ON THE ORDER, NOT ON THE VALUES BEING GOOD. A pruned subtree may contain the best position in the game. It is pruned because THE OPPONENT WOULD NOT ALLOW THE PATH TO IT, so its contents cannot change the decision. 2. α AND β ARE PROPERTIES OF THE PATH, NOT OF THE NODE. They are inherited from ancestors and tightened as siblings are examined. A node visited by a different path would have different α and β — which is why a transposition table must store the depth and the bound type alongside the value, not merely the value. WHAT ALPHA-BETA DOES NOT FIX: · IT DOES NOT REMOVE THE NEED FOR AN EVALUATION FUNCTION. Even at b^(d/2), chess to 80 ply is 35^40 ≈ 10^61 nodes. The search must still be cut off, and EVAL must still estimate. · IT DOES NOT HELP GAMES WITH ENORMOUS BRANCHING FACTORS as much. Go with b ≈ 250 gives √250 ≈ 16, which is still unmanageable at useful depth — and worse, no good evaluation function for Go was known. THAT COMBINATION IS WHY GO RESISTED ALPHA-BETA ENTIRELY and needed Monte Carlo tree search plus learned networks instead. · IT DOES NOT ADDRESS THE HORIZON EFFECT OR QUIESCENCE, which are properties of cutting off rather than of pruning. · IT ASSUMES ZERO-SUM TWO-PLAYER PLAY. With three or more players and utility vectors, the pruning argument breaks down because a bad outcome for one player is not automatically good for another. RELATED PRUNING TECHNIQUES worth naming: FORWARD PRUNING cut moves that look bad without proving they are — unsound, but effective in practice, and used by all strong engines NULL-MOVE HEURISTIC give the opponent a free move; if the position is still good, it is probably good enough to prune LATE MOVE REDUCTION search moves ordered late to a shallower depth NOTE THAT THESE ARE ALL UNSOUND — they can prune the best move. They are used anyway, because the depth bought is worth more in practice than the occasional error. THAT IS AN ENGINEERING JUDGEMENT, and it is the same trade as weighted A* in the informed search topic: accept a bounded chance of suboptimality in exchange for a large speed gain. THE CLOSING SUMMARY OF THE WHOLE SEARCH SECTION: uninformed search gives guarantees at exponential cost; heuristics cut the cost by orders of magnitude; alpha-beta halves the exponent for adversarial search; and when even that is not enough, the field moved to sampling (MCTS) and learned evaluation. EACH STEP TRADES SOMETHING — memory, optimality, or certainty — for tractability.