Programming 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Programming
标  题: [转载]国际象棋程序设计(四)：基本搜索方法
发信站: BBS 哈工大紫丁香站 (Thu Nov 11 10:52:17 2004)

国际象棋程序设计(四)：基本搜索方法

Fran?ois Dominic Laramée/文

　　这个烦琐、没有代码、像胶水一样的连载，已经进入第四部分了，你们还在看下去
吗？如果是的，就写eMail给我，我就可以找到写这些东西的理由了。
　　无论如何，这个月的主题是策略类游戏的双向搜索(Two-Agent Search)【译注：意
思是站在两个立场上的搜索，我也不知道该用什么比较确切的术语】，要了解它们有什
么作用，如何来做，对电脑的程序意味着什么。我们要讨论的技术在所有的游戏中都很
重要，但是仅仅靠它们是不足以下象棋的。下个月，我会介绍一些高级的技术，它们能
显著增强棋力，同时提高搜索效率。

为什么要搜索？

　　简单地说，因为我们还没有聪明到可以抛弃搜索的地步。
　　一个真正聪明的程序可以只依靠棋盘局面来确定，哪一方处于领先以及领先多少，
　　一个真正聪明的程序可以只依靠棋盘局面来确定，哪一方处于领先以及领先多少，
并且制定作战计划让这个优势变为胜果。不幸的是，需要考虑的局面类型太多了，再加
上那么多的规则和特例，就是再聪明的程序也不擅长做此类事情。而它们擅长的则是计
算。因此对象棋程序来说，与其只根据棋盘的局面来决定好的着法，不如使用它们的蛮
力——考虑每一种着法，然后为对手考虑这些着法的所有应对着法，循环下去，直到处
理器吃不消为止。
　　比起掌握复杂的策略，深入的搜索是教电脑下棋的比较简单的方法。例如，考虑马
的捉双问题，走一步棋就可以同时攻击两种棋子(例如一个车和一个后)。掌握这种类型
的走法是需要花一些时间的，更复杂些，我们还要判断这个格子有没有保护。然而，一
个愚钝的3步的搜索就可以学会捉双了，程序最终会尝试让马走到捉双的格子，并探索对

手对于捉双的回应，然后吃掉没有逃跑的那个棋子，从而改变了子力平衡。由于全面搜
索可以看到每一步，所以不会错过任何机会。如果经过5步棋后可以产生杀棋或捉死后(
无论怎样不容易看到)，只要电脑的搜索得足够深，就会看到这个着法。因此，搜索得越

深，电脑就会施展越复杂的作战计划。

爷爷时代的“最小-最大”原理

　　所有双向搜索算法的最基本的思想都是“最小-最大”(Minimax)原理。它可以追溯
到中世纪(Dark Ages)，但我相信它最早是由冯-诺依曼(Von Neumann)【应该是John
von Nuoma，1903-1957，美籍匈牙利数学家】在60年前完整描述的：

　　1. 假设有对局面评分的方法，来预测棋手甲(我们称为最大者)会赢，或者对手(最
小者)会赢，或者是和棋。评分用数字表示，正数代表最大者领先，负数代表最小者领先

小者)会赢，或者是和棋。评分用数字表示，正数代表最大者领先，负数代表最小者领先

，零代表谁也不占便宜；
　　2. 最大者的任务是增加棋盘局面的评分(即尽量让评分最大)。
　　3. 最小者的任务是减少棋盘局面的评分(即尽量让评分最小)。
　　4. 假设谁也不会犯错误，即他们都走能让使局面对自己最有利的着法。

　　那么这该怎么做呢？设想一个简单的游戏，每方只走一步，每步只有两种着法可供
选择。评分函数只和最后棋盘的局面有关，即评分是最大者和最小者着法综合的结果。

最大者的着法    最小者的着法    评分
A               C               12
A               D               -2
B               C               5
B               D               6

　　最大者假设最小者会下出最好的棋，因此他知道，如果他选择着法A，那么他的对手

