跳到主要内容

机器下棋 — 从魔术道具到 AlphaGo

这一章讲三件事: 下棋为什么两千年来都被当作"智能"的试金石,而第一台"下棋机器" 其实是个魔术;博弈树搜索的完整机制——Minimax 替对手想、评估函数给局面打分、 α-β 剪枝(提前砍掉不必计算的分支)把搜索量砍掉一大半;以及围棋为什么拖到 2016 年才被攻破——蒙特卡洛模拟 加上自我博弈,这个组合为什么是质的换代。 这一章篇幅不大,但它是第 01 章"预言生命周期"的兑现现场,也是第 05 章强化学习的 首个工业级应用。

1. 这一章讲什么

原书引图灵:"下棋需要智能。"(Chess requires intelligence)1。 下棋规则固定、胜负分明、千百年被当作智力的度量——所以它是 AI 最早的检验场, 也是打脸与兑现最频繁的战场。

本章时间跨度两百年,机制上只有三个真正的关口:

关口年代机制变化
从魔术到程序1769 → 1950藏在柜子里的棋手 → 评估函数+博弈树
从程序到大师1958 → 1997通用计算机 → α-β 剪枝 + 专用硬件
从搜索到学习1997 → 2016人写评估函数 → 自我博弈+强化学习

第三道关口是本章真正的论点:深蓝战胜卡斯帕罗夫靠的还是"搜索+人写的评估", AlphaGo 靠的是"自己下出来的数据"——机器获取数据的数量和质量远高于人类棋谱, 这为后来的合成数据(机器自己造训练材料)提供了思路2

2. 顶层全景

1769 "土耳其人":柜子里藏人,欧洲巡演几十年后被两个孩子揭穿

1944-50 冯诺伊曼-摩根斯顿提出 Minimax;香农发表《计算机下棋程序》
(棋盘=数组,走法=子程序,局面=评估函数)

1958-62 伯恩斯坦第一款全局程序(每步 8 分钟);Kotok-McCarthy

1966-67 美苏电报赛 3:1;德雷弗斯输给 MacHack(1966)

1980s 专用硬件:Belle(UNIX 作者汤普森)→ 深思(许峰雄)

1996/1997 深蓝对卡斯帕罗夫:先 2:4 落败,再 3.5:2.5 登顶

2006 中国象棋程序击败特级大师;围棋仍遥不可及(组合爆炸)

2016 AlphaGo(强化学习+蒙特卡洛)→ AlphaGo Zero(零人类棋谱)
→ AlphaZero(4 小时学会人类百年的棋类技能)

图说:上半场是"算得更狠"(剪枝、专用芯片),下半场是"学得更好"
(自我博弈)。换代的分水岭是数据来源:人的棋谱 → 机器自己下的棋。

3. 核心原理

3.1 从魔术到程序

1769 年的"土耳其人"是机械 Automaton 时代的顶级魔术:柜子里总藏着一个活人棋手, 1827 年被两个孩子发现后台进出的秘密,1854 年毁于费城一场大火3它留下一课:一个时代对"机器智能"的想象,上限就是它的骗术。 连见过多丧钟的巴贝奇都研究过它,并猜测自己的分析机也能下棋——那只是猜测4

真算法始于 1950 年香农的《计算机下棋程序》:棋盘定义成二维数组,每个棋子配一个 计算所有可能走法的子程序(预先写好的小段程序),最后由评估函数给局面打分5。同一时期冯诺伊曼与 经济学家摩根斯顿在 1944 年的博弈论著作里提出了 Minimax 算法6

评估函数是什么?一句话:把"这个局面好不好"压缩成一个数。子力、位置、机动性…… 按权重加权求和。它的权重是"人喂给机器的判断"——记住这一点,3.5 节 AlphaGo 的 革命性才有对照物:那是把"人写判断"换成了"机器自己学判断"。

3.2 Minimax 与博弈树:替对手想的算法

Minimax 解决的问题是:你走一步,对手会还一手——怎么在"对手也不傻"的前提下 选当前最优? 做法:把"我走、他走、我再走……"的所有分支展开成一棵博弈树, 从叶子往根算:轮到我选的层取最大分(我想要高分),轮到对手的层取最小分 (他想让我低分)。两层交替,一路向上,根节点的值就是"假设双方都不犯错的结局"7

