Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文989 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/989 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月17日 15:20 に公開します）。

@misc{yamagishi2026yoi989,
  author = {Yamagishi, Yuuki},
  title = {Stacking a Transposition Table on Alpha-Beta in Tic-Tac-Toe Does Not Multiply the Savings},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/989},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969451・969456・969461・969490 に記録されました（2026年10月01日 23:00（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

αβ 探索が読む葉の数は、子を並べる順しだいで全部の八割余りから平方根の桁まで動く（論文926）。そこでは、同じ局面の値を表に残して使い回す置換表を扱わなかった。本稿は、三目並べの空の盤から、ミニマックスと αβ のそれぞれに置換表を足し、展開した局面の数を、手の並べ方二通りで数える。新しい定理も法則も主張しない。

第一に、置換表はミニマックスの展開を届く局面の数まで減らす。ミニマックスは $549946$ 局面を展開し、置換表を足すと $5478$ 局面（$\mathbf{0.009961}$ 倍）で、空の盤から届く局面の数と一致した（第2節）。

第二に、αβ に足すと、置換表の効きは弱い。番号順に手を並べた αβ は $18297$ 局面、置換表を足すと $2700$ 局面で、効きは $\mathbf{0.147565}$ 倍だった。中央と角を先にすると $7275$ から $1242$（$0.170722$ 倍）だった（第3節）。

第三に、両方の倍率は、二つの倍率の積よりずっと大きい。番号順で、αβ と置換表の両方の倍率 $0.004910$ は、置換表だけ（$0.009961$）と αβ だけ（$0.033271$）の積 $0.000331$ の $\mathbf{14.814326}$ 倍だった。中央と角が先では $17.139045$ 倍だった（第3節）。

第四に、αβ の表に残る値の多くは確定していない。回転と裏返しをまとめた αβ＋置換表の表のうち、値が確定した局面は番号順で $\mathbf{0.294821}$、中央と角が先で $0.338235$ の割合で、残りは窓で切った上限か下限だった（第4節）。

第五に、分離子は、表に残るのが局面の値そのものか、窓で切った上限と下限か。ミニマックスの表はすべて値そのもので、二度目に出会えば必ず使い回せた。αβ の表は窓ごとの限りで、置換表なしの αβ に対する αβ＋置換表の倍率（$0.147565$）は、ミニマックスでの倍率（$0.009961$）に届かなかった（第5節）。

キーワード：置換表、αβ 探索、ミニマックス、三目並べ、探索、枝刈り

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

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/989/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/989 はいつも最新の版を指します）。

YOI の一覧へ