对抗搜索与博弈树 — minimax、α-β 剪枝与蒙特卡罗
这一章讲三件事: 对手在场时「最优」怎么重新定义; 同一个最优解为什么能少算一半的树;以及不下完这盘棋, 怎么对局面给出一个可比较的分数。 读完你会明白 AlphaGo 之前人类程序的全部家底——和它们各自的死穴。
1. 这一章讲什么
对手出现后,搜索的世界观要换一次。第 2 章的世界不会害你;现在有一方 正在努力让你输。书里摆了三种立场:把对手当成非确定的环境(像对雨建模) 行不行?不行——雨没有意图,对手有1。
本章聚焦确定性、双人、轮流、完美信息、零和的博弈(象棋、围棋这一类)。 形式化与第 2 章惊人地相似:初始状态、Actions、Result,再加上两个新角色—— 终止测试 Is-Terminal 和效用函数 Utility(象棋赢 1、和 1/2、输 0)2。 规模感受一下:井字棋博弈树不超过 9!=362880 个终止节点(只有 5478 个不同状态); 国际象棋超过 10^40 个节点,物理世界造不出这棵树3。
2. 顶层全景
最优决策(算到底)
minimax:两个玩家轮流取 max/min,树底取效用
↓ 太贵:象棋 b≈35, m≈80 → 35^80 ≈ 10^123
α-β 剪枝:同样的答案,跳过「肯定轮不到我」的子树
移动顺序决定一切:完美排序 → 只看 b^(m/2)
算不完(截断搜索)
Eval 代替 Utility + 截断测试 → 启发式 minimax
评价误差的解药:静态搜索(只在安静局面打分)
视野效应:把必然的损失「拖」出搜索视野
没有好评价函数(围棋)
MCTS:不评价,直接把棋随机下完,按胜负统计
选择/扩展/模拟/反向传播 四步循环;UCT 平衡探索与利用
有骰子(随机博弈)
期望极小化极大:机会节点按概率加权
看不到对方(部分可观测)
四国军棋:信念状态+确保将死;扑克:观测力平均为何是错的
图说:纵向是「计算不够时逐级让步」;每一级都是上一级在某个真实博弈上的死因。
3. 核心原理
3.1 minimax:把「对手也最优」写进定义
游戏里 max(先手)的每一步,都必须是对 min 每一种回应的回应—— 策略天生是一棵条件树。minimax 值给「最优」下了精确的定义: 某状态的 minimax 值 = 双方都按最优走到底时,max 得到的效用。 公式只有三行:终止状态取效用;到 max 走的步取后继的 max;到 min 走的步取后继的 min4。
用一个二层树走查(原书图 5-2,数字取自书): max 有 a1/a2/a3 三个选择。a1 底下 min 面对效用 3、12、8——min 挑最小的,3; a2、a3 底下同样推出 2 和 2。max 在 3、2、2 里挑最大的,a1,值 35。
注意这个定 义里的一句潜台词:max 的最优是假设 min 也最优。 对手若不最优,你只会更好;但书里补了一个微妙面:若你确信对手计算不够快, 一个「9/10 概率让你赢、1/10 概率让你输」的冒险走法,可能好过稳稳的和局—— minimax 不帮你做这种投机6。
代价是教科书级的公式:O(b^m)。国际象棋 b≈35、m≈80,35^80≈10^1237。
3.2 α-β 剪枝:算一样的答案,看一半的树
还是上面那棵树。算完 a1(值 3)之后,轮到 a2:a2 的第一个孩子是 2。 此刻一个判断就够——2 < 3,a2 已经死了。不管它剩下的孩子是几, min 都会选 ≤2,max 永远不会来。剩下的孩子一个都不用看8。
两个参数记录「窗外发生了什么」:α = 到目前为止 max 已确保的最低收获(「至少」), β = min 已压到的最高上限(「至多」)。任何一个节点一旦对 max 比 α 差、 对 min 比 β 好,它的剩余分支立刻剪掉9。
用代 数再看一眼图 5-2:根的值 = max(min(3,12,8), min(2,x,y), min(14,5,2)) = max(3, z, 2),其中 z = min(2,x,y) ≤ 2,所以根 = 3,与 x、y 无关—— 这就是剪枝的全部分量10。
剪枝效率对看子节点的顺序极其敏感:
- 顺序完美:只看 O(b^(m/2)) 个节点,有效分支因子从 35 降到约 6—— 同样的时间,搜索深度翻倍11;
- 顺序随机:O(b^(3m/4));
- 实践配方:先试吃子、再试威胁、再试推进,加上「绝招」缓存(上一轮迭代 最好的走法先试),能把节点数压到理想值的两倍左右12。
配套一张换位表:w1,b1,w2,b2 与 w2,b2,w1,b1 通向同一个局面, 把已算过的局面值缓存起来。国际象棋里这招能再把深度扩大一倍13。
3.3 截断:用 Eval 代替 Utility
α-β 之后再深也是有限,于是把 Is-Terminal 换成 Is-Cutoff(深度到顶), 把 Utility 换成 Eval(s)——在非终止局面上估计「赢面」14。
评价函数的两种做法,书里用「两兵对一兵」残局讲清了它们的关系: 如果经验统计说这一类局面 82% 通向胜利、2% 失败、16% 和棋, 那么合理打分是期望值 0.82×1 + 0.02×0 + 0.16×(1/2) = 0.9015。 类别太多数不过来,于是退而求其次:对每个特征(局面的可测属性,如双方子力数量)单独打分再相加—— 加权线性函数。棋手几个世纪的口诀(兵 1 分、马象 3 分、车 5 分、后 9 分) 就是这个函数的系数16。书里还有一句让机器学习开发者会心一笑的话: 把学习算法用到象棋上,发现一个象确实约等于 3 个兵——几个世纪的人类经验, 几小时的机器学习就能复制17。
线性评价有两个著名副作用:
-
视野效应:黑象必死,但黑方可以用兵垫在王前、引王吃兵, 把「象被吃」拖出深度 8 的视野之外——搜索看到的只是「用两个兵换来了安全」18。 解药是单步延伸:遇到「明显唯一」的着法就多看几步。
-
对噪声(随机扰动)敏感:两个分支评分 100 与 99 ——这不该选右。
但若每个评分的标准差(典型波动幅度)是 5, — 实际上 71% 的情况左边(99)才是对的19。
静态搜索治前者:只在「没有悬而未决的吃子」的安静局面上打分20。
还有一类局面根本不用搜:开局和残局查表。开局靠人写的棋谱+统计; 残局用逆向分析从「将死」反推,王象马对王(KBNK)这种人类都头疼的残局, 计算机直接给出从任意局面的完美应对——7 枚棋子以内的全部残局表 包含 400 万亿个状态21。
3.4 MCTS:别评价了,把棋下完
围棋把上面的技术栈打崩了:开局分支因子 361,α-β 只能看 4–5 层; 子力价值这类的特征在围棋里几乎没有预测力22。
蒙特卡罗树搜索换了一个根本思路:评价一个局面,不如从它出发随机把棋下完, 看谁赢。没有 Eval,没有人工特征——游戏规则本身就是终审23。 当然「随机」有讲究:模拟策略(常由自我对弈教出来的神经网络——层层相接的简单计算件)会让 模拟里的双方走出像样的棋,否则统计出来的只是「两个醉汉谁赢」24。
MCTS 的每次迭代四步25:
- 选择:从根沿树往下走,每步用 UCT 公式挑分支,直到树外;
- 扩展:给选中的节点添一个新孩子;
- 模拟:从新孩子开始,用模拟策略下到终局;
- 反向传播:把胜负沿路径加回去——27/35 变 28/36,37/100 变 37/101。
选择公式的核心是 UCB1:
UCB1 = U(n)/N(n) + C·√( ln N(Parent(n)) / N(n) )
└─利用─┘ └──────探索──────┘
U(n)/N(n) 是这个分支到目前为止的胜率(利用);根号项在模拟次数少时很大 (探索)。C 理论上取 √2,实践里调出来——书里拿同一棵树举例:C=1.4 时 60/79 的节点得分最高,C=1.5 时冷门 的 2/11 反超26。 迭代结束后返回模拟次数最多的分支,而不是胜率最高的—— 胜 65/100 比胜 2/3 可信27。
两族的分工与合流:传统观点是围棋(分支因子高、评价函数难)用 MCTS, 象棋(评价函数好)用 α-β;但 α-β 对单点评价误差(一次估分偏离真实胜率的程度)敏感, MCTS 靠大数聚合,天然抗噪。结局是 AlphaZero 这类「B 型」程序 用自我对弈在两种棋里都到了世界冠军级28。书里也算过一笔账: 10 亿个状态预算,极小化极大看 6 层,α-β 看 12 层,MCTS 能跑 1000 万次模拟29。
3.5 有骰子与有暗牌
随机博弈(双陆棋)在树上加第三种节点——机会节点, 值 = 各骰点结果的概率加权平均,整套算法叫期望极小化极大30。 两个必须记住的坑:
- 评价函数必须是获胜概率的 线性变换,不能是任意的分数: 叶子值 [1,2,3,4] 与 [1,20,30,400] 排序相同,却会让算法选出不同的走法—— 因为机会节点要做平均,平均在乎数值本身31。
- 骰子让搜索深度崩塌:双陆棋 n=21 种点数,复杂度 O(b^m·n^m),b≈20 时 只能往前看 3 层;就算翻倍掷骰让 b 高达 4000 也一样32。
部分可观测博弈(四国军棋——你看不到对方任何棋子)用第 3 章的信念状态: 白方走完、黑方应对后,白方的信念状态含 20 种局面33。 「确保将死」定义为对每种感知序列、每种可能的棋盘状态都赢—— 这个定义强到可以算:增量信念状态搜索能找到深度 9 的必胜策略, 远超人类棋手34。还有个纯人类视角不存在的新概念:概率将死—— KBNK 残局即使看不见对方,靠随机试探也能以概率 1 将死;KBBK 只能到 1−ε35。
扑克界的流行近似「观测力平均」(把所有可能的发牌都当成已知的来平均) 被书里用一个三条路的故事拆穿了:前两天岔路口金子在左/在右你都该走 B, 第三天不知道金子在哪边,观测力平均还说走 B——但你该先探再走。 它从不收集信息、不会虚张声势,因为它假装信息总是已知的36。 Libratus 后来在 20 天无限注德州扑克里以 2500 万 CPU 小时的代价赢下四位顶尖牌手, 靠的正是超出「平均」的推断37。
3.6 主走查:α-β 到底省了几片叶子
把 3.1/3.2 的走查并排放着数叶子:
max
┌────┼────┐
a1 a2 a3
/|\ /|\ /|\
3 12 8 2 x y 14 5 2 (x、y 是原书留下的未探明叶子)
minimax:必须算完 9 个叶子 → 根 = 3,选 a1
α-β: 3,12,8 → a1=3;看到 a2 的 2 < 3 → 剪掉 x,y;
14,5,2 → a3=2 → 共算 7 个叶子,答案同样是 3
省掉的是 2 个叶子;树越深,这个比例越逼近一半。答案是同一个,过程少一半—— 这就是 α-β 的全部内容,也是它统治了四十年博弈程序的原因。
4. 作者的判断与证据
- (书内定理) 纳什之前,α-β 的正确性与最优性由 Knuth & Moore(1975) 证明,珀尔(1982)证明它在固定深度搜索里渐近最优38。
- (书内数据) 完美排序 b^(m/2)、35→6、深度翻倍;随机顺序 b^(3m/4); ProbCut 用一半时间打 64% 胜率;7 子残局表 400 万亿状态1121。
- (作者的分析判断) 「α-β 搜索选择评价分最高 的路径,所以评价函数不准时 它也不准;MCTS 依赖多次模拟的聚合,不容易受单次错误影响」39—— 这是对两族算法抗噪性的机理解释,不是定理。
- (书内局限清单,少见地诚实) 四条:评价误差、单步级推理(该按 「扩展这个节点的效用值」分配计算投入——元推理)、缺少抽象层级规划、 机器学习才刚开始融入40。第四条在今天已经完全兑现。
5. 边界与局限
- minimax 的「最优」只在与最优对手对弈时有意义;对真实对手,它甚至可能过于保守。
- Eval 的质量决定 α-β 的质量,而好的评价函数依赖领域知识或海量自我对弈。
- MCTS 的 B 型剪枝可能根本没探索到那步一招毙命的好棋——随机性既抗噪也漏关键41。
- 骰子游戏中深度截断到 3 层左右;桥牌的可能发牌有 10,400,600 种, 只能靠抽象(把「3 个 A 带小牌」当成同一手牌)与抽样硬扛42。
- 书里写于 AlphaZero 之后、大模型之 前:它说的「机器学习融入博弈搜索才刚起步」, 如今已是博弈搜索本身。
6. 可带走的
- 对手建模与不确定性建模是两件事:雨不会针对你调参数。
- 「至少 α、至多 β」两句话就能向任何人解释 α-β 剪枝。
- 剪枝效率几乎完全由访问顺序决定——先看好的,后看差的。
- 评价函数要么解释成「该类局面的期望效用」,要么解释成「胜率的线性变换」; 在带机会节点的树里,后者是硬要求。
- 能查表就别搜索:开局库+残局表把搜索预算留给中盘。
- MCTS 把「评价」外包给了游戏规则本身;UCB1 一行公式同时治利用与探索。
- 「先平均再决策」(观测力平均)会系统性漏掉收集信息的动作—— 任何决策系统里,信息的价值在于它能改变决策(第 11 章的 VPI 会把它算成钱)。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 对手≠雨 | 5 开篇 | text/10-fm.txt:2015(搜「非确定性的」) · text/10-fm.txt:5106(搜「显式地」) |
| 博弈形式化与效用 | 5.1 | text/10-fm.txt:5122(搜「 零和博弈」) · text/10-fm.txt:5139(搜「效用函数」) |
| 井字棋与象棋规模 | 5.1 | text/10-fm.txt:5153(搜「362 880」) · text/10-fm.txt:5154(搜「1040」) |
| minimax 定义与例子 | 5.2 | text/10-fm.txt:5188(搜「极小化极大值」) · text/10-fm.txt:5198(搜「3 个后继状态」) |
| 冒险走法 | 5.2 | text/10-fm.txt:5209(搜「冒险的走法」) |
| O(b^m) 与 35^80 | 5.2.1 | text/10-fm.txt:5226(搜「3580」) · text/10-fm.txt:5226(搜「10123」) |
| α-β 代数证明 | 5.2.3 | text/10-fm.txt:5302(搜「Minimax(root)」) |
| α/β 定义 | 5.2.3 | text/10-fm.txt:500(搜「至少」) |
| 移动顺序与 35→6 | 5.2.4 | text/10-fm.txt:5372(搜「O(bm/2)」) · text/10-fm.txt:1154(搜「两倍」) |
| 绝招与换位表 | 5.2.4 | text/10-fm.txt:5385(搜「绝招」) · text/10-fm.txt:5389(搜「换位表」) |
| 香农 A 型/B 型 | 5.2.4 | text/10-fm.txt:5399(搜「A 型策略」) |
| Eval 与截断 | 5.3 | text/10-fm.txt:5409(搜「Eval」) |
| 两兵对一兵 0.90 | 5.3.1 | text/10-fm.txt:5438(搜「0.82」) |
| 子力价值 | 5.3.1 | text/10-fm.txt:5444(搜「9 分」) |
| 机器学习复制经验 | 5.3.1 | text/10-fm.txt:5463(搜「几小时」) |
| 视野效应 | 5.3.2 | text/10-fm.txt:5486(搜「视野效应」) · text/10-fm.txt:5497(搜「视野之外」) |
| 静态搜索 | 5.3.2 | text/10-fm.txt:5482(搜「静态」) |
| 评价误差 71% | 5.7 | text/10-fm.txt:5904(搜「71%」) |
| 深度账本 | 5.3.3 | text/10-fm.txt:3660(搜「5 层」) · text/10-fm.txt:5532(搜「14 层」) · text/10-fm.txt:5535(搜「Stockfish」) |
| 残局逆向分析 | 5.3.4 | text/10-fm.txt:5552(搜「逆向」) · text/10-fm.txt:5557(搜「400 万亿」) |
| 围棋两难 | 5.4 | text/10-fm.txt:5560(搜「361」) |
| 模拟=规则终审 | 5.4 | text/10-fm.txt:5568(搜「模拟」) · text/10-fm.txt:1501(搜「游戏规则」) |
| 模拟策略 | 5.4 | text/10-fm.txt:5575(搜「模拟策略」) |
| 四步与计数变化 | 5.4 | text/10-fm.txt:5595(搜「选择」) · text/10-fm.txt:5610(搜「27/35」) |
| UCT/UCB1 | 5.4 | text/10-fm.txt:5615(搜「置信上界」) · text/10-fm.txt:5627(搜「1.4」) |
| 返回次数最多 | 5.4 | text/10-fm.txt:5629(搜「65/100」) |
| 三算法对比 | 5.4 | text/10-fm.txt:5646(搜「10 亿」) |
| 抗噪分析 | 5.4 | text/10-fm.txt:5654(搜「依赖于多次模拟的聚合」) |
| MCTS 漏关键招 | 5.4 | text/10-fm.txt:5665(搜「关键路线」) |
| 机会节点与 21 种点数 | 5.5 | text/10-fm.txt:5682(搜「21 种」) |
| 期望极小化极大 | 5.5 | text/10-fm.txt:5697(搜「期望极小化极大值」) |
| 线性变换要求 | 5.5 | text/10-fm.txt:5713(搜「[1, 2, 3, 4]」) |
| 深度崩塌 | 5.5 | text/10-fm.txt:5728(搜「3 层」) |
| 四国军棋信念 20 | 5.6.1 | text/10-fm.txt:5776(搜「20 种局面」) |
| 确保将死深度 9 | 5.6.1 | text/10-fm.txt:5785(搜「确保将死」) · text/10-fm.txt:5791(搜「深度高达 9」) |
| 概率将死 | 5.6.1 | text/10-fm.txt:5794(搜「probabilistic checkmate」) · text/10-fm.txt:5549(搜「KBNK」) |
| 观测力平均错误 | 5.6.2 | text/10-fm.txt:5845(搜「一桶金子」) · text/10-fm.txt:5855(搜「信念状态」) |
| Libratus | 5.6.2 | text/10-fm.txt:5882(搜「Libratus」) · text/10-fm.txt:5887(搜「2500 万」) |
| 四条局限 | 5.7 | text/10-fm.txt:5901(搜「局限性」) · text/10-fm.txt:5918(搜「元推理」) |