Monte Carlo Tree Search (MCTS)
モンテカルロ木探索(MCTS)は、シミュレーションによるプレイアウトから探索木を拡張し、有望な手に重点を置いて行動を選びます。AlphaGoやロボットで使用されています。
モンテカルロ木探索 (MCTS) は、多数のシミュレーションを通じて起こり得る未来の木を展開し、最も有望に見える手により多くの計算予算を割り当てて、次の行動を選ぶ計画アルゴリズムです。ゲームのルールやシミュレーターなど、合法手と結果を生成する方法だけが必要で、手作業で作成した評価関数は必要ありません。また、任意の時点で停止してもそれまでに見つけた最善手を返し、時間をかけるほど回答が改善する anytime アルゴリズムでもあります。Rémi Coulomは2006年にこの手法を命名し、同じ年にLevente KocsisとCsaba Szepesváriが、標準的な形式となった選択規則UCTを発表しました。MCTSは数年のうちにコンピューター囲碁を大きく進歩させ、その後AlphaGoやAlphaZeroを支え、現在ではロボットや車両の動作計画、および大規模言語モデル (LLMs)における推論ステップの探索に使われています。
MCTSの仕組み#
探索では、現在の局面をルートとし、各ノードに訪問回数と、その訪問が勝利につながった回数を記録する木を維持します。各反復は4つの段階で構成されます。
- 選択: ルートから始め、十分に探索されたノードをたどり、勝率の高さと試行回数の少ない手を考慮するUCTスコアが最も高い子ノードを選びます。
- 展開: 未試行の手がある最初のノードに、その手を新しい子ノードとして追加します。
- シミュレーション: 新しい子ノードからゲーム終了まで進め、従来はランダムな手を使って結果を得ます。
- 逆伝播: 経路を戻りながら、結果に基づいて各ノードの訪問回数と勝利数を更新します。
計算予算が尽きると、アルゴリズムはルートの子ノードのうち最も訪問回数が多いものを選びます。これは、平均値が最も高いものを選ぶより安定した選択です。
探索と活用のバランス#
UCTは各ノードでの選択を多腕バンディット問題として扱い、UCB1の式を適用します。子ノードのスコアは、勝率w/nにc·√(ln N / n)を加えた値です。nは子ノードの訪問回数、Nは親ノードの訪問回数、cは探索定数で、理論上は√2ですが、実際には調整されます。手が試される回数が増えるほど第2項は小さくなるため、数回の幸運な勝利だけで他の手が無視されることはなく、見過ごされた手もいずれ再検討されます。
このPythonの例では、小さなゲームでMCTSを実行します。プレイヤーは山から石を1~3個取り、最後の石を取った人が勝ちます。
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")石を2個取る手は、2,000回の訪問のうち1,889回を占め、シミュレーションの91%で勝ちます。一方、石を1個取る手は68回、3個取る手は43回です。これが勝ち筋です。石を8個、つまり4の倍数残すと、先手は相手のどの返答に対しても、山が空になるまで再び4の倍数に戻せます。探索は戦略をコードに記述することなく、ランダムなプレイアウトと訪問統計だけから勝ち筋を見つけました。
AlphaGoからAlphaZero、MuZeroへ#
囲碁の平均分岐数は合法手が約250通りで、チェスの約35通りを大きく上回るため、全探索は困難です。2000年代後半以降、MCTSがコンピューター囲碁の実力向上を牽引しました。DeepMindのAlphaGoは、候補手を提案する方策ネットワークと、局面を評価する価値ネットワークおよび高速なプレイアウトの両方を用いてMCTSを導き、2016年3月に李世乭に4勝1敗で勝利しました。AlphaZeroとMuZeroはさらに進化しました。AlphaZeroはプレイアウトを完全に廃止し、価値ネットワークで葉ノードの局面を評価しました。また、自己対局で得たゲームを使ってそのネットワークを学習させ、各探索の訪問回数を方策ネットワークの目標値として用いました。これにより、MCTSは強化学習内部の方策改善ステップとなります。MuZeroは学習した環境モデルの中で同じ探索を実行するため、ルールを与えられずに囲碁、チェス、将棋、Atariのゲームをプレイできました。
計画と推論におけるMCTS#
ロボットや自動運転車は、合流のような不確実な状況での計画にMCTSを使います。POMCPなどの変種は、隠れた状態に関する信念を追跡することで、部分観測のマルコフ決定過程にも適用できます。カメラ入力から計画する探索では、ルートとなる状態が必要です。たとえば、チェスを指すロボットアームは、盤面画像で学習したUltralytics YOLO26モデルを使ってすべての駒の位置を特定でき、復元された局面を探索のルートにできます。
LLMの推論では、各ノードが部分解、各エッジが推論ステップを表し、プロセス報酬モデルまたは回答の検証によって各分岐を採点します。MicrosoftのrStar-Mathは、プロセス選好モデルを用いたMCTSにより、MATHベンチマークでQwen2.5-Math-7Bのスコアを58.8%から90.0%に向上させました。思考の木では、代わりに幅優先探索または深さ優先探索を使って推論ステップを探索します。学習時のMCTSの利用はより困難でした。DeepSeekはDeepSeek-R1に向けた失敗した試みの一つとしてMCTSを挙げています。トークン列の空間はボードゲームよりはるかに広く、探索を導く価値モデルの学習も困難なためです。その代わりに、検証可能な報酬を用いた強化学習でR1を学習しました。










