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

　

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表示；

　　2. 考虑的深度用n表示，通常说“n层”，n是整数，“层”(Ply)表示一个棋手走的一步棋。例如在上面介绍的迷拟游戏中，搜索深度是2层。每个棋手走1步。

　

　　例如在象棋中，通常在中局阶段分枝因子大约为35种着法，在黑白棋中大约为8。由于“最小-最大”算法的复杂度是O(bⁿ)，所以对一个局面搜索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就能产生无限的能量——在最好的情况下，它处理的结点数是纯粹的“最小-最大”搜索的平方根的两倍，从1500万可以减少到2500。

　　【要说明Alpha-Beta搜索的结点数是死办法(即不用Alpha-Beta搜索的办法)的平方根的两倍那么多，可以分别计算搜索树中两种类型的结点——Alpha结点和Beta结点。

　　Alpha-Beta搜索是完全搜索，如果某个结点是完全搜索的，那么这个结点称为Alpha结点，显然根结点是Alpha结点。那么Alpha结点的分枝又是什么呢？至少有一个Alpha结点，这是肯定的，最好的情况下，剩余的结点都可以产生截断，这些结点称为Beta结点。Beta结点有个特点，只要它的分枝中有一个Alpha结点产生作用，那么剩下的结点就没有搜索的必要了，我们还是取最好的情况，分枝中只有一个Alpha结点。

　　那么如何计算Alpha结点的个数呢？一个Alpha结点下面有b - 1个Beta结点，每个Beta结点下面又有1个Alpha结点，这样深度每增加了两层结点数才扩大b倍，因此总的Alpha结点数就是b^n/2。同样道理，Beta结点也这么计算，得到的结果也是b^n/2，因此总结点数就是2b^n/2。】

　

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

　

　　可是，我们如何才能达到预期的效果呢？我们是否还需要做其他事情？

　　的确是的。只要Alpha-Beta搜索可以找到比其他着法好的着法，它就能对搜索树作出非常有效的裁减，这就意味着，关键在于首先搜索好的着法。当我们在搜索其他着法以前先搜索到最好的着法，那么最好的情况就发生了。然而最坏的情况，搜索着法的顺序是按评分递增的，即每次搜索到的着法都比曾经搜索的着法要好，那么这种情况下的Alpha-Beta搜索就无法作出任何裁减，这种搜索将退化为极其浪费的“最小-最大”搜索。【这就是前一章的标题中写道“也只是有一点点现实”的原因。】

　　对搜索进行排序是相当重要的。让着法随便排列肯定不行，我们必须找到更聪明的办法。不幸的是，如果有简单的办法知道最好的着法，那还有搜索的必要吗？因此我们必须用“猜最好的着法”来对付。

　　有很多技术可以让着法的顺序排列成尽可能好的顺序：

　

　　1. 用评估函数对着法打分，然后排序。直觉上这会起到作用，评估函数越好，这个方法就越有效。不幸的是在象棋中它一点也不起作用，因为下个月我们将了解到，很多局面是不能准确评估的。

　　2. 找到在置换表中已经存在的局面，如果它的数值足够好，就会产生截断，这样就不必再进行其他搜索了。

　　3. 尝试特定类型的着法。例如，后被吃掉肯定是最坏的想法，所以先检查吃子的着法是行之有效的。

　　4. 把这个思路进行拓展，关注已经在同一层深度产生过截断的着法。“杀手启发”(Killer Heuristic)是建立在很多着法是次序无关的基础上的。如果你的后被攻击了，不管你把H2兵挺一格还是两格，对手都会吃掉你的后。因此，如果在搜索H2-H3着法时，“象吃掉后”的着法会产生截断，那么在搜索H2-H4着法时，“象吃掉后”很有可能也产生截断，当然应该首先考虑“象吃掉后”这一步。

　　5. 再把杀手启发拓展到历史表上。如果在前面几回合的搜索中，发现G2-E4的着法很有效，那么很有可能现在仍然很有用(即便原来的格子是象而现在变成了后)，因为棋盘其他位置的情况不太可能有多少变化。历史启发的的实现非常简单，只需要一个64x64的整数数组，它可以起到很可观的效果。

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

　

迭代加深的Alpha-Beta搜索

　

