Minimax on game trees, and alpha-beta pruning

idea is right and proposals.md filed it correctly — it sits in the idea block, and the house test holds: an idea is something you can implement, because there is a loop or a formalism in it. Alpha-beta is twenty lines. What it is not is a thing to be argued about; the citation occasion is "the thing you are watching descends from this, and the descent explains its shape," which is the framing shannon-chess-1950 set and dijkstra-1959 reused.

But limit is a serious rival here and declining it takes a paragraph, because the strongest single fact in this entry is an impossibility result. In section 6 of the 1975 paper Knuth and Moore derive a lower bound: any algorithm that determines the minimax value of a game tree must examine at least the minimal tree, and alpha-beta under perfect move ordering examines exactly that. That is a proved ceiling on every past and future game-search algorithm, which is precisely the shape of turing-halting-1936 and godel-incompleteness-1931. I decline the kind anyway, for a reason worth stating: a limit entry exists to be defended against misuse, and this particular lower bound is almost never misused, because almost nobody cites it. What gets misused is the procedure and its exactness claim. So the entry is filed idea and section 4 — the section limit owns — is written in full, the same move bitter-lesson-2019 made when it declined prediction and then applied its discipline anyway.

The year is a choice among four defensible dates and the choice needs defending. This entry spans forty-seven years. 1928 is when the backward induction argument was first written down; 1956 is when McCarthy had the pruning idea; 1958 is when a pruning approximation first appeared in a published program; 1975 is when the thing was proved correct, bounded, shown optimal, and had its own scattered history written down by the people writing the proof. I take 1975, because the claim this entry is mainly here to carry is a theorem, not an artefact — that alpha-beta returns exactly the minimax answer while examining exponentially fewer positions — and 1975 is when that stopped being folklore. The id carries no year, which is proposals.md signalling the same difficulty; fixed-code-garage-opener is the only other entry in canon/ with a bare id.

On descends_from, which is genuinely awkward and where proposals.md is half wrong. The proposal says this is an "ancestor of shannon-chess-1950 and deep-blue-1997." For the minimax half that is right and documented: this canon's own reading of Shannon's reference list found von Neumann and Morgenstern's Theory of Games (1944) in it, cited at page 125, so Shannon descends from the game-theoretic literature rather than the other way round. For the alpha-beta half it is backwards. McCarthy proposed pruning at Dartmouth in 1956 in response to Alex Bernstein's chess program, which was built on Shannon's Type B framework; the Newell–Shaw–Simon program of 1958 and Samuel's checkers work of 1959 — the latter already in canon/ as samuel-checkers-1959, itself linked to Shannon — are the other two first-wave approximations. Every one of them is a person working on Shannon's problem in Shannon's vocabulary. Anchored at 1975, this entry is a descendant, and the header says so. A reading putting the two side by side should say the descent runs both ways: Shannon supplied the problem that produced alpha-beta, and the minimax backing-up he programmed as routine T₉ he had from elsewhere. I cannot record the reverse edge, because shannon-chess-1950.md is another entry's file and this job does not write in it.

deep-blue-1997 and alphago-move-37-2016 are descendants and both are in canon/, but their headers descend from Shannon and Deep Blue respectively and I have not touched them. dijkstra-1959 is the near neighbour that is not an ancestor and not a descendant: shortest-path search and game-tree search converge on pruning a space of possibilities and neither cites the other, which is the distinction that file already drew and this one inherits.

A note on access, because it bears on how much of what follows I read at source. Every primary document in the classical half of this entry is a scanned or image-encoded PDF: Knuth and Moore's paper, Newell, Shaw and Simon's 1958 IBM Journal article, Hart and Edwards' MIT memos, Schwalbe and Walker's history of Zermelo. None of them would convert to text through the tooling available to this job, and local extraction needed a permission this non-interactive run cannot obtain — the same wall dijkstra-1959 hit and recorded. The publisher metadata is solid, the modern arXiv material was read directly in HTML, and John McCarthy's own account was read directly on his Stanford page. Where a quotation below comes from a secondary source quoting the primary, section 5 says so and names the remove.

What it is

