获取 YOLO 许可
返回 Ultralytics 术语表

Monte Carlo Tree Search (MCTS)

蒙特卡洛树搜索 (MCTS) 通过模拟推演扩展搜索树,并聚焦于有希望的行动来选择动作。它应用于 AlphaGo 和机器人。

蒙特卡洛树搜索(MCTS)是一种规划算法:它通过多次模拟推演,逐步构建可能未来的搜索树,并将更多计算预算花在看起来最有希望的走法上,从而选择下一步行动。它只需要一种生成合法走法和结果的方法,例如游戏规则或模拟器,而不需要手工编写评估函数。它也是一种随时可终止的算法:无论何时停止,都会返回目前找到的最佳走法;投入更多时间则会得到更好的答案。Rémi Coulom 于 2006 年为该方法命名;同年,Levente Kocsis 和 Csaba Szepesvári 发表了 UCT,即后来成为该方法标准形式的选择规则。短短几年内,MCTS 就改变了计算机围棋;之后它为 AlphaGo 和 AlphaZero 提供了动力,如今还用于规划机器人和车辆的行为,以及在推理步骤中进行搜索,以应用于大型语言模型(LLM)。

MCTS 的工作原理#

搜索过程维护一棵树,树根是当前局面,每个节点记录访问次数以及这些访问中获胜的次数。每次迭代分为四个阶段:

  1. 选择: 从树根开始,沿着已充分探索的节点向下搜索,选择 UCT 分数最高的子节点;该分数会平衡较高的胜率与较少尝试的走法。
  2. 扩展: 在第一个存在未尝试走法的节点上,将该走法添加为新的子节点。
  3. 模拟: 从新子节点开始一直模拟到游戏结束;传统做法是随机走子,以获得结果。
  4. 反向传播: 沿路径向上回溯,并根据结果更新每个节点的访问次数和获胜总数。

预算耗尽时,算法会选择树根下访问次数最多的子节点;与选择平均得分最高的节点相比,这种选择更稳定。

平衡探索与利用#

UCT 将每个节点上的选择视为一个多臂老虎机问题,并使用 UCB1 公式:子节点的分数等于其胜率 w/n 加上 c·√(ln N / n),其中 n 是子节点的访问次数,N 是其父节点的访问次数,c 是探索常数;理论值为 √2,实际中会进行调优。随着某种走法被尝试得越来越多,第二项会逐渐减小,因此某个走法不会仅凭几次幸运获胜就挤掉其他走法;而被忽视的走法最终也会再次得到尝试。

下面这个 Python 示例在一个小游戏中运行 MCTS:玩家每次从一堆 10 颗石子中取走 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,000 次访问中的 1,889 次,并在 91% 的模拟中获胜;相比之下,取走一颗和三颗分别获得 68 次和 43 次访问。这是获胜走法:留下 8 颗(4 的倍数)后,先手玩家可以对每种应对都取走相应数量,使石子总数重新成为 4 的倍数,直到石子全部取完。搜索仅凭随机推演和访问统计就找到了该走法,没有编写任何策略。

从 AlphaGo 到 AlphaZero 和 MuZero#

围棋的平均分支因子约为 250 个合法走法,而国际象棋大约为 35 个,这使围棋无法通过穷举搜索解决;从 2000 年代末开始,MCTS 推动了计算机围棋实力的飞跃。DeepMind 的 AlphaGo 使用策略网络为 MCTS 提供指导,由该网络提出可能的走法,并通过价值网络和快速推演来评估局面;2016 年 3 月,AlphaGo 以 4 比 1 击败李世石。AlphaZero 和 MuZero 更进一步。AlphaZero 完全取消了推演,而是使用价值网络为叶节点局面打分,并根据自己与自己对弈的棋局训练该网络;每次搜索的访问次数会作为策略网络的目标值,使 MCTS 成为强化学习中的策略改进步骤。MuZero 则在学习得到的环境模型中运行同样的搜索,因此无需预先提供规则,就能玩围棋、国际象棋、日本将棋和 Atari 游戏。

用于规划与推理的 MCTS#

机器人和自动驾驶车辆会使用 MCTS,在并入车流等不确定场景中进行规划;POMCP 等变体则通过跟踪隐藏状态的信念分布,将其扩展到部分可观测的马尔可夫决策过程。从相机输入开始规划的搜索需要一个状态作为根节点。例如,下棋机器人手臂可以使用一个基于棋盘图像训练的 Ultralytics YOLO26 模型来定位每颗棋子,再将恢复出的局面作为搜索树的根节点。

在 LLM 推理中,每个节点代表一个部分解答,每条边代表一个推理步骤;过程奖励模型或答案检查器会为各分支评分。Microsoft 的 rStar-Math 使用 MCTS 和过程偏好模型,将 Qwen2.5-Math-7B 在 MATH 基准测试上的得分从 58.8% 提高到 90.0%。思维树则使用广度优先或深度优先搜索来探索推理步骤。MCTS 在训练期间较难使用:DeepSeek 将其列为 DeepSeek-R1 的失败尝试之一,因为 token 序列的搜索空间远大于棋盘游戏,而且难以训练出用于引导搜索的价值模型;因此,DeepSeek 改用基于可验证奖励的强化学习训练 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 可用于质量控制、缺陷检测、个人防护装备合规检查和装配线自动化。
了解详情
汽车领域的计算机视觉

汽车领域的计算机视觉

利用 Ultralytics YOLO 模型在汽车领域应用计算机视觉。视觉 AI 可提升道路安全、驾驶辅助和车辆自动化水平,让道路更智能。
了解详情
农业中的计算机视觉

农业中的计算机视觉

借助 Ultralytics YOLO 模型,将视觉 AI 引入智慧农业。为作物监测、牲畜追踪和精准农业提供支持,从而提高产量并实现更智能的生产。
了解详情

让我们携手构建 AI 的未来!

开启你的旅程,迎接机器学习的未来