Abstract
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). A transposition table, which keeps the values of positions for reuse, was not treated there. Starting from the empty board of tic-tac-toe, this paper adds a transposition table to minimax and to alpha-beta and counts the positions expanded, for two move orders. No new theorem or law is claimed.
First, a transposition table cuts minimax expansions to the number of reachable positions: minimax expanded $549946$ positions, and with a transposition table $5478$ ($\mathbf{0.009961}$ times), equal to the number of positions reachable from the empty board (Section 2).
Second, added to alpha-beta, the transposition table helps less: alpha-beta with moves in index order expanded $18297$ positions, and with a transposition table $2700$, a factor of $\mathbf{0.147565}$. With centre and corners first it went from $7275$ to $1242$ ($0.170722$) (Section 3).
Third, the combined factor is far larger than the product of the two: in index order the combined factor $0.004910$ was $\mathbf{14.814326}$ times the product $0.000331$ of the table alone ($0.009961$) and alpha-beta alone ($0.033271$). With centre and corners first it was $17.139045$ times (Section 3).
Fourth, most values left in the alpha-beta table are not exact: in the alpha-beta table with rotations and reflections merged, the share of positions with an exact value was $\mathbf{0.294821}$ in index order and $0.338235$ with centre and corners first; the rest were upper or lower bounds cut by the window (Section 4).
Fifth, the separator is whether the table holds the value of a position itself or upper and lower bounds cut by the window: the minimax table held only values themselves, and a second meeting was always settled from it. The alpha-beta table held bounds per window, and the factor of alpha-beta with a table over alpha-beta without ($0.147565$) did not reach the factor for minimax ($0.009961$) (Section 5).
Keywords: transposition table, alpha-beta search, minimax, tic-tac-toe, search, pruning.
Scope (what is not claimed)
No new theorem or law is claimed: minimax, alpha-beta pruning, transposition tables that keep position values, storing values with upper- and lower-bound flags under alpha-beta, and that tic-tac-toe is a draw, are all known in search. A small game only: only reading tic-tac-toe from the empty board to the end is treated; depth limits, evaluation functions, games on larger boards and the speed of real programs are not. Two move orders only: only index order and centre-and-corners-first are compared, and re-ordering by shallow searches (Paper 951) is not combined. Reasons are not separated: why the two savings do not multiply is not measured term by term. Only expanded positions and the kinds of values left in the table are set out. Relation to earlier papers: Paper 926, in its scope note, did not treat real game programs, leaving out evaluation functions, iterative deepening, transposition tables and move-ordering heuristics themselves, and Paper 951, in its scope note, also did not include other heuristics, leaving out reuse of identical positions (transposition tables); this paper sits in the seat of transposition tables (no earlier occupant; Paper 951 sat in the iterative-deepening and move-ordering seat of the scope note of Paper 926). Paper 607 showed that how often the first player wins at tic-tac-toe splits three ways by what is taken as equal, counting 5478 reachable positions (765 merged) and that the best-play value is a draw. Here the same set of positions is counted by how much search expands. What is added: counting expanded positions for six ways of reading and two move orders, confirming that the table size equals the number of reachable positions, comparing the product of the two savings with the combined factor, giving the share of exact values in the alpha-beta table, and placing the separator on “the value itself, or upper and lower bounds”.
1. Notation and the Question
Game and values: from the empty board of tic-tac-toe, the value for the side to move (win $1$, draw $0$, loss $-1$) is found by reading to the end.
Six ways of reading: minimax (read everything); minimax with a transposition table (keyed by the board, settling a second meeting from the table); the same with the 8 rotations and reflections merged in the key; alpha-beta (cutting branches with a window $[\alpha,\beta]$); alpha-beta with a transposition table (keeping a value read as an upper bound if below the window, a lower bound if above, exact if inside, narrowing the window by stored bounds and settling from the table when the window closes); and the same with the 8 symmetries merged. Two move orders: index order (top left to bottom right) and centre, corners, edges. Expanded positions are those entered to examine children rather than settled from the table.
Question: how much does a transposition table cut expansions under minimax and under alpha-beta, and do the savings multiply when stacked?
2. Minimax and the Transposition Table
Computation 2.1: $5478$ positions are reachable from the empty board, $765$ with rotations and reflections merged (as in Paper 607).
| reading | expanded positions | settled from table | table size |
|---|---|---|---|
| minimax | $549946$ | $0$ | none |
| minimax with table | $5478$ | $10690$ | $5478$ |
| same, symmetries merged | $765$ | $1506$ | $765$ |
The minimax count was the same for both move orders. The table size equalled the number of reachable positions, and the merged table the merged number. All values were $0$.
3. Alpha-Beta and the Transposition Table
Computation 3.1: expanded positions (settled from table in parentheses).
| reading | index order | centre and corners first |
|---|---|---|
| alpha-beta | $18297$ | $7275$ |
| alpha-beta with table | $2700$ ($2077$) | $1242$ ($739$) |
| same, symmetries merged | $599$ ($486$) | $285$ ($187$) |
Computation 3.2: comparison of factors.
| factor | index order | centre and corners first |
|---|---|---|
| table (under minimax) | $0.009961$ | $0.009961$ |
| table (under alpha-beta) | $\mathbf{0.147565}$ | $0.170722$ |
| alpha-beta (without table) | $0.033271$ | $0.013229$ |
| alpha-beta (with table) | $0.492881$ | $0.226725$ |
| both (against minimax) | $0.004910$ | $0.002258$ |
| product of table and alpha-beta factors | $0.000331$ | $0.000132$ |
| both over product | $\mathbf{14.814326}$ | $17.139045$ |
Observation 3.3 the two savings do not multiply. The table cut minimax to $0.009961$, but alpha-beta only to $0.147565$ ($0.170722$ with centre and corners first): conversely, alpha-beta cut $0.033271$ without a table but only $0.492881$ with one. In both move orders the combined factor exceeded ten times the product.
4. Values Left in the Table
Computation 4.1: the alpha-beta table with rotations and reflections merged had $502$ entries in index order and $272$ with centre and corners first, of which $148$ ($0.294821$) and $92$ ($0.338235$) had exact values. Expanded positions over reachable positions were $0.492881$ for alpha-beta with table in index order, and $0.783007$ with symmetries merged.
Observation 4.2 much of the alpha-beta table held bounds cut by the window. Only exact values can be used with any window met next: an upper or lower bound was usable only when the next window lay beyond that bound; otherwise the position was expanded again.
5. The Separator
Observation 5.1 the separator is whether the table holds the value of a position itself or upper and lower bounds cut by the window. Minimax has no window, so its table held only values themselves, and a second meeting was always settled ($10690$ times settled from the table): alpha-beta cuts outside the window, so much of its table held bounds, and the table’s effect stopped at $0.147565$. Why the two savings do not multiply was not measured term by term.
Observation 5.2 what is not said. Depth limits, evaluation functions, games on larger boards, combination with re-ordering by shallow searches, table size limits and replacement, and the speed of real programs are not treated. What is shown is what happens to the savings of a transposition table and alpha-beta when stacked, in a small game that can be read to the end.
6. Roll Call and Closing
- six ways of reading and two move orders (Section 1): all values are draws.
- the table cuts minimax to $\mathbf{0.009961}$ (Computation 2.1): down to the reachable positions.
- added to alpha-beta, $\mathbf{0.147565}$ (Computation 3.2): a weaker effect.
- both over product $\mathbf{14.814326}$ (Computation 3.2): no multiplication.
- share of exact values $\mathbf{0.294821}$ (Computation 4.1): the rest are bounds.
- value itself, or upper and lower bounds (Observation 5.1): the separator; the scope notes of Paper 926 and Paper 951.
Closing: Stacking a transposition table on alpha-beta in tic-tac-toe does not multiply the savings. Reading from the empty board to the end, the table cut minimax expansions from $549946$ to $5478$ ($0.009961$), but cut alpha-beta in index order only to $0.147565$: the combined factor $0.004910$ was $14.814326$ times the product $0.000331$ of the two, and the share of exact values in the alpha-beta table was $0.294821$. The separator is whether the table holds the value of a position itself or upper and lower bounds cut by the window. Placed among the earlier papers: to the alpha-beta leaves Paper 926 and Paper 951 counted by move order, the transposition table neither treated was added, and the set of positions Paper 607 counted was counted from the side of search. To be honest. This counts expanded positions in one small game that can be read to the end. What happens to the savings when a transposition table and alpha-beta are stacked, and no further.
References
- Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence.
- Yamagishi, Y. (2026). How Often the First Player Wins at Tic-Tac-Toe Splits Three Ways by What Is Taken as Equal [Paper 607]. YOI: https://www.yamagishiyuuki.com/yoi/607; DOI: 10.5281/zenodo.23014454
- 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
- Yamagishi, Y. (2026). Re-searching from Shallow Depths to Order Moves Saves Leaves Only When Shallow Values Track Deep Ones [Paper 951]. YOI: https://www.yamagishiyuuki.com/yoi/951
Reference
Yamagishi, Y. (2026). Stacking a Transposition Table on Alpha-Beta in Tic-Tac-Toe Does Not Multiply the Savings [Paper 989]. YOI: https://www.yamagishiyuuki.com/yoi/989
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 989. This paper is a preprint and has not been peer reviewed.