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

　

François Dominic Laramée/文

　

　　哇，看上去好像有很多人在看我的连载，我的脸都红了！

　　这是倒数第二篇文章，我们会介绍和搜索有关的高级技术，他们既能提高速度，又能增强棋力(或者只有一个作用)。他们中有很多，概念上(程序代码可能不行)可以运用到任何2人游戏中，然而让它们用到一些具体问题上，对很多读者来说还需要加工。

　

干吗要那么麻烦？

　

　　到此为止，我们知道的所有搜索算法，都把局面推演到固定的深度。但是这未必是件好事。例如，假设你的程序最多可以用迭代加深的Alpha-Beta算法搜索到5层，那么来看下这几个例子：

　

　　1. 沿着某条路线，你发现在第3层有将死或逼和的局面。显然你不想再搜索下去了，因为游戏的最终目的达到了。搜索5层不仅是浪费时间，而且可能会让电脑自己把自己引入不合理的状态。

　　2. 现在假设在5层你吃到了兵。程序可能会认为这个局面稍稍有利，并且会这么走下去。然而，如果你看得更深远些，可能会发现吃了兵以后你的后就处于被攻击的状态，完了！

　　3. 最后，假设你的后被捉了，不管你怎么走，她会在第4层被对手吃掉，但是有一条路线可以让她坚持到第6层。如果你的搜索深度是5，那么后在第4层被吃掉的路线会被检测出来，这些情况会评估成灾难局面，但是唯一能使后在第6层(超出了搜索树)捉到的那条路线，对于电脑来说被吃是不能被发现的，因此它会认为后很安全，从而打一个较高的分数。现在，为了让后被吃的情况排除在搜索树以外，唯一的办法就是调虎离山，这样做是很冒险的——牺牲一些局面，还是有可能让对手犯下错误让你的后溜掉的。那么如果你要通过牺牲一个车来延缓后的被吃呢？对电脑来说，在第4层丢车要比丢后损失小，所以在这个搜索水平上，它情愿丢一个那么大的子，来推迟那个可怜的后的被吃了。(当然在随后一回合里，电脑会发现无论怎么走，它的后会在第4层被吃掉，并且车丢得莫名其妙。)很早以前Hans Berliner就把这个情况称为“水平线效应”，这在很大程度上可以通过后面即将介绍的“静态搜索”来改善。

　

　　最后要说一句：象棋中的很多局面(其他游戏也一样)太不可预测了，实在很难恰当地评估。评价函数只能在“安静”的局面下起作用，即这些局面在不久的将来不可能发生很大的变化。这将是我们介绍下一个内容。

　

请安静！

　

　　有两种评估局面的办法——动态评估(看局面会如何发展)和静态评估(看它像什么样子，不去管将来怎样)。动态评估需要深入的搜索。我们刚刚提到，局面在不久的将来不可能发生很大的变化的情况下，静态评估才是可行的。这些相对稳定的局面称为“安静”(Quiet)或“寂静”(Quiescent)的局面，它们需要通过“静态搜索”(Quiescence Search)来达到。

　　静态搜索的最基本的概念是指：当程序搜索到固定深度时(比如6层)，我们选择性地继续各条路线，只搜索“非静态”的着法，直到找到静态着法为止，这样才开始评估。

　　找到静态局面是需要游戏知识的。例如，什么样的着法可能引起棋盘上子力平衡的巨大改变？对于象棋来说，子力平衡会导致局面的剧烈变化，所以任何改变子力的着法就是——吃(特别是吃主要棋子)、兵的升变都是，而将军也是值得一看的(仅仅是能导致将死的将军)。【译注：我认为任何将军都应该考虑进去，因为它会导致抽吃、长将等决定性局面的产生】。在西洋棋里，吃子和升变【西洋棋的棋子分兵棋(Man)和王棋(King)，兵棋冲到底线就变成王棋，因此我断定它是国际象棋的前身】都是选择。在黑白棋中，每一步都必须吃子，并且“子力平衡”【仅仅指目前棋子的多少，它和最终棋子的多少没多大联系】在短时间内翻覆无常，所以可以说它根本不存在“静态局面”！

　　我自己的程序用了简单的静态搜索，它只考虑所有带吃子着法的线路(在x层完全搜索以后)。由于通常局面下没有太多合理的吃子着法，所以静态搜索的分枝因子非常小(平均在4-6，双方在吃子后会迅速下降到0)。但是，静态搜索算法要分析大量的局面，它可能会占用整个处理器一半以上的时间。当你的程序使用这个方案以前，你要确定你是否需要用它。

