2026年8月5日作者：Lei阅读 --

零基础读懂蒙特卡洛树搜索(MCTS):不会评估棋局的算法,怎么靠"随机乱下"称霸围棋

零基础向。不预设博弈论或强化学习背景,用三个零件拼出 MCTS:大数定律(不会评估就采样)、老虎机公式 UCB1(逐符号讲解 + 全程手算)、树上的四步循环(选择→扩展→模拟→回传)。然后看 AlphaGo 用神经网络换掉了哪两个零件,以及 LLM 时代 MCTS 为什么被 DeepSeek-R1 放弃、又被 rStar-Math 捡起。

1997 年,深蓝靠每秒评估约 2 亿个局面的暴力搜索击败了国际象棋世界冠军卡斯帕罗夫。所有人都以为围棋只是”同样的办法,更大的机器”——结果接下来将近十年,计算机围棋一直停留在业余水平。问题不在算力,而在一个更根本的地方:深蓝的办法在围棋上根本没法开工。直到 2006 年,一个听起来近乎偷懒的主意出现了:评估一个局面?那就从这个局面开始随机乱下,下完一整局,数数谁赢——多乱下几次,取个平均。就这么个”掷骰子”的办法,配上一条从赌场老虎机问题里借来的公式,让计算机围棋十年内从业余冲到职业,最终长成了 AlphaGo 的骨架。这篇文章不预设你懂博弈论或强化学习,把这台机器拆成三个零件,一个一个装给你看,关键一步全程手算。

一句话主线

MCTS 把”这个局面好不好”这个算不出来的问题,替换成一个可以统计的问题:“从这里随便下完一整局,赢的频率是多少?”剩下的全部设计——选择、扩展、模拟、回传——都只为一件事:把有限的模拟次数,花在最值得深想的分支上。

一、深蓝的办法为什么在围棋上失灵

先搞清楚旧办法卡在哪,新办法的妙处才看得见。

深蓝式搜索(教科书上叫 minimax + alpha-beta 剪枝)的套路是:把接下来几步的所有可能摆成一棵树,搜到某个深度停下,然后用一个评估函数给停下的局面打分——“白方多一个车,大约值 5 分”这类规则——再把分数往回推,选出最优一步。

这个套路需要两样东西,围棋一样都给不起:

树不能太宽。国际象棋每步平均约 35 种选择(术语叫分支因子),围棋约 250 种。往下想 4 步,国际象棋是 35⁴ ≈ 150 万个分支,围棋是 250⁴ ≈ 39 亿个。围棋的合法局面总数约 10¹⁷⁰,比可观测宇宙的原子数多出一百多个数量级——靠加机器是追不上指数的。
评估函数写得出来。国际象棋数子力就能打个八九不离十的分。围棋的一颗子值多少?取决于几十步之后它是活是死、围出多少空——顶尖棋手自己都说不清,更没人能把它写成代码。

第一个问题还能靠剪枝硬扛,第二个问题是死穴:搜索停下来的那一刻你必须给局面打分,而围棋没有打分公式。

二、零件一:不会评估,就用”乱下到底”代替评估

蒙特卡洛方法是一族老办法的统称,思想一句话:算不出来的量,用随机采样的平均值去逼近。想估算圆周率,就往正方形里随机撒点,数落在内切圆里的比例——撒得越多越准。这背后是概率论里的大数定律:独立重复试验的频率收敛于真实概率。

用到棋上就是那个”偷懒”的主意:

想知道局面 S 对黑棋有多好?从 S 开始,让双方完全随机地把这盘棋下完,记录谁赢。重复 1000 次。如果黑棋赢了 620 次,就说 S 的”胜率”约是 62%。

这个数字很粗糙——双方都在乱下,跟真实对局差得远。但它有两个救命的优点:

它不需要任何围棋知识。不用懂死活、不用会数空,只要会判断”终局谁赢”(这在围棋规则里是机械可判的)。写不出评估函数?没关系,不写了。
它的方向是对的。一个厚实的好局面,即使双方乱下,赢面也系统性地偏高;一个崩了的局面,乱下也救不回来。模拟次数够多,好坏排序大体靠谱。

