1.1 モンテカルロ法の定義
モンテカルロ法は、乱数を用いたシミュレーションを繰り返すことで、確率的な問題に対する数値解を求める計算手法である。元々は核物理の分野で発展したが、現在では金融工学、統計学、最適化問題など幅広い領域で利用される。不確実性を内在する問題に対して、大数の法則に基づき、多くのサンプルから期待値を近似する点が特徴である。
1.2 木構造探索と決定木
木構造探索は、問題の状態空間をノード、行動をエッジとする木構造で表現し、その中から最適な経路を探索する手法である。決定木は特に、各ノードで選択肢を分岐させる形式で、ゲームやプランニング問題に頻繁に用いられる。探索の効率を高めるためには、全探索を避け、有望な枝を優先的に評価するヒューリスティクスが不可欠である。
1.3 MCTSの動作原理
モンテカルロ木探索（MCTS）は、上記二つを組み合わせ、木構造を動的に構築しながらランダムシミュレーションを適用する反復アルゴリズムである。各反復は以下の四段階を経る。
1.3.1 選択（Selection）
ルートノードから開始し、子ノードの中から最も評価の高いノードを選択基準（例：UCB1）に従って再帰的に選ぶ。選択は、木の既存部分を活用しつつ、未探索のノードも考慮する必要がある。
1.3.2 拡張（Expansion）
選択によって到達したノードが終端状態でない場合、そのノードに子ノードを一つ追加する。拡張は、可能な行動のうち未評価のものを選ぶことで、探索木を徐々に成長させる。
1.3.3 シミュレーション（Simulation）
拡張後の子ノードから、事前に定義されたポリシー（多くの場合ランダム）に従って、ゲームやタスクの終端状態に到達するまでシミュレーションを行う。結果として報酬（勝敗やスコアなど）を取得する。
1.3.4 バックプロパゲーション（Backpropagation）
シミュレーションで得られた報酬を、訪れたすべてのノードに遡って反映する。各ノードの訪問回数と累積報酬を更新することで、後の選択判断に活用する。
2.1 UCT（Upper Confidence bounds applied to Trees）
UCTは、MCTSにおける選択段階の標準的な指標である。探索と活用のバランスを理論的に保証するUCB公式を木探索に適用したもの。
2.1.1 UCB1公式
UCB1は、各行動の平均報酬に信頼区間の上限を加えた値を比較する。式は 平均報酬 + C × sqrt(ln(親の訪問回数) / 子の訪問回数) で表され、パラメータCで探索の強度を調整する。
2.1.2 探索と活用のバランス
探索は未知のノードを積極的に訪れ、活用は既知の高報酬ノードを優先する。UCB1は、訪問回数の少ないノードには大きな信頼区間を与えることで探索を促進し、訪問が増えると活用へ徐々に移行する。
2.2 改良手法
MCTSの性能を向上させるための様々な拡張が提案されている。
2.2.1 Progressive Widening
行動空間が連続的または非常に大きい場合、最初から全ての子ノードを生成せず、訪問数に応じて徐々に候補を増やす手法。計算資源を集中させる効果がある。
2.2.2 Rapid Action Value Estimation（RAVE）
シミュレーション中に出現した行動の履歴を利用し、各行動の価値を事前に推定する。特に多くの行動が類似する状況で、探索の収束を加速する。
2.2.3 並列化MCTS
複数のシミュレーションを並列実行することで、計算時間を短縮する。ルート並列化、ツリー並列化、リーフ並列化などの方式があり、大規模問題への適用が可能となる。
3.1 ゲームAI
MCTSは特にゲームAIで顕著な成果を上げてきた。
3.1.1 囲碁とAlphaGo
AlphaGoはMCTSに深層ニューラルネットワークを統合し、囲碁のプロ棋士を破った画期的なシステムである。方策ネットワークで有望な手を絞り、価値ネットワークで局面評価を行う。
3.1.2 チェスと将棋
AlphaZeroは囲碁以外の完全情報ゲームにもMCTSを適用し、チェスや将棋でも従来手法を凌駕する性能を示した。ルールのみを入力として自己対戦から学習する点が特徴。
3.1.3 コンピュータゲーム（マリオ、ポーカー）
不完全情報ゲームや複雑な環境でもMCTSは有効である。マリオのステージ攻略やポーカーにおけるブラフの認識など、多様なゲームへの応用が進んでいる。
3.2 ロボティクス
3.2.1 自動運転プランニング
自動運転車の経路計画にMCTSを利用し、不確実な交通環境の中で安全かつ効率的な行動系列をシミュレーションにより探索する。
3.2.2 ロボットアームの動作計画
高次元の関節空間における動作計画にMCTSを適用し、障害物回避や把持動作をリアルタイムに生成する研究が行われている。
3.3 自然科学と工学
3.3.1 分子設計
医薬品開発の分野で、MCTSを用いて分子構造の探索空間を効率的に探索し、所望の特性を持つ化合物を提案する手法が開発されている。
3.3.2 ネットワーク最適化
通信ネットワークのルーティングや資源配分問題にMCTSを適用し、動的な要求変動に適応する最適化手法が研究されている。
4.1 深層学習との統合
4.1.1 方策ネットワークと価値ネットワーク
MCTSのシミュレーションや選択に深層学習を組み合わせることで、ランダムシミュレーションよりも高精度な評価が可能となる。方策ネットワークは有望な行動を確率的に示し、価値ネットワークは局面の勝率を予測する。
4.1.2 AlphaZeroのアーキテクチャ
AlphaZeroは、方策ネットワークと価値ネットワークを共有した一つのニューラルネットワークで表現し、MCTSの結果を教師信号として学習する。ルールのみからトップレベルのゲームAIを実現した。
4.2 確率的文脈への拡張
4.2.1 連続行動空間への対応
行動が連続値で表現される環境では、Progressive Wideningや確率的グラフィカルモデルを組み合わせ、MCTSを連続空間に拡張する手法が提案されている。
4.2.2 部分観測環境への適応
エージェントが環境の一部しか観測できない問題では、信念状態を導入したPOMDP（部分観測マルコフ決定過程）に対するMCTSが研究されている。観測の不確実性を考慮したシミュレーションが重要となる。
5.1 計算コストとメモリ消費
MCTSは反復ごとに木構造を拡張するため、深い探索や広い行動空間では計算コストとメモリ消費が急増する。実時間制約のあるアプリケーションでは、枝刈りや近似手法との併用が必要となる。
5.2 探索空間爆発への対処
5.2.1 ドメイン知識の導入
探索空間を効果的に削減するため、問題固有のヒューリスティクスやシミュレーションポリシーを設計することが有効だが、汎用性が損なわれる可能性がある。
5.2.2 オンライン学習との組み合わせ
シミュレーション結果をオンラインで学習し、次回以降の探索に活かす手法（例：メタラーニングや転移学習）により、同じ問題に対する繰り返しの探索効率を向上させる研究が進められている。