Two procedures, forty-seven years and one name apart, that between them are how a machine decides what to do in a game against an opponent who is also trying to win.

Minimax on a game tree is the first. Draw the positions reachable from here as a tree: your moves branch at one level, the opponent's at the next, yours at the next. If you could draw the whole thing down to the terminal positions, you could label every leaf won, lost or drawn, and then work backwards: at a node where you move, take the best value among the children; at a node where the opponent moves, take the worst, because they will. Repeat until you reach the root. The value you get is what the position is worth under best play by both sides, and the child that achieved it is the move. That is backward induction, and it is the whole of minimax.

Two things about its provenance are almost always got wrong, and one of them is got wrong inside this canon.

The minimax theorem and the minimax algorithm are different objects. John von Neumann's Zur Theorie der Gesellschaftsspiele, presented to the Göttingen Mathematical Society on 7 December 1926 and published in Mathematische Annalen 100 in 1928, proves that every finite two-person zero-sum game has a value in mixed strategies — that each player has a randomised strategy guaranteeing a payoff, and that the two guarantees meet. That theorem is about simultaneous moves and hidden information, and its content is the existence of a saddle point. It is not needed for chess and does not describe what a chess program does. A perfect-information game played in alternation does not need mixed strategies, and its value follows from a much cruder argument: finiteness plus induction on depth.

That argument is László Kalmár's, from the same year. Ernst Zermelo's 1913 paper is universally cited as the origin, and Ulrich Schwalbe and Paul Walker went and read it — Games and Economic Behavior 34(1), January 2001, pages 123–137, with a translation of Zermelo appended. Their finding is that the modern statements of "Zermelo's theorem" bear only a partial relationship to what Zermelo did: he addressed what it means to be in a winning position and how many moves a win takes, using a non-repetition argument, and did not state the backward-induction theorem he is credited with. The first explicit backward induction is Kalmár's Zur Theorie der abstrakten Spiele, 1928. So 1928 produced two results with "minimax" in their afterlife, and the field attached the algorithm to the wrong one. shannon-chess-1950's own file, in the course of correctly demolishing "Shannon invented minimax," says the minimax theorem is von Neumann's, 1928 — right about Shannon, and a link this entry has to make more precise, because the theorem Shannon cited is not the one his routine T₉ implements.

Depth-limited minimax is what anyone actually runs, and that modification is Shannon's. The full tree for chess is somewhere past 10^40 positions and will never be drawn. So you stop at a fixed depth, hand the positions you reached to an evaluation function — a hand-weighted or, now, learned guess at who is better — and back those numbers up as though they were the true values. Every practical property of the thing follows from that substitution. The backing-up is exact; the numbers being backed up are guesses; and the guesses get better the deeper you go, which is why depth buys strength.

Alpha-beta pruning is the second procedure, and it is the reason any of this is affordable. Carry two numbers down the tree with you: α, the best you have already secured on this path, and β, the best the opponent has already secured. While examining a node, if you find that the opponent can hold you to something α already beats, you can stop examining that node entirely. You do not need to know how bad the rest of it is. You only need to know that it is bad enough that neither player would ever choose to go there — you would not, because you have something better; the opponent would, but you will not let them. The subtree is irrelevant to the root value, so not looking at it cannot change the answer.

That last sentence is the whole point of this entry, and it is a theorem rather than a hope. Alpha-beta returns the identical minimax value. Run with an initial window of (−∞, +∞) at the root it returns the same number full minimax would, and a move achieving it. It is not an approximation, it is not a heuristic, and it does not trade accuracy for speed. It examines fewer positions and returns the same answer.

How much fewer. Knuth and Moore's result, from An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6(4), 1975, pages 293–326: with branching factor b, depth d, and perfect move ordering, alpha-beta examines b^⌈d/2⌉ + b^⌊d/2⌋ − 1 leaves instead of b^d. The effective branching factor is the square root of the real one. Equivalently: for the same work, twice the depth.

