第5章 对抗搜索

第5章 对抗搜索

本章讨论在有其他 Agent 计划与我们对抗时，该如何预先规划的问题。

5.1 博弈

第2章介绍了多 Agent 环境，其中每个 Agent 需要考虑到其他 Agent 的行动及其对自身的影响。其他 Agent 的不可预测性可能导致该 Agent 问题求解过程中的偶发性，正像我们在第4章中所讨论的。本章讨论竞争环境，竞争环境中每个 Agent 的目标之间是有冲突的，这就引出了对抗搜索问题——通常被称为博弈。

数学中的博弈论，是经济学的一个分支，把多 Agent 环境看成是博弈，其中每个 Agent 都会受到其他 Agent 的“显著”影响，不论这些 Agent 间是合作的还是竞争的 $ ^{1} $。人工智能中“博弈”通常专指博弈论专家们称为有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏（如国际象棋）。术语中，这是指在确定的、完全可观察的环境中两个 Agent 必须轮流行动，在游戏结束时效用值总是相等并且符号相反。例如下国际象棋，一个棋手赢了，则对手一定是输了。正是 Agent 之间效用函数的对立导致了环境是对抗的。

从人类文明产生以来，博弈就和人类智慧如影随形——有时甚至到了令人担忧的程度。对于人工智能研究人员来说，博弈的抽象特性使得博弈成为感兴趣的研究对象。博弈游戏中的状态很容易表示，Agent的行动数目通常受限，而行动的输出都有严谨的规则来定义。体育游戏如台球和冰球，则有复杂得多的描述，有更大范围的可能行动，也有不够严谨的规则来定义行动的合法性。所以除了足球机器人，体育游戏目前并没有吸引人工智能领域的很大兴趣。

与第3章中讨论的大多数玩具问题不同，博弈因为难于求解而更加令人感兴趣。例如国际象棋的平均分支因子大约是35，一盘棋一般每个棋手走50步，所以搜索树大约有35 $ ^{100} $或者10 $ ^{154} $个结点（尽管搜索图“只可能”有大约10 $ ^{40} $个不同的结点）。如同现实世界，博弈要求具备在无法计算出最优决策的情况下也要给出某种决策的能力。博弈对于低效率有严厉的惩罚。在其他条件相同的情况下，只有一半效率的A*搜索意味着运行两倍长的时间，于是只能以一半效率利用可用时间的国际象棋程序就很可能被击败。所以，博弈在如何尽可能地利用好时间上产生了一些有趣的研究结果。

我们从最佳招数的定义和寻找它的搜索算法开始。接着讨论时间有限时如何选择好的招数。剪枝允许我们在搜索树中忽略那些不影响最后决定的部分，启发式的评估函数允许在不进行完全搜索的情况下估计某状态的真实效用值。5.5 节讨论诸如西洋双陆棋这类包含概率因素的游戏：我们也讨论桥牌，它包含不完整信息，桥牌中每个人都不能看到所有的

牌。最后我们看看最高水平的博弈程序如何与人类对手抗衡以及未来的发展趋势。

首先考虑两人参与的游戏：MAX 和 MIN，马上就会讨论这样命名的原因。MAX 先行，两人轮流出招，直到游戏结束。游戏结束时给优胜者加分，给失败者罚分。游戏可以形式化成含有下列组成部分的一类搜索问题。

$ S_{0} $: 初始状态，规范游戏开始时的情况。

PLAYER(s): 定义此时该谁行动。

● ACTIONS(s): 返回此状态下的合法移动集合。

RESULT(s,a): 转移模型，定义行动的结果。

TERMINAL-TEST(s)：终止测试，游戏结束返回真，否则返回假。游戏结束的状态称为终止状态。

UTILITY(s,p): 效用函数（也可称为目标函数或收益函数），定义游戏者 p 在终止状态 s 下的数值。在国际象棋中，结果是赢、输或平，分别赋予数值+1，0，或 1/2。有些游戏可能有更多的结果，例如双陆棋的结果是从 0 到+192。零和博弈是指在同样的棋局实例中所有棋手的总收益都一样的情况。国际象棋是零和博弈，棋局的收益是 0+1，1+0 或 1/2+1/2。“常量和”可能是更好的术语，但称为零和更传统，可以将这看成是下棋前每个棋手都被收了 1/2 的入场费。

初始状态、ACTIONS函数和RESULT函数定义了游戏的博弈树——其中结点是状态，边是移动。图5.1给出了井字棋的部分博弈树。在初始状态MAX有九种可能的棋招。游戏轮流进行，MAX下X，MIN下O，直到到达了树的终止状态即一位棋手的标志占领一行、一列、一对角线或所有方格都被填满。叶结点上的数字是该终止状态对于MAX来说的效用值；值越高对MAX越有利，而对MIN则越不利（这也是棋手命名的原因）。

最上面的结点是初始状态，MAX 先走棋，放置一个 X 在空位上。图显示了搜索树的一部分，给出 MIN 和 MAX 的轮流走棋过程，直到到达终止状态，所有终止状态都按照游戏规则被赋予了效用值

5.2 博弈中的优化决策

在一般搜索问题中，最优解是到达目标状态的一系列行动——终止状态即为取胜。在对抗搜索中，MIN 在博弈中也有发言权。因此 MAX 必须找到应急策略，制定出 MAX 初始状态下应该采取的行动，接着是 MIN 行棋，MAX 再行棋时要考虑到 MIN 的每种可能的回应，依此类推。这有些类似于 AND-OR 搜索算法（图 4.11），MAX 类似于 OR 结点，MIN 类似于 AND 结点。粗略地说，当对手不犯错误时最优策略能够得到至少不比任何其他策略差的结果。我们将从寻找最优策略开始。

即使是井字棋这样简单的游戏，也很难在一页画出它的整个博弈树，所以讨论如图5.2所示的更简单游戏。在根结点MAX的可能行棋为 $ a_{1} $， $ a_{2} $和 $ a_{3} $。对于 $ a_{1} $，MIN可能的对策有 $ b_{1} $， $ b_{2} $和 $ b_{3} $，等等。这个特别的游戏在MAX和MIN各走一步后结束（按照博弈的说法，这棵博弈树的深度是一步，这包括两个单方招数，每个单方招数称为一层）。终止状态的效用值范围是从2到14。

$ \Delta $ 结点是“MAX 结点”，代表轮到 MAX 走， $ \nabla $ 结点是“MIN 结点”。终止结点显示 MAX 的效用值；其他结点标的是它们的极小极大值。MAX 在根结点的最佳行棋是 $ a_1 $，因为它指向有最高的极小极大值的后继，而 MIN 此时的最佳行棋是 $ b_1 $，因为它指向有最低的极小极大值的后继

给定一棵博弈树，最优策略可以通过检查每个结点的极小极大值来决定，记为MINIMAX(n)。假设两个游戏者始终按照最优策略行棋，那么结点的极小极大值就是对应状态的效用值（对于MAX而言）。显然地，终止状态的极小极大值就是它的效用值自身。更进一步，对于给定的选择，MAX喜欢移动到有极大值的状态，而MIN喜欢移动到有极小值的状态。所以得到如下公式：

