One recurrence contains both players
The paper begins with finite, alternating, two-person games. Its first simplification is representational: instead of carrying separate Max and Min procedures, evaluate every position from the viewpoint of the player whose turn it is.
A position has finitely many legal successors and no infinite legal continuation. A terminal position p receives an integer f(p), positive or negative according to the outcome for the player about to move there. If p has successors p₁,…,pᵈ, its backed-up value is F(p)=max(−F(p₁),…,−F(pᵈ)). Moving changes the viewpoint, so negation converts the successor's value into the present player's value.
This “negamax” equation is equivalent to the familiar pair of minimax equations: Max takes the maximum of successor values and Min takes the minimum. Knuth and Moore prefer the single recurrence for proofs because it removes duplicated cases. They note its kinship to NOR logic: alternating negation and maximum carries the opposition inside one operator.
The definition is conservative. F(p) is the value secured against an optimal opponent, not necessarily the move that performs best against a fallible human. A guaranteed draw can outrank a risky line that wins only if the opponent misses a reply. Alpha-beta preserves this minimax criterion exactly; it does not revise the utility model or estimate an opponent's psychology.
A brute-force procedure follows the recurrence literally. It generates every successor, recursively evaluates each, negates the result and returns the largest. Finiteness ensures termination. The whole paper asks which descendant values must actually be known to return the same root value.
Worked example 1 · a two-ply choice
Suppose the root can move to A or B. The opponent can hold A to terminal outcomes 3 and 5, so A is worth 3 to Max; B offers 2 and 9, so the opponent chooses 2. Max selects A and the root value is 3. Discovering B's reply worth 2 is already enough to refute B; its 9 need not be inspected.
Causal probe 1 · remove the sign change
If the recursive caller maximises F(pᵢ) rather than −F(pᵢ), both levels collaborate for the same player. The computation may still return a number, but it no longer represents adversarial optimal play.
Approximation can be exact enough for a decision
Procedure F1 introduces one-sided branch-and-bound. Procedure F2 introduces both a lower and an upper bound. The crucial insight is that a recursive call need not always report the exact value of its position.
F1(p,bound) promises the exact F(p) when F(p) lies below bound, but may return any value at least bound when the true value reaches or exceeds it. Calling F1(p,+∞) therefore yields the exact root. Inside the loop, once a child establishes a move at least as good as the supplied bound, remaining siblings cannot change the fact the caller needs.
F2(p,α,β) strengthens the contract. If F(p)≤α it may return a value no greater than α; if α<F(p)<β it returns F(p) exactly; if F(p)≥β it may return a value at least β. An infinite initial window still forces the exact root value. Descendants, however, often receive narrow windows and may answer only on the relevant side.
The running variable m starts at α. After each examined successor it equals the maximum of α and the negated values already established. The recursive child receives the sign-reversed window (−β,−m). If its negated return raises m to β or beyond, the procedure stops. This is a beta cutoff from the current position and, viewed through the caller, an alpha proof that the alternative has been refuted.
The proof is an induction on remaining game length. Its invariant separates what has been exactly evaluated from what only has to cross a threshold. If a child's true contribution lies inside the window, the recursive contract supplies it exactly. If it lies beyond beta, any return on that side licenses the same cutoff. Nothing pruned can alter which clause of the outer contract is satisfied.
Worked example 2 · a useful inexact answer
A caller already has a move worth 6. It tests an alternative whose opponent can force 4 on the first reply. The alternative is therefore worth at most 4 to the caller. The exact value might be 4, 1 or −8, but all three lose to 6; a bound is the complete answer for the decision at hand.
Causal probe 2 · report an interior value inaccurately
If the true value lies strictly between α and β, the contract demands equality. Returning only a side-of-bound certificate there can change an ancestor's comparison and corrupt the root result.
Two bounds travel farther than one
The distinction between F1 and the full F2 is not cosmetic. The upper and lower limits change sign and role as recursion descends, allowing information from a remote ancestor to close a branch several levels later.
A shallow cutoff occurs when a sibling is refuted by an alternative already examined at the same parent. One-sided F1 can make these cuts. A deep cutoff occurs because a threshold inherited from higher in the tree becomes decisive below intervening positions. Only the two-sided window carries enough context to create it.
In the paper's ternary height-four example, 81 terminal digits derived from π define the complete game. Brute force inspects all 81. F1 inspects 36; it deliberately leaves some internal values approximate because the root does not depend on them. F2 follows the same nodes through the first four lookahead levels but then makes five deep cutoffs unavailable to F1.
This is why the term “alpha-beta” must not be attached casually to any pruning in a minimax tree. The historical literature sometimes described only the one-sided method, sometimes omitted deep cutoffs, and sometimes used strict inequality where the stronger procedure could cut on equality. Knuth and Moore make the recursive parameter contract the criterion.
Exactness at the root survives because every local approximation respects its caller's window. A pruned subtree is not declared valueless. It is declared incapable of changing the decision represented by the current bounds. If the surrounding alternatives or aspiration window change, the same subtree may become relevant in a later search.
Worked example 3 · an ancestor's threshold reaches a grandchild
At the root, one move establishes 7. Inside a later move, the opponent explores a reply whose first continuation already guarantees 7 against the root player. The cut can occur before that reply's siblings are known. The decisive comparison originated at the root, crossed a player switch, and became a beta threshold below.
Causal probe 3 · reset bounds at every node
Calling every child with (−∞,+∞) still computes correct minimax values, but it discards the accumulated decision context. Every node demands an exact answer and no pruning occurs.
The elegant recursion becomes a practical search process
After presenting paired Max/Min and linked-record forms, the authors mechanically transform recursion into an iterative procedure. The exercise is not merely stylistic: it exposes exactly which state must survive between visits.
A position record points to its first successor; each successor points to the next. A generate operation constructs children only when required. The recursive procedure needs the current position, the next child, α, −β, m and the negated child return. An iterative version stores these quantities in arrays indexed by search depth. The result is compact, though harder to prove correct than the recursive statement.
Real chess programs cannot normally search to actual terminal positions. They declare sufficiently deep nodes terminal and supply a quickly computed evaluation f. The search may extend unstable lines, delay early termination, or use iterative deepening, but the formal result remains conditional on the leaves and successor order actually presented. Alpha-beta returns the same backed-up value as full minimax for that finite search tree.
Move ordering is therefore operationally central. Trying a good move first raises α early at Max nodes or lowers the corresponding bound at Min nodes, making later refutations easier. The paper mentions retaining best moves from a shallower search, killer moves that caused cutoffs elsewhere, and using plausible ordering functions. Ordering changes work, not the minimax answer.
The authors also describe an aspiration window: call F2(p,a,b) when the root is expected between a and b. A narrower initial window can prune more. If the returned value falls outside, a second search with a wider range recovers the exact answer. Speed comes from a prediction, while correctness comes from detecting its failure and re-searching.
Worked example 4 · iterative deepening pays twice
A depth-four search finds move C best. A depth-six search tries C first, so its value becomes an early bound and refutes competitors sooner. The shallow result is not trusted as the final answer; it is reused as ordering information.
Causal probe 4 · accept an aspiration fail-high as exact
If a narrow-window call reports only that the root is at least β, presenting its returned number as the exact minimax value violates F2's contract. Widening or shifting the window is required.
The algorithm was easier to run than to explain
Knuth and Moore devote a full section to priority because the record was fragmented, recollected after the fact, and repeatedly blurred by the difference between F1 and F2.
John McCarthy recalled thinking of the method at the 1956 Dartmouth conference while criticising Bernstein's chess program, though he gave no formal specification then. Arthur Samuel said the idea was present in his checker program but omitted it from his celebrated 1959 article because other contributions seemed more important. Newell, Shaw and Simon published a game-tree pruning description, yet the illustration establishes only a one-sided method.
McCarthy coined “alpha-beta” in a Lisp program that used optimistic and pessimistic position bounds. He initially regarded it as a possibly inaccurate heuristic. Hart and Edwards's 1961 memorandum showed the general method, including deep cutoffs, but supplied no proof. Independently, Alexander Brudno published an identical algorithm with a complicated proof in Russian in 1963.
Full accounts reached English-language literature later. Slagle and Bursky discussed it in 1968 but did not clearly illustrate deep cutoffs; Slagle and Dixon and Samuel did so in 1969. Textbooks still sometimes presented weaker procedures. Knuth even reports doing part of the random-tree analysis years before realising that deep cutoffs existed.
The authors draw a methodological lesson. Ordinary verbal explanation made the method sound mysterious, especially when cuts occurred several levels below their originating bound. A short algorithm plus an invariant made correctness easier to see. Dynamic process description was not decoration: it was a more effective explanatory language for an algorithmic phenomenon.
Worked example 5 · naming is not specification
Two programs may both be called “alpha-beta”. If one propagates a single threshold and the other passes the full sign-reversed window, they make different deep cuts. Historical attribution and technical comparison require inspecting the procedure, not its label.
Causal probe 5 · infer priority from publication date alone
The first printed account need not be the first implementation, while recollection without code cannot settle the exact strength of a method. The paper explicitly marks this uncertainty instead of inventing a clean lineage.
The best case is a minimal certificate, not merely a lucky speed-up
For quantitative analysis, the authors give every node a coordinate such as 314: third successor, then first, then fourth. Under suitable best-first ordering, a simple parity pattern identifies exactly what alpha-beta examines.
A coordinate a₁…aₗ is critical when all entries in the even positions are 1 or all entries in the odd positions are 1. The root is critical. If the first successor of every non-terminal position is optimal and the finite root value is not ±∞, Theorem 1 says F2 examines precisely the critical positions.
The proof classifies them. Type 1 coordinates contain only ones and form the principal variation. Type 2 first depart from one at a parity that receives an upper-bound call; their first successor is type 3 and immediately refutes the branch. Type 3 positions receive a lower-bound call and all their successors are type 2. These call shapes are invariants of the computation.
In a uniform tree of degree d and depth h, the number of terminal positions examined in this best case is d raised to the ceiling of h/2 plus d raised to the floor of h/2, minus one. A full tree has dʰ leaves. For even h, the dominant work is about twice d^(h/2): perfect alpha-beta effectively takes the square root of the leaf count, though constants and non-uniformity still matter.
The result needs its premises. If the root value is +∞ or −∞, one of the two critical families disappears and the count changes. The authors correct earlier hand-waving on this edge case. They also show that “first successor optimal everywhere” is not universally the ordering that minimises leaf evaluations for every non-uniform tree; Figure 4 of the paper gives a counterexample.
Worked example 6 · degree 3, depth 4
The full tree has 3⁴=81 leaves. The critical-position formula gives 3²+3²−1=17 terminal evaluations under its stated ideal conditions. The number is a proof-shaped certificate: one family supports the principal line and the other refutes alternatives.
Causal probe 6 · turn a critical coordinate non-critical
Coordinate 1212 contains non-one entries in both odd and even places, so neither parity is fixed at one. Under Theorem 1's traversal it lies behind a certified cutoff. Coordinate 1311 keeps all odd entries at one and remains critical.
No general evaluator can escape every leaf in the certificate
Theorem 2 strengthens the best-case account. Given any root-evaluation algorithm, the tree can be ordered so that every terminal position examined by alpha-beta is one the competing algorithm also examines.
The comparison assumes terminal values are independent, equivalently that the evaluator has no knowledge of dependencies among leaves. From the leaves the competitor has inspected, construct a lower possible value F₁(p) by assigning −∞ to unexamined terminals, and an upper possible value F₂(p) by assigning +∞. Back these possibilities through the negamax recurrence.
At the root, a correct evaluator must have forced the lower and upper possibilities to coincide with the true value. Otherwise some unseen assignment would change the answer. The proof then permutes successors so the competitor's examined leaves occupy the type 1, 2 and 3 critical roles. Alpha-beta visits precisely those roles and therefore no leaf absent from the competitor's evidence.
For uniform degree-d, height-h trees, Corollary 3 follows: any algorithm that always evaluates the root must inspect at least d^⌈h/2⌉+d^⌊h/2⌋−1 terminal positions in the worst arrangement, and alpha-beta reaches that lower bound with the required order at type 1 and type 2 nodes.
This is not a universal claim that alpha-beta is fastest on every instance, machine or representation. It compares leaf information needed to identify an arbitrary independent-valued minimax tree. An algorithm with transpositions, algebraic structure, correlated evaluations, cached domain knowledge or a different problem contract may fall outside the comparison. The theorem is powerful because its scope is explicit.
Worked example 7 · an unseen leaf remains an adversary
If changing an unexamined terminal from a very low to a very high value can alter the backed-up root, the evaluator has not certified its answer. The F₁/F₂ envelope formalises this counterfactual. A leaf becomes avoidable only when every value it might take is screened off by a bound.
Causal probe 7 · add known sibling dependence
Suppose a game rule proves that two leaves must have the same value. Inspecting one then reveals the other. The independent-terminal lower bound no longer applies unchanged; the extra information can shrink the necessary certificate.
Average work depends on a probabilistic story
The paper next studies uniformly branching trees whose terminal values are independent, identically distributed and continuous, first disabling deep cutoffs to obtain an analysable upper model.
With no deep cutoffs, the event that a coordinate is examined depends on comparisons between maxima of minima in previously visited sibling blocks. The authors derive probabilities pᵢⱼ, expected counts and matrix recurrences. The dependence among comparison events prevents a naive multiplication from being exact, so lower and upper spectral bounds are developed instead.
For fixed degree d and increasing height h, the expected leaf count has an asymptotic branching factor r(d): the hth root of expected work converges. Theorem 5 bounds this factor above and below by constant multiples of d/log d. This is much smaller than d but larger than the square-root scale √d of ideal full alpha-beta.
The table for degrees 2 through 31 shows finite-degree lower and upper estimates. For d=2 they are already close; for larger d, two different upper methods trade places. The detailed constants are less portable than the structure of the result: random ordering still prunes substantially, but its effective branching factor is governed by the assumed value distribution and by suppressing deep cuts.
Expectation must not be confused with a per-tree promise. A bad ordering can approach full minimax, while a favourable one can approach the critical-position count. Nor is a continuous iid leaf model a literal model of chess. It is a controlled baseline that isolates what follows from random values before move ordering and domain dependence are introduced.
Worked example 8 · why a branching factor matters
If expected leaves grow like rʰ, adding two plies multiplies work by roughly r². Reducing r from d to d/log d compounds across depth. Yet the same asymptotic statement says little about shallow fixed trees unless constants and finite-height behaviour are checked.
Causal probe 8 · multiply locally dependent events
Two cutoff tests can share leaf values, so treating them as independent underestimates or overestimates joint probability. Knuth and Moore isolate partial independence and use matrix bounds rather than silently multiplying every local probability.
Real structure can help pruning, but only through a stated model
The random-tree model is pessimistic in four identified ways: it omits deep cutoffs, randomises successor order, makes terminal values distinct and treats them as independent.
Practical programs can guess promising moves, repeated evaluation scores create extra equality cutoffs, and full F2 retains inherited bounds. Knuth and Moore estimate the best case without deep cutoffs: its recurrence has effective branching factor √(d−3/4)+1/2, only a second-order increase over √d when d is large. Poor ordering, however, can make deep cutoffs more valuable than this ideal comparison suggests.
Dependence is examined with a deliberately extreme “total dependency” model. Every node assigns a random ranking to its successors, but all terminal descendants under one successor rank above or below all descendants under another. Terminal values can be represented by concatenated base-d move digits. A good or bad early move shifts an entire family of later outcomes together.
Classifying recursive calls into three types yields exact expected recurrences. For d≥3 the average number of leaves examined grows within a constant factor of the critical-position optimum, hence on the order of d^(h/2). For binary trees a different golden-ratio-like growth appears. The authors also cite an additive branch-value model whose comparisons support the same qualitative belief.
The conclusion is appropriately cautious: there are good grounds to believe dependencies usually make alpha-beta more efficient than independent leaf values do. It is not a theorem that every correlation helps. A dependency must align groups of descendants so an observed bound speaks for unobserved relatives; adversarial correlations could instead frustrate ordering.
Worked example 9 · a blunder moves a whole subtree
If an early chess move loses a queen, most continuations beneath it inherit a poor material score. One sampled reply can then establish a bound relevant to many unseen replies. Independent random leaves would erase that shared cause and make every descendant a fresh surprise.
Causal probe 9 · confuse equality with dependence
Duplicate leaf values and correlated families are different relaxations of the iid-continuous model. Equality can trigger cutoffs at a threshold; dependence lets evidence about one branch predict the ordering of others. Their effects should be measured separately.
Pruning is a proof of irrelevance under a model
Alpha-beta is often described as “not searching” a branch. More precisely, it has already acquired enough comparative evidence to know that no exact value inside that branch can alter the backed-up choice.
The skipped leaves do not vanish from the game. They remain possible continuations under a move that has been refuted relative to an established alternative. The result depends on fixed terminal evaluations, alternating optimal play, finite depth and correct successor generation. An error in any of those ingredients is not repaired by the pruning theorem.
A bound is local authority. Alpha says what the current player can already secure within the caller's context; beta is the point at which the opponent has a better alternative elsewhere. Passing (−β,−m) is therefore structured communication between levels. The search does not share all descendant facts; it shares the thresholds relevant to decision.
This economy suggests a general pattern for intelligent systems: compute only what could cross a decision boundary, but retain a certificate of why omitted alternatives cannot do so. The transfer is conceptual, not automatic. Non-zero-sum games, chance nodes, hidden information, multiple agents and learned stochastic utilities require different recurrences and proof obligations.
Nor does node reduction equal overall efficiency. Move ordering consumes computation; transposition tables consume memory; evaluation may dominate leaf generation; aspiration failures repeat work. The 1975 paper counts positions and leaves under explicit models. Engineering judgement must add the cost of obtaining the bounds.
Worked example 10 · a safe omission
A procurement agent has one verified option worth at least 80. A second option's mandatory compliance check caps it at 75 before optional features are scored. If the utility model and cap are sound, further scoring cannot change the choice. The branch is irrelevant to this decision, not worthless in every context.
Causal probe 10 · change the payoff after pruning
If the utility function is revised so compliance carries a bonus rather than a cap, the old cutoff certificate expires. Pruning is conditional on the backed-up value model that created its bounds.
Evidence boundary
The paper establishes computational properties of finite game-tree evaluation. It does not show that a search procedure experiences conflict, intends victory, or is conscious. Goal-directed selection and phenomenal experience are independent evidential questions.
Reorder five nodes and audit every search
Five controls choose one of four child orders at internal nodes of a fixed depth-four binary game tree. The laboratory evaluates all 4⁵=1,024 configurations, compares alpha-beta with a complete minimax oracle, checks the selected root move and validates every recorded cutoff.
Running exact-value audit…
Running principal-choice audit…
Running cutoff-certificate audit…
Worked example 11 · order is information about work
Change only the root or Node B order. The oracle value and legal principal choice stay fixed, but leaf visits and the depth of cutoffs change. This directly separates semantic invariance from operational sensitivity.
Causal probe 11 · corrupt one cutoff inequality
If the implementation stops before α reaches β, the certificate audit fails because a skipped sibling might still move the returned value inside the caller's window. A fast trace is not a valid trace without the inequality.
Claims, premises and audit handles
| Claim | Required premise | Audit handle |
|---|---|---|
| Alpha-beta returns the minimax root value. | Finite tree, correct terminal values, correct sign-reversed window and cutoff rule. | Compare every control configuration with complete minimax. |
| A pruned sibling cannot alter the current answer. | The running bound has reached or crossed beta. | Record α, β, depth and skipped child count for every cutoff. |
| Perfectly ordered uniform trees need d^⌈h/2⌉+d^⌊h/2⌋−1 leaves. | Uniform degree and height, finite non-infinite root value, required type-1/type-2 order. | Generate coordinates and count the union of parity-critical families. |
| No evaluator can always use fewer leaves in the paper's sense. | Independent arbitrary terminal values and root value required for every assignment. | Vary every unexamined leaf between lower and upper extremes. |
| Random no-deep-cutoff work has branching Θ(d/log d). | Iid continuous terminal values, random successor order and the restricted F1 model. | Do not transfer the asymptotic outside its probabilistic assumptions. |
| Dependence can approach best-case scale. | The specified total-dependency model or the cited additive model. | Inspect which shared ranking makes one leaf informative about relatives. |
Fidelity, pedagogy and executable evidence
Review one: scholarship. The reconstruction retains the paper's finite negamax game model, F1 and F2 contracts, invariant proof, equality cutoff, sign-reversed recursive window, deep-cutoff distinction, aspiration search, documented history, critical coordinates, three proof types, independent-leaf optimality comparison, uniform-tree corollary, random F1 analysis, four pessimistic assumptions and total-dependence model. Claims about asymptotic branching are tied to their sections rather than presented as universal chess measurements.
Review two: teaching and execution. Ten bespoke accessible SVGs carry unique titles, descriptions, captions and source scopes; reduced-motion preference disables animation. Twelve worked examples and twelve causal probes attack the sign convention, window contract, deep bounds, aspiration failure, documentary uncertainty, criticality, independence, probability, dependency, model scope, cutoff inequality and future canon link. The laboratory exhaustively enumerates 1,024 order combinations and applies three exact tests.
AI-telltale and evidence review. The prose does not anthropomorphise pruning as intuition or foresight. Modern phrases such as principal move and cutoff certificate clarify the process without attributing later implementations to 1975. The theorem's “optimal in a certain sense” is unpacked through the F₁/F₂ envelope and never inflated into a claim about wall-clock supremacy.
Implementation review. The oracle evaluates every leaf independently of the alpha-beta routine. A principal move passes only when its exact child value supports the returned root. Each cutoff log includes the inequality α≥β, the number skipped and its depth; at least one of the enumerated cases contains a cutoff below the root's immediate children. Interactive output uses text as well as colour.
Twelve cards for rebuilding the analysis
Intelligence appears here as controlled incompleteness
A brute-force evaluator purchases exact knowledge everywhere. Alpha-beta asks what exactness the decision consumes. Inside its live interval, precision matters; outside, direction relative to a threshold is sufficient. The procedure is not less rigorous because it knows less. It is rigorous about which ignorance is harmless.
The two bounds are a compact institutional memory. Alpha records a defended option; beta records an ancestor's competing commitment. Each recursive call receives only the part of that memory relevant after the viewpoint reverses. This is a disciplined form of context propagation: enough state to justify omission, no demand for a globally complete world model.
Ordering converts a plausible forecast into computational leverage without allowing it to change the answer. A good guess is tried first and may create earlier proof; a bad guess costs work but, with a full root window, cannot falsify minimax. That separation between guidance and guarantee remains valuable in systems where learned proposals sit inside exact verification.
The dependence analysis adds a second lesson. Evidence becomes powerful when the environment has shared structure. If sibling descendants are arbitrary and independent, each unseen value remains an adversarial possibility. If an early event moves an entire family together, one observation constrains many. Efficient intelligence depends as much on finding legitimate dependence as on searching faster.
Worked example 12 · proposal plus verifier
A learned move-ordering model ranks candidate actions. Alpha-beta treats the ranking as a schedule, not as truth: every cutoff still requires a deterministic bound certificate. Better learning saves evaluation; wrong ranking merely spends more. The guarantee lives in the verifier and the finite evaluation model.
Causal probe 12 · let the proposal alter terminal values
If the ordering model also changes leaf utilities opportunistically, errors no longer only affect labour. The oracle itself has moved, so agreement with full minimax of the original tree is lost. Guidance and semantics must remain separately auditable.
Boundary statement
Alpha-beta supplies a lucid model of selective computation in adversarial choice. It is evidence about algorithmic agency: goal-conditioned comparison, memory and proof-directed work: not about subjective awareness.
From informed paths to adversarial bounds
Canon 0075 followed Hart, Nilsson and Raphael's A*: an accumulated path cost and an admissible estimate decide which frontier node earns expansion. Canon 0076 changes the geometry. There is no single traveller and no additive route objective; alternating players back values through a tree. Yet both papers make selective search defensible by attaching a formal meaning to a bound.
A* protects an optimal path with a lower-bound witness on the open frontier. Alpha-beta protects a minimax decision with an interval inherited through opponents. One decides which possibility is most promising; the other decides which alternatives can no longer matter. Together they show two ways partial information can govern computation without silently replacing the target answer.
Canon 0077 turns from search order to relational structure: Alan K. Mackworth's “Consistency in Networks of Relations” (1977). There the question is how local compatibility filtering can expose impossible values before global search.
What this companion adds
This companion reconstructs all nine sections of the 34-page 1975 paper. It begins with the original negamax convention, preserves the distinct F1 and F2 contracts, follows the invariant proof, shows why deep cutoffs require two travelling bounds, and treats the linked-record, iterative and aspiration variants as refinements rather than new semantics.
The quantitative half is presented as a ladder of assumptions: first critical positions under ideal ordering, then the independent-leaf optimality comparison, then random uniform trees without deep cutoffs, then the four reasons that model is pessimistic, and finally a total-dependence construction. The square-root and d/log d scales remain attached to the models that produce them.
Ten animated figures, twelve worked examples, twelve causal probes, a verification ledger and twelve memory cards make the proof obligations inspectable. The executable laboratory varies five order controls across 1,024 cases, compares every run with complete minimax and checks each cutoff as a logged inequality rather than celebrating fewer leaves without a certificate.
Primary and contextual sources
- Donald E. Knuth and Ronald W. Moore, “An Analysis of Alpha-Beta Pruning”, Artificial Intelligence 6(4), 293–326 (1975). Publisher DOI.
- John McCarthy, Marvin L. Minsky, Nathaniel Rochester and Claude E. Shannon, “A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence” (1955), historical context for the 1956 meeting discussed by Knuth and Moore.
- Allen Newell, J. C. Shaw and Herbert A. Simon, “Chess-Playing Programs and the Problem of Complexity”, IBM Journal of Research and Development 2, 320–335 (1958).
- Arthur L. Samuel, “Some Studies in Machine Learning Using the Game of Checkers”, IBM Journal of Research and Development 3, 210–229 (1959).
- Alexander L. Brudno, “Bounds and Valuations for Shortening the Scanning of Variations”, Problemy Kibernetiki 10, 141–150 (1963), cited in the primary as the first published full method.
- Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill (1971), cited for a textbook presentation.