Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

αβ 探索は、互いに最善を尽くす読みの値を変えずに、読まなくてよい枝を切り落とす。本稿は、分岐と深さの決まった一様な木に乱数の葉の値を置き、子を最良の順・乱数の順・最悪の順に並べたときに αβ が読む葉の数を、五つの大きさで十本ずつ数える。新しい定理も法則も主張しない。

第一に、根の値は並べる順によらない。三つの並べ方とも、根の値は全部を読んだミニマックスの値と一致した（第2節）。

第二に、最良の順では、読む葉はクヌースとムーアの式にちょうど一致する。分岐 $8$・深さ $6$ の $262144$ 枚の葉のうち読むのは $\mathbf{1023}$ 枚で、五つの大きさすべて十本とも、式の値（$53$・$127$・$251$・$127$・$1023$）と一致した（第2節）。

第三に、乱数の順では、その間に入る。分岐 $8$・深さ $6$ で平均 $\mathbf{21296.7}$ 枚、分岐を底にした対数を深さで割ると $0.798797$ から $0.834560$ だった（第3節）。

第四に、最悪の順でも、全部を読むとは限らないが、八割余りを読む。読む葉の割合は五つの大きさの最小で $0.857339$・$0.834473$・$0.883873$・$0.941406$・$\mathbf{0.816006}$ だった。最良・乱数・最悪の順は五つの大きさすべてで入れ替わらなかった（第3節）。

第五に、分離子は、並べる順が子の本当の値を知っているかである。本当の値の順に並べれば読む葉は平方根の桁まで減り、知らなければ乱数の間に、逆に並べれば八割余りに戻る。切り落とせる量を決めるのは探索の手順ではなく、並べる順に入っている知識である（第4節）。

キーワード：αβ探索、ミニマックス、ゲーム木、枝刈り、手の並べ方、探索の手間。

射程（何を示さないか）

新しい定理も法則も主張しない。ミニマックスの読み、αβ 探索、最良の順で読む葉の数のクヌースとムーアの式は、いずれも既知である。実際の対局プログラムを扱わない。評価関数、反復深化、置換表、手の並べ方の工夫そのものは扱わない。子の本当の値を知っている場合と知らない場合を置いて数えるだけである。一様な木に限る。分岐と深さが決まり、葉の値が互いに独立な乱数の実数である木だけを数える。極限を主張しない。乱数の順での葉の数の指数が大きい木でどこに近づくかは主張しない。有限の五つの大きさの実測を並べるだけである。既刊との関係：論文886 の射程注記は、強いプログラムには入らず、読みを速くする工夫や評価の作り方は扱わないと書いた。本稿はその読みを速くする工夫の席に座る（先客なし）。論文873 は、探し方の優劣がある時点の損ではなく損の伸び方で決まることを示した。ここでは、同じ値を返す探し方の手間が、木の大きさとともにどう伸びるかを並べる順ごとに数える。加えたのは、三つの並べ方で根の値が変わらないことを確かめたこと、最良の順の葉の数が五つの大きさでクヌースとムーアの式に一致することを示したこと、乱数の順の平均と指数を並べたこと、最悪の順でも八割余りしか読まないことを実測したこと、分離子を「並べる順が子の本当の値を知っているか」に置いたことである。

1. 記法と問い

設定：分岐 $b$・深さ $d$ の一様な木で、根は最大を取る手番、次の段は最小を取る手番とし、以下交互とする。葉 $b^d$ 枚に一様な乱数の実数を置き、ミニマックスで全部の節の本当の値を出しておく。αβ 探索で子を並べる順を三つ置く。

$$\text{最良の順：本当の値の良い順},\qquad \text{乱数の順},\qquad \text{最悪の順：本当の値の悪い順}$$

最良の順で読む葉の数について、クヌースとムーアの式は次のとおりである。

$$N_{\min}=b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1$$

検算では、五つの大きさで木を十本ずつ作り、読んだ葉の数を数えた。

問い：αβ 探索が読む葉の数は、何で決まるか。

2. 根の値と最良の順

計算 2.1：読んだ葉の数（最良と最悪は十本の最小〜最大、乱数は十本の平均）。

