ADR 0002: belief 改善は Determinized UCT から始め、後に Single-Tree IS-MCTS へ移行する¶

Context¶

サンプル ipynb の MCTS は隠し情報 (相手手札・デッキ・相手の賞・自分のデッキ順) を以下の極めて粗い方法で扱っている:

これは IS-MCTS どころか Determinized UCT ですらない (1 サンプル / 1 木のみ)。コンペ Overview が「相手の手札不明が最大の課題」と明言している以上、ここを直すのは最重要レバー。

選択肢:

現状維持 (1 ワールド / 1 木) — 案 1
Determinized UCT (複数ワールド / 各々独立 MCTS 木、root visit を合算して選択) — 案 2
SO-ISMCTS / MO-ISMCTS (1 つの木のノード = 情報集合、各 simulation の冒頭でワールドを 1 つサンプル) — 案 3
Determinized から始めて IS-MCTS に進化させる段階的アプローチ — 案 4

案 4 を採用する。具体的には:

Phase 3 (S3 必達): Determinized UCT を実装。N = 8〜32 ワールドをサンプリングし、各ワールドで search_begin → 独立 MCTS 木を構築 → root の visit count を合算してから行動選択。あわせて obs.logs から 観測ベースの矛盾除外 を src/pca/belief.py に実装 (相手 discard・場のたねポケモン・進化系統の存在から相手 deck/hand 候補を絞る)。
Phase 4-5: Single-Tree IS-MCTS (SO-ISMCTS) に移行。Node を情報集合単位に変え、1 本の木を複数の determinization で共有する。MO-ISMCTS (各プレイヤー別ツリー) はその後の検討。

strategy fusion 問題: Determinized UCT は同じ情報集合の異なる world で別の最適手を選んでしまう (= プレイヤーは情報集合単位で 1 つの方針しか取れないのに、複数 world で別々の最適手を計算してしまう問題)。Cowling, Powley, Whitehouse (2012) と Dou Di Zhu での実証研究で IS-MCTS の方が一貫して品質が高い と報告されている。
実装コスト: IS-MCTS は Node を情報集合単位で管理する必要があり、サンプルコードの Node(状態単位) からの大改修になる。一方 Determinized UCT は サンプルの MCTS 実装を N 回回すだけ で実装可能で、Phase 3 で動かせる。
Phase 3 での効果検証: Determinized UCT 単体でも、ダミー固定 (1 ワールドかつ嘘の固定相手) からは大幅改善する見込み。これを ELO 計測でしっかり確認してから IS-MCTS の追加実装に進む方が、効果のあった部分を切り分けられる。
コンペ Strategy Category 用: 「Determinized から IS-MCTS へ移行した」という進化の物語自体がレポートの章立てになる。

案 1 (現状維持): 棄却。コンペ最大の課題に手を付けないことになる。
案 2 (Determinized 単独): Phase 3 採用、ただしゴールはこれではなく案 3 への通過点。
案 3 (いきなり IS-MCTS): 棄却。実装コストが高く、効果のあった改善部分を切り分けにくい。Node のリファクタが Phase 3 の他の改善 (学習 target 修正など) と衝突する。

Phase 3 で実装難度が低い手段で すぐに勝率を底上げ できる (期待値ベース)。
Phase 4-5 で IS-MCTS に移行する際、Determinized UCT 版を「比較対象」として残せるため、改善効果を数値で報告できる (Strategy Category 用)。
観測ベースの belief 絞り込み (belief.py) は Determinized でも IS-MCTS でも共通に使え、実装が無駄にならない。

Determinized で十分な効果が出てしまうと、IS-MCTS への移行モチベーションが下がり、strategy fusion による上限に気づかない可能性。Phase 4 末で必ず IS-MCTS 化の効果見積もりを行う こと。
determinization 数 N のハイパラ調整が必要。N を増やすと品質向上、計算コスト増加。Phase 0 で測った Search API レイテンシ予算から逆算する。
obs.logs ベースの矛盾除外は実装ミスがあると belief が偏る (例: 相手の場のたねポケモンを deck/hand から除き忘れる)。Phase 0-E の手動トレースで logs の挙動を完全理解してから実装する。

提出 inference 時の wall-clock は N 倍 (1 手選択あたり N 回の MCTS) になる。Phase 5 の推論最適化 (バッチ化、jit/compile) でカバー。

docs/PLAN.md Phase 3-C ロードマップ
Cowling, Powley, Whitehouse (2012) "Information Set Monte Carlo Tree Search" — IS-MCTS 原論文
Whitehouse, Powley, Cowling "Determinization and IS-MCTS for Dou Di Zhu" — 実測比較
本セッション docs/journal/2026-06-17.md
ADR 0001