モンテカルロ木探索（MCTS）は、意思決定プロセス、特にボードゲームをプレイするソフトウェアで使用されるヒューリスティックな木探索アルゴリズムである。これは、探索空間のランダムサンプリングに基づいて探索木を拡張し、最も有望な手に焦点を当てることでゲーム木を解決する。MCTSは2016年にニューラルネットワークと組み合わされ、それ以来、チェス、将棋、チェッカー、バックギャモン、コントラクトブリッジ、囲碁、スクラブル、クロバーなどのゲームや、ターン制ストラテジービデオゲーム、非ゲーム用途にも応用されている。
このアルゴリズムは、プレイアウト（ロールアウトとも呼ばれる）を繰り返し実行することで動作し、ゲームをランダムな手で最後までプレイする。これらのプレイアウトの結果はゲーム木のノードに重み付けするために使用され、より良いノードが将来のプレイアウトで選択される可能性が高くなる。このアプローチは、静的な評価関数を回避し、シミュレーション結果に依存する点で従来のミニマックス探索とは異なる。
歴史
決定論的問題にランダムサンプリングを使用するモンテカルロ法は、1940年代にまで遡る。1987年、ブルース・アブラムソンはミニマックス探索とランダムなゲームプレイアウトに基づく期待結果モデルを組み合わせ、三目並べ、オセロ、チェスにおけるその精度とドメイン独立性を実証した。1989年、W. エルテル、J. シューマン、C. サットナーは同様の手法を自動定理証明に適用し、非情報探索アルゴリズムを改善した。1992年、B. ブリュグマンは囲碁プログラムで初めてこのアプローチを使用した。2002年、チャンらは適応多段階サンプリング（AMS）を提案し、モンテカルロ木にUCBベースの探索と活用を導入して、UCTの基礎を築いた。
2006年、レミ・クーロムはモンテカルロ木探索という名称を考案し、L. コチシュとCs. セペシュヴァーリはUCT（木に適用される上限信頼境界）アルゴリズムを開発した。S. ジェリーらはプログラムMoGoにUCTを実装し、2008年までに9路盤囲碁で段位レベルに達した。Fuegoプログラムもその頃に9路盤囲碁で強いアマチュアを打ち負かし始めた。2012年1月、Zenプログラムは19路盤でアマチュア2段のプレイヤーに3:1で勝利した。
Google DeepMindはAlphaGoを開発し、2015年10月にハンデなしのフルサイズ盤でプロの人間の囲碁プレイヤーを破った最初のプログラムとなった。2016年3月、AlphaGoは李世ドルを4:1で破り、名誉9段のレベルを獲得した。AlphaGoはMCTSと人工ニューラルネットワーク（深層学習の手法）を組み合わせて方策と価値の評価を行い、機械学習における重要なマイルストーンとなった。
動作原理
MCTSは、探索空間のランダムサンプリングに基づいて探索木を拡張し、最も有望な手の分析に焦点を当てる。各ラウンドは4つのステップで構成される：
- 選択：ルートノード（現在のゲーム状態）から開始し、リーフノードに到達するまで連続する子ノードを選択する。選択は有望な手を優先するようにバイアスがかけられ、多くの場合UCTが使用される。
- 展開：リーフノードがゲームを終了しない限り、合法手を表す1つ以上の子ノードを作成する。
- シミュレーション：選択された子ノードからランダムなプレイアウトを完了し、ゲームが決着するまでプレイする。
- バックプロパゲーション：子ノードからルートまでのパス上のノードをプレイアウト結果で更新し、シミュレーション回数と勝利数を適切に増加させる。
引き分けのあるゲームでは、引き分けは両プレイヤーに対して分子を0.5、分母を1増加させる。これにより、各プレイヤーの選択が自身の価値を最大化する手に向かって拡張されることが保証される。
UCTアルゴリズム
2006年に導入されたUCTアルゴリズムは、木探索に上限信頼境界を適用する。これは、子ノードの平均報酬と、訪問回数が少ないノードに対するボーナスに基づいて子ノードを選択することで、探索と活用のバランスを取る。これにより、探索木は代替案を探索しながら最も有望な手に向かって拡張できる。UCTはMoGoやその後のプログラムを含むMCTS実装の標準となり、現在も広く使用されている。
応用
MCTSは、ヘックス、ハバンナ、アマゾンズゲーム、アリマアなどのボードゲームや、Ms. パックマンやフェイブル・レジェンドなどのリアルタイムビデオゲームのプログラムで使用されている。また、スカート、ポーカー、マジック：ザ・ギャザリング、カタンの開拓者などの非決定論的ゲームも扱う。ターン制ストラテジーゲームでは、トータルウォー：ローマIIが高レベルのキャンペーンAIにMCTSを使用している。ゲーム以外にも、MCTSは計画問題や最適化問題に応用されている。
MCTSとニューラルネットワークの組み合わせは、AlphaGoのように特に効果的であることが証明されている。このハイブリッドアプローチは、ニューラルネットワークを使用して選択を導き、位置を評価することで、広範なランダムプレイアウトの必要性を減らす。その後のAlphaZeroなどのプログラムはこれをチェスと将棋に拡張し、人間を超えるパフォーマンスを達成した。