会回应D，使最终评分变成-2(即获胜)。但是，如果最大者走的着法B，那么他就会获胜
，因为最小者的最佳着法仍然是正数(5)。所以按照“最小-最大”算法，最大者会选择
着法B，即使他选择A并且最小者走错时评分还会更高。
　　“最小-最大”原理有个弱点，从简单的例子中还不能明显地看出来——要检查的各

种路线的数量是指数形式的，这就意味者工作量会以几何级数增长。

　　1. 每方有多少种可能的着法，这个数称为分枝因子(Branch Factor)，用b表示；
　　1. 每方有多少种可能的着法，这个数称为分枝因子(Branch Factor)，用b表示；
　　2. 考虑的深度用n表示，通常说“n层”，n是整数，“层”(Ply)表示一个棋手走的

一步棋。例如在上面介绍的迷拟游戏中，搜索深度是2层。每个棋手走1步。

　　例如在象棋中，通常在中局阶段分枝因子大约为35种着法，在黑白棋中大约为8。由

于“最小-最大”算法的复杂度是O(bn)，所以对一个局面搜索4层就需要检查150万条路
线，这是多大的工作量！再增加上去，5层就会把搜索树膨胀到5000万，6层则达到18亿
！【原作者这里写的是8层150万、9层5000万、10层18亿，不知为何多算了4层。】
　　幸运的是，有办法能在精确度不打折扣的情况下大幅度削减工作量。

Alpha-Beta搜索——让“最小-最大”法成为现实(也只是有一点点现实)

　　设想你在迷拟游戏中已经搜索了着法B，结果你知道最大者在整个游戏中最高得分是

5。
　　现在假设你开始搜索着法A了，并且一开始寻找的路线是A-D，这条线路的得分是-2
。对于最大者来说，这是非常糟糕的，如果他走了A，那么结果肯定会是-2，因为最小者

总是走得最好的。这是因为，如果A-C比A-D更好，那么最小者会选择A-D，如果A-C更坏(

比如说-20)，那么最小者就会选择这条路线。所以，没有必要再去看A-C以及其他由A产
生的路线了——最大者必须走B，因为到此位置的搜索已经能证明，无论如何A是个更糟
的选择。
　　这就是Alpha-Beta算法的基本思想——只要你有一步好的着法，你就能淘汰其他可
能导致灾难的变化，而这样的变化是很多的。如果再跟前面介绍的换位表结合起来，当
不同路线的局面发生重复时可以节省下分析局面的时间，那么Alpha-Beta就能产生无限
不同路线的局面发生重复时可以节省下分析局面的时间，那么Alpha-Beta就能产生无限
的能量——在最好的情况下，它处理的结点数是纯粹的“最小-最大”搜索的平方根的两

倍，从1500万可以减少到2500。
　　【又遇到可以发挥的地方了。普遍认为，Alpha-Beta搜索的结点数是死办法(即不用

Alpha-Beta搜索的办法)的平方根那么多，我想办法证明了这个结论。对于n层分枝因子
为b的搜索树，死办法搜索的结点个数是bn，这是显而易见的。那么Alpha-Beta搜索的结

点数又是多少呢？我想到用两个递归函数来解决这个问题。
　　Alpha-Beta搜索是完全搜索，如果某个结点是完全搜索的，那么这个结点称为Alpha

结点，显然根结点是Alpha结点。那么Alpha结点的分枝又是什么呢？至少有一个Alpha结

点，这是肯定的，最好的情况下，剩余的结点都可以产生截断，这些结点称为Beta结点
。Beta结点有个特点，只要它的分枝中有一个Alpha结点产生作用，那么剩下的结点就没