　　如果你正在搜索6层的局面，那么理想的着法顺序应该由同样层数搜索的结果来产生。既然这明显是不可能做到的，那么能否用稍浅的搜索(比如说5层)来代替呢？

　　这就是迭代加深方法背后的思想——一开始搜索2层，用这样种搜索产生的着法顺序来搜索3层，反复如此，直到到达规定的深度。

　　这个技术会受到一般人的质疑——大量的努力是重复的(8到10次乃至更多)，不是吗？

　　那么考虑一下搜索树的深度n和分枝因子b好了。搜索树在第1层的结点数为b，第2层是b²，第三层是b³，等等。如果b很大(记住中局时在35左右)，那么绝大多数工作量取决于最后一层。重复搜索(n - 1)的深度其实是小事一桩，即便迭代加深一点也不起作用，它也只会多花4%的时间(在通常的局面上)。

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

　　【需要指出的是，实际运用中通常只对根结点进行迭代加深，这样搜索的结点数是1 + b + … + bⁿ，比bⁿ大不了多少。如果每个结点都用迭代加深，则需要搜索的结点数就是(1 + b)ⁿ，刚才提到在最好的情况下分枝因子为合理着法数的平方根，即b在6左右，而6ⁿ和7ⁿ是有很大区别的。

　　事实上，要在每个结点上都使用迭代加深，只要检查置换表就可以了，因为从根结点处做深一层的搜索时，除了新增加的一层结点以外，其他各层结点上都有最好的着法存储在置换表中了，这些着法应该优先考虑，绝大多数着法能产生裁剪，而不需要检查杀手表或者做产生产生。

　　另外，迭代加深可以大幅度提高历史表的效率，在前一次N层的搜索中历史表已经有相当丰富的历史着法信息了，在做N + 1层搜索时，这些历史信息可以让着法有更好的顺序。】

　

电脑下棋的风格

　

　　迭代加深的Alpha-Beta搜索和置换表(并且在历史表的推动下)能让计算机对局面搜索到相当的深度，并且可以下国际象棋了。应该这么说，它的祖先“最小-最大”算法决定了那台电脑(曾经在世界上有惊人之举的那台电脑【即冯-诺依曼的ENIAC】)下棋的风格。

　　例如，设想电脑能对一个局面搜索8层，通常在考虑某一步时，这种让人不解的模式会让让它战胜对手。只有少数一些看不清的、复杂的、迷惑人、超出直觉局面，才能让对手抓住一线机会取得胜利，而对于人类棋手(甚至大师)来说，这样的局面陷阱已经可以写到书里去了。

　　然而，如果电脑找到了一个导致和棋的无聊着法，它就会绕过陷阱，因为它假设对手会作出正确的应对，无论那种可能性有多小，只要电脑认为平局是最高的期望。

　　结果你可能会说，电脑下棋会极端谨慎，就像对手都是世界冠军一样。如果考虑到电脑算不到出人类棋手布置的陷阱那个深度，人类就会绞尽脑汁布设陷阱，让电脑犯错误。(人类棋手会研究对手的下棋风格，如果卡斯帕罗夫有机会和深蓝下一百盘棋，他可能会找到深蓝的弱点并且打败它。但是我们不知道有没有这种可能性。【现在看来，卡斯帕罗夫战胜深蓝是不在话下的，因为近几年他一直在和水平更高的电脑较量。】)

　

下一个月

　

　　在第五部分，我们会讨论直接或改变深度的Alpha-Beta搜索的局限。我们还会讨论如何利用一些技术，诸如空着启发(Null-Move Heuristic)、静态搜索(Quiescence Search)、期望搜索(Aspiration Search)、MTD(f)搜索，以及让深蓝名声显赫的“单步延伸”(Singular Extensions)技术，它们会提高下棋水平。坚持住，我们快要结束了！

　

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

　

　　原文：http://www.gamedev.net/reference/programming/features/chess4/

　　译者：象棋百科全书网 (webmaster@xqbase.com)

　　类型：全译加译注

上一篇　国际象棋程序设计(三)：着法的产生

下一篇　国际象棋程序设计(五)：高级搜索方法

返　回　象棋百科全书——电脑象棋

www.xqbase.com