我在本地跑了一个最小的 MCTS:3×3 的 tic-tac-toe,先手 X 用蒙特卡罗树搜索,后手 O 走随机。每盘一局独立结算,每步的模拟次数 n_sim 从 1 调到 1000,每个 n_sim 跑 300 盘统计胜/平/负。数据长这样:
| n_sim | 胜 | 平 | 负 | 不输(胜+平) |
|---|---|---|---|---|
| 1 | 58.7% | 13.0% | 28.3% | 71.7% |
| 3 | 59.7% | 12.3% | 28.0% | 72.0% |
| 10 | 84.7% | 7.0% | 8.3% | 91.7% |
| 30 | 91.0% | 6.0% | 3.0% | 97.0% |
| 100 | 97.0% | 1.7% | 1.3% | 98.7% |
| 300 | 98.0% | 1.7% | 0.3% | 99.7% |
| 1000 | 98.0% | 0.7% | 1.3% | 98.7% |
看两件事。第一,n_sim=1 时 MCTS 其实就是「看一眼随机玩一盘决定走哪」,胜率 58.7% 完全来自先手优势,和随机选差不多。第二,从 1 加到 100,胜率跳到 97%,负率从 28.3% 掉到 1.3%;再把算力加 10 倍到 1000,没什么用了。把算力换成答题分数,这是一条典型的 S 曲线——前段陡峭,后段进入噪声底板。
想自己复测,整段代码 60 行左右,python3 mcts_demo.py 单线程大约 20 秒跑完:
import math, random
WIN = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
def winner(b):
for a,bb,c in WIN:
if b[a] and b[a]==b[bb]==b[c]: return b[a]
return 0 if 0 in b else -1
def moves(b): return [i for i,v in enumerate(b) if v==0]
class Node:
__slots__=('b','player','parent','move','children','N','W','untried')
def __init__(self,b,player,parent=None,move=None):
self.b=b; self.player=player; self.parent=parent; self.move=move
self.children=[]; self.N=0; self.W=0.0; self.untried=moves(b)
def uct(n,c=1.4):
return max(n.children, key=lambda ch: ch.W/ch.N + c*math.sqrt(math.log(n.N)/ch.N))
def rollout(b,p):
while True:
w = winner(b)
if w != 0: return w
b = list(b); b[random.choice(moves(b))] = p; p = 3-p
def mcts_move(b, player, n_sim):
root = Node(list(b), player)
for _ in range(n_sim):
node = root
while not node.untried and node.children: node = uct(node)
if node.untried:
m = random.choice(node.untried); node.untried.remove(m)
nb = list(node.b); nb[m] = node.player
node.children.append(Node(nb, 3-node.player, node, m))
node = node.children[-1]
w = winner(node.b)
if w == 0: w = rollout(list(node.b), node.player)
while node is not None:
node.N += 1
if node.parent is not None:
mover = node.parent.player
if w == -1: node.W += 0.5
elif w == mover: node.W += 1.0
node = node.parent
return max(root.children, key=lambda c: c.N).move
def play(n_sim, games=300):
w=d=l=0
for _ in range(games):
b=[0]*9; cur=1
while True:
x = winner(b)
if x != 0:
if x==-1: d+=1
elif x==1: w+=1
else: l+=1
break
m = mcts_move(b,1,n_sim) if cur==1 else random.choice(moves(b))
b[m] = cur; cur = 3-cur
return w,d,l
for n in [1,3,10,30,100,300,1000]:
random.seed(42+n); w,d,l = play(n)
print(f"n={n:>4} win={w/3:.1f}% draw={d/3:.1f}% loss={l/3:.1f}%")
Rich Sutton 2019 年的 The Bitter Lesson 把这件事包装成一句名言:七十年 AI 史最硬的结论是「通用、能利用算力的方法最终总是最赢的,差距还很大」,他点名 search 和 learning 两条路。但他其实回避了一个更具体的问题——为什么只有这几类算法能平滑地随算力变强?专家系统也会算得更快、规则也可以加更多,怎么就不行?
我这篇想把 Sutton 没说的那层点破:这五个算法在数学上做的是同一件事——用独立样本估计一个分布上的期望。算力多就是样本多,蒙特卡罗收敛率立刻起作用。它们从结构上就是蒙特卡罗估计器的化身,这是一条数学定律,不是工程经验。
五个算法都在估什么期望
讲 MCTS 时最容易看出来,因为「蒙特卡罗」三个字直接写在名字里。其它四个外表完全不像,但骨架是同一副。
MCTS:要估的是「如果现在走动作 ,按某个策略接着玩到结局,期望回报是多少」,即 。rollout 就是一次 Monte Carlo 样本,模拟次数 多了, 的方差按 降。Kocsis 和 Szepesvári 2006 年证明 UCT 把「累积 regret」压到 (Bandit Based Monte-Carlo Planning),所以 n 从 1000 翻 100 倍到 100000,regret 只涨 倍,人均 regret 几乎变成原来的 1/60。这就是上面那张表为什么 n_sim=1→100 猛涨、100→1000 开始饱和。
TD Learning(Sutton 1988):要估的是状态价值 。它不走完整 rollout,用自己当前对下一步的估计作为目标(bootstrap)。样本是一次 transition 。更多 transition 就是更多样本,方差同样按根号降。TD-Gammon 1992 年靠一百五十万局自我对弈学到大师级,就是这个结构在棋盘上跑了很多很多次。
SGD + 反向传播:每步要估的是数据分布上损失的梯度 。一个 batch 就是一次 Monte Carlo 估计,batch size 越大,这一步的梯度估计方差越小,直接按 比例降。反向传播本身是梯度算得快(后面会手算一笔账),但梯度为什么跑着跑着能找到好参数,靠的是整个过程是 Robbins-Monro 1951 年那套 stochastic approximation:有偏噪声的梯度只要无偏采样、步长收敛得慢一点,期望意义下就能收敛到驻点。
CNN 和 Transformer 乍一看是架构不是估计器。但它们本质是给 SGD 用的归纳偏置——CNN 的卷积说「空间平移同一回事」,Transformer 的自注意力说「任意两个位置都该能直接通信」。有了这些偏置,参数量撑大时每个参数都能被 SGD 有效地估出来;没有偏置(比如全连接处理 ImageNet),参数之间彼此独立,样本效率塌了。Transformer 还多一层含义:自注意力本身就是一次加权期望——,读出来就是在 token 分布上算一个条件期望。模型的每一层都在重复这件事。
一张表归纳:
| 算法 | 估的那个期望 | 一个「样本」是什么 | 已知的收敛率 |
|---|---|---|---|
| SGD + BP | 一个 minibatch | 梯度方差 | |
| CNN / Transformer | 同上,加架构先验 | 同上 | 实证幂律,见下节 |
| MCTS (UCT) | 一次 rollout | regret | |
| TD Learning | 一次 transition | TD(0) 收敛到 |
共同分母是:在估期望,而且估的那个期望恰好就是模型/策略好不好的度量。前半句管「能不能收敛」,后半句管「收敛了有没有用」。只缺前半句的方法(比如拟牛顿法估 Hessian)不能当学习算法;只缺后半句的方法(比如估一个和任务无关的量)再准也白搭。
手算 Kaplan 2020 的 0.076 为什么这么小
Monte Carlo 的通用天花板很熟:独立同分布 个样本的均值,误差按 降,对应幂律指数 。拿这个对比一下 Kaplan 等 2020 年测出来的大语言模型 scaling law(arXiv:2001.08361,Eq. 1.5):
是非 embedding 参数量, 是测试集交叉熵。我用一次性 python 脚本验算过几个常用问法(python3 -c 就能复算):
alpha = 0.076
# 参数翻倍:loss 乘 2^(-alpha) = 0.9487,下降 5.13%
# loss 减半:需要参数扩 2^(1/alpha) ≈ 9140 倍
输出:参数翻倍 loss 只下降 5.13%,想把 loss 减半得把参数扩大约 9140 倍(约 )。这个数字第一次算出来我是震惊的——GPT-2 到 GPT-3 参数量涨了 100 倍左右,loss 下降的幅度其实不到 40%。扩算力能换 loss,但汇率比想象的差得多。
然后关键的对比: 相对于纯 Monte Carlo 的 ,效率比只有 ,即把算力效率打了一个多的量级折扣。为什么?因为 LLM 训练不是直接对 loss 本身做 Monte Carlo 均值,而是通过训练过程间接地去拟合语言分布:梯度要穿过很多层,模型要学到层次结构,每层都有自己的样本效率损耗。所以 远小于 是正常的——重要的是 这件事是硬的,只要保持「样本平均估期望」这个骨架,再多算力都一定还能挤出一点 loss。
这个「汇率差但方向硬」的组合,正好解释了为什么业内会花一亿美元把参数从 10B 推到 100B——虽然收益率看起来很低,但这是唯一已知不会在中途断崖的那条曲线。专家系统往上堆规则会在冲突数量超过某个阈值后彻底停住;手工特征会在某个数据量上饱和(HOG 在 ImageNet 上扩多少数据都干不过 AlexNet)。LLM 不会断,这是最贵的性质。
顺手手算一下 Chinchilla(Hoffmann 等 2022,arXiv:2203.15556)。它拟合的是一个两项模型 ,论文给的指数是 、。给定 compute (Kaplan 那套估算),最优分配下 和 各随 怎么长?Lagrange 一下的结论是:
代入 0.34 和 0.28:、。 的指数比 的高 0.097,意味着算力翻倍时该多喂数据,而不是等比例加参数。这就是 Chinchilla 推翻 GPT-3 过度扩参数的那条结论的来源。它不是实验归纳,是两个指数一减就出来的。
(我原本以为 和 应该对半分,直到读到 Hoffmann 的表才意识到 和 必然不相等——语言数据的离散、稀疏结构让它比参数更难榨干。先验直觉在这里是错的,拿论文的具体指数算一遍才看得见。)
想对上面这套幂律推导读得更慢一点,站内有一篇陪读:零基础陪读 Scaling Laws:那篇深读读不动?你缺的其实只是一条直线——它把 log-log 直线和幂律拟合用能手算的小例子装了一遍。
反向传播本身的一笔账:为什么它比数值差分快十一个量级
MCTS 和 TD 的「样本」是 rollout 和 transition,样本成本一眼能看见。SGD 的「样本」是 batch,但真正撑起这件事的其实是算一次梯度便宜。反向传播是 Rumelhart、Hinton、Williams 1986 年的 Nature 论文把它从理论提到实用的那一步,核心贡献就是:一次算完全部参数的梯度,代价只有 ,和前向差一个常数倍。
对比数值差分:想知道参数 的偏导,就把 加一个小扰动 跑一遍前向、再加一遍跑一遍、减掉求差。每个参数两次前向,一共 次前向,每次前向本身是 ,总代价 。
拿 175B 参数的模型套一下:
- 反向传播一步 ≈ 单位操作
- 数值差分一步 ≈ 单位操作
- 两者差 倍
这个差是什么概念?按一张 H100 大概 FLOPS 算,一步 BP 不到 0.2 毫秒,一步数值差分要跑 秒——约 115 天。LLM 训练完全不存在。反向传播不是「稍微快一点」,它是让 SGD 从物理上变得可行的那一步。没有它,前面所有「用样本估期望」的美好数学都在 billion-parameter 这个尺度上全部作废。
这也解释了为什么 CNN、Transformer 无论架构怎么翻新,最底下必须保持 differentiable——一旦某一层不可导,这一层的梯度就得靠 REINFORCE 之类有大方差的估计器补上,整条样本效率的曲线立刻陡掉。注意力机制之所以能撑到今天,是因为它那个 softmax 恰好可微。
反例:专家系统为什么走不动
把「样本平均估期望」这个结构摘掉,看会发生什么。
专家系统的核心是「规则 + 推理机」:知识被人直接编码成 IF-THEN 条款,推理机做查表、合一、冲突解决。MYCIN(1970 年代诊断传染病的系统)和它后面十年所有仿照者的致命问题,不是规则不够多——是规则之间会打架。规则数到几百条时,专家自己就开始搞不清一条新规则会不会推翻之前某几条的组合结论。规模经验上这个点在 ) 条规则,和 Lenat 的 Cyc 项目后来几十万条条目里绝大部分不敢投入生产用途是同一个病因。
用本文的框架看就一句话:专家系统不在估什么期望,它在编译一张查找表。每条规则是一个确定性函数,加规则不是采样,是改函数。算力扩大能换的东西只有「查得更快」,不能换「答得更对」——答得对不对只取决于规则集本身,而规则集是人写的,有人的带宽上限。
手工特征(HOG、SIFT、滑动窗口 + Haar)是同一个病的变体。特征提取函数 是人工固定的常数项,再多训练数据只能让它后面接的分类器更好,但 的表达能力永远在那里。AlexNet 2012 年把 ImageNet top-5 错误率从 26% 砍到 16.4% 的那一刀,本质就是把 换成了可学的参数,于是「特征」也进入了「样本平均估期望」这个闭环。这不是优化问题,是从编译器切换成了估计器。
反过来验证本文这个框架——如果拿掉「用独立样本估计期望」这个约束,这些设计就会退化成专家系统那种查表式编译器:算力只换查得更快,不换答得更对。这就是 Sutton 提到但没明说的那条分界线。
一个新算法能不能 scale with compute:两个问题可以快速判定
有了这个框架,看一个新鲜算法会不会随算力变强不用等训练结果,问两个问题:
- 它在估什么期望?能说清楚那个期望的数学形式吗? 答得出,它至少还在估计器这一边。答不出(只说「优化某个指标」但说不清具体是哪个期望),大概率没上路。
- 每份算力能不能转化成一个独立样本? 样本之间独立,才是 Monte Carlo 收敛率立刻生效的前提。如果每份算力只是让单次推理更慢,不增加样本数,那扩算力没意义——这就是为什么推理时的 Chain-of-Thought 和训练时的加参数效果完全不同(CoT 是在一个样本里花更多算力,而不是多拿样本,所以它受限于别的曲线)。
两问都答得干脆、每问答案都指向「样本+期望」这个骨架,稳;任何一问要绕弯,这个算法大概率在扩算力时会碰墙。
这也解释了近几年大家看到的几个现象。LLM-as-a-Judge 的评测结果为什么比人工评测 noisy 得多——它是在估「人类偏好」这个分布上的期望,但每个 Judge 调用并不独立(prompt 相同、模型相同,相关性拉满),所以虽然每次调用便宜但样本效率低得吓人。相反,MCTS + LLM policy prior(AlphaGo 到 R1 的那条线)为什么能把测试时算力换成正确率——每条 rollout 用不同随机种子、是真正独立样本,Monte Carlo 的通用曲线自动起作用。这不是经验玄学,是蒙特卡罗的数学直接推出来的。
想在 MCTS 这一侧读得再细一点,站内有两篇可挂靠:零基础读懂蒙特卡洛树搜索:不会评估棋局的算法怎么靠”随机乱下”称霸围棋 解释了选择-扩展-模拟-回传四个零件和 UCB1 怎么把 regret 压到 ;别抄 AlphaGo 的 490 万局,抄它花预算的方式 则把同一个结构反过来用到人类学习上。
回到 Sutton 没说的那一层
Sutton 的「苦涩的教训」是经验归纳:通用方法 + 算力 > 巧妙的专用方法。很多人读完当鸡汤,觉得「选个通用方法堆算力就行」。但 Sutton 没说哪些「通用方法」能被算力喂饱、哪些不能——他只是在后视镜里看到 Deep Blue 的 search 和 AlphaGo 的 learning 两条路都赢了。
本文这个视角把它收紧了一个量级:只有那些数学上是「独立样本估计某个期望」的算法,才能被算力无止境地喂饱。这不是一条用来事后解释胜者的话,而是一条事前就能筛算法的判据。它也把 AlphaGo、GPT 这些现象级系统的共性抽到了同一张理论底图上——它们跟 1986 年的反向传播、1988 年的 TD Learning、2006 年的 UCT 用的是同一套蒙特卡罗收敛率,只不过估的期望不一样。
想从更宽的视角把这套话挂到 AI 全史上,站内还有一篇站在 AI 的山巅:12 条原理望远镜,里面的第 9 条「规模与苦涩的教训」和第 11 条「反馈闭环」合起来其实就是本文这个讲法——一个说”赢家长什么样”,一个说”每一代样本怎么来”,两条拼起来就是蒙特卡罗估计器这个共同结构。
翻成厨房里的话:都是在用勺子估一锅汤的平均咸度
把这件事翻成厨房里能讲的话。
想象你要测一锅很大的汤有多咸。办法只有一个:舀一勺尝一下,再舀一勺尝一下,多尝几次取平均。汤越大、浓度越不均,你要尝的勺数越多。但是数学已经保证,你尝得越多,均值越接近真实咸度,误差按勺数的平方根降。这是蒙特卡罗方法,是本文全部的数学内核。
现在换几种舀法:
- MCTS:每一勺不是从锅里随便舀,而是对汤面观察一番,优先去舀之前尝过「比较咸」的那块区域。咸的会得到更多次采样、让均值更快稳定。UCB1 公式告诉你何时该探索一块新区域、何时该深挖旧区域,这就是 的 regret 来源。
- TD Learning:汤还在炖,你尝的是中间状态。你不等汤炖好,先猜「这一勺这样,等炖好会怎样」。猜得八九不离十就记下来,继续炖下一步再修正。
- SGD + 反向传播:你不是尝汤咸不咸,是尝「加盐之后汤会怎么变」——每一勺告诉你盐的梯度。反向传播是一次能同时告诉你所有调料的梯度,不用一样一样试。
- CNN / Transformer:这是给锅本身加了假设。CNN 假设「汤任何地方的小旋涡都长差不多」,所以估一处的旋涡就能用到别处;Transformer 假设「任何两处都可能互相影响」,所以每一勺都要互相比对。假设对了,每一勺的信息密度高得多。
- 专家系统:你不尝了,拿出菜谱——「盐 15 克、糖 3 克、八角两颗」。味道是菜谱定的,不是从锅里尝出来的。算力多只能让你更快读菜谱,不能让菜谱更准。
本文的一句话:BP、CNN、Transformer、MCTS、TD 都能随算力无止境变强,是因为它们都在用独立的勺子估同一锅汤的平均咸度。再多的算力就是再多几勺,蒙特卡罗的根号率是数学定律,不是工程技巧。换掉菜谱做法(专家系统、手工特征),再多的算力也只能让菜谱读得更快,不让答案更准。
想判断某个新算法会不会 scale——问它:“你在估哪锅汤的平均咸度?每份算力能多舀一勺独立的样本吗?“
参考来源
工程实践
- Richard Sutton, The Bitter Lesson(2019 博客原文)
- 站内:零基础陪读 Scaling Laws(Kaplan 幂律的手算陪读)
- 站内:零基础读懂 MCTS 与 别抄 AlphaGo 的 490 万局(UCT 的四个零件 + 人类学习法映射)
- 站内:站在 AI 的山巅:12 条原理望远镜(第 9、第 11 条合起来就是本文的论点)
arXiv 论文 / 原始出版物
- Kaplan et al., Scaling Laws for Neural Language Models, arXiv:2001.08361( 的来源)
- Hoffmann et al., Training Compute-Optimal Large Language Models (Chinchilla), arXiv:2203.15556(、 的来源)
- Vaswani et al., Attention Is All You Need, arXiv:1706.03762
- Kocsis & Szepesvári, Bandit Based Monte-Carlo Planning, ECML 2006(UCT 的 regret 证明)
- Silver et al., Mastering the Game of Go Without Human Knowledge(AlphaGo Zero, Nature 2017)与 A General Reinforcement Learning Algorithm That Masters Chess, Shogi, and Go Through Self-play(AlphaZero, Science 2018)
- Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning 1988
- Rumelhart, Hinton, Williams, Learning Representations by Back-propagating Errors, Nature 1986
- Krizhevsky, Sutskever, Hinton, ImageNet Classification with Deep Convolutional Neural Networks, NeurIPS 2012(AlexNet)
- Robbins & Monro, A Stochastic Approximation Method, Ann. Math. Stat. 1951(SGD 的收敛理论基础)