ISMCTSモジュール

対象: pca.search.ismcts

役割

不完全情報下の tree search を実装する。public information key で tree node を共有し、hidden state を determinization ごとに sample する。leaf は rollout せず、NN value と progress value で評価する。

モジュール一覧

モジュール	役割	実装の要点
config.py	config / protocol	ISMCTSConfig, SearchApi, finish_search_session() を定義する。
tree.py	tree state	ISMCTSNode と ISMCTSTree。node cache、encode cache、node 作成/再利用を扱う。
runtime_stats.py	diagnostics	depth、stop reason、root/non-root candidate filter、Gumbel round別予算/深さ、fallback reason、prize delta、aux prize usage を記録する ISMCTSRuntimeStats。
simulation_types.py	internal dataclasses	leaf batching 用の DeferredLeafEvaluation と CompletedSimulation。
simulation.py	simulation engine	1 simulation の traversal、leaf value、backprop、deferred leaf batch、hidden clone、実験用 root-state pool を実装する。
actions.py	action selection	PUCT、candidate pruning、Dirichlet noise、visit/Q/completed-Q distribution、Gumbel root candidate scoring、option category/equivalence。
public_state.py	information set	public observation から information-set key と public-state tokens を作る。
impl.py	root orchestration	ismcts_policy() と ismcts_policy_with_hidden() の実体。hidden sampling と root decision をまとめる。
policy.py	facade	policy entrypoint の re-export。
types.py	compatibility facade	分割後の型を旧 import path から re-export する。

公開API

API	用途
ISMCTSConfig	探索回数、candidate cap、leaf batching、root selection、Dirichlet noise、value config を指定する。
ISMCTSRuntimeStats	self-play diagnostics に runtime stats を渡す。
ismcts_policy(...)	belief sampling 付き root policy。
ismcts_policy_with_hidden(...)	training-only oracle target 用 fixed-hidden search。
candidate_action_indices(...)	candidate pruning の結果を見る/テストする。
visit_distribution(...)	visit counts を policy target に変換する。
q_distribution(...)	Q / completed-Q を policy target に変換する。
leaf_value_from_decision(...)	leaf value shaping をテストする入口。

処理の流れ

1. impl.ismcts_policy() が model feature 設定で root observation を1回 encode し、同じ結果から root prior/value と action token を作る。
2. belief.sample_hidden_state() で hidden state を determinization ごとに作る。
3. config.SearchApi.search_begin() で CABT search session を開始する。
4. simulation.run_simulation() が actions.select_puct_action() で leaf まで進む。
5. simulation.leaf_value_from_decision() が NN value と progress/aux value を合成する。
6. actions.backpropagate() が path に value を戻す。
7. root selection mode に応じて、visit / Q / Gumbel sequential halving の結果から PolicyDecision を返す。

ルート行動の選択方式

Mode	Behavior
visit	既存互換。通常の PUCT simulation 後、visit distribution から選ぶ。
q_value	通常の PUCT simulation 後、root action の平均 Q から選ぶ。
gumbel_sequential_halving	root だけ Gumbel candidate selection と sequential halving を使い、非 root は既存 PUCT を使う。

gumbel_sequential_halving では、root 合法手を log(prior) + gumbel_noise で候補化し、root decision の開始時に determinizations 個だけ生成した hidden-state pool を全候補・全 round で共有する。候補ごとの simulation quota は pool に均等配分し、端数は round ごとに開始位置をずらす。これにより visit 探索と同じ determinization 条件を保ったまま round ごとに候補を半減する。

候補比較と最終選択は、同じ log(prior) + gumbel_noise に completed-Q transform を加える。未訪問 action の Q は node value と訪問済み action の prior-weighted Q から作る mixed value で補完し、訪問数に応じて Q の寄与を強める。v14 の既定は gumbel-scope: root であり、非 root は既存 PUCT を使う。gumbel-scope: tree の Gumbel bias 付き PUCT は論文の full Gumbel interior selection とは異なるため、比較実験専用とする。

completed-Q transformの実験定数はgumbel-value-scale: 0.1と gumbel-maxvisit-init: 50.0である。v14 self-play、固定benchmark、promotion評価のYAMLに明示し、Python側のdefault変更で実験条件が変わらないようにする。

leaf batching の auto は visit / Gumbel のどちらでも determinizations を基準にする。Sequential Halving で 1 候補に多数の simulation が割り当てられても、それを一つの巨大 batch にはしない。また、root 候補が 1 つしかない場合や整数除算の端数がある場合も全 simulation 予算を使い、その action の後続状態を探索する。diagnostics の visit / Q entropy と top share は、学習 target ではなく実際の root visits と訪問済み action Q から集計する。

leaf batch は item 数に加えて unique と collision を記録する。collision は同じ batch 内で同一 information-set key に到達した件数で、探索結果の選択には使わない。

--ismcts-reuse-root-states は、同じ hidden determinization の CABT root を decision 中で借用する実験オプションで、既定は無効である。Python fake API では行動、visit、Q、target、trace の同値を確認できたが、実 CABT の固定 seed smoke では search_begin の呼び出し回数を減らすと CABT 内部の乱数/state進行が変わり、action trace が一致しなかった。このため v14 YAML でも明示的に false とし、完全同値な高速化には数えない。

探索深さを比較する場合は、self-play の *.search-diagnostics.csv を使う。visit 側では avg_root_candidates_kept / avg_root_legal_actions、Gumbel 側では gumbel_round_trace に round: candidates * simulations_per_candidate -> survivors; depth を保存する。これにより、候補数、予算配分、深さのどこで差が生じたかを同一ゲーム単位で確認できる。

教師方策の生成方式

Mode	Behavior
visit	visit distribution。既存互換。
q_softmax	訪問済み root action の Q softmax。
completed_q	未訪問候補を root の平均 value で埋めた completed-Q softmax。
gumbel_q	Gumbel sequential halving の最終候補だけに Q distribution を置く。
gumbel_completed_q	全合法手に対し softmax(log(prior) + transformed_completed_Q) を使う。Gumbel noise は target に含めない。v14 実験 config の既定。

gumbel_completed_q は action selection のための sampled Gumbel と学習 target を分離する。最終生存候補が1つでも target は全合法手に分布を持ち、policy network の prior と探索後Qの両方を教師にする。

Gumbel 経路の失敗は gumbel-fallback-policy で扱う。error は例外にし、marked_fallback は通常 visit/PUCT 探索へ明示的に退避して gumbel_fallback と gumbel_failure_reason を record metadata / diagnostics に残す。

使い方

from pca.search.ismcts import ISMCTSConfig, ismcts_policy

decision = ismcts_policy(
    obs,
    your_full_deck=deck0,
    opponent_prior_deck=deck1,
    policy_fn=policy_fn,
    search_api=search_api,
    config=ISMCTSConfig(determinizations=8, simulations_per_determinization=8),
)

注意点

• types.py は互換 facade。新しい実装を読むときは config.py, tree.py, simulation.py, impl.py を優先する。
• runtime_stats.py は大きいが、統計 field と delta/snapshot の凝集クラスなので単独 module にしている。
• checkpoint policy は tree cache の EncodedObservation を直接受け取り、leaf評価での再encodeを避ける。tensor padding は decision.policy._build_policy_tensor_batch() に集約し、forward は torch.inference_mode() で行う。public PolicyDecision API は変わらない。