　　当没有吃子发生时，我的程序才开始评价局面。其结果就是将层数固定的搜索树作选择性的延伸，它能克服大多数由“水平线效应”产生的后果。

　

重要的空着

　

　　有个加快象棋程序速度的有效方法，就是引入空着的概念。

　　简而言之，空着就是自己不走而让对手连走两次。大多数局面中，什么事都不做显然不是办法，你总是必须做点事情来改善局面。(老实说，有一些“走也不是，不走也不是”的局面，空着确实是你的最佳选择，但不能走，这种 “被迫移动”(Zugzwang)局面是没有指望的，所以不必对电脑感到失望。)

　　在搜索中让电脑走空着，可以提高速度和准确性。例如：

　

　　1. 假设局面对你来说是压倒性优势，即便你什么都不走，对手也无法挽回。(用程序的术语来说，你不走棋也可以产生Beta截断。)假设这个局面本来准备搜索N层，而空着取代了整个搜索树(你的所有合理着法用空着取代了)，并且你的分枝因子是B，那么搜索空着就相当于只搜索了一个N-1层的分枝，而不是B个这样的分枝。在中局阶段通常B=35，所以空着搜索只消耗了完整搜索所需的3%的资源。如果空着搜索表明你已经强大到没有必要再走棋(即会产生截断)的地步，那么你少花了97%的力气。如果没有，你就必须检查合理的着法，这只是多花了3%的力气。平均来说，收益是巨大的。【当然，空着搜索对于处理“被迫移动”局面还是有负面作用的，特别是在残局中，这个作用相当明显。可以参考《对弈程序基本技术》专题之《高级搜索方法——空着裁剪》一文。】

　　2. 假设在静态搜索中，你面对一个只有车吃兵一种吃子着法的局面，然而接下来对手就会走马吃车。你最好不去吃子而走其他不吃子的着法对吗？你可以在静态搜索中插入空着来模拟这种情况，如果在某个局面下空着比其他吃子着法有利，那么你继续吃子就是坏的选择。并且由于最佳着法是静态着法，所以这个局面就是评估函数可以作用的局面。

　

　　总的来说，空着启发会减少20%到75%的搜索时间。这当然值得，特别是当你把这个方法用在静态搜索算法上的时候，就像改变“走子的一方”这种代码一样简单，用不了十行就行了。

　　【很多书上把“空着”这一技术称为“空着启发”(Null-Move Heuristic)，本文就是这个意思，事实上在历史表、迭代加深等启发的作用下，空着启发已经意义不大了。现在绝大多数程序都使用了称为“空着的向前裁剪”(Null-Move Forward Pruning)的搜索(它跟空着启发是有区别的)，尽管是一种不完全搜索，但它却是诸多向前裁剪的搜索中最有效的一个。】

　

期望搜索和MTD(f)

　

　　普通的老式Alpha-Beta搜索对某个局面最终的“最小-最大”值没有假设。看上去它考虑到任何情况，无论有多反常。但是，如果你有一个非常好的主意(例如由于你在做迭代加深，从而想到前一次的结果)，你就会找出那些和你预期的差得远的路线，预先把它们截断。

　　例如，假设一个局面的值接近于0，因为非常均衡。现在来假设对一个内部结点作先前的评价，它的值在+20,000【这里的单位应该是“千分兵值”， 即1000相当于一个兵的价值，那么马和象等于3000，车5000，后9000，其他因素也折算成这个值，而UCI协议中则用“百分兵值”，因为没有必要过于精确】，那么你可以有充分信心对它截断。

　　这就是“期望搜索”(Aspiration Search)背后的思想，一个Alpha-Beta搜索的变种，开始时用从负无穷大到正无穷大来限定搜索范围，然后在期望值附近设置小的窗口。如果实际数值恰好落在窗口以内，那么你赢了，你会准确无误地找到路线，并且比其他的路线快(因为很多路线都被截断了)。如果没有，那么算法就失败了，但是这个错误是很容易被检测的(因为“最小-最大”值就是其中一条边界)，你必须浪费一点时间，用一个更大的窗口重新搜索。如果前面的情况比后面的情况多，那么总体上你还是赢了。很明显，你预先猜的数值越好，这个技术的收效就越大。