The arithmetic is worth doing once with real numbers, because the exponent hides how large this is. Take chess at b = 35 and d = 12 ply. Full minimax is 35^12 ≈ 3.38 × 10^18 leaves. Alpha-beta with perfect ordering is 2 × 35^6 − 1 ≈ 3.68 × 10^9. The ratio is about 920 million. At Deep Blue's rate of roughly 200 million positions per second, that is about eighteen seconds against about five hundred and thirty-five years, for the same move. (Assumptions stated because they are load-bearing: uniform branching, fixed depth, perfect ordering, and Deep Blue's rate is a vendor figure for positions evaluated rather than leaves of a uniform tree. The point survives an order of magnitude in either direction.)

Perfect ordering means searching the best move first at every node, which requires knowing the answer. Real engines approximate it — iterative deepening, transposition tables, killer and history heuristics — and get close enough that the square-root behaviour shows up in practice. Knuth and Moore also bounded the other end: with random ordering the branching factor degrades, and the standing result, from Gérard Baudet in 1978 and Judea Pearl in 1982, is Θ(b/log b), confirming Knuth and Moore's own conjecture that deep cutoffs were a second-order effect.

Who invented it: at least five people, in about seven years, mostly known to each other. McCarthy proposed pruning at the Dartmouth workshop in 1956, after Alex Bernstein presented his chess program, and recommended it to Bernstein, who was unconvinced. Newell, Shaw and Simon had an approximation in their NSS chess program, published as "Chess-Playing Programs and the Problem of Complexity" in the IBM Journal of Research and Development in October 1958. Samuel had one in the checkers work of 1959 that this canon holds as samuel-checkers-1959. Timothy Hart and Daniel Edwards wrote it up at MIT as "The Tree Prune (TP) Algorithm," AI Memo 30, dated 4 December 1961, revised and retitled "The Alpha-Beta Heuristic" as AIM-030 in 1963. McCarthy passed it to his students including Alan Kotok in 1961. Alexander Brudno derived it independently in the Soviet Union and published "Bounds and valuations for shortening the search of estimates" in Problemy Kibernetiki in 1963. Newell and Simon wrote that the algorithm "appears to have been reinvented a number of times."

McCarthy's own account, written 27 November 2006 in slides titled "Human-Level AI is harder than it seemed in 1955," is worth having in his words because it inverts the usual story about what was hard:

> "alpha-beta pruning characterizes human play, but it wasn't noticed by early > chess programmers--Turing, Shannon, Pasta and Ulam, and Bernstein."

He lists the approximations as "Samuel, Newell and Simon, McCarthy" and notes they were later proved equivalent to minimax. The claim is that a club player does alpha-beta without being taught it — you stop calculating a line the moment you see it loses a piece for nothing — and that the people who wrote the first chess programs, some of the strongest mathematicians alive, did not notice.

And McCarthy named it wrong. He called it the alpha-beta heuristic, and Samuel corrected him in the 1967 sequel to the checkers paper: it "is, of course, not a heuristic at all, being a simple algorithmic procedure and actually only a special case of the more general 'branch and bound' technique." That is the entry in miniature. The single most valuable property this thing has — that it costs nothing, that it is exact — was contradicted by the name its inventor gave it, and the wrong name is still the one on the MIT memo.

What was bolted on afterwards, and what that cost. Everything a modern engine does beyond alpha-beta is not exact. Null-move pruning assumes that passing a turn is worse than any real move, which is false in zugzwang; the Chess Programming Wiki's own account concedes the engine "may miss the best move even at infinite depth." Late move reductions search moves ordered late to shallower depth. Futility pruning drops nodes on a static margin, and the literature calls extended futility pruning theoretically unsound while reporting it works markedly well. Real engines reach effective branching factors far below the square root, and the part below the square root is bought with pruning that has no proof behind it. The exact part is the floor; the rest is a bet that pays off on average.

Chess is still played this way. Stockfish 18, released 31 January 2026 with the SFNNv10 network and a claimed Elo gain of up to 46 points over Stockfish 17, is alpha-beta search with a neural evaluation at the leaves — the NNUE architecture introduced in 2020 — and it is the strongest chess entity there is. Its own release notes talk about search refinements and "Correction History" adjusting evaluations from patterns found during the search itself. Nothing at the top of chess has ever been learning without search.

