Abstract
Alpha-beta search cuts off branches that need not be read without changing the value of play in which both sides do their best. This paper places random leaf values on uniform trees of fixed branching and depth, and counts, for five sizes and ten trees each, how many leaves alpha-beta reads when children are ordered best first, at random, and worst first. No new theorem or law is claimed.
First, the root value does not depend on the order: in all three orders, the root value matched the minimax value obtained by reading everything (Section 2).
Second, in the best order, the leaves read match the Knuth and Moore formula exactly: of $262144$ leaves at branching $8$ and depth $6$, $\mathbf{1023}$ are read, and for all ten trees of all five sizes the count matched the formula ($53$, $127$, $251$, $127$, $1023$) (Section 2).
Third, in random order, the count falls in between: at branching $8$ and depth $6$ the mean is $\mathbf{21296.7}$ leaves, and its logarithm to the base of the branching divided by depth ranged from $0.798797$ to $0.834560$ (Section 3).
Fourth, in the worst order, not everything is read, but over eight tenths is: the smallest fractions of leaves read over the five sizes were $0.857339$, $0.834473$, $0.883873$, $0.941406$ and $\mathbf{0.816006}$. The ranking of best, random and worst orders did not change for any of the five sizes (Section 3).
Fifth, the separator is whether the order knows the children’s true values: ordering by true values reduces the leaves read to the order of the square root; not knowing them gives the random count in between; reversing them returns to over eight tenths. What decides the amount cut off is not the search procedure but the knowledge contained in the order (Section 4).
Keywords: alpha-beta search, minimax, game tree, pruning, move ordering, search effort.
Scope (what is not claimed)
No new theorem or law is claimed: minimax reading, alpha-beta search, and the Knuth and Moore formula for the leaves read in the best order are all known. Real game programs are not treated: evaluation functions, iterative deepening, transposition tables and techniques for ordering moves are not treated. Cases where the children’s true values are known and not known are only set up and counted. Only uniform trees: only trees of fixed branching and depth whose leaf values are independent random real numbers are counted. No limit is claimed, where the exponent of the random-order count tends for large trees is not claimed; only measurements at five finite sizes are set down. Relation to earlier papers: Paper 886, in its scope note, did not enter strong programs and did not treat techniques that speed up reading or the construction of evaluations; this paper sits in that seat of techniques that speed up reading (no earlier occupant). Paper 873 showed that which way of exploring is better is decided not by the loss at one moment but by how the loss grows. Here, for each order, it is counted how the work of search procedures returning the same value grows with the size of the tree. What is added: confirming that the root value does not change across the three orders, showing that the best-order count matches the Knuth and Moore formula at five sizes, setting down the random-order means and exponents, measuring that even the worst order reads only over eight tenths, and placing the separator on “whether the order knows the children’s true values”.
1. Notation and the Question
Setting: in a uniform tree of branching $b$ and depth $d$, the root is a maximizing turn, the next level minimizing, and so on alternately. Uniform random real numbers are placed on the $b^d$ leaves, and minimax gives the true value of every node. Three orders of children for alpha-beta search are set:
$$\text{best order: by true value, best first},\qquad \text{random order},\qquad \text{worst order: by true value, worst first}$$For the leaves read in the best order, the Knuth and Moore formula is:
$$N_{\min}=b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1$$The check builds ten trees at each of five sizes and counts the leaves read.
Question: what decides the number of leaves alpha-beta search reads?
2. The Root Value and the Best Order
Computation 2.1: leaves read (best and worst: minimum to maximum of ten trees; random: mean of ten).
| $b$ | $d$ | leaves $b^d$ | best order | formula $N_{\min}$ | random order | worst order |
|---|---|---|---|---|---|---|
| $3$ | $6$ | $729$ | $53$ | $53$ | $218.6$ | $625$ to $678$ |
| $4$ | $6$ | $4096$ | $127$ | $127$ | $986.0$ | $3418$ to $3711$ |
| $6$ | $5$ | $7776$ | $251$ | $251$ | $1701.1$ | $6873$ to $7116$ |
| $8$ | $4$ | $4096$ | $127$ | $127$ | $1034.5$ | $3856$ to $3973$ |
| $8$ | $6$ | $262144$ | $1023$ | $1023$ | $21296.7$ | $213911$ to $220801$ |
In all three orders the root value matched the minimax value, and the best-order count matched $N_{\min}$ for all ten trees at all five sizes.
Observation 2.2 in the best order, the leaves read fall to the order of the square root of the total. At $b=8$, $d=6$ it is $1023$ of $262144$, one short of twice $b^{d/2}=512$: to confirm the root value it suffices to read all the opponent’s moves under one side’s best move, and only one move of that side under the opponent’s best move.
3. Random Order and Worst Order
Computation 3.1: the mean random-order count, as a logarithm to the base of the branching divided by depth, was $0.817280$, $0.828787$, $0.830360$, $0.834560$ and $0.798797$. The fraction of leaves read in the worst order (minimum of ten) was $0.857339$, $0.834473$, $0.883873$, $0.941406$ and $\mathbf{0.816006}$.
Observation 3.2 even in the worst order, not everything is read, but over eight tenths is. Even in reverse order, cases remain where the upper bound falls to the lower bound during the search and a branch is cut: the ranking best < random < worst held at all five sizes, and the random-order exponent was near $0.8$.
4. The Separator
Observation 4.1 the separator is whether the order knows the children’s true values. The search procedure and the returned value are the same in all three orders; only the order of children differs: ordering with knowledge of the true values reduces the count to the order of the square root, ordering without it gives the random count in between, and reversing returns to over eight tenths. The amount that can be cut off is decided by the knowledge contained in the order.
Observation 4.2 what is not said. Evaluation functions, iterative deepening, transposition tables, strength in real games and the limiting exponent in random order are not treated. What is shown is that the work of alpha-beta search returning the same value moves, with the order of children, from over eight tenths of all leaves to the order of their square root.
5. Roll Call and Closing
- $N_{\min}=b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1$ (Section 1): Knuth and Moore.
- root value the same in three orders (Computation 2.1): matches minimax.
- $\mathbf{1023}$ leaves in the best order (Computation 2.1): matches the formula.
- mean $\mathbf{21296.7}$ leaves in random order (Computation 2.1): in between.
- minimum $\mathbf{0.816006}$ in the worst order (Computation 3.1): over eight tenths.
- whether the true values are known (Observation 4.1): the separator; the scope note of Paper 886; Paper 873.
Closing: The number of leaves alpha-beta search reads ranges, with the order of children, from over eight tenths of all to the order of their square root. The root value was the same in every order, and the best order matched the Knuth and Moore formula exactly: $1023$ of $262144$ leaves at branching $8$ and depth $6$: random order read $21296.7$ leaves on average, and even reverse order read at least $0.816006$ of all, not everything. The procedure and the returned value are the same; only the order differs: the separator is whether the order knows the children’s true values. Placed among the earlier papers: the techniques that speed up reading, left untreated by Paper 886, were counted as knowledge in the order, and the work at each tree size was set out in the growth-based view of Paper 873. To be honest: nothing is said about playing strength. How many times the work of a search returning the same value moves with the order, and no further.
References
- Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence.
- Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
- Yamagishi, Y. (2026). Which Way of Exploring Is Better Is Decided Not by the Loss at One Moment but by How the Loss Grows [Paper 873]. YOI: https://www.yamagishiyuuki.com/yoi/873
- Yamagishi, Y. (2026). On a 4×4 Othello Board, the Move That Flips the Most Is a Best Move in Only a Little Over Half of the Positions [Paper 886]. YOI: https://www.yamagishiyuuki.com/yoi/886
Reference
Yamagishi, Y. (2026). The Number of Leaves Alpha-Beta Search Reads Ranges, with the Order of Children, from Over Eight Tenths of All to the Order of Their Square Root [Paper 926]. YOI: https://www.yamagishiyuuki.com/yoi/926
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 926. This paper is a preprint and has not been peer reviewed.