代价:树的规模随深度指数增长。 原书以象棋为例的量级感受: 分支因子约 30-40,深算四五步就是百万级节点——而选手 1972 年的国际象棋大师 一步要考虑的远不止这个。穷举很快不可行,于是需要两件武器:剪枝更快的硬件

3.3 主走查:α-β 剪枝,用对手的坏消息省掉整棵子树

麦卡锡提出、纽厄尔-司马贺-肖在 JOHNNIAC 上率先实现的 α-β 剪枝,是搜索效率的 第一次跃迁:原书给出的量是——平均而言,同样的算力条件下,α-β 剪枝比原始 Minimax 搜索的树深度大一倍,即向前多看一步8

它的原理拿一棵三层小树走一遍(树的分值是为演示编的):

我方(A,取 max)→ 对手(B,取 min)→ 叶子(评估函数打好的分)

A(我)
/ \
B1(min) B2(min)
/ \ / \
3 5 2 ?(还没算)

第 1 步:算完 B1 的两个孩子 → B1 = min(3,5) = 3
第 2 步:开始算 B2 的第一个孩子 = 2
——此时 A 站在我方视角已经知道:
走 B2 这条线,对手至少能把我压到 2(他还能选更小的)
而走 B1 这条线,我已稳拿 3
第 3 步:剪枝!B2 的第二个孩子(那个"?" )不用算了。
因为无论它是多少,B2 = min(2, ?) ≤ 2 < 3,
我永远不会选 B2。整棵子树被丢弃。

图说:α-β 剪枝不改变结果,只省掉"已知无用"的搜索。
直觉:一旦发现某条路的上限比已走过的路更差,连验证都不必。
剪掉的枝越多,省下的算力越多——省下的算力又可以多看一层。

9

α-β 的哲学意义超出下棋:它证明"穷举式思考"里大量分支是可以被逻辑判死的—— 聪明不在算得多,在于早知道哪些不用算。 这是符号派最优雅的胜利之一; 也是 3.5 节的反面:AlphaGo 时代,这种"按逻辑提前判死分支"的做法,被"神经网络估分+随机采样(随机抽大量对局取平均)" 替代了。

3.4 从 8 分钟一步到深蓝:硬件路线的二十年

第一款能走完全局的程序(伯恩斯坦,1958)每走一步要 8 分钟, "随便会走几步棋的人就能击败这款程序"10。之后二十年是军事竞赛式的追赶: 1966-67 年苏联 ITEP 的 M20 程序通过电报与斯坦福的 Kotok-McCarthy 赛了四局, 3:1 取胜;1967 年格林布拉特的 MacHack 拿到 1400 积分—— 相当于不错的高中生棋手水平,还是 ARPANET 上最早的网游11

硬件专用的路线在 80 年代定型:贝尔实验室的 Belle(发明人之一是 UNIX 的作者 汤普森)成为第一个"大师"级机器棋手——1982 年它在肯尼迪机场被美国海关扣押, 理由是终端里含对苏禁运的芯片,交了 600 美元罚款才赎回12一台下棋机被当军火, 是对"算力即国力"最荒诞也最精确的注脚。

高潮是许峰雄的 ChipTest→深思→深蓝链条:1989 年"深思"成为第一个特级大师级机器 棋手;1996 年深蓝首战卡斯帕罗夫 2:4 落败(但赢了第一局);1997 年再战, 深蓝 3.5:2.5 获胜,成为第一个战胜在任世界冠军的机器。卡斯帕罗夫的评价 从 1995 年的"机器下棋没有洞见",翻转到 1996 年的"有几步简直像上帝下的", 再到赛后的复盘:第二局机器"经常放弃短期利益,表现出非常拟人的危险感"13

深蓝团队自己的态度值得一记:他们不认为机器有智能——坎普尔说这不是智能, 全队都不是 AI 出身,还在学会上和 AI 教授结梁子14"赢了棋"与"承认这是智能", 在 1997 年还是两件事——第 08 章会看到,这个裂缝到 ChatGPT 时代被重新撕开。

3.5 围棋为什么难:蒙特卡洛,用随机代替穷举

国际象棋攻破后,围棋的棋子多、组合可能性远超,画出博弈树再跑 α-β 剪枝 "不太经济"15。突破口是蒙特卡洛方法。原书用最经典的教学例子解释它: 在一个正方形里贴边画一个圆,向正方形随机扔沙粒,数落在圆里的比例, 乘以正方形面积就是圆面积16