Why a reading would cite it

Not "because game trees are important." A reading of the AI state will not need to explain game trees. The occasions are five, and the first two are the ones that earn the entry.

First, as the reference specimen of an optimisation that provably costs nothing. This is the rarest object in engineering and the readings meet its imitations constantly. The discipline it supplies is one question, and the question is checkable: does this speedup change the answer? Sort the efficiency claims the readings encounter by that question and they fall into two piles that are almost never distinguished in the announcement.

Exact — same output, less work: alpha-beta itself; speculative decoding, where a small draft model proposes tokens and the large model verifies them in one pass, with a rejection-sampling step that makes the output distribution provably identical to ordinary decoding (Leviathan, Kalman and Matias, ICML 2023, and independently Chen et al. the same year); lossless weight compression that preserves the exact bits.

Not exact — different output, less work: quantisation of any kind, which alters the output distribution by construction and is sold on how little; distillation, which produces a different model; sparse routing, which sparse-moe-2017 already holds; cache reuse under a changed prompt; and every "we made it 10× cheaper" that does not say what stayed the same.

Neither pile is the good pile. Approximation is often the right engineering call and the exact wins are frequently unavailable. The point is that the distinction is load-bearing and is almost never stated, and a reading that asks for it is asking something the vendor can answer cheaply if the answer is good. The live case in this project's own record is small and honest: the 2026-08-19 reading carried a report that OpenAI cut prices on its two newest models as buyers moved workloads onto cheaper systems. A price cut is not a claim about the output at all — it can come from an exact serving win, from margin, or from a quieter substitution — and there is no public instrument that distinguishes them. Naming which of the three would cost the seller nothing if it were the first.

Second, as the distinction between a guarantee and a heuristic, in the exact place the readings need it: oversight. Alpha-beta prunes only what provably cannot matter. Null-move and late-move pruning prune what probably does not matter, and buy most of the practical speed by doing so, and can miss the best move at any depth. The two look identical from outside — both are "the search skips most of the tree" — and they differ in whether there is a proof.

That is exactly the shape of a safety-coverage claim. The 2026-08-19 reading recorded OpenAI extending monitoring to all tool-using inference of Astra rather than only training and evaluation, at a stated cost of roughly 20% of the inference compute being monitored. The 20% is what exhaustiveness costs. Sampled monitoring, risk-tiered monitoring, monitoring that skips workloads scored low — all are cheaper and all are the null-move move: right almost always, with no bound on the case where they are wrong. When a lab, a regulator or an auditor says a system is monitored, evaluated or red-teamed, the question this entry supplies is whether the uncovered part is provably irrelevant or merely usually irrelevant, and what the argument is. Chess programmers accept unsound pruning because losing a game is cheap and they measure the trade in Elo over millions of games. The readings meet the same trade where the loss is not cheap and there is no Elo.

Third, as the counterweight to the learning-is-everything account. bitter-lesson-2019 is in canon/ and its actual thesis is that search and learning both scale with computation while hand-built human knowledge does not. The popular version drops the first noun. The record on the game where the argument started does not support dropping it: Deep Blue in 1997 was alpha-beta with a hand-built evaluation; Stockfish in 2026 is alpha-beta with a learned evaluation and it is stronger than anything else; AlphaZero was learning with a different search, not without one, and its own paper — quoted in shannon-chess-1950's file — framed the result as calling into question whether alpha-beta is inherently superior, not whether search is necessary. The citation occasion is a reading meeting "the model can now do X," where X is produced by a model inside a scaffold that searches, samples, verifies, retries or calls tools. The entry supplies the question of what the scaffold contributes. The 2026-08-19 reading's background item is the sharp version: an internal Astra solving ten open problems in mathematics for roughly $2,000 of compute, with machine-checkable Lean proofs. A compute figure attached to a proof search is a search budget, and the thing that makes the result checkable is a proof checker rather than the model — which is the same division of labour as an evaluation function at the leaves of a tree, in a different costume.

