🏠 总目录📚 本教程 12 · 评估函数与棋类 AI ← →

搜索不能到底时,评估分数会怎样误导走法?

读后可检查:比较特征评估、地平线效应和随机节点,分清 α-β 与 MCTS 的职责。

📑 本页目录(点开跳转)

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。

MAX:2 MIN:1 MIN:2 1 2 2 4
先在两支各取最小,再由根取最大。
看哪一层原分数变换后
左边叶子1、21、20
右边叶子2、420、400
左 MIN11
右 MIN220
根选择右右

最右列用同一个严格递增映射把 1→1、2→20、4→400。每一步取最大或最小的次序都没有变,所以选择仍为右。

条件别丢:固定搜索树、统一变换所有叶子评分(含终局值)、变换严格递增,并使用一致的平局处理。递减变换会反转偏好;仅非递减的变换可能制造新的平局。

这讲的是固定 Minimax 树的保序性质。实际引擎若依赖分数幅度决定剪枝或扩展,变换后连搜索树都变了,就不能用它保证走法不变;也不能把它直接推广到随机收益的比较。

👻 三、地平线效应

坏结果可能在搜索边界之外,不一定恰好是下一步。 如果边界评估没有把它计入,程序可能选择“拖延损失”,甚至为拖延再付出代价。

保留一个象棋直觉:假设一个象终究保不住,送兵将军能暂时迫使对方应将,推迟吃象。只在象还没丢的时刻数子力,可能误把拖延当救援。

下面是人为规定后果的教学对照,不是一份给定棋谱的强制变化证明。用兵为单位,象记 3;短期评估只数已损失子力。

选择截断估计最终损失
立即丢象−3−3
先送一兵拖延−1−6

拖延这一支的设定是:后续还会丢两兵和一个象,加上已经丢的一兵,最终损失共 6。

浅看时 −1 好于 −3;把后续结果算进去后,−3 好于 −6。问题出在有限搜索和边界估分共同漏掉了后果。

加深搜索有时能解决眼前这个例子,但新的战术也可能出现在更远处。不能断言“加深两层一定多送两个兵”,也不能说评估函数质量完全无关。

缓解方法:静默搜索

普通搜索到深度上限时,先别急着给尚未结束的战术交换下结论。

静默搜索通常继续看一部分战术走法,例如吃子;若正在被将军,必须考虑合法的应将走法。吃子不全是强制走法,“后被攻击”也不代表所有实现都会自动扩展同一组分支。

可以这样理解一个常见框架:

  1. 先检查终局;终局使用胜负结果。
  2. 未被将军时,可把静态评估作为“不继续战术交换”的基线候选。
  3. 再搜索选定的战术走法,把回应的后果纳入估计;被将军时不能用“原地不动”逃避应将。

这能减轻兑子进行到一半造成的误判,但不是彻底解决地平线效应。实现仍需处理重复局面、搜索预算和剪枝条件。

第 11 章的置换表与剪枝帮助复用搜索和分配预算;边界估分、静默搜索、缓存和剪枝是配合关系,不是互相替代。

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

MAX 挑自己最有利的,MIN 挑对自己最不利的,CHANCE 则按概率平均。

例如双陆棋掷骰子会改变可用走法。这里假设局面可观察、随机结果的概率已知;若是看不到的手牌,还需要处理信息集或信念,不能只添加一个 CHANCE 节点就算解决。

$$V(\text{chance})=\sum_k p_k V_k$$

pₖ 是第 k 个结果的概率,非负且总和为 1;Vₖ 是该结果之后的子节点值。它们都从同一方的收益口径计算。

MAX:5 CHANCE:5 CHANCE:4 0.50.50.50.5 10044 两边都按概率平均,不是只看最大的叶子 10
看两支的期望:5 大于 4,选左。

这是只包含 MAX 与 CHANCE 的最小片段;完整的期望极小极大树还可以包含 MIN 层。

逐支算:左边 0.5 × 10 + 0.5 × 0 = 5;右边 0.5 × 4 + 0.5 × 4 = 4,因此 MAX 选左。

⭐ 现在精确值要紧了

保留叶子的排序,不再足以保留“平均以后”的排序。 将上图所有非负叶子值开平方:

比较对象原始分数开平方后
左支期望5约 1.58
右支期望42
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 章讲的是“有哪些保证、保证到哪一步”。非零和也可以有均衡和专门的学习理论,不能简单说“非零和没有答案”。

🔗 这一章连到哪里

✅ 检查点

  1. Type A 与 Type B 怎样分配搜索预算?α-β 总能把指数减半吗?
  2. 线性评估怎样得到示例中的 1.5?对固定 Minimax 树,哪种变换可以保持选择?
  3. 拖延丢象的例子里,短期与长期比较为何相反?加深搜索一定无效吗?
  4. 静默搜索怎样缓解问题?被将军时能只用静态估分吗?
  5. 原来的 10、0 与 4、4 两支各值多少?叶子开平方后呢?
  6. Chinook 的 8 子与 10 子数据库是什么规模?求解结论适用于什么起点和规则?
  7. TD-Gammon 与 TreeStrap 分别怎样获得训练信号?骰子是否保证学习成功?
  8. MCTS 一定不使用评估函数吗?极小极大定理是否保证自我对弈收敛?
👀 答案
  1. Type A 给定深度内全宽度搜索;Type B 有选择地深入。α-β 的指数约减半是理想排序下的量级,不是所有实际搜索都能达到。
  2. 5 − 3 − 0.5 = 1.5。固定 MAX/MIN 树上,对所有叶子统一做严格递增变换并保持平局规则,可保持选择;实际引擎的搜索树不能随变换改变。
  3. 教学对照中,边界只看到 −1 优于 −3;最终却是 −6 差于 −3。加深或改进评估可能发现这次错误,但不能保证不存在更远处的错误。
  4. 到达边界后继续检查选定的战术走法,避免过早评价。被将军时必须考虑合法应将,不能用“不走棋”的静态分数替代。
  5. 原来左 5、右 4,选左;开平方后左约 1.58、右 2,选右。平均比较不仅依赖排序,还依赖分数尺度和概率。
  6. 8 子库为 443,748,401,247 个局面,10 子库约 39 万亿;它们是规模信息,不用背。证明针对英美式跳棋标准初始局面、双方最优为和,不是所有局面都和。
  7. TD-Gammon 由自我对弈中的后续预测和终局结果学习;TreeStrap 利用同次搜索多个节点的值或单侧界。随机骰子有助覆盖,但不提供普遍成功保证。
  8. MCTS 可以用 rollout,也可以用价值网络。均衡存在定理不等于训练收敛定理,有限样本自我对弈可能不稳定。

本节回顾

先记住这四件事

  • 边界估分不是终局证明,线性公式只是一个入门模型。
  • 固定 Minimax 看次序;机会节点平均时还要看概率与收益尺度。
  • 静默搜索缓解有限视野,不是治好所有估分错误。
  • 会下棋、解出了游戏、训练必然收敛,是三种不同的结论。

用手算例子核对为什么 5 大于 4,但开平方后 1.58 小于 2。下一节:13 · CSP 是什么。

打卡记录保存在你的浏览器里,首页能看到总进度