有搜索的必要了，我们还是取最好的情况，分枝中只有一个Alpha结点。
　　现在我们来构造递归函数，设Alpha结点下需要搜索的结点数为Alpha(n)，n为该结
点的深度，那么这个函数的递归表达式是：
Alpha(n) = Alpha(n ? 1) + (b ? 1) ? Beta(n ? 1)
　　用同样的方法可以构造一个Beta(n)的函数：
Beta(n) = Alpha(n ? 1)
　　把它代入前面的Alpha(n)函数中(注意，n要替换成n ? 1，n ? 1要替换成n ? 2)，
就可以得到下面的函数：
Alpha(n) = Alpha(n ? 1) + (b ? 1) ? Alpha(n ? 2)
　　加上初始了条件Alpha(0) = Beta(0) = 1(即Alpha(0) = 1，Alpha(1) = b)后，这
个方程是可以解出来的(利用一些递归函数的技巧，关键时刻来几杯咖啡就可以了)。但
是这里用一个投机取巧的办法——再做一次n替换成n ? 1的事情，这个公式就变成了：
是这里用一个投机取巧的办法——再做一次n替换成n ? 1的事情，这个公式就变成了：
Alpha(n) = b ? Alpha(n ? 2) + (b ? 1) ? Alpha(n ? 3)
　　这样就看出些名堂了吧，Alpha(n ? 3)肯定和Alpha(n ? 2)不在同一数量级，尽管
放心把它舍去吧(投机取巧之所在)，最后公式变成了：
Alpha(n) ? b ? Alpha(n ? 2)
　　这下总算豁然开朗了，相比起死办法的结点数：
Search(n) = b ? Search(n ? 1)
　　其结果为bn，那么Alpha-Beta搜索的结点数不正是bn/2，即bn的平方根吗？原作者
认为是2bn，可能把舍去Alpha(n ? 3)这一项的因素也考虑进去了，他估计这会比预期要

多一倍，一点也不过分。】

对着法排序来优化Alpha-Beta搜索

　　可是，我们如何才能达到预期的效果呢？我们是否还需要做其他事情？
　　的确是的。只要Alpha-Beta搜索可以找到比其他着法好的着法，它就能对搜索树作
出非常有效的裁减，这就意味着，关键在于首先搜索好的着法。当我们在搜索其他着法
以前先搜索到最好的着法，那么最好的情况就发生了。然而最坏的情况，搜索着法的顺
序是按评分递增的，即每次搜索到的着法都比曾经搜索的着法要好，那么这种情况下的A

lpha-Beta搜索就无法作出任何裁减，这种搜索将退化为极其浪费的“最小-最大”搜索
。【这就是前一章的标题中写道“也只是有一点点现实”的原因。】
　　对搜索进行排序是相当重要的。让着法随便排列肯定不行，我们必须找到更聪明的
办法。不幸的是，如果有简单的办法知道最好的着法，那还有搜索的必要吗？因此我们
必须用“猜最好的办法”来对付。
必须用“猜最好的办法”来对付。
　　有很多技术可以让着法的顺序排列成尽可能好的顺序：

　　1. 用评估函数对着法打分，然后排序。直觉上这会起到作用，评估函数越好，这个

方法就越有效。不幸的是在象棋中它一点也不起作用，因为下个月我们将了解到，很多
局面是不能准确评估的。
　　2. 找到在换位表中已经存在的局面，如果它的数值足够好，就会产生截断，这样就

不必再进行其他搜索了。
　　3. 尝试特定类型的着法。例如，后被吃掉肯定是最坏的想法，所以先检查吃子的着

法是行之有效的。
　　4. 把这个思路进行拓展，关注已经在同一层深度产生过截断的着法。“杀手启发”

(Killer Heuristic)是建立在很多着法是次序无关的基础上的。如果你的后被攻击了，
不管你把H2兵挺一格还是两格，对手都会吃掉你的后。因此，如果在搜索H2-H3着法时，

“象吃掉后”的着法会产生截断，那么在搜索H2-H4着法时，“象吃掉后”很有可能也产

生截断，当然应该首先考虑“象吃掉后”这一步。
　　5. 再把杀手启发拓展到历史表上。如果在前面几回合的搜索中，发现G2-E4的着法
很有效，那么很有可能现在仍然很有用(即便原来的格子是象而现在变成了后)，因为棋
盘其他位置的情况不太可能有多少变化。历史启发的的实现非常简单，只需要一个64?64

的整数数组，它可以起到很可观的效果。

　　现在已经谈了所有宝贵的思想，然而最有效的方法却稍稍有背于人的直觉，这个方
法称为“迭代加深”(Iterative Deepening)。


迭代加深的Alpha-Beta搜索

　　如果你正在搜索6层的局面，那么理想的着法顺序应该由同样层数搜索的结果来产生

