モンテカルロ木探索 (G検定)

1. 定義と概要

モンテカルロ木探索とは、選択・展開・シミュレーション・逆伝播という4つの手順を1サイクルとして繰り返しながら、試行の結果に応じて有望な手の周辺に探索木を育てていく手法です。英語では Monte Carlo Tree Search、略してMCTSと呼ばれます。

探索木とは、手の候補をノード、手の選び方を枝として木の形で表した構造です。モンテカルロ木探索はこの木を少しずつ大きく育てていきます（構成要素の詳しい説明は別記事に譲ります）。

1サイクルを構成する4つの手順は、それぞれ次の役割を担っています。

手順	英語名・別名	この段階で行うこと
選択	Selection	これまでの試行結果をもとに、探索木の根（ルート）から子ノードをたどって葉ノードまで進み、次に深掘りする手を選ぶ
展開	Expansion	選ばれた葉ノードの先に新しい候補手のノードを追加し、探索木を広げる
シミュレーション	プレイアウト	追加したノードから終局まで手をランダムに進め、勝敗を確認する
逆伝播	バックプロパゲーション	シミュレーションの結果を、通ってきた経路上の各ノードにさかのぼって記録する

このサイクルを繰り返した末に、根の子ノードのうち最も試行回数の多い手、あるいは勝率の高い手が実際の一手として選ばれます。試行を重ねるほど有望な手の周辺だけが深く読まれ、木の形が偏っていくところがこの手法の特徴です。

モンテカルロ法（乱数を使った試行を大量に繰り返し、その統計から近似的な答えを求める手法。詳しい定義は別記事に譲ります）をそのまま使う場合、候補手それぞれにほぼ均等な回数のランダムな試行を割り振り、その統計だけで手を選びます。そのため、有望な手に試行を集中させる仕組みを持ちません。

この課題に対し、モンテカルロ木探索は選択の段階で統計を使いながら探索木を段階的に育て、勝率の高そうな手には多くの試行を、まだ試行回数の少ない手にも一定の機会を割り振るという工夫を加えています。この工夫により、限られた計算時間の中でも有望な手を効率よく絞り込めるようになりました。評価関数（盤面がどれだけ有利かを数値で表す関数）の設計が難しい囲碁のようなゲームでも実用的な強さを発揮する探索手法として発展した背景には、この割り振り方の違いがあります。

2. 試験対策ポイント

理解するうえで中心になるのは、選択・展開・シミュレーション・逆伝播という4つの手順の名称と、それぞれが何を行うかの対応関係です。選択は統計をもとに葉ノードまでたどる段階、展開は候補手のノードを追加する段階、シミュレーションは終局までランダムに手を進めるプレイアウトの段階、逆伝播は結果を経路上のノードに記録する段階にあたります。この4手順の対応関係は、取り違えやすい点です。

選択の段階では、これまでの勝率が高い手を優先する「活用」と、まだ試行回数が少なく評価が定まっていない手を試す「探索」という、2つの働きのバランスを取る必要があります。探索と活用のバランスとは、すでに良いとわかっている選択肢を使うか、まだ試していない選択肢を試すかという意思決定上の兼ね合いを指します。

このバランスの取り方は、UCB1（UCT、勝率の高い手を優先しつつ、試行回数が少ない手にも機会を与えるための計算指標）という指標で計算されます。勝率の高い手だけを機械的に選び続けるわけではない、というところが論点になります。

モンテカルロ法は候補手にほぼ均等に試行を割り振るのに対し、モンテカルロ木探索は試行結果に応じて探索木を段階的に育てながら有望な手に試行を集中させる点が発展形にあたります。この違いを取り違えない整理が大切です。

また、AlphaGo（モンテカルロ木探索とディープラーニングを組み合わせた、DeepMind社の囲碁AI。技術構成の詳細は別記事に譲ります）は、このモンテカルロ木探索にディープラーニングによるネットワークを組み合わせることで、シミュレーションに頼る割合を減らしつつ探索の精度を高めています。

3. 関連概念との比較・相違点

近い立ち位置にある3つの探索手法は、手をどう評価するかと、試行をどう割り振るかという2つの軸で見分けられます。

手法	手の評価の仕方	試行・探索の進め方
モンテカルロ法	ランダムな試行の統計	候補手ごとにほぼ均等な回数を割り振る
モンテカルロ木探索	ランダムな試行の統計と探索・活用のバランス	探索木を段階的に育て、有望な手に試行を偏らせる
Mini-Max法・αβ法	人手で設計した評価関数	一定の深さまで分岐を規則的に読み切る

モンテカルロ法との最大の違いは、試行の割り振り方にあります。モンテカルロ法は候補手ごとにほぼ均等な回数のランダム試行を行い、その統計だけで手を選ぶのに対し、モンテカルロ木探索は選択・展開・逆伝播という手順で探索木を段階的に育て、有望な手に試行を偏らせて割り振ります。同じ乱数を使った試行という土台を共有しながらも、木を育てて試行を集中させるかどうかが両者の分かれ目になっています。

Mini-Max法・αβ法との最大の違いは、手の評価の仕方にあります。Mini-Max法・αβ法は、あらかじめ人手で設計した評価関数を使い、一定の深さまで分岐を規則的に読み切る探索手法です。これに対しモンテカルロ木探索は評価関数を使わず、ランダムなシミュレーションの統計と探索・活用のバランスによって手を絞り込みます。盤面の価値を数式で表しにくいゲームほど、評価関数に頼らないモンテカルロ木探索の強みが生きる関係にあります。

4. ビジネス・実務での活用シナリオ

ゲーム開発の分野では、将棋・囲碁に限らず、様々なボードゲームやカードゲームのAI開発で、限られた計算時間の中で有望な手を優先的に読み進める探索エンジンとしてモンテカルロ木探索が採用されています。有望な手を優先的に読み進めることで、対局時間の制約内でも高い強さを実現できます。

ロボティクス・自動化計画の分野でも、ロボットの行動計画やタスクのスケジューリングにおいて、無数の行動の組み合わせの中から有望な行動系列を段階的に絞り込む探索手法として応用されています。行動系列を段階的に絞り込むことで、計画の探索にかかる時間を短縮できます。

Web広告や施策の予算配分では、限られた試行回数の中で複数の施策の効果を見極める意思決定が求められます。すでに成果の高い施策を優先しつつ未検証の施策にも機会を残すという考え方は、モンテカルロ木探索と同じ探索・活用のバランスにあたります。この意思決定は、多腕バンディット問題（複数の選択肢の中から、限られた試行回数で最も良い選択肢を見つけ出す意思決定の問題）として扱われます。

5. 要点まとめ

• モンテカルロ木探索は、選択・展開・シミュレーション・逆伝播という4つの手順を繰り返し、有望な手に沿って探索木を育てていく手法です。
• 選択の段階では、勝率の高い手を優先する活用と、まだ試行回数の少ない手を試す探索とのバランスをUCB1（UCT）という指標で取っています。
• モンテカルロ法が候補手にほぼ均等に試行を割り振るのに対し、モンテカルロ木探索は試行結果に応じて木を段階的に育てて試行を集中させる点が異なり、AlphaGoではこれにディープラーニングを組み合わせています。

6. 確認問題