Fourth, as a base rate for simultaneous discovery. Alpha-beta was found independently by McCarthy, by Newell/Shaw/Simon, by Samuel, by the MIT group around Hart, Edwards and Levin, and by Brudno in Moscow, inside about seven years, and the participants themselves said it kept being reinvented. It was not a hard idea, it was an idea whose time had arrived because several people were pointed at the same problem with the same tools. The concentration lens asks who holds a capability and on what terms; the base rate here says that when one lab announces a technique, the prior that two or three others have it undisclosed is not low. Used carefully this cuts both ways — it deflates a uniqueness claim and it also undercuts "only we can do this safely." Used loosely it becomes an argument that nothing is ever novel, which is false and which this entry does not support.

Fifth, and trivially but it will cost someone an hour: in 2026 the word "minimax" in an AI search result is a company. MiniMax Group Inc. is a Shanghai lab, founded December 2021, listed on the Hong Kong exchange in January 2026 where it roughly doubled on debut, shipping the MiniMax-M series of models and the Hailuo video product, and reported in June 2026 to be preparing a Shanghai STAR Market listing. It is exactly the kind of firm the concentration lens tracks and it has not yet appeared in a digest. A reading searching for either sense needs to disambiguate, and a canon entry that did not say so would be setting a trap.

What a reading should not cite this for: nothing here bears on whether models are getting better, on compute, on safety outcomes, or on the needle. It is an instrument for reading claims about efficiency and coverage, and it is a piece of lineage. Nothing in this file is evidence and nothing in it moves anything.

What it got right, and what it got wrong

Not required for idea, but there are five dated claims in the vicinity and two of them have moved recently. Graded against what happened, with dates.

Right, and the entry's whole reason for existing: alpha-beta is exact (claimed from 1956, proved 1975, standing). The value returned at the root with a full window is the minimax value. Seventy years of practice and a machine-checked proof have not dented it. The 2025 formal-verification work below reconfirms it for the plain algorithm.

Right, and unusually well-calibrated: Knuth and Moore's conjecture that deep cutoffs are second-order (1975, due whenever someone did the analysis). They proved the branching factor of their simplified model and speculated that adding deep cutoffs would not change the behaviour substantially. Baudet showed Θ(n/ln n) in 1978 and Pearl settled it in Communications of the ACM 25 in 1982. A conjecture stated with its own uncertainty and confirmed in under a decade — the boring outcome, which is why nobody quotes it.

Wrong, and by the man who invented it: "heuristic" (1956/1961, corrected 1967). McCarthy named it the alpha-beta heuristic, MIT AI Memo 30 was retitled to match, and Samuel wrote the correction into the record in 1967. The name mislabels the one property that matters. Fifty-nine years later the memo still carries the wrong title and textbooks still occasionally teach it as a heuristic, which is how the misuse in section 4 is manufactured.

Mixed, and the direction reversed twice: the 1970s bet that exhaustive alpha-beta beats selective search (made mid-1970s, due repeatedly). shannon-chess-1950 grades Shannon's opposite bet as wrong by the mid-1970s, when full-width alpha-beta programs overtook the plausible-move generators, and that grade stands. But the bet that replaced it — that this is simply how game-playing works — was itself falsified in Go, where alpha-beta never got off the ground and Monte Carlo tree search did, and then partly falsified in chess by AlphaZero. Then the pendulum came back: the strongest chess player in the world in 2026 is alpha-beta with a neural leaf, and the strongest Go player is not. The honest grade is that the answer is domain-specific and that everyone who has stated it as a general law has been wrong within a decade, including in both directions. That is the most useful thing in this section, because it is the standing temptation with every architectural claim the readings meet.

And the newest one, which cuts at the entry's own headline: the standard analysis of alpha-beta is an artefact of its model (1975 analysis, challenged June 2025, revised February 2026). Raphaël Boige, Amine Boumaza and Bruno Scherrer, "AlphaBeta is not as good as you think," arXiv:2506.21996, at NeurIPS 2025: the classical average-case analyses assume leaf values drawn independently, which strips the tree of the ancestor-dependence real games have, and makes the problem trivially easy in a way that flatters alpha-beta. On their structured synthetic games the asymptotic branching factors still converge, but on finite deep trees alpha-beta carries a substantially larger constant multiplicative factor than Scout, a competing exact algorithm from the same family. Nothing here touches exactness — Scout returns the same value too; what is challenged is "alpha-beta is optimal," which turns out to be optimal-in-the-model rather than optimal-in-the-world. Fifty years is a long time for a result to stand before someone checks the modelling assumption underneath it, and the readings should file that observation next to every benchmark they meet.