你可能立刻想反驳:对手又不会随机下棋,这胜率能作数吗?——这个质疑完全正确,它就是朴素蒙特卡洛的真实短板,记住它,第四节 AlphaGo 出场时,被神经网络第一个换掉的正是这个零件。但在 2006 年,“粗糙但不需要领域知识”恰恰是它赢过”精确但根本写不出来”的理由。

现在只剩一个问题。假设当前局面有 250 种走法,你的预算是 10 万次模拟——平均摊,每种走法只分到 400 次,而其中 200 多种是一眼就烂的棋,继续给它们分模拟纯属浪费。怎么把模拟次数花在刀刃上?这个问题的答案来自一个和围棋八竿子打不着的地方:赌场。

三、零件二:老虎机公式 UCB1(手算)

赌场里有三台老虎机 A、B、C,吐钱概率各不相同且你不知道。你有 100 枚硬币,目标是总收益最大。玩了几轮之后你会陷入两难:

目前战绩最好的那台,应该多玩——这叫利用(exploitation);
但其他机器只玩过一两次,战绩差可能只是运气差,应该再试试——这叫探索(exploration)。

全押战绩最好的,可能错过真正的好机器;雨露均沾,又把硬币浪费在烂机器上。这就是多臂老虎机问题,强化学习里最经典的两难。Auer 等人 2002 年给出了一个优雅的解法 UCB1(Upper Confidence Bound,上置信界):每轮给每台机器算一个分数,谁高玩谁:

\text{UCB1}_j = \bar{x}_j + \sqrt{\frac{2\ln n}{n_j}}

逐个符号读:

$\bar{x}_j$ :第 $j$ 台机器到目前为止的平均收益(赢的比例)。这是”利用”项——战绩好,分数高;
$n_j$ :第 $j$ 台机器被玩过的次数; $n$ :所有机器加起来玩过的总次数;
$\sqrt{2\ln n / n_j}$ :这是”探索”加成,整个公式的灵魂。分母是”这台机器被玩过几次”——玩得越少,加成越大,替没被充分了解的机器说话;分子里的 $\ln n$ 随总轮数缓慢增长——意味着哪怕一台机器战绩再烂,只要被冷落得够久,它的加成终会长到让你回头再看它一眼。没有谁被永久放弃,只有谁被暂时冷落。

空讲无感,直接手算。三台机器,约定赢记 1 分、输记 0 分:

前 3 轮(每台先各玩一次):A 赢,B 输,C 赢。战绩:A = 1/1,B = 0/1,C = 1/1。

第 4 轮, $n = 3$ , $2\ln 3 \approx 2.20$ ,三台的 $n_j$ 都是 1,探索加成都是 $\sqrt{2.20/1} \approx 1.48$ :

机器	平均收益 $\bar{x}_j$	探索加成	UCB1 总分
A	1.00	1.48	2.48
B	0.00	1.48	1.48
C	1.00	1.48	2.48

A、C 并列最高(平局任选,玩 A)。假设 A 这次输了,A 变成 1/2。

第 5 轮, $n = 4$ , $2\ln 4 \approx 2.77$ :

机器	平均收益	探索加成	UCB1 总分
A(1/2)	0.50	$\sqrt{2.77/2} \approx 1.18$	1.68
B(0/1)	0.00	$\sqrt{2.77/1} \approx 1.67$	1.67
C(1/1)	1.00	1.67	2.67

C 最高,玩 C。假设 C 赢了,C 变成 2/2。

第 6 轮, $n = 5$ , $2\ln 5 \approx 3.22$ :C(2/2)得 $1.00 + \sqrt{3.22/2} \approx 2.27$ 仍然最高,继续玩 C。假设这次 C 输了,C 变成 2/3。

第 7 轮, $n = 6$ , $2\ln 6 \approx 3.58$ :

机器	平均收益	探索加成	UCB1 总分
A(1/2)	0.50	$\sqrt{3.58/2} \approx 1.34$	1.84
B(0/1)	0.00	$\sqrt{3.58/1} \approx 1.89$	1.89
C(2/3)	0.67	$\sqrt{3.58/3} \approx 1.09$	1.76

