モンテカルロ木探索とは
Monte Carlo Tree Search / MCTS
ランダムなシミュレーションの結果を用いて有望な手を評価しながら探索木を成長させる探索アルゴリズム
ひとことで言うと
ランダムなシミュレーションを繰り返して、有望な手を評価しながら探す探索方法。
概要
モンテカルロ木探索(MCTS)とは、探索木の各ノードから終局までランダムなシミュレーション(プレイアウト)を実施し、その結果に基づいて有望な手を評価しながら、探索木を選択的に成長させていく探索アルゴリズム。 選択(有望なノードを既存の統計に基づき選ぶ)、展開(新しいノードを追加する)、シミュレーション(ランダムなプレイアウトを実施する)、逆伝播(結果を経路上のノードへ反映する)の4つのステップを繰り返すことで、盤面全体を網羅的に探索せずとも有望な手を絞り込める。 囲碁や将棋のように、取りうる手の組み合わせが膨大でminimax法による全探索が難しいゲームAIで広く使われ、AlphaGoが強化学習と組み合わせて用いたことで広く知られるようになった。
背景
囲碁のように取りうる手の組み合わせが極めて多いゲームでは、探索木を網羅的に展開するminimax法的な手法が計算量的に非現実的だった。 モンテカルロ木探索は、ランダムなシミュレーションの統計的な結果を手がかりに、有望な部分木を優先的に深掘りすることで、計算資源を効率的に配分するために考案された。
歴史
2006年: Couloumが、囲碁AIにモンテカルロ木探索を適用する手法を提案し、従来のゲーム木探索を上回る性能を示す。 2016年: DeepMindのAlphaGoが、モンテカルロ木探索と深層強化学習を組み合わせ、トップ囲碁棋士に勝利し広く注目を集めた。
利点
- 盤面全体を網羅的に探索せずとも、統計的に有望な手を優先的に評価・展開できる
- 評価関数を人手で精密に設計しなくても、ランダムシミュレーションの結果から手の良し悪しを推定できる
欠点
- 十分な精度を得るには多数回のシミュレーションが必要で、計算コストが大きい
- シミュレーションの母数が少ない探索初期は、評価の信頼性が低くなりやすい
比較
- 探索木 — モンテカルロ木探索は、探索木の有望な部分を統計的に絞り込みながら探索する手法の1つ