12 · 评估函数与棋类 AI

⏱ 34 分钟 ｜ ⭐ 搜索总得停下来；停下来那一刻拿什么给局面打分，决定了引擎的棋力

🎯 一句话

搜不到终局就得在半路给局面估分：评估函数是一串特征的加权和。 ⚠️ 但固定深度会带来地平线效应 —— 程序把坏消息推到搜索深度之外，然后以为它不存在。

🛑 一、Shannon 1950 的两条路

第 10 章算过国际象棋是 $35^{100} \approx 10^{154}$，第 11 章的 α-β 把它砍成 $35^{50}$ —— 还是毫无可能。 所以讲义在「关键思想」里单列一条：有限地平线 + 近似评估（Zuse 1945、Wiener 1948、Shannon 1950）。Shannon 同时给了两条路：

⭐ 现代引擎两个都要：α-β 全宽度搜到 $d$ 层（A），再对「危险」的分支单独往下延伸（B）。

📊 二、评估函数：一串特征的加权和

$$\text{EVAL}(s) = \sum_i w_i\, f_i(s)$$

讲义给的国际象棋特征分四类：

KnightCap 用了 2000 个特征。⭐ 为什么 2000 个还能算得飞快？讲义的解释是稀疏： 任一局面下绝大多数特征都是 0（后同时只能待在 64 格里的一格）。 再加上增量更新 —— 走一步只有少数几个特征会变，没必要重算整个和。

⭐ 权重不必手调，可以用强化学习学出来（讲义原话）。这条线在强化学习基础整套 16 章里讲透了，本板块不重写。

⭐⭐ 一个容易忽略的性质：对 Minimax，只有序重要

任何单调变换都不改变 Minimax 选出的走法（讲义："move choice is preserved under any monotonic transformation of EVAL"）。 确定性博弈里的收益是序数效用 —— 只要排序对，数值本身怎么缩放都无所谓。⚠️ 这条舒服的性质，下一节遇到骰子就没了。

👻 三、地平线效应

⚠️ 定义：坏事就发生在搜索深度之外那一步。 程序找到一串拖延的走法，把坏消息推到地平线以外 —— 于是它「看不见」了，评估函数还挺高兴。

一个标准场景：黑方有个象必然要被吃掉，怎么都保不住。程序搜到深度 8，发现可以先用兵去将军 —— 白方必须应，消耗掉两层；再送一个兵将军，又两层。等深度用完，象还在盘上，评估函数给了高分。 代价是白送三个兵，而象下一步照丢不误。

⭐⭐ 关键认识：这是「固定深度」本身的病，不是评估函数写得不好。 深度从 8 加到 10，只是把地平线往后挪两层，程序会多送两个兵。

治法：静默搜索

静默搜索（quiescence search）：到达深度上限时先看一眼局面安不安静 —— 有没有吃子、将军、后被攻击？ 不安静就继续往下搜，但只搜这些强制性走法，直到平静了再评估。 讲义原话：「如果存在危险局势（例如后正被攻击），就延伸搜索深度。」

⭐ 直觉：评估函数只在静态局面上可信。 兑子兑到一半的时候给盘面打分是没有意义的 —— 你数的子力，下一步就要变。

讲义说现代象棋程序依赖三样东西：静默搜索、置换表、剪枝启发式 —— 后两样都在第 11 章。

🎲 四、期望极小极大：骰子进来了

西洋双陆棋、大富翁这类博弈里，树上多一层 CHANCE 节点（掷骰子、洗牌、发牌）。 讲义的改法只有一行：CHANCE 节点返回子节点值的平均（按概率加权）。

$$V(\text{chance}) = \sum_k P(k)\, V(\text{子}_k)$$

⭐⭐ 现在精确值要紧了

拿上图做实验。把评估函数换成 $\sqrt{\cdot}$ —— 它是严格单调递增的，按第二节的说法不该影响任何东西：