搬到下棋:随机模拟对弈双方走棋,模拟次数足够多时,每个落子点的获胜频率就逼近 真实胜率——挑频率最高的点落子16。次走查(数值为演示编的):

轮到黑棋,候选落点 4 个。对每个候选点:
让"纯随机水平"的黑白双方从该局面往下随机走完 1000 局
候选 A:黑赢 620 局 → 胜率 62%
候选 B:黑赢 550 局 → 55%
候选 C:黑赢 480 局 → 48%
候选 D:黑赢 300 局 → 30%
→ 黑棋选 A 落子。
模拟局数越多,胜率越准;但每多一千局,就是多一千次模拟对弈的计算。

蒙特卡洛的智慧在于承认"算不完",用统计频率换确定的答案。 但纯随机模拟的棋力很低, 2016 年之前的围棋程序仍逊于人类顶尖——直到把两样东西接上: 用神经网络代替"纯随机"来模拟走棋(走得更像人),用强化学习自我博弈来生成 训练数据(不再依赖人类棋谱)——这就是 AlphaGo17

3.6 AlphaGo 与 AlphaZero:数据来源的革命

原书把 AlphaGo 的意义钉在强化学习上:"谷歌 DeepMind 的围棋程序 AlphaGo 是 强化学习最早的工业级应用",团队里有萨顿的 4 个学生,包括首席科学家席尔瓦18

真正的换代是数据来源:

代际数据来源意义
AlphaGo(2016)人类棋谱起步,再自我对弈站在人类积累上
AlphaGo Zero完全摆脱人类棋谱,零人类知识从随机落子自学到超人类
AlphaZero方法推广到国际象棋、将棋等4 小时学会人类花百年掌握的棋类技能19

"零人类知识"这一步的深层含义原书点得很准:机器获取数据的数量和质量远高于 人类棋谱——这为后来的"合成数据"提供了一些思路2。第 10 章讨论大模型数据墙 时,这条线会再次出现:棋盘是规则封闭的小世界,自我博弈可以无限造数据; 语言不是,所以语言模型需要人类文本——这是"经验时代"与"人类数据时代"的分界

3.7 一个回环:图灵测试最初测的是下棋

原书在本章结尾埋了一个精巧的回环。图灵 1950 年《计算机与智能》定义的"模仿游戏" (图灵测试)考的是语言;但 1948 年他离开 NPL 前写的内部报告《智能机器》的结尾, 已经定义了模仿游戏——只不过当时模仿游戏考的不是语言能力,而是下棋能力。 原书的解读:"到了 1950 年,图灵已经意识到语言是比下棋更加通用的智能能力。"20

两百年走成一个环:从"会下棋才算智能"出发,到"下棋不算智能"收场—— 不是下棋变容易了,是人类对智能的定义被机器一步步逼着上移。

4. 作者的判断与证据

史实层:土耳其人魔术的揭穿过程、深蓝两战的比分、Chinook 与廷斯利的对局 (1992 人胜;1994 廷斯利赛中确诊胰腺癌去世;2007 年《科学》证明跳棋先手和棋)、 Belle 被海关扣押,均有一手来源(原书给出许峰雄自传、Newborn 的技术史)。

传说与轶事层(原书自己的标注):拿破仑 1809 年与"土耳其人"对局, "有好恶者把棋谱记录在案"——棋谱存在,对局轶事的渲染成分读者自辨3。 卡斯帕罗夫"像上帝下的"是他本人的原话,有采访来源13

作者观点层:本章标题"机定胜人,人定胜天"是作者的二元判词——机器赢了棋, 人借机器变得更强。史实支撑是深蓝之后职业棋手更多依赖计算机训练, 年轻棋手更快达到高积分,卡尔森式"像计算机的下法"成为新常态21

判断(我们的,不是书里的): 机器淘汰的是"人机对抗"这个赛道,放大的是"人机协作"这个赛道——深蓝之后,职业棋手更多用机器训练,年轻棋手更快到达高积分。 如果错,会错在: 若有一代顶尖棋手完全不靠机器训练也达到同等水平(比如传统师徒体系的延续),则"放大协作"的功劳就不能记在机器名下。

