Monte Carlo Tree Search (MCTS)
蒙特卡洛树搜索 (MCTS) 通过模拟推演扩展搜索树,并聚焦于有希望的行动来选择动作。它应用于 AlphaGo 和机器人。
蒙特卡洛树搜索(MCTS)是一种规划算法:它通过多次模拟推演,逐步构建可能未来的搜索树,并将更多计算预算花在看起来最有希望的走法上,从而选择下一步行动。它只需要一种生成合法走法和结果的方法,例如游戏规则或模拟器,而不需要手工编写评估函数。它也是一种随时可终止的算法:无论何时停止,都会返回目前找到的最佳走法;投入更多时间则会得到更好的答案。Rémi Coulom 于 2006 年为该方法命名;同年,Levente Kocsis 和 Csaba Szepesvári 发表了 UCT,即后来成为该方法标准形式的选择规则。短短几年内,MCTS 就改变了计算机围棋;之后它为 AlphaGo 和 AlphaZero 提供了动力,如今还用于规划机器人和车辆的行为,以及在推理步骤中进行搜索,以应用于大型语言模型(LLM)。
MCTS 的工作原理#
搜索过程维护一棵树,树根是当前局面,每个节点记录访问次数以及这些访问中获胜的次数。每次迭代分为四个阶段:
- 选择: 从树根开始,沿着已充分探索的节点向下搜索,选择 UCT 分数最高的子节点;该分数会平衡较高的胜率与较少尝试的走法。
- 扩展: 在第一个存在未尝试走法的节点上,将该走法添加为新的子节点。
- 模拟: 从新子节点开始一直模拟到游戏结束;传统做法是随机走子,以获得结果。
- 反向传播: 沿路径向上回溯,并根据结果更新每个节点的访问次数和获胜总数。
预算耗尽时,算法会选择树根下访问次数最多的子节点;与选择平均得分最高的节点相比,这种选择更稳定。
平衡探索与利用#
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。