三つの並べ方とも根の値はミニマックスの値と一致し、最良の順の葉の数は五つの大きさの十本すべてで式 $N_{\min}$ に一致した。

観察 2.2　最良の順では、読む葉は葉の総数の平方根の桁まで減る。$b=8$・$d=6$ では $262144$ 枚のうち $1023$ 枚で、$b^{d/2}=512$ の二倍に一枚足りない。根の値を確かめるには、一方の手番の最善の手の下で相手の全部の手を、相手の最善の手の下で一方の一手だけを読めばよいからである。

3. 乱数の順と最悪の順

計算 3.1：乱数の順の葉の数の平均を、分岐を底にした対数にして深さで割ると $0.817280$・$0.828787$・$0.830360$・$0.834560$・$0.798797$ だった。最悪の順で読む葉の割合（十本の最小）は $0.857339$・$0.834473$・$0.883873$・$0.941406$・$\mathbf{0.816006}$ だった。

観察 3.2　最悪の順でも、全部は読まないが、八割余りを読む。逆の順に並べても、探索の途中で上限が下限以下になって枝が切られる場面が残る。最良 < 乱数 < 最悪 の順は五つの大きさすべてで入れ替わらず、乱数の順の指数は $0.8$ の近くにあった。

4. 分離子

観察 4.1　分離子は、並べる順が子の本当の値を知っているかである。探索の手順も返す値も三つの並べ方で同じで、違うのは子を並べる順だけである。本当の値を知って並べると平方根の桁まで減り、知らずに並べると乱数の間に、逆に並べると八割余りに戻る。切り落とせる量は、並べる順に入っている知識の量で決まる。

観察 4.2　言わないこと。評価関数、反復深化、置換表、実際の対局での強さ、乱数の順の指数の極限は扱わない。示したのは、同じ値を返す αβ 探索の手間が、子を並べる順で全部の八割余りから平方根の桁まで動くことである。

5. 点呼と結び

1. $N_{\min}=b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1$（第1節）：クヌースとムーア。
2. 根の値は三つの順で同じ（計算 2.1）：ミニマックスと一致。
3. 最良の順で $\mathbf{1023}$ 枚（計算 2.1）：式に一致。
4. 乱数の順で平均 $\mathbf{21296.7}$ 枚（計算 2.1）：その間。
5. 最悪の順で最小 $\mathbf{0.816006}$（計算 3.1）：八割余り。
6. 本当の値を知っているか（観察 4.1）：分離子・論文886 の射程注記・論文873。

結び：αβ 探索が読む葉の数は、子を並べる順しだいで全部の八割余りから平方根の桁まで動く。根の値はどの順でも同じで、最良の順ではクヌースとムーアの式にちょうど一致し、分岐 $8$・深さ $6$ で $262144$ 枚のうち $1023$ 枚だった。乱数の順では平均 $21296.7$ 枚、逆の順でも読む割合は最小 $0.816006$ で、全部は読まなかった。探索の手順も返す値も同じで、違うのは並べる順だけである。分離子は、並べる順が子の本当の値を知っているかである。既刊との位置：論文886 が扱わなかった読みを速くする工夫を、並べる順に入る知識として数え、論文873 の伸び方の見方で木の大きさごとの手間を並べた。正直に言えば、対局の強さは言わない。同じ値を返す読みの手間が並べる順で何倍動くか、そこまでである。

参考文献

1. Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence.
2. Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
3. 山岸勇輝 (2026). 『探し方の優劣は、ある時点の損ではなく、損の伸び方で決まる』[論文873]. YOI: https://www.yamagishiyuuki.com/yoi/873
4. 山岸勇輝 (2026). 『4×4 のオセロで最も多く返す手が最善手と重なるのは、半分をわずかに超える局面だけ』[論文886]. YOI: https://www.yamagishiyuuki.com/yoi/886

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

書誌

山岸勇輝（2026）「αβ 探索が読む葉の数は、子を並べる順しだいで全部の八割余りから平方根の桁まで動く」［論文926］. YOI: https://www.yamagishiyuuki.com/yoi/926

@misc{yamagishi2026yoi926,
  author = {Yamagishi, Yuuki},
  title = {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},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/926},
  note = {Preprint, edition 1}
}