《对弈程序基本技术》专题
　
什么样的结点需要搜索？全部还是选择性的？
　
David Eppstein */文
* 加州爱尔文大学(UC Irvine)信息与计算机科学系
　
　　Alpha-Beta告诉我们怎样搜索，但是我们仍然需要知道，何时需要展开结点(搜索它的子结点)，以及何时停下来从而调用评价函数。
　
水平线效应
　
　　在前面我给你们看的伪代码中，每一步棋都搜索到一个固定的深度，这个深度被称为“水平线”(Horizon)。对于看到水平线以内会发生的威胁，这个方法非常有效，但是它显然不能检查到水平线以后的威胁。例如在8层的搜索中(即搜索4个回合)，就可能得不到在5步内有杀棋的任何信息。它不知道的事情，就无法作出防御，而且只是简单地忽略那些遥远的威胁。然而当局势面临中等深度的威胁而丢子不可避免时，固定深度的搜索有时会走出更糟的棋，因为某些丢子会在搜索水平线以内，而有些却不在。在这种情况下，程序会走出糟糕的并且无意义的棋，试图来延缓丢子的发生，使得它出现在程序看不到的未来。这种现象称为“水平线效应”(Horizon Effect)。
　　这里有个例子。在下面的局势中，黑象被白兵包围，不管黑的怎么走，象总是会在几步内被吃掉；例如白车可以沿着h2-h1-a1-a2吃掉象。这是一个8层深的变化，那么假设黑方的程序也搜索8层。可能当前局面对黑方来说，最好的走法就是用象换兵，即象吃掉兵，兵吃掉象。在后面的残局里，黑方的三个连兵足以战胜或守和白车。【译注：其实守和的希望也不大，译者认为黑方还是会输掉的，因为白王的位置非常好，可以独挡三黑兵，使得白车有时间拔掉b线的黑兵。】但是程序搜索8层，很有可能会挺黑兵将军白王。白必须应对(例如自己来吃掉兵)，这个应对使得丢象被暂时避免，拖延到程序看不到的步数内，并且程序认为象是安全的。实际上在这个局面里，固定深度的程序可能会连续地送吃兵，把象被吃的结果延缓几步，但是最终可能输掉整盘棋。
　
　
　　对付水平线效应的一个方法，就是在你的程序里增加一些知识：如果从评价中知道象被包围，那么搜索程序就不会通过弃兵来延缓丢象。另一个方法是让搜索更快更深：你的程序搜索的层数越多，因超过水平线而延缓丢象的做法，发生的可能性就越小。但是对于普通局面来说，最有效的做法就是让搜索深度更灵活，使得程序在丢兵的路线上搜索得更深，而在其它路线上不必要搜索得很深。
　
蛮力和选择性
　
　　在Shannon【申朗，参阅译文《电脑国际象棋简史》】最早关于电脑国际象棋的文章中，提到程序调整搜索深度的两种策略。
　　最明显的就是我给你们看的伪代码：全部范围，固定深度的蛮力搜索。只要把“深度”这个参数输入到你的程序中，每搜索一层就减一，到达零时停下来。这样做的好处在于，只要在搜索水平线以内，一些甚至很怪异的线路也看得到。但是高的分枝因子就意味着任何线路都不可能很深(即学士程度，对任何事物都只知道个皮毛【原文是“Bachelor's degree: knows nothing about everything”】)。更遭的是，程序可能会栽倒在水平线效应下。
　　Shannon提到的另外一个方法就是选择性裁剪：不是搜索固定的深度，而是通过搜索每个结点的部分着法来减少分枝因子(避免那些“明显是坏棋”的着法)。因此这样可以搜索得很深，但是有些线路完全看不见(即博士程度，只对某个狭窄方面的懂得很多【原文是“Ph.D.: knows everything about nothing”，源于一句用来讽刺博士的笑话：“A PhD knows more and more about less and less until he knows everything about nothing”】)。Shannon认为这个思想非常好，因为它更接近人类的思考方式。Turing【图灵，参阅译文《电脑国际象棋简史》】的思想有所不同，只搜索吃子的着法。更典型的做法是，对所有的子结点作评价，而只对最好的k个作展开，这里k是小于实际分枝因子的一个参数。
　　不幸的是，“明显是坏棋”的着法往往根本不坏，而是取得胜利的精彩弃子。如果你没有找到你应该走的那步着法，你就必须更努力地去找其他可以获胜的方法。更糟的是，对手可能会在后面几步作出有力的反击，如果你没有看出来，那么你会掉入陷阱从而输掉棋局。
　　如今没有哪个思想会被单纯地使用的。我们把两者结合起来：选择性地延伸。每条路线都搜索固定的深度，但是某些路线要搜索得比水平线深。有时我们也会做裁剪(不是像Alpha-Beta那样的安全裁剪)，这通常也是非常保守的，因为只挑出好的着法实在太困难了，但是有时对于确实很坏的着法，我们可以挑出并且忽略它们。除了国际象棋以外，有些棋类有更高的分枝因子，这就有必要使用更冒进的裁剪技术了。【例如五子棋，每个局面都有100种以上的合理着法，但是我们只会挑有意义的着法，要么有进攻作用(己方棋子周围的一些着点)，要么有防守作用(敌方棋子邻近的着点)，除此以外一概不予考虑。】
　
什么时候需要延伸？
　
　　延伸的目标是什么呢？是获得更好(更准确)的评价。所以下面的结点必须延伸：
　　(1) 目前的评价可能不准确时；
　　(2) 目前的着棋路线在整个博弈搜索树中是非常重要的；
　　或者以上两个情况的组合。
　
静态搜索
　
　　在国际象棋或其他棋类中，有吃子和不吃子的着法(西洋跳棋、围棋、Fanorano等)，如果有吃子的情况，那么每次吃子时评价都会改变。
　　“静态搜索”(Quiescence Search)的思想是，到达主搜索的水平线后，用一个图灵型的搜索只展开吃子(有时是吃子加将军)的着法。其他棋类不同于国际象棋，可能只包括一些会很大程度上改变评价的着法。静态搜索还必须包括放弃的着法，来决定停止吃子。因此，主Alpha-Beta搜索中每个调用评价函数的地方，都会被一个类似Alpha-Beta的但只搜索吃子着法的函数代替，如果当前结点的评价函数足以高出边界，那么就让搜索停下来。代码如下：
　
// 静态搜索
// 主Alpha-Beta搜索中，原来出现“eval()”的地方现在调用这个函数
quiesce(int alpha, int beta) {
　int score = eval();
　if (score >= beta) {
　　return score;
　}
　for (每个吃子着法 m) {
　　执行着法 m;
　　score = -quiesce(-beta,-alpha);
　　撤消着法 m;
　　if (score >= alpha) {
　　　alpha = score;
　　　if (score >= beta) {
　　　　break;
　　　}
　　}
　}
　return score;
}
　
　　有人还把将军加入到静态搜索中，但是你要当心，由于没有深度参数，静态搜索会有巨大的结点数。吃子通常是有限的(在棋子全部吃完以前你只能有16次子)，而将军可以一直进行下去并导致无限制递归。【对于是否展开将军着法的问题，可以尝试一种做法，如果局面被将军，就展开全部着法，即做应将处理，而不对当前局面作评价，参阅“静态搜索”一文。】
　
选择性延伸
　
　　如果局面在前面的路线中非常活跃，那么这就证明后面会有进一步的手段，或者前面的着法使得这些手段推迟了，从而在很深的地方会有好的局面。因此如果搜索到一个“感兴趣”的着法例如吃子或将军，就要增加搜索深度。在Alpha-Beta的伪代码中，调用搜索过程时参数“depth - 1”可以用“depth - 1 + extension”来代替。你必须小心不要经常做这些事，否则最终会把搜索树延伸得特别庞大(甚至可能无限大)。
　　有一个技巧可以使这样的延伸终止，即延伸一个分数的层数。比较好的做法是，“深度”参数记录的是你想要搜索的层数乘上一个因子，比如说“深度 = 层数 x 24”。在递归调用Alpha-Beta搜索的时候，就传递参数“Depth - 24 + Extension”。如果延伸值总是小于24，那么这个方法能保证终止，这个方法还可以有选择地多延伸些或少延伸些。
　　在评价函数里加上“局面如何难以评价”这个知识，也是有用的，这样就可以在局面太难评价的时候延伸搜索。我的程序就做到了这点，程序对当前结点调用评价函数。如果局面十分复杂，而且深度接近零，那么评价会返回一个特殊的值【表示评价失败，这个值不能在“-Infinity”和“Infinity”之间，否则会和正常值混淆】，通知搜索继续进行下去。如果深度达到一个负得很大的数【原作者的意思是评价连续失败导致延很长】，那么评价函数总是成功的，这样搜索将会终止。
　
如何把准确性和重要性结合起来？
　
　　到目前为止，我们都在讨论并试图找到评价局面可能不准确的原因。但是对于搜索树的一些不重要的部分，或许我们不在乎它不准确，而我们真正关心的是主要变例上的结点。我们如何来关注选择性延伸的重要性呢？
　　(1) 在Alpha-Beta搜索时，不要只根据准确性作延伸，而忽视了重要性；
　　(2) 对主要变例部分(或附近)的线路作延伸，例如单步延伸(Singular Extension)，深蓝(Deep Blue)及其前身就用这个方法，如果一个局面的某个着法远比其他着法好，就延伸这个着法。
　　(3) 把视线从Alpha-Beta上移开。有一个称为“对策数搜索”(Conspiracy Number Search)的策略，即某些局面会使得能应对的好的着法很少【根据原文，译者也无法了解这个策略的确切含义】，这些局面要搜索得深一些。
　　【选择性延伸通常运用在强制着法上，强制着法的界定在各个程序中有所不同，但主要有以下几种判断方法：
　　(1) 将军：此时必须应将，显然属于强制着法；
　　(2) 单一应着：走子的一方只有一种合理着法时，显然属于强制着法；
　　(3) 杀棋威胁：当一方不走子时就会被对方在几步内杀掉，那么解除杀棋威胁也属于强制着法，这种判断比较困难，通常利用下面所介绍的“空着搜索”来做判断。
　　(4) 吃回被吃棋子：这很有可能是兑子过程，因此大多数情况下为强制着法；
　　(5) 通路兵挺进：在王兵残局中，最简单的处理就是搜索到兵升变时的局面，从而绕开正方型法则、关键格理论等知识，这就需要对通路兵的挺进作延伸。(如果兵挺5格才能到达升变格，那么原来搜索8层还看不到升变，作了延伸以后搜索5层就能看到了，因为在连续挺兵的这条线路上已经延伸到了10层。)
　　大多数程序都结合以上若干种判断，以决定是否进行延伸。】
　
空着搜索
　
　　这个思想符合本文的整个主题，即在适当时机调整搜索层数，但是它是通过相反的方式来表现的。这个思想不是在复杂的局面上延伸，而是在简单的局面上减少搜索。
　　这个思想是建立在国际象棋知识的基础上的：有害的着子是非常罕见的(除了残局以外)。通常如果轮到你走，你一定能让局面更好些。所有可能的着法都使局面变得更糟，这样的局面称为“无等着”(Zugzwang)(德语，意思为强迫着子)，通常只发生在残局中。像其他棋类，例如五子棋，无等着根本不会发生。因此，如果你改变国际象棋的规则，允许有“弃权”的着法，那么弃权通常是错误的，它不会使棋局有进展。
　　因此，假设你搜索一个希望高出边界的结点(即Alpha-Beta搜索的返回值至少是Beta)，空着搜索就是先搜索“弃权”着法【即“空着”(Null-Move)】，即使它通常不是最好的。如果弃权着法高出边界，那么真正最好的着法也可能高出边界，你就可以直接返回Beta而不要再去搜索了。要把搜索做得更快，弃权着法搜索的深度通常比常规着法浅。
　　你必须小心，这种启发会改变搜索结果，也可能使你忽略棋局中的一些重要的线路。不要连续两次用空着(因为这样你的搜索会退化，结果只返回评价函数)，而且要小心，只能在不会出现无等着的情况下使用。在国际象棋中，这就意味着当局面还有很多子的时候才能使用。
　
// 带空着启发的Alpha-Beta搜索
alphabeta(int depth, int alpha, int beta) {
　if (赢棋 || depth <= 0) {
　　return score;
　}
　放弃着子;
　if (上一步不是空着 && 局面不是无等着局面 &&
　　　alphabeta(depth - 3, beta, beta + 1) >= beta) {
　　// 【深度参数如果是 depth - 1，那就是纯粹的“启发”算法，而现在搜索浅了(depth - 3)，因此称为“空着裁剪”更为恰当。】
　　return beta;
　}
　/* 【“放弃着子”蕴涵着交换着子方的操作，空着启发做完后还必须交换回来。这样，上面用醒目颜色标出的代码(是由译者标出的)就存在一些问题，应该改为：
　
　if (上一步不是空着 && 局面不是无等着局面) {
　　放弃着子;
　　int val = alphabeta(depth - 3, beta, beta + 1);
　　撤消放弃着子; // 如果只作简单处理，放弃着子和撤消放弃着子都只交换着子方。
　　if (val >= beta) {
　　　return beta;
　　}
　}
】 */
　for (每个可能的着法 m) {
　　执行着法 m;
　　alpha = max(alpha, -alphabeta(depth - 1, -beta, -alpha);
　　撤消着法 m;
　　if (alpha >= beta) {
　　　break;
　　}
　}
　return alpha;
}
　
　　原文：http://www.ics.uci.edu/~eppstein/180a/990204.html
　　译者：象棋百科全书网 (webmaster@xqbase.com)
　　类型：全译加译注
  • 上一篇　基本搜索方法——置换表
  • 下一篇　高级搜索方法——简介(二)
  • 返　回　象棋百科全书——电脑象棋
    •

    www.xqbase.com