5. 边界与局限

  • 深蓝与 AlphaGo 不可比:前者是"搜索+人写评估函数"的蛮力巅峰, 后者是"学习+自我博弈"的方法换代;说"深蓝早就赢了,围棋只是算力问题"是常见误读。
  • 本章不展开 AlphaGo 的网络结构(策略网络/价值网络/MCTS 的耦合),原书只在 第 6 章给了谱系;要机制细节需另配资料。
  • "4 小时学会人类百年"的参照物:AlphaZero 训练用的是专用 TPU 集群; 4 小时背后是上万次并行自我对弈——这个算力参照原书未给,引用时别把 4 小时 理解成一台笔记本。
  • 中国象棋与国际象棋的难度之辨:原书明确说"一些外行认为中国象棋更难,其实非也", 落后只是因为没人投入22——纠正一个流行误解。

6. 可带走的

  1. 下棋是 AI 的体温计:每个时代的最强搜索技术,都先在下棋上现形;
  2. 评估函数 = 把"局面好不好"压成一个数;深蓝之前的机器智能上限, 就是人写评估函数的水平;
  3. Minimax = 替对手想一层,他取最小我取最大;博弈树指数膨胀, 这是所有棋类 AI 的共同敌人;
  4. α-β 剪枝:发现某条路上限已输,整棵子树连验证都不必—— 同样算力多看一倍深;它也示范了符号派的优雅:用逻辑直接判死无用分支;
  5. 蒙特卡洛 = 用随机模拟的频率换确定的答案;"算不完"的问题先换问法, 再谈求解——这个思想后来统治了围棋和整个近似计算;
  6. 1997 深蓝胜卡斯帕罗夫兑现了 1957 年的预言,比许诺晚了 40 年(第 01 章的主走查); 而深蓝团队不认为那是智能——"赢了"与"智能"脱钩自此始;
  7. AlphaGo 的换代点是数据来源:人类棋谱 → 自我博弈;"零人类知识"的 AlphaGo Zero 在规则封闭的世界里无限造数据,这是"合成数据"思路的源头;
  8. 图灵测试的初版考的是下棋(1948),1950 年才改成语言——智能的定义 被机器的进步逼着从棋盘挪向语言,这条上移曲线至今没有停;
  9. 人定胜天的另一面:深蓝之后职业棋手靠机器训练,整体水平不降反升—— "机器淘汰人"在棋盘上从未发生,发生的是"不用机器的棋手被淘汰"。

7. 原文地图

主题原书章原文位置
图灵"下棋需要智能"第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:8(搜「Chess requires intelligence」)
土耳其人与揭穿第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:16(搜「土耳其人」) · text/11-ch07.txt:28(搜「假货」) · text/11-ch07.txt:32(搜「施伦伯杰」)
拿破仑对局第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:22(搜「拿破仑」)
巴贝奇与分析机第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:38(搜「巴贝奇」)
图灵 1947 无机时、两步将死第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:44(搜「机时」) · text/11-ch07.txt:49(搜「两步将死」)
塞缪尔自学习跳棋第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:54(搜「塞缪尔」)
Chinook 与廷斯利、跳棋和棋第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:58(搜「Chinook」) · text/11-ch07.txt:68(搜「和棋」)
Minimax 与香农评估函数第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:76(搜「Minimax」) · text/11-ch07.txt:92(搜「评估函数」)
博弈树指数增长第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:97(搜「博弈树」)
α-β 剪枝与深度大一倍第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:99(搜「α-β剪枝」) · text/11-ch07.txt:105(搜「大一倍」)
伯恩斯坦 8 分钟一步第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:108(搜「伯恩斯坦」) · text/11-ch07.txt:111(搜「随便会走几步棋」)
美苏电报赛 3:1第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:122(搜「电报」) · text/11-ch07.txt:122(搜「3:1」)
MacHack 与德雷弗斯第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:127(搜「MacHack」) · text/11-ch07.txt:128(搜「德雷弗斯」)
Belle 被海关扣押第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:180(搜「Belle」) · text/11-ch07.txt:181(搜「没收」)
弗雷德金奖金第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:186(搜「弗雷德金奖金」)
许峰雄、ChipTest→深思第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:193(搜「许峰雄」) · text/11-ch07.txt:209(搜「深思」)
深蓝两战比分、"像上帝下的"第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:216(搜「深蓝」) · text/11-ch07.txt:218(搜「像上帝」) · text/11-ch07.txt:225(搜「拟人」)
深蓝团队不认为机器有智能第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:237(搜「坎普尔」) · text/11-ch07.txt:239(搜「梁子」)
棋手靠机器训练、卡尔森第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:230(搜「教练」) · text/11-ch07.txt:234(搜「卡尔森」)
中国象棋不比国际象棋难第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:245(搜「其实非也」)
围棋组合爆炸、蒙特卡洛第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:251(搜「蒙特卡洛」) · text/11-ch07.txt:252(搜「圆的面积」) · text/11-ch07.txt:256(搜「挑概率最大的地方落子」)
AlphaGo 是强化学习工业级应用第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:260(搜「工业级」) · text/11-ch07.txt:264(搜「席尔瓦」)
不依赖人类棋谱、合成数据第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:267(搜「人类棋谱」) · text/11-ch07.txt:268(搜「合成数据」)
AlphaGo Zero 与 AlphaZero第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:269(搜「Zero」) · text/11-ch07.txt:272(搜「AlphaZero」) · text/11-ch07.txt:272(搜「4小时」)
1948 报告的下棋版模仿游戏第7章 计算机下棋简史:机定胜人,人定胜天text/11-ch07.txt:276(搜「模仿游戏」) · text/11-ch07.txt:280(搜「语言是比下棋」)

