Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

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

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

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

日付の証拠（OpenTimestamps）

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

書誌

要旨

αβ 探索が読む葉の数は子を並べる順で大きく変わるが、本当の値を知らなければ最良の順には並べられない。本稿は、深さ 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節）。

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

Abstract

The number of leaves alpha-beta search reads changes greatly with the order of children, but without knowing the true values one cannot use the best order.This paper compares the total leaves evaluated by iterative deepening, which re-searches from depth 1 upward and orders children by the values returned by the previous search, with a single search in random order and with the formula for the best order, on trees whose position scores are related between shallow and deep searches and on trees whose scores are not.No new theorem or law is claimed.

First, on trees where shallow and deep values are related, re-searching reads fewer leaves: when a child’s score is its parent’s score plus a random number, the total leaves of iterative deepening were $0.547664$ times those of a single random-order search for branching $4$ and depth $6$, $\mathbf{0.408755}$ times for branching $4$ and depth $8$, and $0.437245$ times for branching $6$ and depth $6$ (Section 2).

Second, on trees where they are unrelated, re-searching reads more leaves: when position scores are independent random numbers at each depth, the total leaves of iterative deepening were $1.507492$, $\mathbf{1.729632}$ and $1.378168$ times those of a single random-order search (Section 2).

Third, on related trees, the ordering at the last depth comes close to the best order: leaves read at the last depth alone were $1.829396$, $1.946184$ and $2.235112$ times the best-order formula, against $6.961942$, $15.300718$ and $13.563032$ times on unrelated trees (Section 3).

Fourth, every method gives the same root value: for all three sizes and both kinds of tree, the root values of iterative deepening, random order and best order matched full minimax, and the leaves of the best order matched the Knuth-Moore formula ($127$, $511$ and $431$) (Section 2).

Fifth, the separator is whether shallow values predict the order of moves at depth: re-searching costs the leaves of the shallow searches, but if the ordering is right, more branches are cut in the deep search and the cost is recovered. If it is not right, only the cost remains (Section 4).

Keywords: iterative deepening, alpha-beta search, move ordering, game tree, leaves read, related evaluations

版の記録

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

YOI の一覧へ