モンテカルロ木探索とは
Monte Carlo Tree Search / MCTS
ランダムなシミュレーションの結果を用いて有望な手を評価しながら探索木を成長させる探索アルゴリズム
ひとことで言うと
ランダムなシミュレーションを繰り返して、有望な手を評価しながら探す探索方法。
概要
モンテカルロ木探索(MCTS)とは、探索木の各ノードから終局までランダムなシミュレーション(プレイアウト)を実施し、その結果に基づいて有望な手を評価しながら、探索木を選択的に成長させていく探索アルゴリズム。 選択(有望なノードを既存の統計に基づき選ぶ)、展開(新しいノードを追加する)、シミュレーション(ランダムなプレイアウトを実施する)、逆伝播(結果を経路上のノードへ反映する)の4つのステップを繰り返すことで、盤面全体を網羅的に探索せずとも有望な手を絞り込める。 囲碁や将棋のように、取りうる手の組み合わせが膨大でminimax法による全探索が難しいゲームAIで広く使われ、AlphaGoが強化学習と組み合わせて用いたことで広く知られるようになった。
背景
囲碁のように取りうる手の組み合わせが極めて多いゲームでは、探索木を網羅的に展開するminimax法的な手法が計算量的に非現実的だった。 モンテカルロ木探索は、ランダムなシミュレーションの統計的な結果を手がかりに、有望な部分木を優先的に深掘りすることで、計算資源を効率的に配分するために考案された。
歴史
2006年: Couloumが、囲碁AIにモンテカルロ木探索を適用する手法を提案し、従来のゲーム木探索を上回る性能を示す。 2016年: DeepMindのAlphaGoが、モンテカルロ木探索と深層強化学習を組み合わせ、トップ囲碁棋士に勝利し広く注目を集めた。
アーキテクチャ
探索木の各ノードは、そのノードを経由したシミュレーションの回数と勝率(平均報酬)の統計を保持する。 ノードの選択では、これまでの勝率が高いノード(活用)と、まだ十分に試していないノード(探索)のバランスを取るため、UCB1(Upper Confidence Bound)等の指標に基づいて次に展開するノードを決める。 AlphaGoでは、ランダムなプレイアウトの代わりに、ニューラルネットワークによる局面評価と組み合わせることで、探索の効率と精度を大きく高めた。
ワークフロー
選択: ルートから、UCB1等の指標が最大のノードを子孫までたどる。 展開: 未展開の子ノードを1つ追加する。 シミュレーション: 追加したノードから終局までランダム(またはネットワークによる)プレイアウトを実施する。 逆伝播: シミュレーション結果を経路上の全ノードの統計へ反映する。 探索の予算(時間・回数)が尽きるまでこれを繰り返し、最も訪問回数の多い手を選択する。
利点
- 盤面全体を網羅的に探索せずとも、統計的に有望な手を優先的に評価・展開できる
- 評価関数を人手で精密に設計しなくても、ランダムシミュレーションの結果から手の良し悪しを推定できる
- 探索を打ち切った時点でも、それまでの統計に基づく最善手を返せるためAnytimeアルゴリズムとして扱いやすい
欠点
- 十分な精度を得るには多数回のシミュレーションが必要で、計算コストが大きい
- シミュレーションの母数が少ない探索初期は、評価の信頼性が低くなりやすい
- ランダムなプレイアウトだけに頼ると、局所的に不利な手を過大評価してしまうことがある
比較
- 探索木 — モンテカルロ木探索は、探索木の有望な部分を統計的に絞り込みながら探索する手法の1つ
関連用語
よくある質問
モンテカルロ木探索はどんな場面で使われる？
囲碁・将棋のように取りうる手の組み合わせが膨大なボードゲームのAIのほか、行動の候補数が多い意思決定問題全般に応用されている。
AlphaGoでのモンテカルロ木探索の役割は？
ランダムなプレイアウトの代わりにニューラルネットワークによる局面評価・着手予測を組み合わせ、探索を効率化する中核コンポーネントとして使われた。