Footnotes

  1. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 8 段(text/11-ch07.txt:8,搜「Chess requires intelligence」)。

  2. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 267-268 段(text/11-ch07.txt:267,搜「人类棋谱」)与第 268 段(搜「合成数据」)。 2

  3. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 16 段(text/11-ch07.txt:16,搜「土耳其人」)与第 22 段(搜「拿破仑」)、第 28-32 段(搜「假货」)。原书对棋谱的表述是"有好恶者把拿破仑和'土耳其人'的对战棋谱记录在案"(第 24 段,搜「棋谱」)。 2

  4. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 38 段(text/11-ch07.txt:38,搜「巴贝奇」)。

  5. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 1 段(text/11-ch07.txt:1,搜「计算机下棋」)与第 91 段(搜「评估函数」)。

  6. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 76 段(text/11-ch07.txt:76,搜「Minimax」)。

  7. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 96-97 段(text/11-ch07.txt:96,搜「max」)与第 97 段(搜「博弈树」)。原书:"max一方的评估函数取值越高越好,min一方的则越低越好"。

  8. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 99 段(text/11-ch07.txt:99,搜「α-β剪枝」)与第 105 段(搜「大一倍」)。演示树为编造,α-β 的"边算边停"机制描述见原文第 102-104 段(搜「边画树」):"α-β剪枝术则采取边画树边计算评估函数的动态方法……树的搜索过程就停止"。

  9. 同上,α-β 剪枝机制出处;演示博弈树的分值为编造。

  10. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 108 段(text/11-ch07.txt:108,搜「伯恩斯坦」)与第 110 段(搜「随便会走几步棋」)。

  11. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 119-135 段(text/11-ch07.txt:122,搜「电报」)、第 127 段(搜「MacHack」)、第 129 段(搜「1400」)、第 131 段(搜「ARPANET」)。

  12. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 174-176 段(text/11-ch07.txt:174,搜「Belle」)与第 180-183 段(搜「没收」)。

  13. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 214 段(text/11-ch07.txt:214,搜「insight」)与第 218 段(搜「像上帝」)、第 225 段(搜「拟人」)。 2

  14. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 237-238 段(text/11-ch07.txt:237,搜「坎普尔」)。

  15. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 251 段(text/11-ch07.txt:251,搜「蒙特卡洛」)。

  16. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 252 段(text/11-ch07.txt:252,搜「圆的面积」)与第 255 段(搜「获胜概率」)。走查中的候选点与胜率为演示编的。 2

  17. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 260 段(text/11-ch07.txt:260,搜「工业级」)与第 260 段(搜「巴托」)。神经网络+自我博弈的组合见第 267 段。

  18. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 259-264 段(text/11-ch07.txt:260,搜「工业级」)。

  19. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 269 段(text/11-ch07.txt:269,搜「Zero」)与第 273 段(搜「4小时」)。

  20. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 276 段(text/11-ch07.txt:276,搜「模仿游戏」)与第 280 段(搜「语言是比下棋」)。

  21. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 230 段(text/11-ch07.txt:230,搜「教练」)与第 234 段(搜「卡尔森」)。

  22. 出处:「第7章 计算机下棋简史:机定胜人,人定胜天」第 245 段(text/11-ch07.txt:245,搜「其实非也」)。