Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

αβ 探索が読む葉の数は子を並べる順で大きく変わるが、本当の値を知らなければ最良の順には並べられない。本稿は、深さ 1 から順に読み直し、前の読みで返った値の順に子を並べる反復深化が評価する葉の総数を、乱数の順で一度だけ読む場合と、最良の順の式と比べる。局面の点数が浅い読みと深い読みでつながる木と、つながらない木の二つで数える。新しい定理も法則も主張しない。

第一に、浅い読みと深い読みがつながる木では、読み直すほうが葉が少ない。局面の点数が親の点数に乱数を足したものなら、反復深化の葉の総数は、乱数の順で一度だけ読む場合の枝 $4$・深さ $6$ で $0.547664$ 倍、枝 $4$・深さ $8$ で $\mathbf{0.408755}$ 倍、枝 $6$・深さ $6$ で $0.437245$ 倍だった（第2節）。

第二に、つながらない木では、読み直すほうが葉が多い。局面の点数が深さごとに独立な乱数なら、反復深化の葉の総数は乱数の順で一度だけ読む場合の $1.507492$・$\mathbf{1.729632}$・$1.378168$ 倍だった（第2節）。

第三に、つながる木では、最後の深さの並びは最良の順に近い。最後の深さだけで読んだ葉は最良の順の式の $1.829396$・$1.946184$・$2.235112$ 倍で、つながらない木では $6.961942$・$15.300718$・$13.563032$ 倍だった（第3節）。

第四に、どの読み方も根の値は同じである。三つの大きさと二つの木のすべてで、反復深化・乱数の順・最良の順の根の値は全部を読んだ値と一致し、最良の順の葉の数はクヌース＝ムーアの式（$127$・$511$・$431$）と一致した（第2節）。

第五に、分離子は、浅い読みの値が深い読みの手の順を当てるかである。読み直しの手間は浅い読みの葉のぶん増えるが、並べ方が当たれば深い読みで切れる枝が増えて取り返す。当たらなければ手間だけが残る（第4節）。

キーワード：反復深化、αβ 探索、手の並べ方、ゲーム木、読む葉の数、評価のつながり。

射程（何を示さないか）

新しい定理も法則も主張しない。αβ 探索、最良の順で読む葉の数の式（クヌースとムーア）、深さを増やしながら読み直す反復深化、前の読みの結果で手を並べる工夫は、いずれも既知である。置いた木である。枝 $4$・深さ $6$、枝 $4$・深さ $8$、枝 $6$・深さ $6$ の三つの一様な木を、それぞれ $6$ 本ずつ乱数で作った。局面の点数の作り方は二つだけで、実在のゲームの評価には対応しない。ほかの工夫を入れない。同じ局面の使い回し（置換表）、窓を狭める読み、時間の管理は入れない。並べ方は前の読みで返った値（切られた子は上下の限り）の順だけである。速さを論じない。数えるのは評価した葉の数で、実際の時間やプログラムの強さは扱わない。既刊との関係：論文926 の射程注記は、実際の対局プログラムを扱わず、評価関数、反復深化、置換表、手の並べ方の工夫そのものは扱わないと書いた。本稿はそのうち反復深化と手の並べ方の席に座る（先客なし・置換表には入らない）。論文926 は、αβ 探索が読む葉の数が、子を並べる順しだいで全部の八割余りから平方根の桁まで動くことを示した。ここでは、本当の値を知らないまま浅い読みで並べ方を作ると、どこまで最良の順に近づけるかを数える。加えたのは、反復深化の葉の総数を乱数の順と最良の順に並べたこと、浅い読みと深い読みがつながる木とつながらない木で得と損が入れ替わることを示したこと、最後の深さだけの葉を最良の順と比べたこと、根の値の一致を確かめたこと、分離子を「浅い読みの値が深い読みの手の順を当てるか」に置いたことである。

1. 記法と問い

木：枝 $b$・深さ $d$ の一様な木。局面の点数を二通りに作る。①つながる木：子の点数は親の点数に標準正規の乱数を足したもの（浅い読みの点数と深い読みの点数がつながる）。②つながらない木：深さごとに独立な標準正規の乱数。