A sixth thing, which is not a claim but a composition failure, and it is the most important grade here. Alpha-beta is exact. Alpha-beta with a transposition table — the standard practical version, in every real engine — is not automatically exact, and the failure is subtle enough that it went unnoticed in a published algorithm for decades. Wieger Wesselink, Kees Huizing and Huub van de Wetering, "Formal Verification of Minimax Algorithms" (arXiv:2509.20138, submitted 24 September 2025, revised 22 April 2026) mechanised the correctness argument in Dafny. They obtained a complete proof for one practical variant of depth-limited negamax with alpha-beta and transposition tables — and a concrete counterexample for another, Marsland's NegamaxTTM. The root cause they give is reuse of a bound computed under one alpha-beta window inside a search with a wider one, which prunes a child that should have survived.

Sit with that, because it is the cleanest cautionary tale this canon has about composed guarantees. The provably-free optimisation stays provably free right up to the point where it is combined with the memoisation that makes it practical, and there the proof has to be redone, and when someone finally did redo it by machine in 2025 they found a published algorithm that fails. A guarantee about a component is not a guarantee about the system. A reading meeting "the model is provably X" or "the sandbox guarantees Y" has, in this, a fifty-year-old example where the component theorem was correct, universally believed, correctly stated, and did not survive being plugged into the thing next to it.

Commonly misused as

The section belongs to limit and this entry is idea, but the argument in the header was that the misuse here attaches to the procedure rather than the lower bound, so the section is where the entry earns its keep. Gödel is the house standing example — a theorem about formal systems pressed into service to prove minds are not machines — and the pattern below is the same shape at lower stakes and higher frequency.

"Minimax is von Neumann's theorem." The theorem is; the algorithm is not. Von Neumann's 1928 result is about mixed strategies in simultaneous-move zero-sum games and its content is the existence of a saddle point. The backward-induction procedure a game program runs needs none of it, and its first explicit statement is Kalmár's, also 1928, after a Zermelo paper from 1913 that Schwalbe and Walker showed does not say what it is cited for. The attribution is so entrenched that proposals.md proposed this entry as "von Neumann's 1928 theorem, applied from the 1950s," and shannon-chess-1950's file names von Neumann 1928 while making a different and correct point about Shannon. What actually matters about the confusion is that both senses are live in AI right now, in different subfields, under the same word. When a paper on generative adversarial networks writes min_G max_D, or an adversarial robustness paper writes a min-max objective over perturbations, that is von Neumann's sense — a saddle point, an equilibrium, an optimisation. When a game-playing or planning system says minimax, that is Kalmár's sense — an alternating tree, evaluated by backward induction. A reading that meets "minimax" in a technical claim should establish which one before doing anything else, because the two support completely different inferences.

"Alpha-beta is a heuristic." It is not, and the person who named it said so and was corrected in print. It is exact, and it is a special case of branch and bound. This one matters beyond pedantry: calling it a heuristic puts it in the same mental bin as null-move pruning, and the entire value of the entry is that those two things are on opposite sides of a line.

"Alpha-beta lets you search twice as deep." Only with perfect move ordering, which requires already knowing the best move. The realised gain depends on ordering quality and degrades to Θ(b/log b) at random. The claim is a best-case bound quoted as a typical one — the same failure mode as any benchmark headline that omits the conditions, and worth noticing that the canonical textbook statement of the field's cleanest result has this bug in it.

"Modern chess engines are neural networks." Stockfish is alpha-beta search with a neural network at the leaves. The network replaced the hand-tuned evaluation Shannon specified in 1950; it did not replace the tree. Reading the 2026 engine as "a neural network that plays chess" gets the architecture exactly backwards and is the single most common way the search half of bitter-lesson-2019 gets dropped.

