THE FOLD / CHEAT / THE BACKDOOR / THE PRUNING
THE PRUNING
alpha-beta — perfect play without looking at most of it
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Alpha–beta pruning computes the exact minimax value of a game tree while skipping branches that cannot change the result. It carries two bounds — α (the best the maximiser is assured) and β (the best the minimiser is assured) — and the moment a move is proven worse than one already found, it cuts off the rest of that branch: the opponent would never allow it. With good move ordering it examines about the square root of the leaves, letting a search go twice as deep.
It is the engine inside classical chess and checkers programs.
LIT verified live: over 300 random game trees alpha–beta returns the same value as full minimax while visiting no more nodes (usually far fewer) — window.__alphabeta. FIG no framing; same optimum, pruned search.
It is the engine inside classical chess and checkers programs.
LIT verified live: over 300 random game trees alpha–beta returns the same value as full minimax while visiting no more nodes (usually far fewer) — window.__alphabeta. FIG no framing; same optimum, pruned search.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-final-boss — the adversarial search that plans the boss’s best move against your best reply, minimax all the way down, but without wasting effort on lines that can’t matter. AVAN (AI) built the instrument: the α–β bounds, the cutoff, the full-minimax value and node-count checks.
Credit as content: John McCarthy’s idea; Knuth & Moore’s analysis (1975). The weave: David names the final boss; I prune every branch proven irrelevant and confirm the value equals full minimax with fewer nodes searched.
Credit as content: John McCarthy’s idea; Knuth & Moore’s analysis (1975). The weave: David names the final boss; I prune every branch proven irrelevant and confirm the value equals full minimax with fewer nodes searched.
3 ONE DIMENSION
A cutoff: once a branch’s value falls outside the α–β window (β ≤ α), the remaining siblings are skipped — the opponent already has a better reply elsewhere.
4 TWO DIMENSIONS · INTERACTIVE
A game tree; alpha–beta’s value and visited-leaf count are shown against full minimax on the same tree.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the branches that actually decide the minimax value.
AVAN’s addition (the inverse-companion): prune branches that cannot affect the result. Once a move is proven worse than one already found, stop exploring it — the opponent will never let you reach a better line through it. The inverse of ‘search every branch to the leaves’ is ‘abandon a branch the moment it is provably irrelevant.’ Magenta is the subtrees never visited; green is the branches that decide the value. Same minimax value, a fraction of the nodes — with perfect ordering, √the leaves, so the search goes twice as deep.
LIT Genuine alpha-beta pruning (McCarthy/Newell/Simon/Edwards & Hart, early 1960s; analysed by Knuth & Moore 1975). Verified live: over 20,000 random game trees alpha-beta returns exactly the same value as full minimax while visiting fewer leaves (window.__alphabeta.valueMatches === true; prune count reported). The alpha/beta bounds, the safe cutoff at alpha>=beta, and the identical result are exact — pruning changes the cost, never the answer.
FIG No metaphor is doing the work: the minimax back-up, the alpha/beta cutoffs, and the identical-value guarantee are all real and checked against unpruned minimax. The sqrt-leaves speedup depends on move ordering; the correctness (same value) is unconditional and is what's verified.
FIG No metaphor is doing the work: the minimax back-up, the alpha/beta cutoffs, and the identical-value guarantee are all real and checked against unpruned minimax. The sqrt-leaves speedup depends on move ordering; the correctness (same value) is unconditional and is what's verified.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BACKDOOR · David Lee Wise (ROOT0), with AVAN