読み方：①乱数の順：子を乱数で並べ、深さ $d$ を一度だけ αβ で読む。②反復深化：深さ $1$・$2$・…・$d$ と読み直し、各局面で前の読みが返した値の大きい順に子を並べる（前に読まなかった局面は乱数の順）。③最良の順：全部を読んだ本当の値の順に並べて一度読む。数えるのは評価した葉の数で、反復深化はすべての深さの合計である。最良の順の葉の数はクヌース＝ムーアの式 $b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1$ になる。

問い：本当の値を知らずに浅い読みで並べ方を作ると、読み直しの手間を払ってなお、葉は減るか。

2. 読む葉の数

計算 2.1：木 $6$ 本の平均。

六つの組のすべてで、三つの読み方の根の値は全部を読んだ値と一致し、最良の順の葉の数は式と一致した。

観察 2.2　つながる木では読み直すほうが少なく、つながらない木では多い。三つの大きさのどれでも、つながる木では反復深化の総数が乱数の順で一度読むより少なかった。つながらない木では三つとも多く、枝 $4$・深さ $8$ では $1.729632$ 倍だった。同じ読み方が、木の作り方で得にも損にもなった。

3. 最後の深さの並び

計算 3.1：反復深化の最後の深さだけで評価した葉の数。

観察 3.2　つながる木では、浅い読みで作った並びが最良の順の 2 倍前後まで近づく。最後の深さだけを見ると、つながる木の葉は最良の順の $1.829396$ から $2.235112$ 倍だった。つながらない木では $6.961942$ から $15.300718$ 倍だった。

4. 分離子

観察 4.1　分離子は、浅い読みの値が深い読みの手の順を当てるかである。反復深化は、浅い深さの葉を読むぶんだけ手間が増える。つながる木では、浅い読みで作った並びで最後の深さの葉が最良の順の $1.829396$ から $2.235112$ 倍まで減り（計算 3.1）、手間を取り返した。つながらない木では並べ方が当たらず、増えた手間だけが残った。

観察 4.2　言わないこと。実際のゲームの評価がどちらの木に近いか、置換表や窓を狭める読みを入れたときの数、プログラムの速さは扱わない。示したのは、置いた二つの木で、反復深化の得と損が浅い読みと深い読みのつながりで入れ替わることである。

5. 点呼と結び

1. 二つの木と三つの読み方（第1節）：つながるか、つながらないか。
2. つながる木で乱数の順の $\mathbf{0.408755}$ 倍まで（計算 2.1）：読み直すほうが少ない。
3. つながらない木で $\mathbf{1.729632}$ 倍まで（計算 2.1）：読み直すほうが多い。
4. 最後の深さは最良の順の $1.829396$ から $2.235112$ 倍（計算 3.1）：並びが当たる。
5. 根の値と最良の順の式が一致（計算 2.1）：読み方で答は変わらない。
6. 浅い読みが手の順を当てるか（観察 4.1）：分離子・論文926 の射程注記。

結び：浅い読みから読み直して手を並べると、浅い読みが深い読みとつながる木でだけ、読む葉が減る。局面の点数が親の点数に乱数を足したものなら、反復深化の葉の総数は乱数の順で一度読む場合の $0.408755$ から $0.547664$ 倍で、最後の深さの並びは最良の順の $2$ 倍前後まで近づいた。深さごとに独立な乱数なら、反復深化は $1.378168$ から $1.729632$ 倍と、かえって多く読んだ。分離子は、浅い読みの値が深い読みの手の順を当てるかである。既刊との位置：論文926 が本当の値を知る場合と知らない場合で数えた並べ方の効き目を、浅い読みで並べ方を作る反復深化として数えた。正直に言えば、実際のゲームの評価がどちらに近いかは言わない。浅い読みが当たるかどうかで、読み直しが得にも損にもなること、そこまでである。

参考文献

1. Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence.
2. Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence.
3. 山岸勇輝 (2026). 『αβ 探索が読む葉の数は、子を並べる順しだいで全部の八割余りから平方根の桁まで動く』[論文926]. YOI: https://www.yamagishiyuuki.com/yoi/926

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

書誌

山岸勇輝（2026）「浅い読みから読み直して手を並べると、浅い読みが深い読みとつながる木でだけ、読む葉が減る」［論文951］. YOI: https://www.yamagishiyuuki.com/yoi/951

@misc{yamagishi2026yoi951,
  author = {Yamagishi, Yuuki},
  title = {Re-searching from Shallow Depths to Order Moves Saves Leaves Only When Shallow Values Track Deep Ones},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/951},
  note = {Preprint, edition 1}
}