Programming 版 (精华区)

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

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

Fran?ois Dominic Laramée/文

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

干吗要那么麻烦？

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

看下这几个例子：

　　1. 沿着某条路线，你发现在第3层有将死或逼和的局面。显然你不想再搜索下去了
　　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=3

5，所以空着搜索只消耗了完整搜索所需的3%的资源。如果空着搜索表明你已经强大到没

有必要再走棋(即会产生截断)的地步，那么你少花了97%的力气。如果没有，你就必须检

查合理的着法，这只是多花了3%的力气。平均来说，收益是巨大的。【当然，空着搜索
对于处理“被迫移动”局面还是有负面作用的，特别是在残局中，这个作用相当明显。
可以参考《对弈程序基本技术》专题之《高级搜索技术(一)——空着的朝前裁剪》一文
。】
　　2. 假设在静态搜索中，你面对一个只有车吃兵一种吃子着法的局面，然而接下来对

　　2. 假设在静态搜索中，你面对一个只有车吃兵一种吃子着法的局面，然而接下来对

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

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

期望搜索和MTD(f)

　　普通的老式Alpha-Beta搜索对某个局面最终的“最小-最大”值没有假设。看上去它

考虑到任何情况，无论有多反常。但是，如果你有一个非常好的主意(例如由于你在做迭

代加深，从而想到前一次的结果)，你就会找出那些和你预期的差得远的路线，预先把它

们截断。
　　例如，假设一个局面的值接近于0，因为非常均衡。现在来假设对一个内部结点作先

前的评价，它的值在+20,000【这里的单位应该是“千分兵值”， 即1000相当于一个兵
的价值，那么马和象等于3000，车5000，后9000，其他因素也折算成这个值，而UCI协议

中则用“百分兵值”，因为没有必要过于精确】，那么你可以有充分信心对它截断。
　　这就是“期望搜索”(Aspiration Search)背后的思想，一个Alpha-Beta搜索的变种

，开始时用??到+?来限定搜索范围，然后在期望值附近设置小的窗口。如果实际数值恰
好落在窗口以内，那么你赢了，你会准确无误地找到路线，并且比其他的路线快(因为很

好落在窗口以内，那么你赢了，你会准确无误地找到路线，并且比其他的路线快(因为很

多路线都被截断了)。如果没有，那么算法就失败了，但是这个错误是很容易被检测的(
因为“最小-最大”值就是其中一条边界)，你必须浪费一点时间，用一个更大的窗口重
新搜索。如果前面的情况比后面的情况多，那么总体上你还是赢了。很明显，你预先猜
的数值越好，这个技术的收效就越大。
　　在上世纪90年代中期，研究员Aske Plaat把期望搜索拓展为一个逻辑问题：如果你
把带期望的Alpha-Beta搜索的窗口大小设定成0，将会发生什么事？它当然永远不会成功

。但是如果它成功了，那速度将是惊人的，因为它把几乎所有的路线全都截断了。现在
，如果失败意味着实际数值低于你的估计，那么你用稍低点的宽度为零的窗口再试一次
，重复下去。这样，你就等于用Alpha-Beta搜索来做某个“最小-最大”值的拆半查找(B

inary Search)，直到你最终找到那个宽度为零的窗口。
　　这个伟大的设想发表在一个网站上：http://theory.lcs.mit.edu/~plaat/mtdf.htm

l，它的具体实现称为MTD(f)搜索算法，只有十多行。加上Alpha-Beta搜索和换位表的运

用，MTD(f)呈现出惊人的效率，还善于做并行计算。它在“粗糙”(简单且快速)的局面
分析中运行得更好，很明显，如果局面评估的最小单位越大(例如从0.001个兵增加到0.1

个兵)，它搜索的步数就越少。

　　在Alpha-Beta搜索的变种当中，还有很多具有广泛用途的算法(例如声名狼藉【我也

不知道原作者用的infamous指什么含义】的NegaScout，我宁可给白痴讲广义相对论，也

不想给你们讲这些)，但是Plaat坚持认为MTD(f)是至今为止效率最高的算法。我就信了
他的话，所以我的程序里用了MTD(f)，你们可能会感叹这个算法是多么简短啊！

单步拓展
单步拓展

　　在我们结束这个主题以前，这是最后一个话题。在象棋中，有些着法明显比其他的
好，这样就可能没必要搜索其他的变化了。
　　例如，假设你在迭代加深过程中正在做深度为N-1的搜索，发现某步的评分为+9000(

即你吃了对方的后)，而其他都低于0。如果像比赛一样想节约时间，你会跳过前面的N层

搜索而对这步进行N层搜索【对于这步来说，搜索加深了一层，对于优势局面来说，优势

应该是越来越大的，所以加深一层后评分应通常要高】，如果这步额外搜索的评分不比
预期的低，那么你可以假设这步棋会比其他着法都好，这样你就可以提前结束搜索了。(

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

下一个月

　　在第六部分中，我们会着重讨论局面评估函数，它才真正告诉程序一个局面是好是
坏。这个主题具有极其广泛的内容，可以花几年时间来改进评估方法(也确实有人这样做

)，因此我们必须对这些内容进行彻底讨论，包括它们的可行性和重要程度。【在这篇普

话说，只有深蓝那种硬件水平才吃得消它，我那笨拙的Java代码肯定不行。但是它的成
及型的连载中，作者怎么可能给你们讲那么多呢？】如果任何事情都按照计划进行，我
就该用一些Java代码来给你们填饱肚子，但是这很难办到，不是吗？

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

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


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