Moscow, the Institute of Control Sciences, 1974: the Soviet program Kaissa won the first World Computer Chess Championship in Stockholm. Its heart is game-tree search — and the load-bearing fact of that search is a proof: alpha-beta returns the exact same value as full minimax while visiting far fewer positions. This panel is runnable: build a fixed-seed game tree, search it both ways, and watch the two values agree while the node counts diverge.
source Kaissa — Adelson-Velsky, Arlazarov & Donskoy, Institute of Control Sciences, Moscow; winner of the 1st World Computer Chess Championship, Stockholm 1974; heir to the 1966–67 US–USSR correspondence match. Room: THE MACHINE. Rendered, not quoted.
Built at the Institute of Control Sciences in Moscow by Georgy Adelson-Velsky, Vladimir Arlazarov and Anatoly Donskoy. Named for the muse of chess. In Stockholm, 1974 it won the first World Computer Chess Championship with a clean 4–0.
Its lineage runs back to the 1966–67 US–USSR correspondence match between an American program (Kotok–McCarthy) and the Moscow ITEP program — the Soviet side won. The team also gave computer science the AVL tree. What Kaissa did in hardware, the two windows below prove in mathematics.
A two-player game is a tree: you (MAX) pick the move that maximises the score; the opponent (MIN) picks the move that minimises it, alternating down to leaf positions with known values. Minimax walks the whole tree and returns the single value both sides are forced into under best play.
This value is the ground truth — the number the position is worth. It is exact but expensive: a tree of branching b and depth d has bd leaves, and minimax visits every one.
Carry two bounds down the tree: α (best MAX can already force) and β (best MIN can already force). The instant a branch proves it cannot change the answer — α ≥ β — it is pruned, unexamined and unmissed.
With good move ordering the best case visits only ~ 2·bd/2 leaves instead of bd — the square-root of the work. Same effort now reaches twice the depth. And crucially: the value it returns is identical to minimax. It skips only what cannot matter.
Choose branching b and depth d. A fixed-seed PRNG fills the leaf values, so the tree is fully reproducible — no Math.random. The same tree is searched by full minimax and by alpha-beta.
Leaf count = bd. Kept small so the whole tree is walkable in the page; the algorithm has no such limit.
Both searches on the same fixed tree. The value must agree; the leaves visited need not:
| search | value | leaves visited |
|---|
Theory for this b, d: —
THE BEST CASE. A best-ordered copy of the same tree (best move first at every node) is searched too — its leaf count is the Knuth–Moore minimum b⌈d/2⌉ + b⌊d/2⌋ − 1, the square-root frontier.
| tree (b,d,seed) | minimax | alpha-beta | = |
|---|
Alpha-beta does not remove the wall — the game tree is still exponential. It halves the exponent: best case 2·35d/2 — at depth 4, 2·352−1 = 2,449 leaves instead of 1,500,625. Same budget, twice the horizon. That is the entire game.
"Pruning changes the answer — you skipped positions, so you must have missed something." Cut. Alpha-beta returns the exact minimax value. It only ever skips a branch after proving that branch cannot alter the result. The witness below re-runs full minimax and confirms the numbers match, every tree.
"A deeper but pruned search is weaker than a shallow full one." Cut. The pruned search of depth d is the same value as the full search of depth d — and reaches deeper for the same cost. Strictly better.
"Move ordering is a cosmetic optimisation." Cut. Ordering is what turns bd into ~2·bd/2. Worst-ordered alpha-beta prunes nothing and degenerates to full minimax — the whole gain lives in the order.
The red move: cut a branch alpha-beta is not allowed to skip — prune after the first child even while the rest could still change the value (a cut when α < β). Leaves visited drop further, but the returned value is now wrong.
Break the α ≥ β cutoff rule and re-search: the witness (5) compares each tree’s alpha-beta value against full minimax and turns red. Legal alpha-beta must equal minimax; an over-eager cut is caught the instant the values disagree.