"Alpha-beta was superseded by MCTS." In Go, effectively yes. In chess, no — and the correct summary is that which search wins is a property of the game's branching factor and how evaluable its positions are, not a fact about the march of progress. Anyone stating it as a general succession is over-reading two data points.

"AI is just minimax" / "it's just search." The deflationary move, and the mirror of the AI-effect problem dijkstra-1959 names. It is true that a great deal of what gets called reasoning is search with a learned evaluation, and it is not true that saying so settles anything, any more than "it's just arithmetic" settles what a processor is. The entry should be used to ask what the system does that backward induction cannot, not as a rhetorical device.

And the inverse, which is now the commoner error: "LLM reasoning is tree search." Some of it genuinely is — Monte Carlo tree search over reasoning traces, best-of-n with a process reward model, beam search over partial solutions are all real and published techniques. But a chain of thought generated autoregressively and checked by a verifier is not minimax and there is no adversary in it; the min layer, which is the entire content of minimax, is missing. Calling long inference "search" because it explores alternatives imports connotations — optimality, exactness, a bound on what is skipped — that nothing about sampling supplies. A reading meeting a test-time-compute claim should ask what the branches are and who, if anyone, is minimising.

One thing that is not a misuse, so it does not get policed: describing Deep Blue, Stockfish and every classical planner as descendants of this idea is correct, and so is noting that A\* — which dijkstra-1959 holds as the join between graph search and AI — and alpha-beta are siblings rather than relatives. Both are exact procedures that skip provably irrelevant work, both arrived within a decade, and neither cites the other. Converges with; does not descend from.

Sources

Read directly, in HTML:

• John McCarthy, "Human-Level AI is harder than it seemed in 1955," slides dated 27 November 2006, http://www-formal.stanford.edu/jmc/slides/wrong/ — source for the "alpha-beta pruning characterizes human play" quotation, the list of early programmers who missed it (Turing, Shannon, Pasta and Ulam, Bernstein), and the attribution of approximations to Samuel, Newell and Simon, and McCarthy. This is the primary source for McCarthy's own account and it is the only classical primary in this entry I read at source.
• chessprogramming.org, Alpha-Beta — the multiple-discovery chronology (McCarthy at Dartmouth 1956 after Bernstein; Newell and Simon 1958; Samuel 1959; Edwards and Hart 1961; Brudno 1963), the Knuth–Moore node count, and the Samuel quotation on "not a heuristic at all." The tail of that quotation — "which has been rediscovered many times and which is currently being exploited in integer programming research" — came from a search summary of the same page rather than the fetched text, and is marked here rather than quoted above.
• chessprogramming.org, Null_Move_Pruning — the zugzwang exception and the concession that the technique can prune the best move.
• handwiki.org, Alpha–beta pruning — the Newell and Simon "reinvented a number of times" quotation, the "returns the same move as minimax would" statement, the square-root branching factor, and pointers to Pearl and to Saks and Wigderson (1986, randomised optimality). The Saks–Wigderson result is recorded here only; I did not verify it against the paper and have not used it above.
• Wikipedia, Zermelo's theorem (game theory) — for Schwalbe and Walker's finding and for Kalmár 1928 as the first explicit backward induction.
• stockfishchess.org/blog/2026/stockfish-18/ — release date 31 January 2026, SFNNv10, "Elo gain of up to 46 points," Correction History. The post describes search refinements without naming alpha-beta; the architecture claim above rests on the NNUE announcement of 2020 that shannon-chess-1950's file already read, and on secondary summaries.
• arxiv.org/abs/2509.20138 and its HTML full text — Wesselink, Huizing and van de Wetering, "Formal Verification of Minimax Algorithms," submitted 24 September 2025, revised 22 April 2026. Source for the Dafny mechanisation, the witness-based correctness criterion, and the NegamaxTTM counterexample including the authors' own diagnosis quoted above.
• arxiv.org/abs/2506.21996 — Boige, Boumaza and Scherrer, "AlphaBeta is not as good as you think," submitted 27 June 2025, revised 5 February 2026, NeurIPS 2025. Source for the independence-assumption critique and the constant-factor gap against Scout.

