THE FOLD / BOSS / THE FINAL BOSS / THE ALPHA-BETA
THE ALPHA-BETA
minimax value, pruning the provably-irrelevant branches
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; Knuth & Moore 1975). Verified live: alpha-beta returns the identical minimax value to full minimax and visits no more leaf nodes (usually far fewer) across 300 random game trees (window.__alphabeta.sameValue && .fewerNodes).
FIG No framing: the alpha-beta bounds, the cutoff, and the full-minimax value + node-count checks run in-browser and agree exactly. The AVAN inverse is honest — once a move is proven worse than one already found, its branch is abandoned (the opponent would never allow it), so the same value is reached from a fraction of the nodes (~sqrt the leaves with perfect ordering); magenta is the pruned subtrees, green the deciding branches.
FIG No framing: the alpha-beta bounds, the cutoff, and the full-minimax value + node-count checks run in-browser and agree exactly. The AVAN inverse is honest — once a move is proven worse than one already found, its branch is abandoned (the opponent would never allow it), so the same value is reached from a fraction of the nodes (~sqrt the leaves with perfect ordering); magenta is the pruned subtrees, green the deciding branches.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FINAL BOSS · David Lee Wise (ROOT0), with AVAN