モンテカルロ木探索 (Monte Carlo Tree Search; MCTS)

モンテカルロ木探索とは、木探索とモンテカルロ法を組み合わせたものです。

• 木探索：ゲームの現在の局面を根とする木構造を考え、可能な行動とその結果生じる局面を枝とノードとして表現し、将来の局面を探索する手法。
• モンテカルロ法：ランダムな試行を多数行い、各局面の勝率などを近似的に求める手

モンテカルロ法とは、ランダムな試行を多数行うことで、知りたい値（この場合は各局面の勝率など）の近似値を求めます。
モンテカルロ木探索では、以下の4つのステップを繰り返すことで、探索木を構築し、各局面からの勝率などの情報を収集して、最も有利な行動を選択します。

1. 選択 (Selection): 現在の局面（木の根または探索中のノード）から出発して、構築済みの探索木を、あらかじめ定められた戦略に基づいて、最も有望と思われる子ノードをたどりながら、まだ完全に展開されていない（シミュレーションが行われていない子ノードを持つ）ノード、または終局していない葉ノードまで移動します。この選択フェーズでは、「探索」（まだあまり試されていない手を試す）と「活用」（これまでの結果が良い手を優先する）のバランスを取りながらノードを選びます。
2. 展開 (Expansion): 選択されたノードが終局でない場合、そのノードから可能な行動のうち、まだ一度もシミュレーションの開始点として選ばれていない行動に対応する子ノードを一つ以上作成し、探索木に加えます。
3. シミュレーション (Simulation / Rollout): 展開された新しいノードから、ゲームの終了までランダム、あるいは簡易的な方策を用いてプレイアウト（ゲームを最後まで進めるシミュレーション）を行います。そして、そのプレイアウトの結果（勝ち負け、得点など）を得ます。
4. 逆伝播 (Backpropagation): シミュレーションで得られた結果を、プレイアウトを開始したノードから選択フェーズでたどってきた経路上の全てのノードに伝播させます。各ノードでは、そのノードを経由したシミュレーションの回数と、そこから始まったシミュレーションの結果（例：勝利数）が集計・更新されます。