同一棵树，同一个单调变换，走法翻了。

⭐⭐ 确定性博弈里 EVAL 是序数的（排序对就行）； 随机博弈里 EVAL 必须是基数的 —— 讲义的原话是 EVAL 应当正比于期望收益。

这就是为什么 TD-Gammon 的网络输出被明确解释成获胜概率，而不是随便一个「越大越好」的分数。

⚠️ 代价：骰子把分支因子乘上去了。双陆棋每回合有 21 种骰子结果，复杂度变成 $O\big((bn)^m\big)$，实际只能搜 2–3 层。 α-β 也能改编到随机博弈上，但讲义说了前提：评估必须有界。

🕹 五、棋类 AI 简史

三条值得单独记：

深蓝（1997） 六局击败卡斯帕罗夫。传统上电脑开局强（开局库）、残局强（深搜）， 人类靠中局「打开局面」抬高分支因子取胜 —— 卡斯帕罗夫试了，但深蓝速度够快扛住了。 ⚠️ 现在普通 PC 上的引擎已经明显强于深蓝。

Chinook 的残局库覆盖 8 子以下的全部 443,748,401,247 个局面（后扩到 10 子、38 万亿）。 2007 年 Schaeffer 证明跳棋双方最优下必和，方法是增量地把博弈树填出来、跳过那些大概率会被剪掉的分支， 算了几个月后收敛到「真实的（剪枝后的）树」的骨架 —— ⭐ 第 11 章的剪枝在这里直接变成了证明工具。

⭐ TD-Gammon（Tesauro）：196 个输入、20 个隐藏单元、1 个输出，输出就是获胜概率。 Tesauro 训了两个网络对比 —— EP 网（学人类专家偏好，监督学习）和 TD 网（自我对弈，TD 学习），TD 网赢了。 再加上三步前瞻（期望极小极大）和手工特征，1995 年成为世界最强双陆棋手。

⭐ 讲义解释了它为什么在双陆棋上行得通：骰子的随机性逼着自我对弈去探索大得多的搜索空间。 而在国际象棋这种确定性博弈上，直接 TD 学习效果很差 —— 必须把学习和树搜索结合起来。

TreeStrap（Veness 2009）就是那个结合：非叶节点也一起更新（包括没被选中的走法）， 而且 ⭐⭐ α-β 造成截断时那个上界或下界照样能拿来当训练目标 —— 正是第 11 章说的「被剪节点的值退化成一个界」。 它第一次证明国际象棋可以从随机初始权重、纯自我对弈练到大师级。

🌲 六、MCTS 和 α-β 的分工

围棋分支因子超过 300，而且静态评估极难写（一块棋是死是活往往要算到很深才知道），α-β 那条路走不动。 MCTS 换了思路：不穷举，采样 —— 树随机地一点点长出来，走一小段之后把剩下的棋随机下完，用大量对局的胜率统计代替评估函数。

⭐ 分工一句话： α-β = 穷举 + 剪枝 + 一个写得出来的评估函数；MCTS = 采样 + 统计，不需要评估函数。 分支小、评估写得出来的地方（国际象棋）α-β 至今仍最强；分支 300 以上、评估难写的地方（围棋）MCTS 赢。

AlphaGo 是 MCTS + 深度网络（先学人类棋谱再自我对弈），AlphaZero 完全靠自我对弈。

⭐⭐ 最后一个扣子：自我对弈为什么讲得通？ 因为围棋、象棋、将棋都是二人零和博弈 —— 第 13 章证明了这类博弈的值 $v$ 唯一、且「最优策略」与对手打什么无关， 两边都在逼近同一个确定的东西。⚠️ 换成非零和（谈判、多方拍卖），「自我对弈会收敛到什么」重新变成没有答案的问题。

🔗 这一章连到哪里

✅ 检查点

