12 · 评估函数与棋类 AI
⏱ 34 分钟 | ⭐ 搜索总得停下来;停下来那一刻拿什么给局面打分,决定了引擎的棋力
本章目标:分清“估分”“搜出来的值”和“已经证明的胜负”。
先看一个局面怎样打分,再看有骰子后为什么不能随便改分数。历史与进一步的学习方法可以分次看;页面时长不是阅读期限。
🎯 一句话
搜不到终局,就在搜索边界估计局面好坏;这个估计能帮助选招,但不是胜负证明。
评估函数可以是特征加权和,也可以是非线性神经网络。它和搜索配合:搜索展开候选走法,评估给边界局面打分,结果再沿树传回。
先记一个风险:看得有限,又把尚未结束的交换估错,就可能把坏结果拖到视野之外。 这叫地平线效应。
🕰️ 一、Shannon 1950 的两条路
全部算完太贵,所以要决定“算到哪里停”和“停下后怎么估”。
沿用第 10 章的粗略模型:每层 35 个选择,向下 100 层,叶节点量级为 $35^{100}\approx 2.6\times10^{154}$。这是固定分支的教学估算,不是国际象棋所有合法对局的精确计数。
第 11 章的 α-β 在理想走法排序下,可把深度指数约减半;这里仍有 $35^{50}\approx1.6\times10^{77}$ 的量级。一般排序没有这个最好情况的保证。
| 搜索思路 | 怎样分配计算 |
|---|---|
| Type A | 对给定深度内的合法走法做全宽度搜索 |
| Type B | 用棋类知识挑选更有希望的分支,把预算用在更深处 |
这是 Shannon 1950 年论文中的两类思路,不是“现代引擎只能二选一”。实际引擎可结合走法排序、选择性延伸、剪枝、评估等;不同剪枝是否保持原树结果,要看条件。历史入口见 Computer History Museum 的早期理论资料。
现在可以先往下:我们就练“边界上怎样估分”。
📊 二、评估函数:先从特征加权和学起
约定:本节所有分数从 MAX 方看,越高越有利。 终局直接按胜负规则赋值;尚未终局才使用近似评估。不能同一棵树里有时给白方打分、有时给轮到的一方打分而不转换符号。
一种容易理解的线性评估是:
$$\operatorname{EVAL}(s)=\sum_i w_i f_i(s)$$
s 是局面;fᵢ 是从局面提取的第 i 个特征;wᵢ 表示这个特征对分数的影响。先算每项贡献,再相加。
- 子力:先用后 9、车 5、象和马各 3、兵 1 作粗略示意,计算双方数量差。
- 位置:例如马在某个格子的奖励,来自位置表,不是“所有位置都是固定小数”。
- 交互:某个子被保护、被攻击,或两个子协同造成的影响。
- 其他:兵型、机动性、王的安全等。单位必须统一,不能把任意比例的分数直接相加。
可手算的教学局面:其他子力差相互抵消,MAX 多一车、少一象,位置项暂记 −0.5。那么子力项为 5 − 3 = 2,总分为 1.5 个兵的单位。
这不是实际棋局的胜负判断:如果 MAX 下一步会被将死,“多一车”也没用。终局胜负必须高于普通子力比较,王也不能简单定一个普通棋子的交换价。
为什么特征多,仍可能算得快?
用 64 个指示量表示“己方后在哪个格子”,在恰有一个后的局面里,只有一个量为 1,其余为 0。这说明了稀疏表示;升变产生多个后时,不能仍说“永远只有一个非零项”。
一步棋通常只改变部分特征,可以增量更新。注意:有稀疏特征,不等于所有特征都稀疏,也不保证整个评估器一定快。
KnightCap 是用 TDLeaf 与搜索结合学习线性评估参数的历史实例;原文报告的是具体训练实验,不宜背一个没有对应版本依据的“2000 个特征”。想看学习机制,接到强化学习基础;原始实验见 Baxter 等人的论文。
⭐ 对固定 Minimax 树,保留严格次序有什么用
先固定一棵只有 MAX / MIN 节点的树:MAX 在根,两个孩子都是 MIN。 左边叶子 1、2;右边叶子 2、4。
| 看哪一层 | 原分数 | 变换后 |
|---|---|---|
| 左边叶子 | 1、2 | 1、20 |
| 右边叶子 | 2、4 | 20、400 |
| 左 MIN | 1 | 1 |
| 右 MIN | 2 | 20 |
| 根选择 | 右 | 右 |
最右列用同一个严格递增映射把 1→1、2→20、4→400。每一步取最大或最小的次序都没有变,所以选择仍为右。
条件别丢:固定搜索树、统一变换所有叶子评分(含终局值)、变换严格递增,并使用一致的平局处理。递减变换会反转偏好;仅非递减的变换可能制造新的平局。
这讲的是固定 Minimax 树的保序性质。实际引擎若依赖分数幅度决定剪枝或扩展,变换后连搜索树都变了,就不能用它保证走法不变;也不能把它直接推广到随机收益的比较。
👻 三、地平线效应
坏结果可能在搜索边界之外,不一定恰好是下一步。 如果边界评估没有把它计入,程序可能选择“拖延损失”,甚至为拖延再付出代价。
保留一个象棋直觉:假设一个象终究保不住,送兵将军能暂时迫使对方应将,推迟吃象。只在象还没丢的时刻数子力,可能误把拖延当救援。
下面是人为规定后果的教学对照,不是一份给定棋谱的强制变化证明。用兵为单位,象记 3;短期评估只数已损失子力。
| 选择 | 截断估计 | 最终损失 |
|---|---|---|
| 立即丢象 | −3 | −3 |
| 先送一兵拖延 | −1 | −6 |
拖延这一支的设定是:后续还会丢两兵和一个象,加上已经丢的一兵,最终损失共 6。
浅看时 −1 好于 −3;把后续结果算进去后,−3 好于 −6。问题出在有限搜索和边界估分共同漏掉了后果。
加深搜索有时能解决眼前这个例子,但新的战术也可能出现在更远处。不能断言“加深两层一定多送两个兵”,也不能说评估函数质量完全无关。
缓解方法:静默搜索
普通搜索到深度上限时,先别急着给尚未结束的战术交换下结论。
静默搜索通常继续看一部分战术走法,例如吃子;若正在被将军,必须考虑合法的应将走法。吃子不全是强制走法,“后被攻击”也不代表所有实现都会自动扩展同一组分支。
可以这样理解一个常见框架:
- 先检查终局;终局使用胜负结果。
- 未被将军时,可把静态评估作为“不继续战术交换”的基线候选。
- 再搜索选定的战术走法,把回应的后果纳入估计;被将军时不能用“原地不动”逃避应将。
这能减轻兑子进行到一半造成的误判,但不是彻底解决地平线效应。实现仍需处理重复局面、搜索预算和剪枝条件。
第 11 章的置换表与剪枝帮助复用搜索和分配预算;边界估分、静默搜索、缓存和剪枝是配合关系,不是互相替代。
🎲 四、期望极小极大:骰子进来了
MAX 挑自己最有利的,MIN 挑对自己最不利的,CHANCE 则按概率平均。
例如双陆棋掷骰子会改变可用走法。这里假设局面可观察、随机结果的概率已知;若是看不到的手牌,还需要处理信息集或信念,不能只添加一个 CHANCE 节点就算解决。
$$V(\text{chance})=\sum_k p_k V_k$$
pₖ 是第 k 个结果的概率,非负且总和为 1;Vₖ 是该结果之后的子节点值。它们都从同一方的收益口径计算。
这是只包含 MAX 与 CHANCE 的最小片段;完整的期望极小极大树还可以包含 MIN 层。
逐支算:左边 0.5 × 10 + 0.5 × 0 = 5;右边 0.5 × 4 + 0.5 × 4 = 4,因此 MAX 选左。
⭐ 现在精确值要紧了
保留叶子的排序,不再足以保留“平均以后”的排序。 将上图所有非负叶子值开平方:
| 比较对象 | 原始分数 | 开平方后 |
|---|---|---|
| 左支期望 | 5 | 约 1.58 |
| 右支期望 | 4 | 2 |
| MAX 选择 | 左 | 右 |
左支变成 0.5 × √10 + 0.5 × √0 ≈ 1.58;右支变成 0.5 × 2 + 0.5 × 2 = 2。开平方保留单个分数的高低,却改变了不同结果之间的差距,因此选择翻转。
如果目标是期望得分,叶子就要使用相容的得分或效用尺度。不能把任意“越大越好”的分数都当成获胜概率。
可以怎样改尺度?骰子又增加多少计算?
正仿射变换可以保留选择:统一用 aV + b 替换叶子值,其中 a > 0。由于每个机会节点概率之和为 1,其期望也变成 aE[V] + b;MAX、MIN 的次序同样保留。开平方不属于这一类变换。
双陆棋的一对公平六面骰有 36 个等概率有序结果,合并次序后是 21 种组合:
- 6 种对子,每种概率 1 / 36。
- 15 种不同点数,每种概率 2 / 36。
- 不能给这 21 种都分配 1 / 21。
粗略设每次随机分支有 n 种,每个结果下有 b 个动作,连续展开 m 组“随机结果 + 决策”,规模为 $O((nb)^m)$。这是给定模型的复杂度估计;不是所有随机博弈都只能搜索 2–3 层。
要在机会节点剪枝,需要用未搜索部分的合法上下界推断总期望范围。例如:已知半数概率对应值 10,其余半数的值在 [0,10],那么总期望在 [5,10]。若 MAX 另有价值 11 的选项,这一支就不必精算。
没有这种界,不能只看到一个差结果就照搬普通 α-β 截断。 少量尚未看到的大收益,仍可能改变平均。
🕹 五、棋类 AI 简史:分清成果的性质
不用背一串“谁打败谁”。下面四个例子分别回答:算得快、证明结果、学会估分、用搜索教估分。
深蓝:工程系统赢得一场比赛
1997 年,深蓝在六局比赛中以 3.5 比 2.5 击败卡斯帕罗夫。它结合专用硬件、搜索、评估与棋类知识;不是单凭一个加权和,也不能把胜利简化为“中局分支多,但机器够快”。见 IBM 的深蓝记录。
赢得这场比赛不等于证明国际象棋的标准初始局面是胜、负或和。不同年代引擎的强弱比较,还需要明确版本、硬件和时限,不用“现在普通 PC 一定更强”代替证据。
Chinook:标准初始局面的和棋证明
2007 年解决的是英美式 8×8 跳棋的标准初始局面:双方最优对弈为和棋。 不是任何跳棋变体,也不是任意残局都和棋。
它结合残局数据库和前向证明搜索:先确定大量残局的精确胜负,再用有依据的搜索把初始局面连接到这些结果。剪掉分支需要证明该分支不影响结论,不是因为“大概率不会用到”就忽略它。
项目的 8 子残局库记录 443,748,401,247 个局面;2007 年求解论文入口对应的 10 子库约 39 万亿个局面。这些是数据库规模,不是要求读者记住的公式。
项目历程从 1989 年开始,中间有暂停,到 2007 年完成求解;不能说整个证明只算了几个月。这一例体现剪枝与验证的关系,而不是“训练逐渐收敛”的故事。
TD-Gammon:自我对弈学习估分
TD-Gammon 用神经网络预测局面结果,再用自我对弈中的后续预测和终局结果更新网络。 它是非线性评估函数,不属于前面那个单纯线性加权和。
Tesauro 的 1995 年文章描述了四个输出,对应白方/黑方普通获胜与 gammon 获胜,未单独建模少见的三倍 backgammon。输出再按收益口径组合,不能笼统写成“一个输出就是胜率”。
原文还区分了版本:仅用棋盘编码的实验中,40 个隐藏单元、20 万盘训练达到与监督学习的 Neurogammon 相近的水平;加入手工特征后的版本更强。1992 年介绍的 2.0 版使用两层前瞻。不要把不同版本的输入数、隐藏层、输出数和搜索深度拼成一个“固定架构”。
1995 年报道的结论是接近顶尖人类的水平,不是证明“世界第一”。这些具体条件见 Tesauro 本人的文章。
这里保留两个学习启发:
- 骰子的随机性有助于产生不同局面,但不自动保证充分探索或训练收敛。
- 监督学习专家示例和自我对弈提供不同训练信号;一个实验中的胜负不能推出哪一种学习方式永远更好。
TDLeaf 与 TreeStrap:让搜索结果帮助学习
国际象棋上的学习并非“不可能”,难点包括探索不足、战术后果和估分误差。 搜索可以提供更有用的训练信号。
TDLeaf 把 TD 学习与搜索主变化的叶节点联系起来。TreeStrap 则利用同一次搜索中多个节点的返回值,不只学习最终实际走过的一条路线。
对于 α-β 返回的界,要保留“只知道范围”的含义:若只知道值至少为 5,当前估计为 3,可以向上修正;估计为 7 时,不能假装真实答案就是 5、硬拉回去。下界与上界对应单侧约束。
Veness 等人 2009 年的 Meep 实验从随机评估权重出发,借助自我对弈与搜索获得了较强棋力。原文把在线测试表现描述为大师级范围;这是特定配置下的实测,不是任意网络、任意自我对弈都收敛的证明。见 TreeStrap 原论文。
历史补充:早期人物、机器与学习实验
以下按思想发展分组,避免把“设想”“运行的程序”“实验结果”“数学定理”混成同一种成就。
- 机械设想:土耳其行棋傀儡内部有人操纵,不是自动推理;Babbage 曾设想供人挑战的井字棋装置。不能据此声称他与 Lovelace 已共同造出该机器。参见 博物馆的机械棋手史与 Babbage 生平资料。
- 理论与程序设想:Zermelo 的 1913 年工作讨论棋类博弈的理论问题;von Neumann 的 1928 年极小极大定理和与 Morgenstern 合著的 1944 年著作属于博弈论发展,不能把年份合并成“完美棋局算法已经高效可算”。条件接到零和与极大极小。
- 有限搜索:Zuse、Wiener、Turing、Shannon 都出现在早期机器下棋的探索史中。这里重点学习 Shannon 的有限搜索与估分,而不要求背有争议的“第一个完整程序”归属。
- 运行中的搜索与学习:McCarthy 参与早期棋类搜索研究;Samuel 的 1959 年跳棋工作探索了通过学习调整评估。搜索、缓存、表示和学习可以配合,但不在本页声称哈希表、压缩、学习三者都由他首次发明。
- MENACE:Michie 在 1960 年代初用火柴盒与彩色珠子演示井字棋的学习:局面对应盒子,珠子对应可选动作,胜负反馈改变抽取倾向。它说明简单部件也能实现学习,不说明已掌握所有棋类。
- 近期里程碑:TD-Gammon、深蓝、Chinook 之后,AlphaGo(2016 年对李世石的比赛)、AlphaGo Zero(2017 年)与 AlphaZero(2017 年预印本、2018 年正式论文)体现了搜索与学习的继续结合;差别见下一节。
🌲 六、MCTS 和 α-β 的分工
不是“象棋只能用 α-β,围棋只能用 MCTS”,也不存在分支数超过 300 就自动换算法的规则。
19×19 围棋开局有 361 个落点,之后合法动作数随局面改变;高分支与复杂局面估分使分配搜索预算很重要。但算法选择还与评估质量、时间、硬件和任务有关。
| 方法 | 主要怎样使用预算 |
|---|---|
| α-β | 在 Minimax 树中用上下界排除不会影响结果的分支 |
| MCTS | 根据已有访问统计反复选择、扩展、评估并回传,集中更多模拟到有希望的分支 |
基本 MCTS 可以用 rollout:从边界局面按某种策略模拟到终局,回传结果。rollout 策略可以随机,但“MCTS 必须把剩下的棋随机下完”不是定义。
现代做法也可以用价值网络直接评估边界,用策略网络指导分配搜索;所以“MCTS 不需要评估函数”并不成立。α-β 若只搜到截断深度,通常同样需要边界评估;能搜到终局的部分则使用精确结果。
三个名字,分开记:
- AlphaGo:结合人类棋谱学习、自我对弈、网络与树搜索,早期版本还使用 rollout。
- AlphaGo Zero:训练不依赖人类棋谱,通过自我对弈学习围棋。
- AlphaZero:进一步在围棋、国际象棋和将棋上分别训练;无需人类棋谱,不等于无需游戏规则、合法动作实现或算法设计。见 研究团队的 AlphaGo Zero 说明与 AlphaZero 说明。
自我对弈有目标,不等于自动到达目标
极小极大定理说明适用的零和博弈存在均衡值,不负责保证任意训练算法找到它。 策略也未必唯一。
搜索和学习会遇到有限样本、函数逼近、探索不足、对手持续变化等问题。即使均衡存在,某种自我对弈更新也可能循环或不稳定。
第 13 章讲的是“有哪些保证、保证到哪一步”。非零和也可以有均衡和专门的学习理论,不能简单说“非零和没有答案”。
🔗 这一章连到哪里
- 11-剪枝.html:检查 α-β 返回的是精确值、上界还是下界;TreeStrap 不能把界当真值。
- 博弈论与集体决策 13 · 零和与极大极小:区分均衡存在、最坏情况保证与学习收敛。
- 强化学习基础 05 · 蒙特卡洛与时序差分:TD-Gammon 使用的学习思路。
- 强化学习基础:继续看评估或策略怎样从交互中学习。
- 13-CSP是什么.html:下一站改问“哪一组赋值同时满足所有约束”。
✅ 检查点
- Type A 与 Type B 怎样分配搜索预算?α-β 总能把指数减半吗?
- 线性评估怎样得到示例中的 1.5?对固定 Minimax 树,哪种变换可以保持选择?
- 拖延丢象的例子里,短期与长期比较为何相反?加深搜索一定无效吗?
- 静默搜索怎样缓解问题?被将军时能只用静态估分吗?
- 原来的 10、0 与 4、4 两支各值多少?叶子开平方后呢?
- Chinook 的 8 子与 10 子数据库是什么规模?求解结论适用于什么起点和规则?
- TD-Gammon 与 TreeStrap 分别怎样获得训练信号?骰子是否保证学习成功?
- MCTS 一定不使用评估函数吗?极小极大定理是否保证自我对弈收敛?
👀 答案
- Type A 给定深度内全宽度搜索;Type B 有选择地深入。α-β 的指数约减半是理想排序下的量级,不是所有实际搜索都能达到。
- 5 − 3 − 0.5 = 1.5。固定 MAX/MIN 树上,对所有叶子统一做严格递增变换并保持平局规则,可保持选择;实际引擎的搜索树不能随变换改变。
- 教学对照中,边界只看到 −1 优于 −3;最终却是 −6 差于 −3。加深或改进评估可能发现这次错误,但不能保证不存在更远处的错误。
- 到达边界后继续检查选定的战术走法,避免过早评价。被将军时必须考虑合法应将,不能用“不走棋”的静态分数替代。
- 原来左 5、右 4,选左;开平方后左约 1.58、右 2,选右。平均比较不仅依赖排序,还依赖分数尺度和概率。
- 8 子库为 443,748,401,247 个局面,10 子库约 39 万亿;它们是规模信息,不用背。证明针对英美式跳棋标准初始局面、双方最优为和,不是所有局面都和。
- TD-Gammon 由自我对弈中的后续预测和终局结果学习;TreeStrap 利用同次搜索多个节点的值或单侧界。随机骰子有助覆盖,但不提供普遍成功保证。
- MCTS 可以用 rollout,也可以用价值网络。均衡存在定理不等于训练收敛定理,有限样本自我对弈可能不稳定。
本节回顾
先记住这四件事
- 边界估分不是终局证明,线性公式只是一个入门模型。
- 固定 Minimax 看次序;机会节点平均时还要看概率与收益尺度。
- 静默搜索缓解有限视野,不是治好所有估分错误。
- 会下棋、解出了游戏、训练必然收敛,是三种不同的结论。
用手算例子核对为什么 5 大于 4,但开平方后 1.58 小于 2。下一节:13 · CSP 是什么。