注意发生了什么:轮到 B 了。它一次没赢过、平均收益是零,但被冷落了 6 轮之后,探索加成默默长到 1.89,反超了战绩更好的 A 和 C。这就是 UCB1 的性格:短期内偏爱赢家,长期内不冤枉任何人。Auer 等人证明了这个策略的”后悔值”(因为没玩最优机器而损失的收益)增长速度是理论最优量级——你不可能做得比它好太多。

四、零件三:把老虎机装进树里,就是 MCTS

2006 年,两项工作几乎同时把上面两个零件拼在了一起。Rémi Coulom 提出用树结构组织蒙特卡洛模拟并创造了”蒙特卡洛树搜索”这个名字,他的程序 Crazy Stone 随即拿下当年计算机奥林匹克 9 路围棋冠军;Kocsis 与 Szepesvári 则把 UCB1 精确地搬进树里,得到 UCT 算法(UCB applied to Trees),并证明:给足时间,它收敛到 minimax 最优解——偷懒的办法,有不偷懒的理论保证。

关键的观念一跳是:树里的每个节点,都是一排老虎机。“当前局面下走哪一步”是在拉哪台老虎机,“拉一次”就是”做一次模拟”,“吐不吐钱”就是”模拟输赢”。于是每个节点只需要记两个数:被模拟过几次( $n_j$ ),赢了几次。

完整的 MCTS 就是把下面四步循环几千几万遍:

flowchart LR
    A["① 选择 Selection<br/>从根出发,每层用 UCB<br/>挑分数最高的孩子"] --> B["② 扩展 Expansion<br/>走到树的边界<br/>长出一个新节点"]
    B --> C["③ 模拟 Simulation<br/>从新节点随机乱下<br/>直到终局分出胜负"]
    C --> D["④ 回传 Backpropagation<br/>胜负结果沿来路<br/>更新每个祖先的战绩"]
    D -->|"循环几千次"| A

① 选择:从根节点(当前局面)出发,每一层都用 UCB 公式在孩子里挑分数最高的往下走——树里每一层都在玩老虎机;
② 扩展:走到一个还有未尝试走法的节点,为其中一个新走法建一个节点(树长大了一格);
③ 模拟:从新节点开始随机快下到终局,得到一个胜负——这就是第二节的”乱下到底”,行话叫 rollout;
④ 回传:把胜负沿着来时的路径报告给每一个祖先节点,各自的”模拟次数 +1,赢局数视结果 +1 或 +0”。

再手算一次,这回在树上。设根节点已经做过 12 次模拟,三个候选走法 a、b、c 的战绩(从根节点行棋方视角)是:

走法	战绩	平均胜率	探索加成( $2\ln 12 \approx 4.97$ )	UCB1 总分
a	4 胜 / 6 次	0.67	$\sqrt{4.97/6} \approx 0.91$	1.58
b	1 胜 / 4 次	0.25	$\sqrt{4.97/4} \approx 1.11$	1.36
c	1 胜 / 2 次	0.50	$\sqrt{4.97/2} \approx 1.58$	2.08

第 13 次模拟走 c——尽管 a 的平均胜率更高,但 c 只被试过 2 次,不确定性大,值得再看看。选择阶段进入 c 的子树后逐层重复同样的比较,直到边界;扩展一个新节点;随机模拟,假设这次输了;回传:c 变成 1 胜/3 次,根节点变成 13 次。下一轮所有分数重算。

两个细节值得点破:

双人博弈里,相邻两层的视角是对立的:轮到对手的那一层,节点统计的是对手的胜率,选择时也是替对手挑对他最好的走法。MCTS 天然继承了 minimax “你走你的最优,我走我的最优”的对抗结构;
最后真正落子时,选的不是平均胜率最高的走法,而是被模拟次数最多的那个——访问次数本身就是算法用真金白银(模拟预算)投出来的票,比平均值更抗噪。