$$ \begin{aligned}&MINIMAX(s)=\\&\{\begin{array}{ll}UTILITY(s)&s 为终止状态 \\\max_{a\in Actions(s)}MINIMAX(RESULT(s,a))&s 为 MAX 结点 \\\min_{a\in Actions(s)}MINIMAX(RESULT(s,a))&s 为 MIN 结点 \end{array}.\end{aligned} $$

我们将这些定义应用于图 5.2 中的博弈树。底层终止结点的效用值即为它们的效用函数值。第一个 MIN 结点为 B，其三个后继的值分别是 3、12 和 8，所以它的极小极大值是 3。类似地，可以得出其他两个 MIN 结点的极小极大值都是 2。根是 MAX 结点，其后继结点分的极小极大值分别为 3、2 和 2，所以它的极小极大值是 3。可以确定在根结点的极小

极大决策：对于 MAX 来说 $ a_{1} $ 是最优选择，因为它指向有最高的极小极大值的终止状态。

对 MAX 的最推行棋进行求解时做了 MIN 也按最佳行棋的假设——尽可能最大化 MAX 的最坏情况。如果 MIN 不按最佳行棋行动怎么办？这种情况下显然（习题 5.7）MAX 可以做得更好。可能有一些策略在对付非最优化对手方面做得比极小极大策略好，但是用这些策略对付最优化对手则会得到更差的结果。

5.2.1 极小极大算法

极小极大算法（图5.3）从当前状态计算极小极大决策。它使用了简单的递归算法计算每个后继的极小极大值，直接实现上面公式的定义。递归算法自上而下一直前进到树的叶结点，然后随着递归回溯通过搜索树把极小极大值回传。例如，在图5.2中，算法先递归到三个底层的叶结点，对它们调用UTILITY函数得到有效用值分别是3、12和8。然后它取最小值3作为回传值返回给结点B。通过类似的过程可以分别得到C和D的回传值均为2。最后在3、2和2中选取最大值3作为根结点的回传值。

返回最佳可能行棋对应的行动，即在假设对手行棋是为了使效用值最小的前提下，能够导致最佳效用值的行动。函数 MAX-VALUE 和 MIN-VALUE 遍历整个博弈树一直到叶结点，以决定每个状态的回传值。 $ \arg\max_{a \in S} f(a) $ 计算出集合 S 中有最大 $ f(a) $ 值的 $ a $

极小极大算法对博弈树执行完整的深度优先探索。如果树的最大深度是 m，在每个结点合法的行棋有 b 个，那么极小极大算法的时间复杂度是 $ O(b^{m}) $。一次性生成所有的后继的算法，空间复杂度是 $ O(bm) $，而每次生成一个后继的算法（参见原书第 87 页），空间复杂度是 $ O(m) $。当然对于真实的游戏，这样的时间开销完全不实用，不过此算法仍然可以作为对博弈进行数学分析和设计实用算法的基础。

5.2.2 多人博弈时的最优决策

许多流行的游戏都允许多个参加者。让我们来看一看如何把极小极大思想推广到多人博弈中。从技术观点上看这很自然，但由此也产生了一些有趣的新概念问题。

首先需要用向量值替换每个结点上的单一效用值。例如若博弈有三个人 A、B 和 C 参

与，则每个结点都与一个向量 $ \langle v_{A}, v_{B}, v_{C} \rangle $ 相关联。对于终止状态，这个向量代表有从每个人角度出发得到的状态效用值（在两人的零和博弈中，由于效用值总是正好相反所以二维向量可以简化为单一值）。最简单的实现方法就是让函数 UTILITY 返回一个效用值向量。

现在考虑非终止状态。考虑在图 5.4 中的博弈树上标为 X 的结点。此时，轮到游戏者 C 选择行棋。它有两种选择，导致的终止状态的效用值向量分别是： $ \langle v_A=1, v_B=2, v_C=6 \rangle $ 和 $ \langle v_A=4, v_B=2, v_C=3 \rangle $。6 比 3 大，所以 C 选择第一种走法。这意味着如果在状态 X，后继的招数会走到效用值向量为 $ \langle v_A=1, v_B=2, v_C=6 \rangle $ 的终止状态。所以，X 的回传值就是这个向量。结点 n 的回传值就是该选手在结点 n 选择的后继者的效用值向量。任何玩过诸如强权外交游戏这样的多人博弈的人很快会意识到这比双人游戏要复杂得多。多人博弈通常会涉及在游戏选手之间出现正式或者非正式联盟的情况。随着游戏的进行，联盟不断建立或者解散。我们该如何理解这种行为？联盟是否是各选手选择最优策略的自然结果？结果可能确实是这样。例如，假设 A 和 B 相对比较弱，而 C 比较强。对于 A 和 B 而言，它们一起进攻 C 比等 C 逐个消灭它们要好，这通常是最优策略。这样，博弈从纯自私的行为变成合作。当然，一旦 C 在联合攻击下被削弱，联盟就会失去价值，于是 A 或者 B 就会破坏协议。某些情况下，明确的联盟仅仅是使本将要发生的事情具体化。另外一些情况下，毁约会损害社会声誉，也可能会有直接利益，选手要在这两方面之间寻求平衡。在 17.5 节会有更详细的讨论。

如果游戏是非零和的，合作也可能发生在两人游戏中。例如，假设终止状态的效用值向量是 $ \langle v_{A}=1000, v_{B}=1000 \rangle $，并且 1000 对于两个选手都是最高的可能效用值。那么双方的最优策略就是尽一切可能来到达此状态，即双方会自动合作来达到共同渴望的目标。

5.3 $ \alpha-\beta $ 剪枝

极小极大值搜索的问题是必须检查的游戏状态的数目是随着博弈的进行呈指数级增长。不幸的是，指数增长无法消除，不过我们还是可以有效地将其减半。这里的技巧是可能不需要遍历博弈树中每一个结点就可以计算出正确的极小极大值。于是，借用第3章中的剪枝思想尽可能消除部分搜索树。这种特别技术称为 $ \alpha $- $ \beta $剪枝。将此技术应用到标准的极小极大搜索树上，会剪掉那些不可能影响决策的分支，仍然返回和极小极大算法同样的

结果。

再来看图 5.2 中的两层博弈树。重新观察最优决策的计算过程，特别注意此过程中在每个结点的已知信息。图 5.5 解释了每一步骤。结果发现可以在不计算评价其中两个叶结点的情况下就确定极小极大决策。

每一结点上标出了可能的取值范围。（a）B 下面的第一个叶结点值为 3。因此作为 MIN 结点的 B 值至多为 3。（b）B 下面的第二个叶结点值为 12。MIN 不会用这招，所以 B 的值仍然至多为 3。（c）B 下面的第三个叶子值为 8；此时已经观察了 B 的所有后继，所以 B 的值就是 3。现在可以推断根结点的值至少为 3，因为 MAX 在根结点有值为 3 的后继。（d）C 下面的第一个叶结点值为 2。因此 C 这个 MIN 结点的值至多为 2。不过已经知道 B 的值是 3，所以 MAX 不会选择 C。这时再考察 C 的其他后继已经没有意义了。这就是 $ \alpha $- $ \beta $ 剪枝的实例。（e）D 下面的第一个叶结点值为 14，所以 D 的值至多为 14。这比 MAX 的最佳选择（即 3）要大，所以继续探索 D 的其他后继。还要注意现在知道根的取值范围，根结点的值至多为 14。（f）D 的第二个后继值为 5，所以我们又必须继续探索。第三个后继值为 2，所以 D 的值就是 2 了。最终 MAX 在根结点的决策是走到值为 3 的 B 结点

还可以把这个过程看作是对 MINIMAX 公式的简化。假设图 5.5 中的 C 结点的两个没有计算的子结点的值是 x 和 y。根结点的值计算如下：

$$ \begin{aligned}MINIMAX(root)&=\max(\min(3,12,8),\min(2,x,y),\min(14,5,2))\\&=\max(3,\min(2,x,y),2)\\&=\max(3,z,2)\quad 其中 z=\min(2,x,y)\leq2\\&=3\end{aligned} $$

即，根结点的值以及因此做出的极小极大决策与被剪枝的叶结点x和y无关。

$ \alpha $- $ \beta $剪枝可以应用于任何深度的树，很多情况下可以剪裁整个子树，而不仅仅是剪裁叶结点。一般原则是：考虑在树中某处的结点 n（见图 5.6），选手选择移动到该结点。如果选手在 n 的父结点或者更上层的任何选择点有更好的选择 m，那么在实际的博弈中就永远不会到达 n。所以一旦发现关于 n 的足够信息（通过检查它的某些后代），能够得到上述结

论，我们就可以剪裁它。

记住极小极大搜索是深度优先的，所以任何时候只需考虑树中某条单一路径上的结点。 $ \alpha $- $ \beta $ 剪枝的名称取自描述这条路径上的回传值的两个参数：

$ \alpha= $ 到目前为止路径上发现的MAX的最佳（即极大值）选择

$ \beta= $ 到目前为止路径上发现的 MIN 的最佳（即极小值）选择

α-β搜索中不断更新α和β的值，并且当某个结点的值分别比目前的MAX的α或者MIN的β值更差的时候剪裁此结点剩下的分支（即终

如果对选手而言 m 比 n 好，那么行棋就不会走到 n

止递归调用）。完整算法参见图5.7。建议读者把此算法应用于图5.5中的树。

注意算法和图 5.3 中的极小极大算法相似，除了在 MIN-VALUE 和 MAX-VALUE 中修改 $ \alpha $ 和 $ \beta $ 的值（还有用来传递这些参数的记录）

5.3.1 行棋排序

$ \alpha $- $ \beta $剪枝的效率很大程度上依赖于检查后继状态的顺序。例如在图5.5（e）和（f）中，根本不能剪掉D的任何后继（从MIN的角度），因为首先生成的是最差的后继。如果D的第三个后继先生成，就能够剪掉其他两个。这意味着应首先检查可能最好的后继。

如果能够这样做 $ ^{1} $，那么 $ \alpha $- $ \beta $算法只需检查 $ O(b^{m/2}) $个结点来做出决策（ $ m $是对的最大深度），而不是极小极大算法的 $ O(b^{m}) $。这意味着有效分支因子不是 $ b $而是 $ \sqrt{b} $——对于国际象棋而言不是35而是6。换种说法，在同样的时间里 $ \alpha $- $ \beta $算法比极小极大算法向前预测大

约两倍的步数。如果后继状态采用随机顺序而不是最佳优先的顺序，那么要检查的总结点数大约是 $ O(b^{3m/4}) $。对于国际象棋，有一些相当简单的排序函数（如吃子优先，然后是威胁、前进、后退）可以使得检查的总结点数为 $ O(b^{m/2}) $ 的两倍。

增加动态行棋排序方案，如先试图采用以前走过的最好行棋，可能让我们非常接近理论极限。以前的行棋可能是上一步棋——面临同样的棋局威胁——也可能来自当前行棋的上一次搜索过程。从当前行棋获得信息的一种方法是迭代深入搜索。首先，搜索一层并记录最好行棋路径。接着搜索更深一层，此时使用记录的路径来导引行棋排序。在第3章已经看到，指数级增长的博弈树上的迭代深入搜索只增加了常数级别的搜索时间，可能从行棋排序做得更多。最好行棋称为绝招，先走绝招称为绝招启发式。

第3章提到，搜索树中的重复状态会使搜索代价呈指数级增长。在博弈中，重复的状态频繁出现是因为换位——不同行棋序列导致同样棋局。例如，白棋走 $ a_{1} $，黑棋用 $ b_{1} $应对，白棋在棋盘另一边的不相关的一招 $ a_{2} $，黑棋走 $ b_{2} $来应对。于是序列 $ [a_{1},b_{1},a_{2},b_{2}] $和 $ [a_{2},b_{2},a_{1},b_{1}] $都到达同样棋局。第一次遇到某棋局时把该棋局的评估值存储在哈希表里很有价值，这样当它后来再出现时不需要重新计算。存储以前见过的棋局的哈希表一般被称为换位表；它本质上和图搜索中的explored表相同（参见3.3节）。使用换位表可以取得很好的动态效果，在国际象棋中有时可能把到达的搜索深度扩大一倍。另一方面，如果可以每秒钟评价上百万个结点，那么在换位表中就不太可能保存所有评价了。选择保留有价值的结点而摒弃其他结点，则有许多不同的策略。

5.4 不完美的实时决策

极小极大算法生成整个博弈的搜索空间，而 $ \alpha $-β算法允许我们剪裁掉其中的一大部分。然而， $ \alpha $-β算法仍然要搜索部分空间直到终止状态。这样的搜索深度也是不现实的，因为要在合理的时间内确定行棋——典型地最多只有几分钟的时间来决策。Claude Shannon发表论文《设计计算机国际象棋程序》（1950），文中提出应该尽早截断搜索，应将启发式评估函数用于搜索中的状态，有效地把非终止结点转变为终止结点。换言之，建议按两种方式对极小极大算法或 $ \alpha $-β算法进行修改：用估计棋局效用值的启发式评估函数 EVAL 取代效用函数，用决策什么时候运用 EVAL 的截断测试取代终止测试。因此得到如下的启发式极小极大值，s 为状态，d 为最大深度：

$$ \begin{aligned}&H-MINIMAX(s,d)=\\&\{\begin{array}{ll}EVAL(s)& 如果 CUTOFF-TEST(s,d) 为真 \\\max_{a\in Actions(s)}H-MINIMAX(RESULT(s,a),d+1)&s 为 MAX 结点 \\\min_{a\in Actions(s)}H-MINIMAX(RESULT(s,a),d+1)&s 为 MIN 结点 \end{array}.\end{aligned} $$

5.4.1 评估函数

与第3章中启发式函数返回对目标距离的估计一样，对于给定的棋局，评估函数返回对游戏的期望效用值的估计。估计的思想早在Shannon之前就有。数百年来，人类与计算

机程序相比搜索的力量更加受限，国际象棋棋手（其他游戏也一样）找到了一些判断棋局价值的方法。显而易见的是博弈程序的性能严重依赖于评估函数的质量。不准确的评估函数可能引导 Agent 走向失败。如何设计好的评估函数呢？

首先，评估函数对终止状态的排序应该和真正的效用函数的排序结果一样：赢状态的评估值一定要好于平局，而平局一定要好于输的状态。否则，使用它的 Agent 可能会出昏招，即使它可以向前一直看到游戏结束。第二，评估函数的计算本身不能花费太长时间（总观点是为了更快地搜索）。第三，对于非终止状态，评估函数应该和取胜几率密切相关。

先讨论 “取胜几率” 的含义。国际象棋不是几率博弈：我们确定知道当前状态，没有骰子。不过如果搜索必须在一些非终止状态截断，那么算法对这些状态的最后结果必然是不确定的。这种不确定性引入的原因是计算局限性，而不是信息受限。在计算能力有限的情况下，评估函数对给定状态进行评估，它能做的就是尽可能猜测最后的结果。

下面把上述思想具体化。大多数评估函数都要考虑状态的不同特征参数——例如在国际象棋中，包括白兵的数目、黑兵的数目、白后的数目、黑后的数目，等等。这些特征一起定义了状态的各种类别或者等价类：同一分类中的状态对所有特征具有相同的值。例如，某分类是包含两兵对一兵的残局。一般来说，任何给定的分类都会包含制胜的状态，导致平局的状态和会导致失败的状态。评估函数无法知道到底是在哪种状态，不过它可以为每个结果返回一个值，反映出这些状态的比例。例如，假设经验告诉我们某类中72%的状态是制胜的（效用值+1），20%是会输的（0），而其他8%是平局（1/2）。那么该类中状态的合理评价是期望值： $ (0.72 \times +1) + (0.20 \times 0) + (0.08 \times \frac{1}{2}) = 0.76 $。总体上每个分类确定一个期望值，帮助产生任一状态的评估函数。对于终止状态，评估函数无须返回实际的期望值，因为状态的排序保持不变。

在实际应用中，这种分析往往有太多的分类，因此需要太多的经验去估计所有的取胜可能。所以，大多数评估函数会分别计算每个特征的影响，然后把它们组合起来找到总数值。例如，国际象棋的入门书中给出各个棋子的子力价值估计如下：兵值1分，马和象值3分，车值5分，后值9分。其他特征诸如“是否好兵阵”和“王是否安全”可能值半个兵。这些特征值简单地加在一起就得到了对棋局的评估。

如果评估比对方多大概一个兵的棋力时，实际上会有较大的胜面，如果评估比对方多三个兵的棋力时基本上是必胜的，如图5.8（a）所示。评估函数可如下表示，这在数学上称为加权线性函数：

$$ \mathrm{EVAL}(s)=w_{1}f_{1}(s)+w_{2}f_{2}(s)+\cdots+w_{n}f_{n}(s)=\sum_{i=1}^{n}w_{i}f_{i}(s) $$

其中 $ w_{i} $ 是权值， $ f_{i} $ 是棋局的某个特征。对于国际象棋来说， $ f_{i} $ 可能是棋盘上每种棋子的数目， $ w_{i} $ 可能是每种棋子的价值（如兵为1，象为3，等等）。

把特征值这样加起来的方法看起来是合理的，不过实际上这是以很强的假设为基础：每个特征的贡献独立于其他特征的值。例如给象赋予3分忽略了象在残局中能够发挥更大作用的事实，象在残局中有更大的发挥空间。因此，当前国际象棋或其他博弈程序也使用非线性的特征组合。例如，两象的价值比单个象价值的两倍要略大一些，象在残局中棋力值更高（即当下棋步数很大并且剩余棋子数很少时）。

在（a）中，黑方多一个马两个兵，应该取胜。在（b）中白方会吃掉黑方皇后，从而确立几乎必胜的优势

机敏的读者会发现特征和权值并不是属于国际象棋规则！它们来自于几个世纪以来人们下棋的经验。有些博弈很难总结经验规律，这时可以利用第18章的机器学习技术来确定评估函数的权值。要指出的是，机器学习也证实了国际象棋中的一个象确实值三个兵。

5.4.2 截断搜索

下一步则是修改 ALPHA-BETA-SEARCH，当适合截断搜索时调用启发式函数 EVAL。实现时用下面一行程序替换图 5.7 中提到 TERMINAL-TEST 的两行代码：

if CUTOFF-TEST(state, depth) then return EVAL(state)

内存中还必须安排记录一些信息，这样 depth 在每一次递归调用时可以逐渐增加。最直接的控制搜索次数的方法是设置固定的深度限制，这样 CUTOFF-TEST(state, depth) 当 depth 大于固定深度 d 时返回 true（同 TERMINAL-TEST 一样，对于所有终止结点它也返回 true）。根据游戏规则许可的时间来决定深度 d。更好的方法是使用迭代深入（参见第 3 章）。当时间用光时，程序返回目前最深的完整搜索所选择的招数。而且，迭代深入同样可以帮助行棋排序。

由于评估函数的近似本质，这种方法可能会导致错误。重新考虑国际象棋中基于子力优势的简单评估函数。假设程序在搜索图5.8（b）的棋局时到达了深度限制，此时黑方有一马两兵的优势。程序会报告这个状态的启发式函数值，从而认为这个状态会导致黑方获胜。而其实下一步白方就可以毫无意外地吃掉黑方皇后。因此，这个棋局实际是白棋赢，需要向前多看一步才能预测。

显然我们需要更加复杂的截断测试。评估函数只适用于那些静态棋局——即，评估值不会很快出现大的摇摆变化的棋局。例如在国际象棋中，有很好吃招的棋局对于只统计棋力的评估函数来说就不是静态的。非静态棋局可以进一步扩展直到变为静态棋局。这种额外的搜索称为静态搜索；有时它只考虑某些类型的棋招，诸如吃子能够快速消解棋局的不确定性。

地平线效应更难消除。这是指对手招数导致我方严重损失并且从理论上基本无法避免时。考虑图5.9中的棋局，可以看出黑象无路可逃。例如，白车可以走h1,a1,a2从而吃掉

它；黑象被吃掉在6步后发生。黑方没有行动序列能够将黑象“拉出地平线”。假设黑方搜索深度为8步。黑方的绝大多数选择都会导致黑象被吃掉，这样的选择都是“坏”招。不过黑方会考虑检查白方的王和e4的兵。王会吃掉兵。此时黑方可以重新考虑f5的兵可以吃掉另外一个兵。这需要4步，还有剩下4步不足以吃掉象。黑方会认为牺牲两个兵保住了象，实际上象被吃掉是不可避免的，只是超出了黑方能看到的地平线。

黑方行棋后，黑象命运已定。但是黑方可以通过检查白王和兵，迫使王吃兵。这样就将象拉出了地平线，被牺牲掉的兵被搜索算法视为好棋招

黑棋在子力上领先，然而如果白棋能够把第七行上的兵推进到第八行升格为皇后，那么白棋基本就可以赢了。黑棋可以通过用车将白棋国王的军来延迟这种结果大约14步，不过最后也无法避免兵升变为皇后。固定深度的搜索问题在于它相信这些延缓招数能阻止升变皇后的行棋——我们称延缓招数把不可避免的升变皇后的行棋推“出了搜索地平线”，将其推进了无法检测到的空间。

单步延伸是避免地平线效应的一种策略，单步延伸指的是在给定棋局中一种棋招要“明显好于”其他棋招。一旦在搜索某处发现单步延伸，牢记它。当搜索到达指定深度界限，算法会检查单步延伸是否合法；如果是，算法允许考虑此棋招。这样做可能超过深度限制，但由于单步延伸很少，不会增加太多开销。

5.4.3 向前剪枝

截至目前我们讨论了在特定层次上进行截断搜索，并可以证明 $ \alpha $- $ \beta $剪枝对决策结果没有影响（至少对启发式评估值没有影响）。另一种可能是使用前向剪枝，是指在某个结点上无需进一步考虑而直接剪枝一些子结点。显然，大多数人在下国际象棋的时候，对每个棋局只考虑部分行棋（可能是潜意识的）。向前剪枝的一种方法是柱搜索：在每一层，只考虑最好的n步行棋可能，这称为“柱”，并不是考虑所有行棋招数。不幸的是，这种方法很危险，因为无法保证最佳的行棋不被裁剪掉。

PROBCUT 算法，或概率截断算法（Buro，1995）是 $ \alpha $- $ \beta $ 搜索的向前剪枝版本，使用先验经验的统计信息在一定程度上保护最佳行棋不被剪枝掉。 $ \alpha $- $ \beta $ 搜索会剪枝所有被证明在 $ (\alpha, \beta) $ 窗口外的结点。PROBCUT 算法则剪枝可能在窗口外结点。它首先通过浅层搜索计算得到结点的倒推值 v，然后根据以前的经验来估计深度 $ \hat{d} $ 上的值 v 是否可能在 $ (\alpha, \beta) $ 范围外。Buro 将此技术应用于他的 Othello 程序 LOGISTELLO，发现即使给原有版本两倍的

时间，使用 PROBCUT 算法的版本仍有 64% 的获胜概率。

充分利用本章所描述的技术，程序就可以得体地下国际象棋（或其他游戏）。假设已经实现了国际象棋的评估函数，使用静态搜索的合理截断测试，同时拥有很大的换位表。再假设，经过数月的艰苦努力，可以在最新的个人计算机上每秒生成和评估大约一百万个结点，这差不多允许在标准的时间控制下（每步棋三分钟）对每步棋可以搜索大约2亿个结点。国际象棋的分支因子大约是35，而 $ 35^{5} $大约是5000万，所以如果使用极小极大搜索只能向前预测5层。这样的程序也很容易被平均水平的人类棋手打败，人类棋手偶尔可以向前计划6到8层。如果使用 $ \alpha $- $ \beta $搜索可以预测大约10层，接近于专业棋手水准了。5.8节会讨论另外一些剪枝技术，可以把有效搜索深度扩展到14层。要达到大师级水准需要广泛地调整评估函数，并需要存有最优开局和残局招法的大型数据库。

5.4.4 搜索与查表

仅仅为了决定以兵走e4来开局就考虑上亿个游戏状态，看起来有些矫枉过正。一个世纪以来一些书描述了如何下好开局和残局（Tattersall，1911）。所以，很多博弈程序在开局和残局都使用查表而不是搜索就不奇怪了。

开局时，计算机大多依赖于人类的专门知识。人类专家给出的最好开局的建议都来自于书本并且编制成计算机内的表。然而，计算机还可以根据数据库中存储的各种棋局来统计什么样的开局更容易赢。开局的前几步行棋并没有太多选择，因而可以依赖于许多专家知识和过去的棋局。大概十步以后就会到达一个很少见到的棋局状态，此时就要从查表方式切换到搜索。

博弈接近尾声时棋局的可能性有限，又恢复到查表。此时是计算机具备了专门知识：计算机对残局的分析远胜人类。对于王车对王（KRK）残局人可以给出通用策略：将对手王挤至棋盘一边以减少它的活动范围，使用自己的王防守住以防对手王逃脱。其他残局，如王象马对王（KBNK）残局，很难把握也没有简明的策略。而计算机可以通过一些政策完全地解决残局问题，这些政策是指从每一种可能状态到该状态最佳棋招的映射。这样我们就只需查表而不用总是计算。KBNK表有多大呢？有462种方法可以将两个王不邻接地放置在棋盘上。王放好以后，有62个空位放象，61个空位放马，两个选手轮流下棋，所以可能棋局状态为 $ 462\times62\times61\times2=3494568 $。这其中有些状态是死棋；直接在表中标出来。然后执行逆向极小极大搜索：将象棋规则颠倒，进行悔棋而不是行棋。白方走的任何棋招，不管黑方如何回应，如果终止在赢的棋局，就一定会赢。这种搜索一直进行到3494568种棋局都被消解成赢、输或平局，同时你会拥有所有KBNK残局的准确无误的表。

使用这种技术和杰出的优化技巧，Ken Thompson（1986，1996）和 Lewis Stiller（1992，1996）解决了所有5个棋子的残局和部分6个棋子的残局，并将结果上传至互联网。Stiller发现了一种认输的情况但是需要262步行棋；这有些奇怪因为国际象棋规则规定50步之内必须吃子或移动兵。Marc Bourzutschky和Yakov Konoval（Bourzutschky，2006）在随后的工作中求解了所有无兵6子残局的情况和部分7子残局；有一种KQNKRBN残局的最好下法需要517步行棋才能吃子，会导致认输。

如果能将残局表从6子扩展到32子，那么白方在开局就会知道它会赢、平或输。到目

前为止这尚未实现，但跳棋能做到这一点，历史注释中有这方面内容。

5.5 随机博弈

在现实生活中，很多不可预知的外部事件会把我们推到无法预计的情景中。许多博弈用随机因素，如掷骰子，来反映这种不可预测性。我们把这叫做随机博弈。西洋双陆棋就是这样一种组合了运气和技巧的游戏。选手在行棋时通过掷骰子来决定合法移动。在图5.10中的西洋双陆棋棋局中，白方掷出了“6-5”有四种可能的选择。

游戏的目标是把自己的棋子全部移出棋盘。白方顺时针向25移动，黑方逆时针向0移动。每个棋子可以按照掷出的骰子数移动到任意位置除非那里有多个对方棋子；如果那里对方棋子只有一个，这个棋子就被吃掉，要从起点重新开始。在图中所示棋局里，白方掷了6-5，有4种合法移动(5-10,5-11)，(5-11,19-24)，(5-10,10-16)，(5-11,11-16)，从中选一个。(5-11,11-16)指的是把棋子从5移到11，接着再把棋子从11移到16

尽管白方知道自己的合法行棋，但不知道黑棋会掷出多少，也不知道黑棋会有哪些合法行棋。这意味着白棋无法构造我们在国际象棋和井字棋中的标准博弈树。西洋双陆棋的博弈树中除了 MAX 和 MIN 结点之外还必须包括机会结点。在图 5.11 中机会结点用圆圈表示。每个机会结点的子结点代表可能的掷骰子结果；每个分支上标记着骰子数及其出现的概率。两个骰子可以有 36 种组合，每种概率是相等的；不过掷出 5-6 和 6-5 是一样的，所以总共只有 21 个不同的掷法。6 个有相同骰子数的组合（1-1 到 6-6）每个都以 1/36 的概率出现，即 $ P(1-1)=1/36 $，而其他 15 种不同掷法的概率是 1/18。

下一步讨论如何做出正确的决策。显然，我们仍然希望选择能够导致最佳棋局的行棋。但是，这样产生的棋局没有明确的极小极大值，只能计算棋局的期望值：机会结点所有可能结果的平均值。

可把确定性博弈中的极小极大值一般化为包含机会结点的博弈的期望极小极大值。终止结点，MAX结点和MIN结点（掷骰子结果已知的）的使用和以前完全一样。对于机会结点我们计算期望值，是所有可能结果的加权和：

EXPECTIMINIMAX(s) =

$$ \{\begin{array}{ll}UTILITY(s)&s 为终止状态时 \\\max_{a}EXPECTIMINIMAX\ (RESULT(s,a))&s 为 MAX 结点时 \\\min_{a}EXPECTIMINIMAX\ (RESULT(s,a))&s 为 MIN 结点时 \\\sum_{r}P(r)\ EXPECTIMINIMAX\ (RESULT(s,r))&s 为机会结点时 \\\end{array}. $$

其中 r 表示可能的掷骰子结果（或其他偶然事件），RESULT $ (s,r) $ 仍是状态 s，附加了掷骰子结果 r。

5.5.1 机会博弈中的评估函数

和极小极大值一样，期望极小极大值的近似估计可以通过在某结点截断搜索并对每个叶结点计算其评估函数来进行。你也许会认为像西洋双陆棋的评估函数应该和国际象棋的评估函数类似——对好棋局给予高分。但实际上，机会结点的存在意味着人们需要更加仔细地考虑评估值的含义。图5.12指出：叶结点的评估函数值为[1,2,3,4]， $ a_{1} $是最佳棋招；但如果评估值为[1,20,30,400]， $ a_{2} $是最佳棋招。可以看出，评估值取值范围不同，程序行棋会表现得完全不一样！为了避免这种敏感性，评估函数应该与棋局获胜概率（或者更一般的说，是棋局的期望效用值）成正线性变换。这在涉及不确定性的情况中是非常重要和普遍的特性，将在第16章中进行进一步讨论。

如果程序能够提前知道游戏后面出现的所有掷骰子结果，那么求解这样的有骰子的游戏和没有骰子的游戏是一样的，用极小极大算法要花费的时间为 $ O(b^{m}) $，b 是分支因子，m 是最大博弈树深度。因为期望极小极大值同样要考虑所有可能的掷骰子序列，它需要花费的时间为 $ O(b^{m}n^{m}) $，其中 n 是不同掷骰子结果的数目。

尽管把搜索深度限制在某个比较小的值 d，和极小极大值搜索相比，在大多数机会博弈中由于额外代价的存在使得向前考虑得很远是不现实的。在西洋双陆棋中 n 是 21 而 b 通常是 20 左右，但是在有些情况下如果骰子数翻倍 b 可能高达 4000，实际可能考虑的只有 3 层。

可以换一种方式考虑这个问题： $ \alpha $- $ \beta $剪枝的优势在于采取最佳招数的情况下它允许忽略一些未来不会发生的情况。这样，它可以集中精力在可能发生的情况上。而在有骰子的游戏中，因为招数的生效必须以掷骰子的结果使之成为合法的招数作为前提，所以没有可能的行棋序列。这是不确定性引起的普遍问题：可能性急剧增多，制定详细的行动计划没有任何意义，因为世界很可能不朝着那个方向发展。

读者可能会想到对机会博弈树使用类似 $ \alpha $- $ \beta $剪枝技术。确实可以。对于 MAX 和 MIN 结点的分析不变，不过可以用一些灵活性剪掉部分机会结点。考虑图 5.11 中的机会结点 C，观察当检查和评价它的子结点时它的值会发生什么变化。是否有可能在考察它的全部子结点前就发现 C 的上界呢？（回想一下，这是在 $ \alpha $- $ \beta $剪枝中剪掉一个结点和它的子树所需要的）乍一看这好像不可能，因为 C 的值是它的所有子结点的平均值，而要计算平均值则确实需要检查所有子结点。但是如果限制效用函数的可能值的范围，就可能得到平均值而无需检查所有结点。例如，限制所有的效用值在-2 到+2 之间；那么叶结点的值是有界的，也就是说不用检查机会结点的所有子结点就可以设置机会结点的上界。

还可以用蒙特卡罗仿真来评估棋局。从 $ \alpha $- $ \beta $搜索（或其他）算法开始。从初始棋局出发，算法通过掷骰子不断与自己下棋。在西洋双陆棋中，尽管算法的启发式并不完善而且搜索的深度也只有几层（Tesauro，1995），算法依然表现出对棋局的评估很有效。对于掷骰子的博弈，这种类型的仿真技术叫rollout。

5.6 部分可观察的博弈

国际象棋通常被视为微型战争，但与现实战争相比，它至少缺乏一点特征，部分可观察性。在“战争风云”中，敌方的存在和部署通常是不知道的，除非面对面的时候。因此，战争中通常会有侦察兵和间谍来收集信息，同时会对敌人隐瞒信息或虚张声势以搞乱敌方。部分可观察博弈同样具备这些特征，所以会与上一节介绍的内容有很多不同。

5.6.1 军棋：部分可观察棋类博弈

在确定性的部分可观察博弈中，棋局状态的不确定性是由于不知道敌方的动作而引起的。这一类游戏包括儿童游戏 Battleships（选手的船都藏着而且不能动）和 Stratego（可以看见棋子位置但不知道棋子种类）。我们要讨论的游戏是军棋，是国际象棋的部分可观察变种，棋子可以移动但是对方看不见棋子是什么。

军棋的规则如下：白方和黑方都只能看见自己一方的棋局。有一个裁判可以看见双方棋局，对游戏进行判决并阶段性地宣布游戏进程。轮到白方走的时候，如果目标位没有黑棋，他会告诉裁判他的合法行棋。如果白方行棋不合法（有黑子占位），裁判会宣布“非法”。在这种情况下，白方可以继续选择合法的行棋——同时可以学到黑方的棋子布局。如果是合法行棋，裁判会宣布：如果有吃子则说“占领X”，如果是黑王则宣布“D方向检查”，检查的方向D可能是“马”，“行”，“列”，“大斜线”或“小斜线”（如果发现有检查，裁判会宣布检查两次）。如果黑方认输或逼和，裁判会宣布；否则，该由黑方行棋。

军棋看起来有些可怕，但人类可以很好的把握，并且计算机也试图赶上来。这里需要4.4节和图4.14中描述的信念状态——在给出所有历史感知信息情况下的逻辑可能状态集合。首先，白方的信念状态是单独的，原因是黑方还没走棋。当白方走完棋并且黑方回应后，白方的信念状态包括20种棋局，理由是对白方的每种行棋黑方都有20种可能回应。跟踪博弈过程中的信念状态确实是问题的状态评估问题，公式4.6给出了更新步骤。如果我们将对手看作是不确定性的来源，就可以将军棋状态评估直接是第4.4节中的部分可观察、不确定性的框架；就是说，白方的RESULTS由白方自身行棋和黑方回应的种种可能组成。 $ ^{1} $

在给定某信念状态下，白方可能会问，“我能赢下这盘吗？”对部分可观察游戏，策略概念有些变化；我们需要的是规范所有可能感知信息下的行棋，而不是规范对手所做的行棋回应。对军棋而言，赢的策略，或确保将死，是指不管对手如何反应，当前信念状态的每一种感知信息序列情况都会赢。如果这样定义，就可以不考虑对手的信念状态——即使对手能看到所有棋子也要决策正确。这简化了计算。图5.13中给出了KRK（王车对王）残局中的必赢策略。在这种情况下，黑方只有一个棋子（王），所以白方的信念状态可以通过在棋盘上标出黑王的所有可能位置来表示。

4.4 节提过，可以将与或搜索应用在信念状态空间以找出必赢策略。那一节提到的增量信念状态算法如果搜索深度到9通常能在中盘取胜——超过了大多数人类选手的能力。

军棋还允许一新概念：概率将死，这在完全可观察环境中没有任何意义。信念状态的每一种棋局里仍然要求这种将死能工作；因为取胜选手的行棋是随机选择的所以是概率的。要理解这种思想，可考虑用白王来找孤独的黑王。只是简单地随机移动，白王最终还是会碰上黑王尽管后者总是设法躲避着，理由是黑方无法总是猜对正确的逃跑路线。在概率论中，检测发生的概率是1。KBNK残局——王象马对王——会赢；白方给黑方提供无限的随机选择序列，黑方的猜测会出错并导致失败。另一方面，KBBK残局，赢的概率是1-ε。白方只通过移动象就可以赢。如果黑方正好在并且吃掉了象（如果象有保护则输掉了），此局会和棋。白方可以在长序列中随机选择点来走这险招，这样ε被减小到很小的常量，但不会是0。

在合理深度内很少有确保将死或概率将死的情况，除非是在残局中。有时将死策略会在当前信念状态的某些棋局中很适用，但不是所有的。实施这样的策略有时候会成功，导致意外将死——意外是指白方并不知道他会有将死——如果黑方棋子不巧正在该位置（人类博弈中的将死大多具备意外的性质）。对这种想法人们自然会问给定策略有多大的比例能赢，当前信念状态的每种棋局有多大可能成为真实的棋局状态。

人们首先可能倾向于认为当前信念状态中的每个棋局是平等的——但这是错误的。例如，考虑黑方先走一步棋后白方的信念状态。由定义（假设黑方按最优策略行棋），黑方实

施了最优选择，所以从次优策略得出的所有棋局状态概率值均为0。这些参数并不是完全正确的，原因是每个选手的目标不仅是要将棋子移到正确的位置而且还要尽可能最小化对方能够得到的信息。实施任何可预测的“最优”策略都可能给对手提供信息。所以，部分可观察博弈中的最佳行棋需要支持随机性（这也是饭店卫生检查人员总是随机抽查酒店的原因）。这意味着偶尔可以走“本质上”很弱的棋——但可以从不可预测性上获取优势，因为对手不可能在这点上做好准备。

综合以上考虑，看起来与当前信念状态的各棋局相关的概率只能在给定随机策略的情况才能计算；反过来，计算此策略需要知道可能所在棋局的各状态概率。这个难题可以采纳博弈论概念“平衡”求解，这一点将在第17章中讨论。平衡规范了每个选手的最优随机策略。然而，即使是很小的游戏，平衡的计算代价高得让人望而却步，更不用说军棋了。目前来看，军棋的有效算法的研究是个热点。大多数系统只考虑自身的信念空间，设置向前看的深度，而不考虑对手的信念状态。评估函数与可观察的博弈相似，但包含了新元素即信念状态的大小——越小越好！

5.6.2 牌类游戏

牌类游戏有很多是随机部分可观察的，无法观察到的信息是随机生成的。例如，在很多游戏中，发牌是随机的，选手手上拿到的牌别人无法知道。这样的游戏包括桥牌，惠斯特（一种牌类游戏——译者注），拱猪和其他形式的扑克牌。

乍一看，牌类游戏和掷骰子有些相像：牌是随机发给游戏者的，也就决定了每个游戏者可能的招数，只是所有“掷骰子”都发生在游戏的开始！尽管这样类比后来发现是错误的，它至少提出了有效算法：考虑未知牌的所有可能应对策略；一个一个按照完全可观察博弈来处理；然后在其中选择具有最好平均结果的招数。假设应对策略 s 的发生概率是 P(s)；那么我们希望的招数是：

$$ \arg\max_{a}\sum_{s}P(s)\operatorname{MINIMAX}(\operatorname{RESULT}(s,a)) $$

这里，如果计算可行就运行 MINIMAX；否则，运行 H-MINIMAX。

目前，在大多数的牌类游戏中，可能的应对策略数目相当大。例如，在桥牌中，每个选手可以看到四手牌中的两手；两手看不见的牌各包括 13 张，所以可能的组合有 $ \begin{pmatrix} 26 \\ 13 \end{pmatrix} = 10\ 400\ 600 $ 种。解决一种情况都是困难的，更不用说求解 1 千万个了。此时，使用蒙特卡罗近似：不再考虑所有可能组合，随机采样 N 个样本，设组合 s 在样本中出现的概率与 $ P(s) $ 成正比：

$$ \arg\max_{a}\frac{1}{N}\sum_{i=1}^{N}MINIMAX(RESULT(s_{i},a)) $$

（注意公式中并没有 $ P(s) $，这是因为样本已经根据 $ P(s) $ 换算过了）随着 N 不断变大，随机样本的总和越接近真实情况，但即使是很小的 N，如 100 到 1000 间，这种方法也能给出很好的近似。如果能给出 $ P(s) $ 一些合理估计，这种方法同样适用于确定性博弈如军旗。

像惠斯特和拱猪这样的游戏，牌局开始时没有投标或打赌，每种情况概率是相等的，

所以 $ P(s) $ 是一样的。桥牌则有叫牌过程，每组要给出想打的点数。选手就手上的牌首先达成协议，双方在叫牌过程中也可能获得了更多的信息。如何在出牌时利用这些信息不易处理，原因跟军旗中描述的一样：选手们不想让对手知道得更多。即使这样，这种方法对桥牌依然很有效，这一点将在5.7节中讨论。

公式（5.1）和（5.2）给出的策略有时被称为平均观察力，因为第一步走完之后游戏就变成可观察的。不考虑它的直觉吸引力，这种策略会导致迷路。考虑如下故事：

第一天：道路 A 通向一堆金子；道路 B 通往一个岔路。左拐你会发现更多的金子，右拐你会被一辆公共汽车撞到。

第二天：道路 A 通向一堆金子；道路 B 通往一个岔路。右拐你会发现更多的金子，左拐你会被一辆公共汽车撞到。

第三天：道路 A 通向一堆金子；道路 B 通往一个岔路。一分支上会有更多的金子，但走错了路你会被一辆公共汽车撞到。

平均观察力会有如下的推理：第一天 B 是正确的选择；第二天 B 是正确的选择；第三天情形与第一天和第二天类似，所以 B 一定是正确的选择。

现在我们来看为什么平均观察力会失败：它完全没有考虑走牌后 Agent 所在的信念状态。完全忽略信念状态是不可取的，尤其是有一种可能是会死的时候。因为它假设每一个未来状态都自动成为完美知识之一，这种方法从不选择收集信息的行动（像图 5.13 中的第一步）；它也不会选择向对手隐藏信息或向同伴提供信息的行动，因为它假设他们已经知道了；它从不虚张声势， $ ^{1} $因为它假设对手知道它的牌。第 17 章将构建算法来求解真实的部分可观察决策问题。

5.7 博弈程序发展现状

1965 年，俄罗斯数学家 Alexander Kronrod 称国际象棋为 “人工智能果蝇”。John McCarthy 不同意：正如遗传学家使用果蝇做实验以推广生物学应用一样，AI 用国际象棋来做同样的传播。可能更好的类比是国际象棋之于 AI 正如赛车大满贯之于汽车工业一样：博弈程序不可思议的快，但不适合开车购物或在非赛道上开。不管怎样，赛车和博弈都令人兴奋，都影响了一定的社会影响。本节介绍不同博弈类游戏的发展现状。

国际象棋：IBM的深蓝国际象棋程序，虽然现在已经退休，因为在直播中打败世界冠军Garry Kasparov而闻名。深蓝在有30个IBM RS/6000处理器的并行计算机上运行 $ \alpha $- $ \beta $搜索。它的特别之处在于它有480个定制的VLSI国际象棋处理器，用来执行生成行棋的功能、树的最后几层行棋的排序以及叶结点的评价。每步棋它搜索多至300亿个棋局，常规搜索深度是14步。它成功的关键是它对于足够感兴趣的主动或被动的行棋有突破搜索深度进行扩展能力。在某些情况下搜索深度可达40层。它的评估函数考虑了超过8000个特征，许多特征用来描述特有的棋子模式。它的“开局手册”有4000个棋局，它有存有70万个

大师级比赛棋谱的数据库，可以从中提取综合建议。系统用大型残局数据库保存已解决的残局，其中包含了全部的5子残局和很多的6子残局。这个残局数据库实际上扩展了有效搜索深度，允许深蓝在某些情况下表现完美，甚至当它距离将死对手还有很多步棋的时候。

深蓝的成功加强了人们广泛支持的信念：计算机的博弈水平的提高源自更强有力的硬件——这也是IBM的观点。算法上的进步允许标准个人计算机上运行的程序来赢得世界计算机国际象棋冠军杯。剪枝启发式有很多变形，有些可以把有效分支因子降低到3以下（实际分支因子大约是35）。这其中最重要的是空招启发式，通过使用让对手在游戏开始时连走两步棋的浅层搜索，能对棋局值生成一个很好的下界。这个下界常常允许 $ \alpha $- $ \beta $剪枝，从而节省完全深度搜索的开销。同样重要的技术是徒劳修剪，它可以帮助提前决策哪些行棋会引起后继结点的 $ \beta $截断。

HYDRA 可以看成是深蓝的后继。HYDRA 是 64 位 1GB 处理器集群，硬件是 FPGA（现场可编程门阵列）芯片。HYDRA 每秒可评估 2 亿个棋局，大概和深蓝一样，但由于充分发挥了空招启发式和向前剪枝技术，它的搜索深度达到了 18 层而不是 14。

RYBKA 是 2008 年和 2009 年计算机国际象棋世界杯的冠军，目前被认为是最强的计算机棋手。它使用的是现成的 8 核 3.2GHz 的 Intel Xeon 处理器，但对程序部分所知甚少。RYBKA 的主要优势在于由国际象棋大师 Vasik Rajlich 主要开发的评估函数，参与开发的还至少有其他三位国际象棋大师。

最近的比赛证实顶级的计算机国际象棋程序领先于所有人类棋手。（详见历史注释。）

西洋跳棋：Jonathan Schaeffer 和他的同事开发出在个人电脑上运行的使用的 Chinook 程序。Chinook 在 1990 年的简化比赛中战胜了长久以来的人类世界冠军，自 2007 年以来 Chinook 使用 $ \alpha $- $ \beta $ 搜索和存有 390000 亿个残局的数据库表现趋于完美。

奥赛罗（Othello），也叫翻转棋（Reversi），计算机中的奥赛罗游戏比棋盘中的可能更流行。它的搜索空间比国际象棋的小，通常是5到15步合法行棋，不过棋局评估要从零做起。1997年Logistello程序（Buro，2002）以6比0击败了人类世界冠军Takeshi Murakami。目前一般都承认人类在奥赛罗上无法与计算机抗衡。

西洋双陆棋（backgammon）：第5.5节解释了为什么掷骰子的不确定性使得深度搜索代价昂贵。大多数双陆棋的研究工作集中在改进评估函数。Gerry Tesauro（1992）把强化学习方法与神经网络相结合，开发出了相当精确的评估函数，并将之应用于深度为2或3的搜索中。经过上百万次的自我训练，Tesauro的程序TD-GAMMON稳定地排名在世界前列。此程序对游戏的开放招数的观点，在一定程度上根本改变了人类认识。

围棋是亚洲最流行的棋盘游戏。由于棋盘是 $ 19 \times 19 $ 的，几乎所有空格都可以走棋，初始的分支因子为 361，这对于常规的 $ \alpha $- $ \beta $ 搜索算法来说太令人生畏了。另外，写出评估函数也十分困难，原因是达到残局之前的控制通常很难预测。所以顶级的程序，如 MOGO，使用的是蒙特卡罗香草算法，而不是 $ \alpha $- $ \beta $ 搜索。关键是在部署过程中如何行棋。没有积极剪枝；所有移动都是可能的。UCT（树的上限置信区间）方法是首先进行少量迭代确定随机走棋，对走法进行选择性采样，集中关注那些有希望赢得比赛的走法。采用的技巧包括基于知识的规则，用于给定模式下的特殊行棋建议，和受限局部搜索来确定战术问题。一些程序还使用了特殊的组合博弈论技术来分析残局。这些技术把围棋分解进行独立分析，然后再整合（Berlekamp 和 Wolfe，1994；Müller，2003）。这样得到的最优解法使很多职业围棋选手

惊奇，人们一直以为人类更精于此道。当前的围棋程序可以在缩小的9×9棋盘达到大师级，在全棋盘上只是个好的业余选手而已。

桥牌是不完整信息的游戏：选手看不到其他选手的牌。桥牌也是多人游戏，有四个人参加而不是两人，牌手们两人一对组成对抗双方。在第5.6节中讨论过，部分可观察游戏如桥牌的最优打法要考虑多种因素，包括信息搜集、通信交流、和精细的概率权重等。赢得1997年计算机桥牌赛冠军的Bridge Baron程序（Smith等人，1998）采用了上述技术。尽管它不是最优解法，Bridge Baron是少数几个成功地运用复杂的分层规划（参见第11章）的博弈系统，它包含了诸如飞牌和挤牌这样的为桥牌选手所熟悉的先进理念。

GIB 程序（Ginsberg，1999）使用蒙特卡罗方法所向披靡地赢得了 2000 年计算机桥牌世界杯的冠军。从那时开始，其他的取胜程序都使用了 GIB 的方法。GIB 的主要贡献是使用了基于解释的一般化来分别计算和缓存各种情形标准中最优打法的通用规则。例如，如果一位牌手手中有一门花色的 A-K-Q-J-4-3-2，另一选手有 10-9-8-7-6-5，第一位选手有 $ 7 \times 6 = 42 $ 种方法在这门花色上领先。但是 GIB 把这处理成两种情形：首位选手在高牌和低牌中领先；不管具体是哪张牌。利用这种优化（还有其他的），这使得 GIB 可以很快地准确解决每副牌。GIB 的战术精确性弥补了它在信息推理方面的缺陷。它参加了 1998 年的人类标准桥牌世界杯（只涉及主打，无叫牌），在 35 名选手中取得了第 12 名，大大超出了很多专家的意料。

GIB 使用蒙特卡罗仿真可以达到专家水准，而军棋程序却不行有几个原因。首先，GIB对完全可观察版本的游戏评估是精确的，它搜索了整个博弈树，而军棋程序依赖的是不精确的启发式。但更重要的事实是在桥牌中，部分可观察信息的不确定性大多来自发牌，而不是对手会如何打牌。蒙特卡罗适于处理随机性，但并不总是能处理好，特别是涉及信息价值的策略时。

拼字（Scrabble）：很多人认为拼字游戏困难的是想出好单词，但在给定官方字典条件下，写出程序找出最好的拼法并不难（Gordon，1994）。然而这并不意味着游戏已经求解：这样做得到的是好的解法但不是专家水平的解。问题是拼字游戏既是部分可观察的也是随机的：你并不知道对手有哪些字母或你会抓到哪张。所以要玩好拼字同时包括了西洋双陆棋和桥牌的难点。尽管这样，在2006年QUACKLE程序以3：2打败了前世界冠军David Boys。

5.8 其他 途径

因为大多数情况下无法计算博弈中的最优决策，所有算法都必须做一些假设或近似。基于极小极大搜索、评估函数和 $ \alpha $- $ \beta $剪枝的标准方法只是其中一条途径。也许由于这种方法使用的时间已经相当长，所以它压倒其他方法占据了主导地位。有些人认为正是由于这个原因致使博弈的研究脱离了主流人工智能：因为这种方法没有为决策的一般问题发展出新见解提供足够的发展空间。本节我们来看看其他方法。

首先，考虑启发式极小极大方法。给定一棵搜索树，假设其叶结点的评估值是正确的，极小极大方法能选择出最优招数。在现实中，评估通常是对棋局的粗糙估计，可能有很大的误差。图5.14给出了一棵极小极大搜索的两层博弈树，算法建议走右路因为100>99。在

所在评估值都正确时这是最优的选择。但是评估函数值只是近似值。假设叶结点间相互独立，并且评估值都有误差，误差随机分布于0和标准差 $ \sigma $之间。那么当 $ \sigma=5 $时，左路分支有71%的可能表现更好， $ \sigma=2 $时也有58%的可能表现更好。这是因为右路分支的四个结点值都很接近99；如果其中一个由于误差而真实值低于99，此时左路选择才是最优。

现实中的情况更加复杂，因为结点的评估值通常不是独立的。如果一个结点评估错误，那么兄弟结点出错的可能性相当大。评估值为99的结点的兄弟结点的评估值为1000，这意味着实际上可能有更高的值。我们可以让评估函数返回可能值上的可能分布概率，但也很难将这些分布正确结合，因为对结点和兄弟结点之间的关系我们没有好的模型。

下面讨论生成博弈树的搜索算法。算法设计者的目标是规范计算过程以运行快速和产生好招数为目标。 $ \alpha $- $ \beta $剪枝算法不仅被设计用于选择一个好的招数，还要计算出所有合法招数的取值范围。而这些额外信息是不需要的，我们举例说明原因。考虑某棋局中只有一种合法招数。 $ \alpha $- $ \beta $搜索仍然会生成搜索树并对其进行评估，告诉我们这个唯一的选择是最优招数。实际上此时无论如何我们都会走这步，知道它的值毫无意义。类似的，如果一些合理行棋中有一招是明显的好棋，或者是有一招是明显的坏棋时，我们也不想浪费时间去 $ \alpha $- $ \beta $搜索来确定精确取值空间。这是结点扩展的效用值的思想。一个好的搜索算法应该选择那些效用值高的结点扩展——即，那些可能发现好棋的结点。如果没有结点扩展的效用值高于它的开销（从时间上考虑），那么算法就停止搜索而走一步棋。注意这种技术不仅适合于明显喜好的情形，也适合于对称招数，这里对称招数指的是没有搜索可以说明某招数比其他的更好。

这种关于计算该做什么的推理称为元推理（关于推理的推理）。它不仅应用于博弈，还可以用在其他任何种类的推理中。所有计算的目标都是为了试图到达更好的决策，都有开销，也都有对决策质量的一定改进。 $ \alpha $- $ \beta $算法结合了最简单类型的元推理，是树中的某些分支可以被忽略而不带来损失的影响的定理。它可能可以做得更好。在第16章中，会看到这些想法变得更精确更易于实现。

最后再次考察搜索自身的本质。启发式搜索和博弈的算法都是通过生成具体状态的序列实现的，从初始状态开始，然后应用评估函数。显然，这跟人类的博弈方式不同。在国际象棋中，人的头脑中有一个特定目标——例如，诱捕对方的皇后——然后可以用这个目标有选择性地生成一个达到目标的看似合理的计划。这种目标制导的推理或者规划有时完全消除了组合搜索。David Wilkins（1980）的PARADISE是唯一在国际象棋中成功运用目标制导推理的程序：它有能力解决某些需要18步组合的国际象棋问题。不过目前对如何把两

种算法结合在同一鲁棒且高效的系统中我们所知不多，虽然 Bridge Baron 可能选择了一条正确的路。一个完整的集成系统会成为博弈研究和人工智能研究的重大成就，因为它会成为实现一般智能 Agent 的基础。

5.9 本章小结

已经讨论过各种博弈游戏，以理解最优招数以及如何在实际中玩得好。本章的重要思想如下：

博弈游戏通过下列元素定义：初始状态（棋盘设置），每个状态下的合法行动，每个行动的结果，终止测试（说明什么时候游戏结束），和终止状态上的效用函数。

在有完整信息的两人零和游戏中，极小极大算法可以通过对博弈树的深度优先枚举选出最优招数。

☑ $ \alpha-\beta $ 搜索算法可以计算出和极小极大算法一样的最优招数，由于消除了被证明无关的子树，效率得到提高。

通常，考虑整棵博弈树是不可行的（即使用 $ \alpha-\beta $算法），所以在某个点截断搜索，并应用启发式评估函数对某个状态的效用值进行计算。

很多博弈程序在开局和残局使用提前计算好的表，通过查表而不是搜索来计算最佳招数。

机会博弈可以通过扩展极小极大算法来求解，扩展后的算法通过计算其全部子结点的平均效用值来评价机会结点，平均效用值是用每个子结点的概率加权平均。

对于像桥牌和车棋这样的不完整信息的游戏，需要对每个游戏者当前和未来的信念状态进行推理。对行动值的缺失信息，可以简单地处理成取可能配置上的平均值而得到。

计算机程序在西洋跳棋、奥赛罗和西洋跳棋上已经可以击败人类最好的棋手。对不完美信息博弈，如扑克游戏，桥牌和军棋上水平上也已经很接近了，而计算机在分支因子很大并且启发式知识很少的博弈中如围棋仍处于业余水平。

参考文献与历史注释

机器博弈的早期历史有无数骗局。其中最臭名昭著的是 Wolfgang von Kempelen 男爵（1734—1804）的号称会下国际象棋的机器“The Turk”，它曾经击败过拿破仑，但后来被发现其实是把著名的棋手藏在魔术师变戏法用的柜子里（参见 Levitt，2000）。它从1769年一直用到1854年。在1846年，Charles Babbage（曾对“土耳其人”很着迷）似乎第一个严肃地讨论了计算机下国际象棋和西洋跳棋的可行性（Morrison和Morrison，1961）。他没有理解搜索树的指数复杂度，声称“分析机的组合能力大大走出了需求，这包括国际象棋”。Babbage还设计了下井字棋的专用机器，但是没有建造出来。第一部真正的博弈机器大约是1890年由西班牙工程师Leonardo Torres y Quevedo建造的。它专门用来下“KRK”（王车对王）残局的国际象棋机器，不论王和车在什么位置都保证赢。

极小极大算法可以追溯到现代集合论的创始者 Ernst Zermelo 于 1912 年发表的一篇论文。很遗憾论文中有一些错误，没有能给出极小极大的正确描述。另一方面，文章确实陈述了计算倒推值的基本思想并提出了（没有证明）众所周知的 Zermelo 定理：国际象棋是确定的——或者白方赢或者黑方赢或者是平局；我们只是不知道到底结果是什么。Zermelo 认为最终总会知道结果，“国际象棋将会推动博弈的所有特征。”开创性的著作《博弈与经济行为理论》(Theory of Games and Economic Behavior)(von Neumann 和 Morgenstern,1944)是博弈论的坚实基础，这本书给出了有些博弈需要随机（或者无法预测的）策略的分析。详见本书第17章。

1956 年 John McCarthy 构思了 $ \alpha $- $ \beta $ 搜索，尽管他并没有发表。国际象棋程序 NSS（Newell 等人，1958）使用了简化版本的 $ \alpha $- $ \beta $ 搜索；它是第一个使用 $ \alpha $- $ \beta $ 搜索的国际象棋程序。Hart 和 Edwards（1961）、Hart 等人（1972）的论文中描述了 $ \alpha $- $ \beta $ 剪枝。 $ \alpha $- $ \beta $ 搜索应用于 John McCarthy 的学生写的 “Kotok-McCarthy” 国际象棋程序中（Kotok，1962）。Knuth 和 Moore（1975）证明了其正确性并给出了时间复杂度的分析。Pearl（1982b）证明了 $ \alpha $- $ \beta $ 搜索在所有固定深度的博弈树搜索算法中是渐近最优的。

研究人员做出了一些努力试图去克服第5.8节提到的“标准方法”弊端。第一个有理论基础的非空竭启发式搜索算法可能是B*（Berliner，1979），试图为博弈树的每个结点保持可能的取值区间，而不仅是给它一个估计值。选择叶结点进行扩展以精化取值区间，直到有进一步棋“脱颖而出”。Palay（1985）用值的概率分布替代区间扩展了B*算法。David McAllester（1988）的对策数搜索算法通过修改叶结点的值，扩展那些能造成根结点优先考虑新招数的叶结点。MGSS*（Russell和Wefald，1989）使用第16章的决策论技术来估计叶结点的期望值，以改进根结点的决策质量。在奥赛罗上这种算法比 $ \alpha $- $ \beta $算法要好，尽管它搜索的结点数量的量级要小。原理上，MGSS*方法适用于控制任何形式的深思熟虑。

α-β搜索在很多方面都像是深度优先分支界限法的两人模拟，在单个 Agent 情况下 A*算法占统治地位。SSS*算法（Stockman，1979）可以被看作是双人 A*算法，要达到同样的决策不会扩展比α-β算法更多的结点。内存需求和队列的计算开销使得原始形式的 SSS*算法并不实用，不过有从 RBFS 算法发展出来（Korf 和 Chickering，1996）的线性空间版本。Plaat 等人（1996）研究出 SSS*算法的新观点，把α-β算法和调换表（transposition table）结合在一起，克服了原始算法的缺陷，开发出称为 MTD(f)的新变种，并被很多顶级程序所采用。

D. F. Beal（1980）和 Dana Nau（1980，1983）研究了极小极大算法应用在近似评价中的缺陷。他们指出在树中叶结点的值分布的某种特定假设下，极小极大算法在根结点产生的值实际上不如直接用评估函数可靠。Pearl 的书《启发式》（1984）对这种明显的悖论给出了部分解释，同时分析了很多博弈算法。Baum 和 Smith（1997）提出基于概率的对极小极大值的替代方法，结果显示某些游戏中它表现更好。Donald Michie（1966）提出了期望极小极大算法。Bruce Ballard（1983）对 $ \alpha $- $ \beta $剪枝进行了扩充以求解有机会结点的问题，Hauk（2004）重新审视了这项工作并提供了经验结果。

Koller 和 Pfeffer（1997）描述了一个求解部分可观察问题的完整系统。此系统是通用的，处理最优策略中含有随机行棋的博弈，也关注那些用以往系统求解起来过于复杂的博弈问题。当然，它无法求解一些复杂博弈如扑克、桥牌和军棋。Frank 等人（1998）给出了

蒙特卡罗搜索的一些变形，包括那些 MIN 有完整信息但 MAX 却没有的。在确定的部分可观察博弈中，军棋引起了广泛关注。Ferguson 演示了用象和马（1992）或两个象打败王的随机策略。第一个军棋程序关注残局的将死并在信念状态空间完成与或搜索（Sakuta 和 Iida，2002；Bolognesi 和 Ciancarini，2003）。增量的信念状态算法可以确保找到更多的中盘将死（Russell 和 Wolfe，2005；Wolfe 和 Russell，2007），但有效的状态评估依然是有效行棋的主要难点（Parker 等人，2005）。

国际象棋是 AI 最先考虑的任务，很多早期对计算机时代有影响力的人物几乎都对用计算机下国际象棋感兴趣，其中包括 Konrad Zuse（1945）、Norbert Wiener 的书《控制论》（1948）和 Alan Turing（参见 Turing 等人，1953）。但是给出了博弈的完整思想包括棋局表示、评估函数、静止搜索和一些选择性（非穷举）博弈树搜索的是 Claude Shannon 的文章“国际象棋程序设计”（1950）。Slater（1950）和他的论文审稿人也讨论了计算机下棋的可能性。

D. G. Prinz（1952）实现的程序能求解一些国际象棋的残局问题，但不能完整地下一盘棋。Los Alamos 美国国家实验室的 Stan Ulam 和他的小组写出在 $ 6 \times 6 $ 棋盘上下棋的程序（没有象）（Kister 等人，1957）。在 12 分钟内它可以搜索 4 层深度。Alex Bernstein 写出了第一个可以下整盘标准国际象棋的程序（Bernstein 和 Roberts，1958）。 $ ^{1} $

第一次计算机国际象棋比赛是在 Kotok-McCarthy 程序和 20 世纪 60 年代中期由莫斯科理论和实验物理学研究所（Adelson-Velsky 等人，1970）编写的 ITEP 程序之间进行的。这场洲际比赛通过电报传输进行。1967 年 ITEP 以 3 比 1 获胜。第一个成功和人进行象棋比赛的程序是 MIT 的 MACHACK-6（Greenblatt 等人，1967）。它的 Elo 积分是 1400 分，大大超过了初学者的水平线 1000 分。

1980年设立的Fredkin奖，给第一个达到大师等级分的程序提供奖励。第一个得到5000美元的奖励的程序是BELLE（Condon和Thompson，1982），积分为2250。第一个拿到10000美元奖励的是1989年达到USCF（美国国际象棋联盟）的2500等级分（接近特级大师等级）的是DEEP THOUGHT（Hsu等人，1990）。100000美元大奖颁给了在1997年里程碑式地战胜了世界冠军Garry Kasparov的DEEP BLUE（Campbell等人，2002；Hsu，2004）。Kasparov写道：

决定性的比赛发生在第二局，它在我的记忆中留下了伤痕……我们看到了远远超出我们能疯狂想象的事情，计算机能够预见到它的决策的长远影响。那台机器拒绝走一步有短期优势的决策棋——这显示了类似于人类的对危险的感觉（卡斯帕罗夫，1997）。

Ernst Heinz（2000）提供了可能是现代国际象棋程序的最完整描述，他开发的DARKTHOUGHT程序在1999年世界杯上非商业PC程序中排名最高。

最近几年，计算机国际象棋程序领先于人类棋手。2004—2005 年 HYDRA 以 3.5 : 0.5 打败了世界冠军特级大师 Evgeny Vladimirov。2006 年，DEEP FRITZ 以 4 : 2 打败了世界冠

军 Vladimir Kramnik，2007 年 RYBKA 在先让出一些优势（如让一卒）的情况下先后打败了几位特级大师。2009 年，有史以来最高的 Elo 积分是 Kasparov 的 2851。HYDRA（Donninger 和 Lorenz，2004）的积分已经达到 2900 和 3100 之间，但是这个积分是基于一些小型比赛并不可靠。Ross（2004）讨论了人类棋手如何利用计算机程序的弱点。

计算机第一个完整下完的经典博弈游戏是西洋跳棋。Christopher Strachey（1952）写出了第一个可运行的西洋跳棋程序。从1952年开始，IBM的Arthur Samuel利用业余时间开发出能够通过自己大量下棋学习评估函数的西洋跳棋程序（Samuel，1959，1967）。我们将在第21章详细讨论。Samuel的程序开始是个新手，不过仅通过几天的自我下棋学习后它就超过了Samuel本人的水平。1962年它利用对方的错误击败了“蒙目西洋跳棋”冠军Robert Nealy。许多人认为考虑到Samuel使用的计算设备（IBM704）的内存是1万字，长期存储用的是磁带，处理器是0.000001GHz，这次胜利仍然是一个伟大的成就。

这项由 Samuel 开始的挑战由 Alberta 大学的 Jonathan Schaeffer 继续着。他的 Chinook 在 1990 年美国公开赛取得第二名，从而获得了向世界冠军挑战的权利。接着它遇上了麻烦，Marion Tinsley。Tinsley 博士是 40 多年的世界冠军，在所有比赛中总共只输过三盘。在第一次与 Chinook 的对弈中，Tinsley 遭受了他职业生涯中的第四盘和第五盘失败，不过仍以 20.5 比 18.5 赢了整个比赛。1994 年 8 月的世界冠军赛中，Tinsley 因健康原因退出了比赛。于是 Chinook 成为正式的世界冠军。Schaeffer 继续完善残局数据库，在 2007 年“彻底解决”了西洋跳棋（Schaeffer 等人，2007；Schaeffer，2008）。这一点 Richard Bellman（1965）早已预料到。他在介绍倒推分析的动态规划方法时指出，“对于西洋跳棋，由于给定棋局下可能的行棋数很小，我们很自信地期待计算机能够完美求解此类问题。”然而 Bellman 并没有提到整个西洋跳棋博弈树的大小。大概共有 500 千万亿个棋局。在有 50 台或更多机器的集群上计算 18 年后，Jonathan Schaeffer 的小组完成了所有 10 个棋子以下的残局表：共有超过 39 万亿个。从这出发，他们可以使用向前 $ \alpha $- $ \beta $ 搜索来得到西洋跳棋的最好行棋。请注意这是双向搜索的应用（3.4.6 节）。构建所有选手的残局表是不实用的：这可能需要 10 亿 GB 的存储。而不用表的搜索也是不实用的：搜索树中有 $ 8^{47} $ 个棋局，以当前的计算水平需要上千年来求解。要求解西洋跳棋，需要把灵巧搜索、残局数据、处理器和内存价格下降结合在一起。这样，西洋跳棋就可以加入到 Qubic（Patashnik，1980）、Connect Four（Allis，

1988）和 Nine-Men 的 Morris（Gasser，1998）等计算机已求解的博弈行列中。

西洋双陆棋是机会博弈，Gerolamo Cardano（1663）给出了数学分析，但直到1970年才有计算机的参与，即BKG程序（Berliner，1980b）；它使用了复杂的手动构造的评估函数，并且只搜索一步深度。它是在主要经典博弈游戏中击败人类世界冠军的第一个程序（Berliner，1980a）。Berliner欣然承认那场比赛BKG运气很好。Gerry Tesauro（1995）的TD-GAMMON一直保持着世界冠军水准。BGBLITZ程序是2008计算机奥林匹克赛的冠军。

围棋是确定性博弈，过大的分支因子使得它很有挑战性。Bouzy 和 Cazenave（2001）和 Müller（2002）总结了计算机围棋程序的关键问题和早期发展情况。1997 年之前没有出现有竞争力的围棋程序。现在最好的程序通常能给出大多是大师级的行棋；主要问题是在完成一盘棋的过程中它至少会出一个昏招从而导致对手取胜。很多博弈使用 $ \alpha $- $ \beta $ 搜索，但围棋程序使用的更多的是基于 UCT（树的上限置信区间）的蒙特卡罗方法（Kocsis 和 Szepesvari，2006）。2009 年最强的围棋程序是 Gelly 和 Silver 的 MOGO（Wang 和 Gelly，2007；Gelly 和 Silver，2008）。2008 年 8 月，MOGO 令人惊奇地战胜了专业选手金明完，尽管人类让了九子（这大致等价于国际象棋中让了一后）。金明完认为 MOGO 大概是二段或者三段水平，高级业余选手中水平较低的棋手。在这场比赛中，运行 MOGO 的机器是有 800 个处理理 15 teraflop 的超级计算机（计算能力大概是 Deep Blue 的 1000 倍）。几周之后，MOGO 在让 5 子的情况下，战胜了职业六段选手。在围棋的 $ 9 \times 9 $ 简化版本中，MOGO 接近于职业选手 1 段的水平。蒙特卡罗搜索的新形式很有可能带动计算机围棋的飞速发展。计算机围棋协会出版的《计算机围棋通讯》描述了当前的发展状况。

桥牌：Smith 等人（1998）讲述了基于规划的程序如何赢得了 1998 年的计算机桥牌世界杯，Ginsberg（2001）的基于蒙特卡罗住址的 GIB 程序赢得了接下来的计算机冠军，并且令人惊奇地战胜了人类棋手和标准问题集。从 2001 至 2007 年，计算机桥牌冠军 5 次被 JACK、2 次被 WBRIDGE5 所夺得。尚没有学术文章描述这些程序的结构，传闻它们都使用了蒙特卡罗技术，该技术在桥牌中的使用由 Levy（1989）提出。

拼字（Scrabble）：MAVEN 是顶级程序之一，它的作者 Brian Sheppard（2002）描述了该程序。Gordon（1994）讨论了如何生成最高分的行棋，Richards 和 Amir（2007）讨论了对手建模问题。

足球（Kitano等，1997/b；Visser等，2008）和台球（Lam和Greenspan，2008；Archibald等人，2009）以及其他连续空间的随机游戏逐渐引起了AI研究人员的关注，不仅仅是在仿真界也包括真实的游戏机器人。

每年都会有计算机博弈比赛，论文也出现在多种会议中。名字容易引起误会的论文集《人工智能的启发式程序设计》报道了计算机奥运会，其中包括了范围广泛的各种博弈游戏。通用博弈比赛（Love等，2006）中的程序要参加的博弈是未知的，博弈规则有逻辑描述，程序要自学这些规则来参加比赛。还有一些博弈研究方面的重要论文被编辑成文集（Levy，1988a，1988b；Marsland和Schaeffer，1990）。成立于1977年的计算机国际象棋协会（ICCA）出版《国际计算机博弈游戏（ICGA）协会会刊》（以前是ICCA会刊）。重要论文还发表在由Clarke（1977）发起的系列论文集《计算机国际象棋进展》中。在《人工智能》杂志2002年第134卷中包括了对国际象棋、翻转棋、海克斯、日本将棋、围棋、双陆棋、扑克牌、拼字以及其他游戏的发展状况描述。自1998年起，“计算机与博弈”会议每两年举办一次。

习题

5.1 假设你有先知， $ OM(s) $，可以准确预测对手在任一状态下的行棋。利用这一点，给出博弈问题的形式化，并将之视为（单个 Agent）搜索问题。给出寻找最优解的算法。

5.2 考虑两个八数码难题的问题求解。

a. 参照第3章给出完整的问题形式化。

b. 可达的状态空间有多大？请给出精确的数字表达式。

c. 假设我们这样修改问题：两个选手轮流移动；用硬币来决定选手移动的是哪道题；第一个求解了某道题的就是赢家。在这样的假设下应该使用什么算法来确定移动？

d. 如果两位选手都是完美的，请说明最终总会有人获胜。

5.3 假设习题 3.3 中的朋友不想与其他朋友见面。这个问题就变成了两个选手的追逐-逃避博弈。现在假设两个人轮流移动。当两个处于同一结点时游戏结束；对于追逐者记录他所使用的时间（逃避者没输就是“赢”）。示例见图 5.16。

（a）图中边的代价均为1。初始状态追逐者在P在b点、逃避者E在d点。（b）该图的部分博弈树。每个结点中标有P、E的坐标。P先走。标有“？”的分支表示尚未探索

a. 复制博弈树并给出终止结点的值。

b. 在每个分支结点边上写出你对它的值的推理（数字，或不等式，如 $ \geq $14或“？”）。

c. 在每个问号下边，写出到达此分支的结点名称。

d. 解释（c）中如何通过考虑图中的最短路径得出结点的取值界限。记住到达叶结点的开销和求解的开销。

e. 假设给出了博弈树及（d）的叶结点界限，计算顺序从左到右。用圆圈画出“？”

结点中不再扩展的结点，并勾出那些完全不用考虑的结点。

f. 你能根据树的信息证明谁将赢吗？

5.4 考虑一个或多个如下的随机博弈：大富翁，拼字，已知定约的桥牌，Texas 扑克。请给出状态描述、行棋生成器、效用函数、评估函数。

5.5 描述并实现一个实时的多人游戏环境，状态中包含时间，每个选手有固定的时间分配。

5.6 讨论如何将标准博弈技术应用于连续物理状态空间的游戏，如网球、台球、门球。

5.7 证明下面的断言：对于每棵博弈树，MAX 使用极小极大算法对抗次优招数的 MIN 得到的效用值不会比对抗最优招数的 MIN 得到的效用值低。你能否找出一棵博弈树，使得 MAX 用次优策略依然要好于次优 MIN 时的策略。

5.8 考虑图 5.17 中描述的两人游戏。

选手 A 先走。两个选手轮流走棋，每个人必须把自己的棋子移动到任一方向上的相邻空位中。如果对方的棋子占据着相邻的位置，你可以跳过对方的棋子到下一个空位。（例如，A 在位置 3，B 在位置 2，那么 A 可以移回 1。）当一方的棋子移动到对方的端点时游戏结束。如果 A 先到达位置 4，A 的值为 +1；如果 B 先到位置 1，A 的值为 -1。

a. 根据如下约定画出完整博弈树：

每个状态用 $ (s_{A}, s_{B}) $表示，其中 $ s_{A} $和 $ s_{B} $表示棋子的位置。

每个终止状态用方框画出，用圆圈写出它的博弈值。

把循环状态（在到根结点的路径上已经出现过的状态）画上双层方框。由于不清楚他们的值，在圆圈里标记一个“？”。

b. 给出每个结点倒推的极小极大值（也标记在圆圈里）。解释怎样处理“？”值和为什么这么处理。

c. 解释标准的极小极大算法为什么在这棵博弈树中会失败，简要说明你将如何修正它，在（b）的图上画出你的答案。你修正后的算法对于所有包含循环的游戏都能给出最优决策吗？

d. 这个4-方格游戏可以推广到n个方格，其中n>2。证明如果n是偶数A一定能赢，而n是奇数则A一定会输。

5.9 本题以井字棋（圈与十字游戏）为例练习博弈中的基本概念。定义 $ X_n $ 为恰好有 $ n $ 个 $ X $ 而没有 $ O $ 的行、列或者对角线的数目。同样 $ O_n $ 为正好有 $ n $ 个 $ O $ 的行、列或者对角线的数目。效用函数给 $ X_3 = 1 $ 的棋局 +1，给 $ O_3 = 1 $ 的棋局 -1。所有其他终止状态效用值为 0。对于非终止状态，使用线性的评估函数定义为 $ Eval(s) = 3X_2(s) + X_1(s) - (3O_2(s) + O_1(s)) $。

a. 估算可能的井字棋局数。

b. 考虑对称性，给出从空棋盘开始的深度为2的完整博弈树（即，在棋盘上一个X一个O的棋局）。

c. 标出深度为2的棋局的评估函数值。

d. 使用极小极大算法标出深度为1和0的棋局的倒推值，并根据这些值选出最佳的起

始行棋。

e. 假设结点按对 $ \alpha-\beta $剪枝的最优顺序生成，圈出使用 $ \alpha-\beta $剪枝将被剪掉的深度为2的结点。

5.10 如下定义井字棋家族。S 表示方格棋盘，W 表示赢的棋局。每个赢局是 S 的子集。例如，在标准井字棋中，S 是 9 格集合而 W 是 8 个子集：三行、三列和两个对角线。在其他方面，这个游戏与标准井字棋相同。从空棋盘开始，选手轮流在空格处画上自己的标记。如果选手画出了赢局，则赢得了比赛。如果棋盘上没有空格但没有人赢，则是和棋。

a. 设 $ N = |S| $，即方格数。请给出井字棋博弈树中结点数上限，将之表示为关于 N 的函数。

b. 给出博弈树在最坏情况下即 $ W = \{\} $ 时的下限。

c. 请给出通用井字棋棋局的评估函数。该函数可能依赖于 S 和 W。

d. 假设可能在 100N 条机器指令内生成新棋局并检查它是否是赢局，假设是 2GHz 处理器。不计内存限制。利用你在 a 中的估算，在 1 秒的计算机时间内使用 $ \alpha - \beta $ 能够完全求解的博弈树是多大？1分钟呢？1小时呢？

5.11 设计通用博弈程序，有能力完成多种博弈游戏。

a. 实现下面一种或多种游戏的行棋生成器和评估函数：Kalah 游戏（美国播棋），翻转棋，西洋跳棋和国际象棋。

b. 构造一个通用的 $ \alpha $- $ \beta $博弈 Agent。

c. 比较增加搜索深度、改进行棋排序和改进评估函数对程序的影响。你的有效分支因子有多接近于完美行棋排序的理想情况呢？

d. 实现一个选择搜索算法，如 B*（Berliner，1979），对策数搜索（McAllester，1988），或 MGSS*（Russell 和 Wefald，1989），并与 A*的性能作出比较。

5.12 对于两人非零和游戏，每个人都有自己的效用函数并且相互知道，应如何修改极小极大算法和 $ \alpha $- $ \beta $剪枝算法进行求解？如果对终止效用值没有约束， $ \alpha $- $ \beta $剪枝是否可能剪裁某一结点呢？如果每位选手任一状态的效用函数值至多相差常量 k 呢？博弈是否成为合作了呢？

5.13 请给出 $ \alpha-\beta $ 剪枝正确性的形式化证明。要做到这一点需考虑图 5.18。问题为是否要剪

掉结点 $ n_{j} $，它是一个 MAX 结点，是 $ n_{1} $ 的一个后代。

$$ n_{1} $$

$$ n_{j} $$

a. $ n_{1} $ 的值是所有后代结点的最小值： $ n_{1} = \min(n_{2}, n_{21}, \cdots, n_{2b}) $。请为 $ n_{2} $ 找到类似的表达式，以得到用 $ n_{j} $ 表示的 $ n_{1} $ 的表达式。

b. 深度为 i 的结点 $ n_{i} $ 的极小极大值已知， $ l_{i} $ 是在结点 $ n_{i} $ 左侧结点的极小值（或者极大值）。同样， $ r_{i} $ 是在 $ n_{i} $ 右侧的未探索过的结点的极小值（或者极大值）。用 $ l_{i} $ 和 $ r_{i} $ 的值重写 $ n_{1} $ 的表达式。

c. 现在重新形式化表达式，来说明为了向 $ n_{1} $ 施加

影响， $ n_{j} $ 不能超出由 $ l_{i} $ 值得到的某特定界限。

d. 假设 $ n_{j} $ 是 MIN 结点的情况，请重复上面的过程。

5.14 请证明在最佳行棋排序的情况下， $ \alpha-\beta $剪枝的时间复杂度为 $ O(2^{m/2}) $，其中 m 为博弈树的最大深度。

5.15 假设你的国际象棋程序每秒可以评价一百万个结点。在保存于调换表中的游戏状态的压缩表示基础上进行决策。你在2GB的内存表里可以存储多少条目？对于每一步棋三分钟的搜索而言时间是否足够？计算一次评估函数的时间里你可以做多少次查表操作？现在假设调换表存储在磁盘上。标准磁盘硬件进行一次磁盘寻道的时间里能完成多少次评估？

5.16 本习题考虑机会博弈的剪枝。图5.19给出了一个简单游戏的完整博弈树。假设叶结点的计算顺序是从左到右，而且在一个叶结点被评估之前我们对它一无所知，可能的取值范围是 $ -\infty $到 $ \infty $。

a. 复制这个图，在图中标出所有内部结点的值，用箭头指出根结点选择的行棋。

b. 给定前六个叶结点的值，还需要计算第七个和第八个叶结点的值吗？如果是给定前七个叶结点的值，第八个还需要计算吗？请对你的结论给出解释。

c. 假设叶结点的值都在-2到2之间。计算完前两个叶结点值之后，左手机会结点的取值范围是多少？

d. 用圆圈划出在 c 中假设下无需计算的叶结点。

5.17 考虑机会博弈，请给出期望极小极大算法的实现和 Ballard（1983）描述的*- $ \alpha $- $ \beta $算法的实现。以西洋双陆棋为例测试这些算法，并度量*- $ \alpha $- $ \beta $算法的剪枝有效性。

5.18 证明即使在有机会结点的情况下，对叶结点值的正线性变换（例如把值 x 变换成 $ ax + b $，其中 a > 0）不会影响在博弈树中对行棋的选择。

5.19 考虑有机会结点的游戏中选择行棋的过程：

生成一些掷骰子的序列（比如50个）直到适当的深度（比如8）。

已知的掷骰子结果使得博弈树变成确定性的。对于每个掷骰子序列，用 $ \alpha-\beta $算法求解该确定性博弈树。

用这些结果来估计每步棋的值，从而选出最佳的。

这个过程是否运转良好？为什么？

5.20 下面的讨论中，max 树仅包含 MAX 结点，“期望极大值”树以根为 MAX 结点，之

后是机会结点与 MAX 结点交替。对于机会结点，所有概率都非 0。目的是在受限的深度内搜索找出根结点的值。对以下 a～g，请要么给出实例要么给出不可能的理由。

a. 假设叶结点是有限的但不受限制，在 max 树上可能应用剪枝（如 $ \alpha $- $ \beta $）吗？

b. 同样条件下，在期望极大值树中有可能剪枝吗？

c. 如果叶结点值都是非负数，max 树可能剪枝吗？举例说明，或说明不可能的理由。

d. 如果叶结点值都是非负数，期望极大值树可能剪枝吗？举例说明，或说明不可能的理由。

e. 如果叶结点值都在[0, 1]之间，max 树可能剪枝吗？举例说明，或说明不可能的理由。

f 如果叶结点值都在[0, 1]之间，期望极大值树可能剪枝吗？

f. 如果叶结点值都在[0, 1]之间，期望极大值树可能剪枝吗？

g. 考虑期望极大值树中的机会结点。以下哪种计算顺序最有可能形成剪枝？

i. 最低概率优先

ii. 最高概率优先

iii. 都差不多

5.21 判断真假，并给出简洁说明。

a. 在完全可观察、轮流下棋的零和游戏中，假设两位选手绝对理性，这对第一位选手猜测第二位选手的下棋策略没有任何帮助——即，第一位选手无法知道第二位选手将走哪一步棋。

b. 在部分可观察、轮流下棋的零和游戏中，假设两位选手绝对理性，这对第一位选手猜测第二位选手的下棋策略没有任何帮助。

c. 完美的理性西洋双陆棋 Agent 绝不会输。

5.22 仔细考虑习题 5.4 每种博弈中的偶然事件和不完全信息的相互影响。

a. 标准的期望极小极大值模型适合哪种博弈？给出算法实现，适当修改博弈环境，用博弈 Agent 上运行你的算法。

b. 习题 5.19 中描述的方案适合于哪种博弈？

c. 在某些游戏中游戏者对于当前状态的认识是不同的，你会如何处理这些情况。