モンテカルロ木探索（MCTS）は、意思決定プロセス、特にボードゲームをプレイするソフトウェアで使用されるヒューリスティックな木探索アルゴリズムである。これは、探索空間のランダムサンプリングに基づいて探索木を拡張し、最も有望な手に焦点を当てることでゲーム木を解決する。MCTSは2016年にニューラルネットワークと組み合わされ、それ以来、チェス、将棋、チェッカー、バックギャモン、コントラクトブリッジ、囲碁、スクラブル、クロバーなどのゲームや、ターン制ストラテジービデオゲーム、その他の領域に適用されている。
このアルゴリズムは、ゲームがランダムな手で完了するまでシミュレートされるプレイアウト（またはロールアウト）を繰り返し実行することで動作する。これらのプレイアウトの結果はゲーム木のノードに重み付けするために使用され、将来の選択をより有望な手へと導く。MCTSの各ラウンドは、選択、拡張、シミュレーション、バックプロパゲーションの4つのステップで構成される。
歴史
決定論的問題にランダムサンプリングを使用するモンテカルロ法は、1940年代にまで遡る。1987年、ブルース・エイブラムソンはミニマックス探索とランダムなゲームプレイアウトに基づく期待結果モデルを組み合わせ、三目並べや他のゲームでの有効性を実証した。1989年、W. エルテル、J. シューマン、C. ズットナーは同様の手法を自動定理証明に適用し、探索時間を改善した。1992年、B. ブリュグマンはこのアプローチを囲碁プレイプログラムで使用した。2002年、チャンらは適応多段階サンプリング（AMS）を提案し、モンテカルロ木におけるUCBベースの探索と活用を導入して、UCTの基礎を築いた。
2006年、レミ・クーロムはモンテカルロ木探索という用語を作り出し、L. コチシュとCs. セペシュヴァーリはUCT（木に適用される上限信頼境界）アルゴリズムを開発した。S. ゲリーらはプログラムMoGoにUCTを実装し、2008年までに9路盤囲碁で段位レベルに達した。2012年、Zenプログラムは19路盤でアマチュア2段のプレイヤーに勝利した。Google DeepMindのAlphaGoは、MCTSをニューラルネットワークと組み合わせて使用し、2015年にプロの人間の囲碁プレイヤーを破った最初のプログラムとなり、2016年には李世ドルを打ち負かした。
動作原理
MCTSの焦点は、ランダムサンプリングに基づいて探索木を拡張することにより、最も有望な手を分析することにある。各プレイアウトはゲームを終了までシミュレートし、その結果はノードに重み付けをして、より良い手がより頻繁に選択されるようにする。基本的な純粋モンテカルロゲーム探索は、各合法手に等しいプレイアウトを適用し、最も勝利数が多い手を選択する。
MCTSの各ラウンドは4つのステップを含む：
- 選択: ルートから開始し、リーフノードに到達するまで連続する子ノードを選択する。
- 拡張: ゲームが決着していない限り、リーフから1つ以上の子ノードを作成する。
- シミュレーション: 新しいノードからランダムなプレイアウトを完了する。
- バックプロパゲーション: 新しいノードからルートまでの経路に沿ってノード統計を更新する。
UCTアルゴリズム
UCTアルゴリズムは、上限信頼境界の式を使用して探索と活用のバランスを取る。これは、平均勝率と訪問回数が少ないノードへのボーナスに基づいて子ノードを選択し、木が有望な手に向かって拡張しながらも代替案を探索し続けることを可能にする。このアプローチはMCTSの効率性の中心である。
応用
MCTSは、ヘックス、ハバナ、アマゾンズゲーム、アリマーなどのボードゲームや、ミズ・パックマンやフェイブル・レジェンズなどのリアルタイムビデオゲームのプログラムで使用されている。また、スカート、ポーカー、マジック：ザ・ギャザリング、カタンの開拓者などの非決定論的ゲームにも適用される。ゲーム以外では、MCTSは計画問題や最適化問題でも探求されている。
意義
AlphaGoのようにMCTSと深層ニューラルネットワークを組み合わせることは、人工知能と機械学習における画期的な出来事となった。これは、ヒューリスティック探索が深層学習手法と統合され、複雑な領域で人間を超えるパフォーマンスを達成できることを実証し、その後の生成AIや他の分野の研究に影響を与えた。