1. Shannon 1950 给的 Type A 和 Type B 各是什么？现代引擎用哪个？
2. 评估函数长什么样？KnightCap 有 2000 个特征，为什么还算得飞快？对 Minimax，它的精确值要紧吗？
3. 什么是地平线效应？举一个具体场景。为什么说「加深一层」治不好它？
4. 静默搜索怎么做？背后的直觉是什么？
5. 手算：左 CHANCE 节点两个等概率叶子是 10 和 0，右边是 4 和 4。MAX 选哪支？把评估函数换成 $\sqrt{\cdot}$ 之后呢？这说明了什么？
6. Chinook 的残局库覆盖了多少个局面？Schaeffer 证明跳棋必和用的是什么方法？
7. TD-Gammon 为什么在双陆棋上成功，而直接 TD 学习在国际象棋上不行？
8. α-β 和 MCTS 的分工是什么？自我对弈能收敛，底下垫的是哪条结论？

🛑 可以停在这里

⚡ 走神救援

α-β 把象棋从 $35^{100}$ 砍到 $35^{50}$，还是搜不完，所以必须半路停下来估分 —— 这就是 Shannon 1950 的「有限地平线 + 近似评估」。他给了两条路：Type A（固定深度、全宽度）和 Type B（只挑有希望的几步、搜得更深），现代引擎两个都用。评估函数是特征加权和 $\sum w_i f_i(s)$：子力（后 9 / 车 5 / 马 = 象 3 / 兵 1）、位置、交互、兵型机动性。KnightCap 有 2000 个特征却算得飞快，因为任一局面下绝大多数特征是 0（稀疏）＋增量更新。⭐⭐ 对 Minimax，精确值不要紧、只有序要紧 —— $1,2,2,4$ 和 $1,20,20,400$ 选出同一支，收益是序数效用。⚠️ 地平线效应：坏事就在深度之外那一步，程序用一串拖延走法把它推出去 —— 黑象必丢，它先送兵将军消耗层数，深度用完时象还在盘上、评估函数给高分，代价是白送三个兵而象照丢。⭐⭐ 这是固定深度本身的病，加深两层只是把地平线挪两层。治法是静默搜索：到深度上限先看局面安不安静（吃子、将军、后被攻击），不安静就只沿强制走法继续搜，直到平静再评估。⭐ 直觉：评估函数只在静态局面上可信。期望极小极大给树加一层 CHANCE 节点，值取子节点的概率加权平均。⭐⭐ 这里精确值突然要紧了：左支 $0.5\times10+0.5\times0=5$、右支 $4$，选左；把 EVAL 换成 $\sqrt{\cdot}$（严格单调递增！）后变成 $1.58$ 对 $2.00$，走法翻了。所以随机博弈里 EVAL 必须正比于期望收益 —— 这正是 TD-Gammon 输出被解释成「获胜概率」的原因。双陆棋每回合 21 种骰子结果，实际只搜 2–3 层。简史里三条：1997 深蓝（卡斯帕罗夫想靠打开局面抬高分支因子，被速度扛住）；2007 Chinook 用 443,748,401,247 个 8 子残局 + 「增量填树、跳过会被剪的分支」证明跳棋必和（⭐ 剪枝变成了证明工具）；TD-Gammon（196 输入 / 20 隐层 / 1 输出＝获胜概率，TD 自我对弈网打赢了监督学专家偏好的网）。⭐ 它在双陆棋行得通是因为骰子逼着自我对弈探索大得多的空间；确定性博弈得靠 TreeStrap（连 α-β 截断产生的上下界都拿来训练，正是 11 章那个「值退化成界」）。最后 α-β 与 MCTS 的分工：前者穷举 + 剪枝 + 写得出来的评估函数，后者采样 + 统计、不需要评估函数；象棋归前者，围棋归后者。⭐⭐ 自我对弈之所以讲得通，垫在底下的是零和的极大极小定理：值唯一、最优策略与对手无关。非零和就没这个保证。

下一节 👉 13-CSP是什么.html