。既然这明显是不可能做到的，那么能否用稍浅的搜索(比如说5层)来代替呢？
　　这就是迭代加深方法背后的思想——一开始搜索2层，用这样种搜索产生的着法顺序

来搜索3层，反复如此，直到到达规定的深度。
　　这个技术会受到一般人的质疑——大量的努力是重复的(8到10次乃至更多)，不是吗

？
　　那么考虑一下搜索树的深度n和分枝因子b好了。搜索树在第1层的结点数为b，第2层

是b2，第三层是b3，等等。如果b很大(记住中局时在35左右)，那么绝大多数工作量取决

于最后一层。重复搜索(n?1)的深度其实是小事一桩，即便迭代加深一点也不起作用，它

也只会多花4%的时间(在通常的局面上)。
　　但是，它的优势是非常可观的——由浅一层搜索的结果排列得到的顺序，在层数加
深时可以大幅度增加截断率。因此，迭代加深的Alpha-Beta搜索实际上找的结点数，会
比直接的Alpha-Beta搜索的少很多。在使用换位表后，它的收效就更可观了——重复搜
索浅的部分就几乎不需要时间了，因为这些结果在换位表里都有，没有必要重新计算了
。

电脑下棋的风格

　　迭代加深的Alpha-Beta搜索和换位表(并且在历史表的推动下)能让计算机对局面搜
索到相当的深度，并且可以下国际象棋了。应该这么说，它的祖先“最小-最大”算法决

索到相当的深度，并且可以下国际象棋了。应该这么说，它的祖先“最小-最大”算法决

定了那台电脑(曾经在世界上有惊人之举的那台电脑【即冯-诺依曼的ENIAC】)下棋的风
格。
　　例如，设想电脑能对一个局面搜索8层，通常在考虑某一步时，这种让人不解的模式

会让让它战胜对手。只有少数一些看不清的、复杂的、迷惑人、超出直觉局面，才能让
对手抓住一线机会取得胜利，而对于人类棋手(甚至大师)来说，这样的局面陷阱已经可
以写到书里去了。
　　然而，如果电脑找到了一个导致和棋的无聊着法，它就会绕过陷阱，因为它假设对
手会作出正确的应对，无论那种可能性有多小，只要电脑认为平局是最高的期望。
　　结果你可能会说，电脑下棋会极端谨慎，就像对手都是世界冠军一样。如果考虑到
电脑算不到出人类棋手布置的陷阱那个深度，人类就会绞尽脑汁布设陷阱，让电脑犯错
误。(人类棋手会研究对手的下棋风格，如果卡斯帕罗夫有机会和深蓝下一百盘棋，他可

能会找到深蓝的弱点并且打败它。但是我们不知道有没有这种可能性。【现在看来，卡
斯帕罗夫战胜深蓝是不在话下的，因为近几年他一直在和水平更高的电脑较量。】)

下一个月

　　在第五部分，我们会讨论直接或改变深度的Alpha-Beta搜索的局限。我们还会讨论
如何利用一些技术，诸如无意义着法启发 (Null-Move Heuristic)、静态搜索(Quiescen

ce Search)、期望搜索(Aspiration Search)、MTD(f)搜索，以及让深蓝名声显赫的“单

步拓展”(Singular Extensions)技术，它们会提高下棋水平。坚持住，我们快要结束了

！

能会找到深蓝的弱点并且打败它。但是我们不知道有没有这种可能性。【现在看来，卡
下一个月

　　在第五部分，我们会讨论直接或改变深度的Alpha-Beta搜索的局限。我们还会讨论
如何利用一些技术，诸如无意义着法启发 (Null-Move Heuristic)、静态搜索(Quiescen

ce Search)、期望搜索(Aspiration Search)、MTD(f)搜索，以及让深蓝名声显赫的“单

步拓展”(Singular Extensions)技术，它们会提高下棋水平。坚持住，我们快要结束了

！

　　Fran?ois Dominic Laramée，2000年8月

　　出处：www.gamedev.net
　　译者：黄阿姨 (auntyellow@citiz.net)
　　类型：全译
--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝


※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 202.118.229.*]