Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

αβ 探索が読む葉の数は、子を並べる順しだいで全部の八割余りから平方根の桁まで動く（論文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節）。

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

射程（何を示さないか）

新しい定理も法則も主張しない。ミニマックス、αβ 枝刈り、同じ局面の値を表に残す置換表、αβ では値に上限・下限の印を付けて保存すること、三目並べが引き分けであることは、いずれも探索の分野で既知である。小さなゲームに限る。三目並べの空の盤から終わりまで読むだけで、深さの限り、評価関数、大きな盤のゲーム、実戦のプログラムの速さは扱わない。並べ方を二つに限る。手を番号順に並べる場合と、中央と角を先にする場合だけを比べ、浅い読みで並べ直す工夫（論文951）とは組み合わせない。理由を分けない。二つの節約が掛け算にならない理由を、項ごとに分けて測ってはいない。展開した局面の数と、表に残った値の種類を並べるだけである。既刊との関係：論文926 の射程注記は、実際の対局プログラムを扱わず、評価関数、反復深化、置換表、手の並べ方の工夫そのものは扱わないと書き、論文951 の射程注記も、ほかの工夫を入れず、同じ局面の使い回し（置換表）は入れないと書いた。本稿はそのうち置換表の席に座る（先客なし。論文951 は論文926 の射程注記のうち反復深化と手の並べ方の席に座った）。論文607 は、三目並べで先手が勝つ割合が何を等しいと置くかで三つに分かれることを示し、届く局面 5478 通り（まとめて 765 通り）と、最善の値が引き分けであることを数えた。ここでは同じ局面の集まりを、探索がどれだけ展開するかで数える。加えたのは、六つの読み方と二つの並べ方で展開した局面を数えたこと、置換表の表の大きさが届く局面の数と一致すると確かめたこと、二つの節約の積と両方の倍率を比べたこと、αβ の表で値が確定した割合を出したこと、分離子を「値そのものか、上限と下限か」に置いたことである。

1. 記法と問い

ゲームと値：三目並べの空の盤から、手番の側から見た値（勝ち $1$・引き分け $0$・負け $-1$）を、終わりまで読んで決める。

六つの読み方：ミニマックス（全部読む）、ミニマックス＋置換表（盤の並びを鍵に値を残し、二度目は表で済ませる）、同じく回転と裏返しの 8 通りをまとめた鍵、αβ（窓 $[\alpha,\beta]$ で枝を切る）、αβ＋置換表（読んだ値が窓の下なら上限、上なら下限、中なら確定として残し、表の限りで窓を狭め、窓が閉じれば表で済ませる）、同じく 8 通りをまとめた鍵。手の並べ方は、番号順（左上から右下）と、中央・角・辺の順の二つ。展開した局面は、表で済まさずに子を調べに入った局面の数である。

問い：置換表は、ミニマックスと αβ で、展開する局面をそれぞれどれだけ減らし、二つを重ねると節約は掛け算になるか。

2. ミニマックスと置換表

計算 2.1：空の盤から届く局面は $5478$、回転と裏返しでまとめると $765$ だった（論文607 と同じ）。

ミニマックスの数は二つの並べ方で同じだった。置換表の表の大きさは届く局面の数と、対称をまとめた表はまとめた数と一致した。値はどれも $0$ だった。

3. αβ と置換表

計算 3.1：展開した局面（かっこ内は表で済んだ回数）。

計算 3.2：倍率の比べ。

観察 3.3　二つの節約は掛け算にならない。置換表はミニマックスを $0.009961$ 倍にしたが、αβ には $0.147565$ 倍（中央と角が先で $0.170722$ 倍）しか効かなかった。逆に、αβ は置換表なしで $0.033271$ 倍効いたが、置換表ありでは $0.492881$ 倍だった。どちらの並べ方でも、両方の倍率は積の 10 倍を超えた。

4. 表に残る値