四步循环滚起来之后,一个漂亮的性质自动涌现:树是不对称生长的。有希望的分支被反复选中,越搜越深;烂棋浅尝辄止,只留一个浅浅的树桩。对比 minimax 对好坏分支一视同仁地均匀展开,MCTS 把算力自动灌进了值得深想的地方——而且随时可以叫停:停在哪一刻,当前访问次数最多的走法就是当前最优答案,多想一秒就多准一分。

这套机制的战绩来得很快:2006 年 Crazy Stone 夺冠,2008 年 MoGo 在 9 路盘达到段位水平,2009 年 Fuego 在 9 路盘执白战胜顶尖职业棋手;综述文献的说法是,MCTS 让计算机围棋从 14 级(平均业余水平)跃升到 5 段(高段水平)。但 19 路大棋盘上离职业顶尖仍差一截——纯随机 rollout 的粗糙,和开局阶段海量走法的均匀探索,两个短板都撞到了天花板。

五、AlphaGo:用神经网络换掉两个”随机”零件

2016 年 3 月 AlphaGo 4:1 战胜李世石。刨掉工程细节,AlphaGo 对 MCTS 的改造可以概括成一句话:骨架不动,把两个最随机的零件换成神经网络:

换掉”均匀探索”:一个在人类棋谱上训练的策略网络(policy network),看一眼局面就输出”这 250 种走法里,像样的大概是这十几个”——作为先验概率,让搜索从第一次模拟起就绕开明显的烂棋;
换掉”随机乱下”:一个价值网络(value network),看一眼局面直接吐出胜率估计——第二节里”对手不会随机下棋”的那个死穴,终于用学出来的评估补上了。

选择阶段的公式也随之升级,从 UCB1 变成 PUCT(出自 Rosin 2011,经 DeepMind 改造):

a_t = \arg\max_a \left( Q(s,a) + c_{puct} \cdot P(s,a) \cdot \frac{\sqrt{\sum_b N(s,b)}}{1 + N(s,a)} \right)

和 UCB1 逐项对照,骨架完全一样——“平均战绩 + 探索加成”:

$Q(s,a)$ :走法 $a$ 在搜索中的平均价值,对应 $\bar{x}_j$ ;
$N(s,a)$ :走法 $a$ 的访问次数,还在分母里压制被反复访问的走法; $\sum_b N(s,b)$ 是所有走法访问次数之和,对应总次数 $n$ ;
新零件是 $P(s,a)$ :策略网络给的先验——网络觉得像样的走法,探索加成天生更高;网络觉得离谱的走法,几乎不会被浪费模拟。探索不再一视同仁,而是带着直觉的探索。

2017 年的 AlphaGo Zero 把这条路走到头:不用任何人类棋谱,从随机权重开始自我对弈;策略和价值合并成一个双头网络;rollout 彻底删除,叶子节点全靠价值网络评估;每步棋跑 1600 次模拟。最精妙的是训练闭环:MCTS 搜索之后得出的走法分布,比网络自己的直觉更强——就把它当作训练目标,让网络学习”搜索想清楚之后的结论”。网络变强,搜索随之变强(先验和评估都更准了),搜索变强,又产出更高质量的训练目标。左脚踩右脚,从零登顶:这就是”搜索 + 学习”飞轮,后来 AlphaZero 用同一套配方(每步 800 次模拟)通吃国际象棋和将棋。

用一个对照表收拢这一节:

零件	朴素 MCTS(2006)	AlphaGo Zero(2017)
走法先验	均匀(全靠试)	策略头 $P(s,a)$
叶子评估	随机 rollout 到终局	价值头直接打分
选择公式	UCB1	PUCT
知识来源	无(纯统计)	自我对弈自举

六、LLM 时代:被 R1 放弃,被 rStar-Math 捡起

读过上一篇 DeepSeek-R1 解剖的读者会记得:R1 团队明确尝试过把 MCTS 用于语言模型推理,然后放弃了。现在你有了足够的零件知识,能真正读懂他们给出的两条理由:

搜索空间不对等。围棋每步 250 种选择,语言模型每个 token 有几万种选择,而一步推理是几十上百个 token——树的宽度指数爆炸,四步循环的”选择”阶段直接失效;
没有廉价的裁判。MCTS 的地基是”模拟到终局,胜负机械可判”。数学推理没有”下完一整局”的廉价模拟,判断一条中间推理路径的好坏需要一个细粒度价值模型——而 R1 团队发现这个模型本身就极难训练,还容易被钻空子。

于是 R1 选择了另一条路:不做推理时搜索,用强化学习把”探索—回溯”内化成模型在一条线性思维链里的行为。用本文的语言说:R1 把树折叠进了草稿纸——“Wait, 换条路想”就是它的分支与回溯。

但 MCTS 在 LLM 上并没有出局,它换了个岗位。微软的 rStar-Math(2025)给出了反例:7B 的小模型做策略,一个用步骤间相对偏好(而非绝对打分,恰好绕开 R1 撞上的那堵墙)训练的过程偏好模型做价值引导,每步生成的代码用执行结果验证,在 MCTS 框架下自我进化四轮——把 Qwen2.5-Math-7B 在 MATH 基准上从 58.8% 推到 90.0%,超过了 o1-preview,AIME 能解出约 53.3% 的题。

所以真实的图景是灰度的,不是”MCTS 过时了”:

模型足够大、算力足够多时,“多采样 + 只认结果的奖励”更划算——这是苦涩教训又一次应验,R1 的选择;
模型小、步骤可验证(如可执行代码)、预算可控时,显式搜索仍是最可靠的能力放大器——rStar-Math 的选择;
更普遍的角色转移:MCTS 从”推理时的引擎”退居”训练数据的生成器”——用搜索生产高质量推理轨迹,再把轨迹蒸馏进模型。AlphaGo Zero 的”学习搜索想清楚之后的结论”,换了个马甲活在 LLM 训练管线里。

带走的模型

三句话,以后遇到任何带”搜索”字样的 AI 系统都用得上:

MCTS = 大数定律 + 老虎机 + 树。评估算不出来,就用随机模拟的频率代替(蒙特卡洛);模拟预算有限,就用”平均战绩 + 探索加成”分配(UCB1);决策是序贯的,就把老虎机装进树的每一层(UCT)。
“评估难,就采样;分配难,就 UCB。“这两个招式远不止下棋能用——A/B 测试的流量分配、推荐系统的冷启动、超参数搜索,内核都是同一个探索/利用公式。
看任何”搜索 + 学习”系统,问三个问题:先验从哪来?评估从哪来?搜索结果怎么反哺学习?朴素 MCTS 的答案是”没有/随机模拟/不反哺”,AlphaGo Zero 的答案是”策略头/价值头/当训练目标”,rStar-Math 的答案是”小模型/过程偏好模型/蒸馏进下一轮”。三套答案,一个骨架。

参考来源

奠基论文:

Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search — Coulom, CG 2006,MCTS 命名之作,Crazy Stone
Bandit Based Monte-Carlo Planning — Kocsis & Szepesvári, ECML 2006,UCT 与收敛性证明
Finite-time Analysis of the Multiarmed Bandit Problem — Auer et al., 2002,UCB1
A Survey of Monte Carlo Tree Search Methods — Browne et al., 2012,经典综述
Monte Carlo Tree Search: a review of recent modifications and applications — Świechowski et al., 2022,近年综述

AlphaGo 系:

Mastering the game of Go with deep neural networks and tree search — Silver et al., Nature 2016,AlphaGo
Mastering the game of Go without human knowledge — Silver et al., Nature 2017,AlphaGo Zero
Multi-armed bandits with episode context — Rosin, 2011,PUCT 出处

LLM 时代:

DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning — 放弃 MCTS 的两条理由(见其”不成功的尝试”一节)
rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking — Guan et al., 2025,MCTS + 过程偏好模型

站内相关:

解剖 DeepSeek-R1 的”思考” — R1 为什么选了 MCTS 的反面
示范教不会的东西:为什么大模型需要强化学习 — 零基础 RL 概念打底