探索設計
状態: crates/dl-manaka-core/src/search/ に実装済みです。
DLManaka は Gumbel AlphaZero MCTS を、対局の着手選択と自己対局用の改善方策生成の両方に使います。
Gumbel を使う理由
方策の argmax だけでは先読みがありません。一方、通常の PUCT では訪問回数を有効な学習目標にするまで大きな探索量が必要になりやすいです。Gumbel AlphaZero は少ないシミュレーション数でも方策改善の教師信号を作れるよう設計されています。
実装は Danihelka et al., Policy Improvement by Planning with Gumbel（ICLR 2022）を基にし、DeepMind の mctx と照合しています。
基本量
探索ノードは方策ロジット、ネットワーク価値、辺の統計を持ちます。価値の視点は明示し、バックアップでは通過した辺ごとに 1 回符号を反転します。
探索結果は次で方策ロジットに混ぜます。
sigma(q) = (c_visit + max_b N(b)) * c_scale * q現在は c_visit = 50、c_scale = 1.0、最小・最大値での再スケーリングなしです。
未訪問手の Q は、ノードの生の価値と訪問済み手の 事前分布で重み付けした Q から 補完 Q（completed Q） を作って埋めます。訪問 0 なら生のネットワーク価値へ戻ります。訪問済み手の事前確率の総和が 0 になった場合は、0 除算を避けるため単純平均へ切り替えます。
ルート選択
Gumbelノイズは探索開始時に合法手ごとに 1 回だけ生成し、その探索中は使い回します。
ルートのスコアは
gumbel + logit + sigma(Q)で、Sequential Halving の訪問スケジュールと組み合わせます。候補集合を別に持たず、訪問回数の条件で候補除外を表現します。
歴史的な既定値:
simulations = 32
max_considered = 16
c_visit = 50
c_scale = 1本番・自己対局設定では上書きできるため、この既定値をそのまま測定条件として扱わないでください。
ルートより下
ルート以外の選択は決定的です。logit + sigma(completedQ) が作る改善方策に対し、目標割合より訪問数が不足している手を優先します。
Gumbel の乱数はルートだけで使います。
最終着手と学習目標
学習目標は合法手上の
improved_policy = softmax(logit + sigma(completedQ))です。
訪問回数の softmax ではありません。 通常の AlphaZero 型訪問回数を使う教師信号に置き換えると、学習アルゴリズム自体が変わります。
実際の着手は、訪問数が最大のルート手から同じルートスコアで選びます。そのため argmax(improved_policy) と一致する保証はありません。
root_value は改善方策下の期待価値と定義します。探索前のネットワーク評価は root_v_hat として別に保持します。
バッチ探索
batched.rs は複数の探索経路をまとめ、葉を 1 回の GPU 呼び出しで評価します。複数経路が同じ葉へ到達した場合、その葉は 1 回だけ評価し、結果を各経路へ バックアップ します。
重要な不変条件は 2 つです。
batch_size = 1は逐次探索と完全一致すること。- バッチ幅を シミュレーション数と独立に増やさないこと。大きすぎるバッチでは同じ待機中の葉への衝突が増え、推論単体が速くなってもノード数や PV の深さが減ることがあります。
葉が評価待ちの間は仮想損失を入れ、後続経路を他の枝へ分散させます。同一局面の再訪のネットワーク出力は再利用できますが、木と訪問統計はノードごとに保持します。
ルール処理
- ルートの 1 手詰め: MCTS 前に厳密確認し、見つかればネットワークを呼ばず返す。
- 終端の葉: 合法手なしなら詰み。手番側の価値は
-1。 - 千日手: 各探索ノードではなく対局ループで処理する。
- 深さ上限: メモリ・時間の安全上限であり、千日手検出ではない。
- 入玉宣言: 探索内では現在未対応。
USI での動作
dl-manaka-usi は シミュレーション数、バッチ幅、仮想損失、方策のみ などの探索オプションを公開します。go depth / go nodes / go movetime は対局探索の打ち切り条件として使えます。
自己対局の教師生成では、事前計算した Sequential Halving の探索量を最後まで使います。途中で打ち切ると改善方策に偏りが入るためです。
評価対局では gumbel_scale = 0。自己対局では 0 以外にし、ルート候補に多様性を持たせます。
btime / wtime / byoyomi から一般的な時間配分を決める仕組みはまだなく、stop も探索を即時中断する仕組みにはなっていません。
コード構成
| ファイル | 役割 |
|---|---|
gumbel.rs | sigma、補完 Q、選択規則 |
halving.rs | Sequential Halving のスケジュール |
tree.rs | ノード、辺、バックアップ |
sequential.rs | 逐次探索 |
batched.rs | バッチ探索・評価 |
result.rs | 共通結果の組み立て |
検証
実装を間違えやすい箇所をテストしています。
- 複数辺を通るバックアップの符号反転
- 手計算した completed Q
- 方策が嫌う手でもルートの 1 手詰めを返すこと
- 数百シミュレーションでの数値安定性
- バッチ 1 と逐次探索の一致
- 1 手先読みで方策の悪手を除外できる回帰局面