YOLOのライセンス
Ultralytics用語集に戻る

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つの段階で構成されます。

  1. 選択: ルートから始め、十分に探索されたノードをたどり、勝率の高さと試行回数の少ない手を考慮するUCTスコアが最も高い子ノードを選びます。
  2. 展開: 未試行の手がある最初のノードに、その手を新しい子ノードとして追加します。
  3. シミュレーション: 新しい子ノードからゲーム終了まで進め、従来はランダムな手を使って結果を得ます。
  4. 逆伝播: 経路を戻りながら、結果に基づいて各ノードの訪問回数と勝利数を更新します。

計算予算が尽きると、アルゴリズムはルートの子ノードのうち最も訪問回数が多いものを選びます。これは、平均値が最も高いものを選ぶより安定した選択です。

探索と活用のバランス#

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を学習しました。

ソリューションを見る

スポーツにおけるコンピュータービジョン

スポーツにおけるコンピュータービジョン

Ultralytics YOLOが、選手やボールの追跡、パフォーマンス分析、コーチングへの知見、アスリートのリハビリを通じて、スポーツビジョンをどのように支えるかをご紹介します。
詳しく見る
航空画像向けコンピュータービジョン

航空画像向けコンピュータービジョン

Ultralytics YOLOを使用して、ドローンや航空画像をリアルタイムの知見に変換し、農業、水産養殖、自然保護、地理空間分析に活用できます。
詳しく見る
航空宇宙分野のコンピュータービジョン

航空宇宙分野のコンピュータービジョン

Ultralytics YOLOを活用して航空宇宙分野でコンピュータビジョンを導入し、航空機検査、滑走路上のFOD検出、空港の地上業務、複合材の欠陥検出に活用できます。
詳しく見る
セキュリティ分野のコンピュータービジョン

セキュリティ分野のコンピュータービジョン

Ultralytics YOLOモデルであらゆる施設を保護しましょう。ビジョンAIは、周辺監視、脅威検知、ナンバープレート認識、職場の安全管理を支援します。
詳しく見る
ロボティクス分野のコンピュータービジョン

ロボティクス分野のコンピュータービジョン

Ultralytics YOLOモデルで、よりスマートなマシンを実現しましょう。ロボティクスにおけるビジョンAIは、自律ナビゲーション、認識、物体追跡、リアルタイム制御を支援します。
詳しく見る
物流におけるコンピュータービジョン

物流におけるコンピュータービジョン

Ultralytics YOLOモデルで物流を効率化しましょう。ビジョンAIにより、荷物検査、仕分け、車両追跡、倉庫のリアルタイム安全監視を実現します。
詳しく見る
小売業におけるコンピュータービジョン

小売業におけるコンピュータービジョン

Ultralytics YOLOモデルで小売のあり方を変革しましょう。ビジョンAIにより、在庫追跡、棚の監視、行列管理、より高度な顧客インサイトを実現します。
詳しく見る
医療分野におけるコンピュータービジョン

医療分野におけるコンピュータービジョン

Ultralytics YOLOモデルで医療ソリューションを構築しましょう。医療分野のビジョンAIは、医用画像処理の高速化、より高度な診断、患者モニタリングを実現します。
詳しく見る
製造業におけるコンピュータービジョン

製造業におけるコンピュータービジョン

Ultralytics YOLOモデルで製造を最適化しましょう。ビジョンAIは、品質管理、欠陥検出、PPE準拠、組立ラインの自動化を推進します。
詳しく見る
自動車分野におけるコンピュータービジョン

自動車分野におけるコンピュータービジョン

Ultralytics YOLOモデルで自動車分野にコンピュータービジョンを導入しましょう。ビジョンAIは、道路の安全性、運転支援、車両の自動化を向上させ、よりスマートな道路を実現します。
詳しく見る
農業におけるコンピュータービジョン

農業におけるコンピュータービジョン

Ultralytics YOLOモデルでスマート農業にビジョンAIを導入しましょう。作物のモニタリング、家畜の追跡、精密農業を支援し、より高く効率的な収量を実現します。
詳しく見る

AIの未来を一緒に築きましょう!

機械学習の未来に向けた歩みを始めましょう