計算 4.1：回転と裏返しをまとめた αβ＋置換表の表の大きさは、番号順で $502$、中央と角が先で $272$ で、値が確定した局面はそれぞれ $148$（$0.294821$）と $92$（$0.338235$）だった。展開した局面を届く局面の数で割ると、番号順の αβ＋置換表で $0.492881$、対称をまとめて $0.783007$ だった。

観察 4.2　αβ の表の多くは、窓で切った限りだった。確定した値だけが、次に出会ったどんな窓でも使える。上限か下限の値は、次の窓がその限りの外にあるときだけ使えて、そうでなければその局面をもう一度展開した。

5. 分離子

観察 5.1　分離子は、表に残るのが局面の値そのものか、窓で切った上限と下限か。ミニマックスは窓を持たないので表はすべて値そのもので、二度目に出会えば必ず済んだ（表で済んだ回数 $10690$）：αβ は窓の外を切るので、表の多くは限りになり、置換表の効きは $0.147565$ 倍にとどまった。二つの節約が掛け算にならない理由を項ごとに分けては測っていない。

観察 5.2　言わないこと。深さの限り、評価関数、大きな盤のゲーム、浅い読みで並べ直す工夫との組み合わせ、表の大きさの限りと入れ替え、実戦のプログラムの速さは扱わない。示したのは、終わりまで読める小さなゲームで、置換表と αβ の節約が重ねたときにどうなるかである。

6. 点呼と結び

1. 六つの読み方と二つの並べ方（第1節）：値はどれも引き分け。
2. 置換表でミニマックスは $\mathbf{0.009961}$ 倍（計算 2.1）：届く局面の数まで。
3. αβ に足すと $\mathbf{0.147565}$ 倍（計算 3.2）：効きが弱い。
4. 両方÷積 $\mathbf{14.814326}$（計算 3.2）：掛け算にならない。
5. 確定した値の割合 $\mathbf{0.294821}$（計算 4.1）：残りは限り。
6. 値そのものか、上限と下限か（観察 5.1）：分離子・論文926 と論文951 の射程注記。

結び：三目並べで置換表と αβ を重ねても、節約は掛け算にならない。空の盤から終わりまで読むと、置換表はミニマックスの展開を $549946$ から $5478$（$0.009961$ 倍）にしたが、番号順の αβ には $0.147565$ 倍しか効かなかった。両方の倍率 $0.004910$ は二つの積 $0.000331$ の $14.814326$ 倍で、αβ の表で値が確定した局面は $0.294821$ の割合だった。分離子は、表に残るのが局面の値そのものか、窓で切った上限と下限か。既刊との位置：論文926 と論文951 が並べ方で数えた αβ の葉に、両編が扱わなかった置換表を足し、論文607 が数えた局面の集まりを探索の側から数えた。正直に言えば、終わりまで読める小さなゲーム一つで、展開した局面を数えた。置換表と αβ を重ねると節約がどうなるか、そこまでである。

参考文献

1. Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence.
2. 山岸勇輝 (2026). 『三目並べで先手が勝つ割合は、何を等しいと置くかで三つに分かれる』[論文607]. YOI: https://www.yamagishiyuuki.com/yoi/607 ・ DOI: 10.5281/zenodo.23014454
3. 山岸勇輝 (2026). 『αβ 探索が読む葉の数は、子を並べる順しだいで全部の八割余りから平方根の桁まで動く』[論文926]. YOI: https://www.yamagishiyuuki.com/yoi/926
4. 山岸勇輝 (2026). 『浅い読みから読み直して手を並べると、浅い読みが深い読みとつながる木でだけ、読む葉が減る』[論文951]. YOI: https://www.yamagishiyuuki.com/yoi/951

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「三目並べで置換表と αβ を重ねても、節約は掛け算にならない」［論文989］. YOI: https://www.yamagishiyuuki.com/yoi/989

@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}
}