ボードゲーム「シタデル」におけるモンテカルロ木探索ベースモデルの訓練のための対戦相手モデリング

1. はじめに

モンテカルロ木探索（MCTS）は、適応性とドメイン固有知識の低使用を組み合わせ、ボードゲームにおける意思決定の効果的な手法として確立されています。その性能は、囲碁のような完全情報の決定論的ゲームで顕著です（SILVER et al., 2016）。

しかし、その応用は、複数プレイヤー、隠れた情報、時間制約のある環境では大きな限界に直面し、シミュレーションの高い計算コストと適応の難しさが応答性と決定の質を損なっています（POWLEY et al., 2014）。

この文脈では、MCTSと強化学習（RL）を統合するハイブリッドアプローチが有望であり、計画フェーズを実行から切り離すことを可能にします。検索の事前保存による永続的な決定構造の構築により、ゲーム中のアクションの瞬時選択が可能となり、オンラインシミュレーションの必要性を減らし、戦略的深みを維持します（BROWNE, 2012; SWIECHOWSKI, 2023）。

本研究では、オフライン強化学習技術を組み合わせたハイブリッドMCTSモデルをテストし、開発しました。このモデルは、ボードゲーム「シタデルズ」（FAIDUTTI, 2016）のシミュレーション環境において、異なる対戦相手を用いて訓練およびテストされました。

2. 全体的な目的

本研究の全体的な目的は、隠された情報を持つマルチプレイヤーボードゲームにおいて効率的に動作可能なハイブリッドMCTS-RLフレームワークを開発することであり、シタデルズをケーススタディとして使用します。

この提案は、永続的な決定構造のオフライン構築を通じて従来のMCTSの計算上のボトルネックを排除し、実行時に高速で堅牢なアクションを可能にすることを目指しています。

3. 方法論

本研究は、質的・量的分析を伴う応用実験研究として特徴づけられる。

最初の段階では、ボードゲーム「シタデルズ」のデジタルシミュレーション環境の開発と適応が行われた。続いて、人間プレイヤーが使用する実際の戦略を模倣するように構築された、カスタマイズされた戦略を持つ5つのエキスパートエージェントと、ランダムに行動を選択するベースラインエージェントの開発が行われた。環境と開発されたエージェントの検証後、ハイブリッドMCTS-RLフレームワークの開発が開始された。

MCTSモデルは、本質的には、複数のシミュレーションの実行を通じて動作するヒューリスティック探索アルゴリズムである。これらのシミュレーション中に訪問される個別のゲーム状態ごとに、ツリーデータ構造内に対応するノードが作成される。初期ゲーム状態は、このツリーのルートノードを表す。

しかし、木全体を保存して将来の決定に利用するという提案は、分岐因子が膨大であるため実現不可能です。これを可能にするには、木を抽象化する必要があります。ゲーム状態はその基本的な特性（例：プレイヤーの金、手札の枚数）に分割され、各特性は独立したデータテーブルにマッピングされます。

この構造では、テーブルの行は状態特性の取りうる値を表し、列はエージェントが取れる行動（例：金を得る、カードを引く）を表します。各セルには2つの値が格納されます。その状態でその行動を取った後に達成された勝利数（n）と、この組み合わせが探索された総回数（m）です。これらのテーブルは、シタデルズの試合のシミュレーションを通じてデータが蓄積され、エージェントの学習モデルを構成します。

トレーニングプロセスには強化学習の要素が含まれます。各シミュレーション試合後、結果が決定テーブルを更新し、将来の選択に影響を与えます。勝利は報酬として機能し、効果的な行動を強化して再び選択される確率を高めますが、敗北はこの可能性を減少させます。このように、多くのシミュレーションを通じて、モデルは継続的に適応し、新しい選択肢の探索と実証済み戦略の活用のバランスを取りながら、徐々により効果的な行動へと収束していきます。

4. 結果と考察

提案されたMCTSモデルの性能を評価するために、ベースライン戦略（エキスパートエージェントとランダムエージェント）間のパワーバランスを理解することが重要でした。これを達成するために、各戦略は4つの同一の対戦相手に対して10,000試合のラウンドを実施しました。

図1に示されたヒートマップは、各戦略（Y軸）が異なる対戦相手（X軸）に対してどのような性能を示すかを示しています。戦略には明確な長所と短所があります：エキスパート1、2、3はほとんどのシナリオで有能である一方、エキスパート4と5はかなり効果が低いです。予想通り、完全にランダムな戦略は、最小限の構造を持つ対戦相手に対しても非常に低い性能を示します。

図1: 戦略間の比較。

次のステップは、MCTS-RLモデルを評価することでした。各バージョンのモデルに対して、それぞれ対戦相手の1つに焦点を当てた異なるトレーニングセッションが実施され、合計100,000回のトレーニングマッチが行われました。その後、各トレーニング済みモデルのパフォーマンスが、以前と同じテストモデルに従ってすべてのタイプの対戦相手に対して、およびランダムに選ばれた多様な対戦相手に対して測定されました。

図2に示されたヒートマップは、各モデルの統合勝率を示しています。最も重要な結果は、多様な環境でトレーニングされたモデルのものであり、一貫したパフォーマンスを達成し、ほとんどすべてのテストシナリオで他のバージョンのモデルを上回りました。これは、トレーニング中に多様な戦略にさらされることが、より堅牢で汎用的なプレイ能力を開発するために重要であったことを示唆しています。

図2: トレーニング済みモデル間の比較。

エキスパート4と5（最も弱い対戦相手と見なされる）に対して訓練されたモデルは、驚くほど効果的なエージェントになった。逆に、エキスパート1と3（強い対戦相手と見なされる）に対して訓練されたモデルは、全体的なパフォーマンスが非常に低いモデルを生成した。

この対比の考えられる説明は、高度なエキスパート戦略は高度に特化される傾向があるのに対し、MCTS-RLモデルは訓練の開始時点ではランダムな動作に近いということである。強い対戦相手に対しては、潜在的に有利な行動であっても、モデルが成功のパターンを認識するのに十分な勝利をもたらさない可能性がある。一方、特化度の低い対戦相手に対しては、勝利がより頻繁に発生し、学習が促進される。それでも、これは確認が必要な仮説のままである。

5. 結論

この研究は、MCTSツリーの抽象化を使用して、手番間で獲得した知識を保持する提案手法の実現可能性を示した。結果は、モデルが環境に対して堅牢な戦略を開発できることを確認した。

多様な環境で訓練されたエージェントの優れた性能は、複数の戦術への露出が汎用モデルを構築する上で基本であることを示しています。さらに、研究は最終的なエージェントの品質が訓練相手の見かけ上の強さよりも多様性に依存することを示しています。

今後の研究として、なぜ専門化されていない戦略がより強力な戦略よりも効率的なモデルをもたらしたのか、その実際の理由をより正確に探求することが興味深いでしょう。さらに、提案モデルを他のMCTSモデルと比較することで、アプローチのより正確な評価を得るのにも役立つでしょう。