Bibliographically verified but not read — every one is an image-encoded PDF that would not convert through this job's tooling, and local extraction needs a permission a non-interactive run cannot obtain:

• D. E. Knuth and R. W. Moore, "An analysis of alpha-beta pruning," Artificial Intelligence 6(4), 293–326 (1975); reprinted as chapter 9 of Knuth's Selected Papers on Analysis of Algorithms, CSLI Lecture Notes 102 (2000). The abstract's own summary — expository presentation, correctness proof, historical discussion, optimality "in a certain sense," bounds under random data — and the section 6 minimal-tree lower bound are taken from publisher metadata and from Schaeffer and Plaat's "New Advances in Alpha-Beta Searching," which states the lower bound as "any algorithm that wants to find the minimax value has to search at least this tree." Both ScienceDirect and the ACM Digital Library returned HTTP 403 to this job; two full-text PDF mirrors were fetched and neither would convert.
• A. Newell, J. C. Shaw and H. A. Simon, "Chess-Playing Programs and the Problem of Complexity," IBM Journal of Research and Development, October 1958, pp. 320–335; reprinted in Feigenbaum and Feldman, Computers and Thought (1963), pp. 39–70. The volume number is disputed in the sources I could reach — both 2(4) and 4(2) appear, and the bitsavers scan that would settle it refused the connection. Recorded as unresolved rather than guessed.
• T. Hart and D. Edwards, "The Tree Prune (TP) Algorithm," MIT AI Memo 30, 4 December 1961; revised and retitled "The Alpha-Beta Heuristic," AIM-030, 1963.
• A. L. Brudno, "Bounds and valuations for shortening the search of estimates," Problemy Kibernetiki (1963).
• A. L. Samuel, "Some Studies in Machine Learning Using the Game of Checkers. II—Recent Progress," IBM Journal, November 1967 — the "not a heuristic at all" correction.
• J. von Neumann, "Zur Theorie der Gesellschaftsspiele," Mathematische Annalen 100, 295–320 (1928), presented to the Göttingen Mathematical Society on 7 December 1926.
• L. Kalmár, "Zur Theorie der abstrakten Spiele" (1928).
• U. Schwalbe and P. Walker, "Zermelo and the Early History of Game Theory," Games and Economic Behavior 34(1), January 2001, 123–137, with a translation of Zermelo (1913) appended. Their conclusion is quoted above at one remove.
• G. M. Baudet, "On the branching factor of the alpha-beta pruning algorithm," Artificial Intelligence 10(3) (1978); J. Pearl, "The solution for the branching factor of the alpha-beta pruning algorithm and its optimality," Communications of the ACM 25 (1982), 559–564, DOI 10.1145/358589.358616. The Θ(b/log b) result is taken from summaries of both; HandWiki gives a different-looking expression for one of Pearl's bounds and I have not reconciled them, so nothing above rests on the exact constant.

Modern claims, verified individually:

• Y. Leviathan, M. Kalman and Y. Matias, "Fast Inference from Transformers via Speculative Decoding," ICML 2023, arXiv:2211.17192; and, independently, Chen et al., arXiv:2302.01318. Cited above only for the property that the output distribution is provably identical to ordinary decoding, which both papers establish by construction.
• MiniMax Group Inc.: founded December 2021 in Shanghai; HKEX listing January 2026, closing at HK$345 against an offer price of HK$165; MiniMax-M series and Hailuo AI; reported June 2026 to be preparing a Shanghai STAR Market listing. From Wikipedia, Caixin Global and CNBC via search summaries; not read at source, and cited above only as a disambiguation warning rather than as any kind of finding.

Project context read while writing: README.md, LENSES.md, canon/proposals.md, canon/shannon-chess-1950.md (in part), canon/dijkstra-1959.md, and digests/2026-08-19-00.md. The digest is the source for the three 2026 items referred to in section 2 — the OpenAI monitoring overhead, the Astra mathematics result, and the model price cuts — and each of those rests on the primary sources that reading cited, not on this file. No evidence was added anywhere, no needle, score or landmark is placed here, and nothing outside this file was written.