　　在上世纪90年代中期，研究员Aske Plaat把期望搜索拓展为一个逻辑问题：如果你把带期望的Alpha-Beta搜索的窗口大小设定成0，将会发生什么事？它当然永远不会成功。但是如果它成功了，那速度将是惊人的，因为它把几乎所有的路线全都截断了。现在，如果失败意味着实际数值低于你的估计，那么你用稍低点的宽度为零的窗口再试一次，重复下去。这样，你就等于用Alpha-Beta搜索来做某个“最小-最大”值的拆半查找(Binary Search)，直到你最终找到那个宽度为零的窗口。

　　这个伟大的设想发表在一个网站上：http://theory.lcs.mit.edu/~plaat/mtdf.html，它的具体实现称为MTD(f)搜索算法，只有十多行。加上Alpha-Beta搜索和置换表的运用，MTD(f)呈现出惊人的效率，还善于做并行计算。它在“粗糙”(简单且快速)的局面分析中运行得更好，很明显，如果局面评估的最小单位越大(例如从0.001个兵增加到0.1个兵)，它搜索的步数就越少。

　　在Alpha-Beta搜索的变种当中，还有很多具有广泛用途的算法(例如名声狼藉的NegaScout，我宁可给白痴讲广义相对论，也不想给你们讲这些)【之所以说NegaScout名声狼藉，是因为它的发明者Reinefeld首次发表该算法时，程序中有一个致命错误，导致搜索效率大幅度降低，甚至低于普通的Alpha-Beta搜索，如今这个算法更多地被PVS(主要变例搜索)取代，因为它更容易理解】，但是Plaat坚持认为MTD(f)是至今为止效率最高的算法。我就信了他的话，所以我的程序里用了MTD(f)，你们可能会感叹这个算法是多么简短啊！

　　【MTD(f)在整个过程中只使用极小窗口，并且每次都从根结点开始的，这个过程极大程度地依赖于置换表，称为“用存储器增强的试探驱动器”(Memory-enhanced Test Driver，简称MTD)，它只需要传递两个参数(深度n和试探值f)，故得名为MTD(n,f)，缩写为MTD(f)。实际运作中MTD(f)是以迭代的形式收敛的，而不是原作者所说的拆半查找。

　　在Plaat的文章中，MTD(f)的代码有10行，而跟它异曲同工的算法PVS，则只比普通的Alpha-Beta多了5行左右，因此很奇怪原作者(Laramée)为什么如此看好MTD(f)。MTD(f)在并行计算上确实比PVS有优势，由于Plaat等人拿MTD(f)和PVS算法的比较是在并行机上完成的，才得出MTD(f)优于PVS的结论，而事实上大部分的程序用的都是PVS。】

　

单步延伸

　

　　在我们结束这个主题以前，这是最后一个话题。在象棋中，有些着法明显比其他的好，这样就可能没必要搜索其他的变化了。

　　例如，假设你在迭代加深过程中正在做深度为N - 1的搜索，发现某步的评分为+9000(即你吃了对方的后)，而其他都低于0。如果像比赛一样想节约时间，你会跳过前面的N层搜索而对这步进行N层搜索【对于这步来说，搜索加深了一层，对于优势局面来说，优势应该是越来越大的，所以加深一层后评分应通常要高】，如果这步额外搜索的评分不比预期的低，那么你可以假设这步棋会比其他着法都好，这样你就可以提前结束搜索了。(记住，如果平均每层有35种合理着法，那么你就可能节省97%的时间！)

　　深蓝的小组发展了这个思想并提出了“单步延伸”(Singular Extension)的概念。如果在搜索中某步看上去比其他变化好很多，它就会加深这步搜索以确认里边没有陷阱。(实际过程远比这里说的要复杂，当然基本思想没变。)单步延伸是耗费时间的，对一个结点增加一层搜索会使搜索树的大小翻一番，评估局面的计算量同时也翻一番。换句话说，只有深蓝那种硬件水平才吃得消它，我那笨拙的Java代码肯定不行。但是它的成效是不可否认的，不是吗？【原作者的意思可能是指，单步延伸技术会明显提高棋力，同时也会增加搜索时间。】

　

下一个月

　

　　在第六部分中，我们会着重讨论局面评估函数，它才真正告诉程序一个局面是好是坏。这个主题具有极其广泛的内容，可以花几年时间来改进评估方法(也确实有人这样做)，因此我们必须对这些内容进行彻底讨论，包括它们的可行性和重要程度。【在这篇普及型的连载中，作者怎么可能给你们讲那么多呢？】如果任何事情都按照计划进行，我就该用一些Java代码来给你们填饱肚子，但是这很难办到，不是吗？

　

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

　

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

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

　　类型：全译加译注

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

下一篇　国际象棋程序设计(六)：局面评估函数

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

www.xqbase.com