Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

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

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

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

日付の証拠（OpenTimestamps）

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

書誌

要旨

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

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

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

Abstract

Alpha-beta search cuts off branches that need not be read without changing the value of play in which both sides do their best.This paper places random leaf values on uniform trees of fixed branching and depth, and counts, for five sizes and ten trees each, how many leaves alpha-beta reads when children are ordered best first, at random, and worst first.No new theorem or law is claimed.

First, the root value does not depend on the order: in all three orders, the root value matched the minimax value obtained by reading everything (Section 2).

Second, in the best order, the leaves read match the Knuth and Moore formula exactly: of $262144$ leaves at branching $8$ and depth $6$, $\mathbf{1023}$ are read, and for all ten trees of all five sizes the count matched the formula ($53$, $127$, $251$, $127$, $1023$) (Section 2).

Third, in random order, the count falls in between: at branching $8$ and depth $6$ the mean is $\mathbf{21296.7}$ leaves, and its logarithm to the base of the branching divided by depth ranged from $0.798797$ to $0.834560$ (Section 3).

Fourth, in the worst order, not everything is read, but over eight tenths is: the smallest fractions of leaves read over the five sizes were $0.857339$, $0.834473$, $0.883873$, $0.941406$ and $\mathbf{0.816006}$. The ranking of best, random and worst orders did not change for any of the five sizes (Section 3).

Fifth, the separator is whether the order knows the children’s true values: ordering by true values reduces the leaves read to the order of the square root; not knowing them gives the random count in between; reversing them returns to over eight tenths. What decides the amount cut off is not the search procedure but the knowledge contained in the order (Section 4).

Keywords: alpha-beta search, minimax, game tree, pruning, move ordering, search effort

版の記録

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

YOI の一覧へ