高级搜索方法――空着裁剪

空着向前裁剪

Bruce Moreland /文

没有副作用即可获得额外的速度

空着向前裁剪(Null-Move Forward Pruning)，运用可能忽视重要路线的冒险策略，使得国际象棋的分枝因子锐减，它导致搜索深度的显著提高，因为大多数情况下它明显降低了搜索的数量。它的工作原理是裁剪大量无用着法而只保留好的。

这个技术在很多刊物上报道过，但是使得大家都来关注空着的，则是由Chrilly Donniger发表在1993年9月的ICCA杂志上的一篇文章。

试想国际象棋搜索树中的某个局面，你的程序将以D层搜索这个局面的每个着法。如果其中任何一个着法的分数超过Beta，你就会马上返回Beta。如果任何一个超过Alpha，但是没有超过Beta，你就要记住着法和分值，因为这有可能是主要变例的一部分。如果它们全部小于或等于Alpha，你就要返回Alpha。

空着向前裁剪是你搜索任何着法之前要做的事。你要问一个问题：“如果我在这里什么都不做，对手能做什么?”

记得在刚才，你没有问这个问题。你只是去找最佳的着法去打击对手。问对手是否会打击你，这个问题却有所不同。

但是事实证明很多情况下对手无法打击你。比如说你送了一个车，而其他棋子都没有作用，在这种情况下，对手随便走哪步你都吃亏，因为你丢了一个车。空着向前裁剪的要点，就是简单地去掉那些没用的着法，而不要在这上面多花时间。

这就好比像打架时，根据自己的能力给对手一个出击的机会，来增加自己的信心。如果任凭对手攻击也无法击倒你，那么你攻击他的时候他会输掉。

我们不讨论这个策略了，现在来谈它是如何运用在电脑国际象棋中的。在你搜索着法以前(事实上在你生成着法以前)，你做一个减少深度的搜索，让对手先走，如果这个搜索的结果大于或等于Beta，那么你简单地返回Beta而不需要搜索任何着法。

这个思想就给了对手出击的机会，如果你的局面仍然好到超过Beta的程度，你就假设如果你搜索了所有的着法也会超过Beta。

这个方法能节省时间的原因是，开始时用了减少深度的搜索。深度减少因子称为R，因此跟你用深度D搜索所有的着法相比，现在你是先以D-R搜索对手的着法。一个比较好R是2，如果你要对所有的着法搜索6层，你最终只对对手所有的着法搜索了4层。【译注：因为放弃着法后层数应该减1，所以实际在对手上面搜索的层数是D-1-R。】

这就使得很多时间节约下来了，实践证明可以使搜索增加一到两层。效果真的非常可观!

代码如下，醒目的文字是在Alpha-Beta搜索的基础上增加的部分：

#define R 2
int AlphaBeta(int depth, int alpha, int beta) {
　if (depth == 0) {
　　return Evaluate();
　}
　MakeNullMove();
　val = -AlphaBeta(depth - 1 - R, -beta, -beta + 1);
　UnmakeNullMove();
　if (val >= beta) {
　　return beta;
　}
　GenerateLegalMoves();
　while (MovesLeft()) {
　　MakeNextMove();
　　val = -AlphaBeta(depth - 1, -beta, -alpha);
　　UnmakeMove();
　　if (val >= beta) { // 把这部分去掉，就用纯粹的最小-最大代替了Alpha-Beta。
　　　return beta;
　　}
　　if (val > alpha) {
　　　alpha = val;
　　}
　}
　return alpha;
}

在这个代码中我用了一个诀窍。我需要知道空着搜索的值是否是Beta或更好，如果还不如Beta，我不关心它到底比Beta有多糟，因此我用了极小窗口，试图让裁剪做得更快。实际上我用(Beta-1, Beta)调用了搜索，但是由于递归时必须把Alpha和Beta颠倒并取负数，这就变成源代码中的样子了。

不用说，这个代码在一方被将军时不能发挥作用(因为对手立刻把王吃掉了)。什么地方允许调用空着向前裁剪，必须掌握好分寸，因为如果你允许一次连续地这么做，那么搜索将退化成什么都不做了。一个很简单的尝试，就是当中没有间隔一个实在着法的时候，不要让两个空着搜索连在一起。另一个思想是在一个实在着法之前，允许连续两个空着裁剪。实践证明这两个方法都做得很好。

嗯，还是有副作用的

不幸的是，空着向前裁剪在某些地方不能正常运行。我们作了一个重要的假定——假定走了一步棋会比不走棋有更高的分值。不幸的是，这个假定在很多典型的局面上并不成立，这些局面非常普遍，并且有一个名称——无等着局面(Zugzwang)。无等着局面指的是，如果你不走棋，局势会好些，但是你被强迫走子，这使得你的局势会崩溃。下面是个典型的例子：

在这个局面里，如果白方被迫走子，他走Kb2，而黑走Kd2助兵变后。如果白方不走棋，那么黑的走Kc3，局面就是和棋。(事实上这是一个互相的无等着局面，因为双方都被先走棋所困扰，这个问题不在我们的讨论范围内。)

如果到达这个局面，而且试图用空着向前裁剪，那么可能会认为黑方没有威胁白方，因为现在黑方确实没威胁白方。而现在黑方在等待白方毁掉局势，这就完全不同了。

由于这个原因，空着向前裁剪不能在残局中使用，或者至少不能直接地使用。如果你试图在残局中用，则会出现很糟糕的事情。

有一个更困扰人的例子，是这样的：

这个局面选自Goetsch和Campbell的《空着启发的试验》(Experiments with the Null-Move Heuristic)一文，发表在《电脑、象棋与认知》(Computers, Chess and Cognition)(ISBN 0-387-97415-6)一书中。

这个局面轮到白方走，白的下一步就被将死了，而且无能为力。对这个局面做两层的搜索，毫无疑问：1. <任何着法> Qg2#。

如果你在这里试图用空着向前裁剪，那么不幸发生了。我们原来打算做两层的完全搜索，现在要做的是对对方做零层搜索，并试图找到威胁。在零层搜索中，黑方不走子，所以调用“评价”函数，由于白方领先一个车而返回+5左右。这或许会大于Beta，因此搜索返回Beta。

这是我们不希望发生的!搜索应该返回一个很小的值，表示白方被杀。

我们这里看到的是一种水平线效应，经常发生在启用空着向前裁剪的时候。没有空着向前裁剪时，白方走了一步没用的着法，然后有足够的搜索深度(在这个例子中只需要一层)让黑杀掉白。用了空着向前裁剪并且用一个足够高的R值(例如R= 2)，白方不做任何事情，但是黑方也没有足够深度来看到胜利了。

这个例子或许让你感到奇怪，或许它只会在很浅的搜索中才发生，但是有很多例子在足够的搜索深度下仍然会发生这样的事，即用正常的搜索可以看到的棋，用了空着向前裁剪后就被忽视了。实际上，这个黑后在h3格并且黑兵在f3格的棋型，对于国际象棋程序来说都是很危险的。【原作者的意思是，如果程序遇到这种棋型，应该考虑适当延伸搜索深度，或者用更小的R值做空着裁剪。】

空着向前裁剪的另一个问题在于它会导致“搜索的不稳定性”。空着搜索的成功与否取决于Beta的值。这个结点下次访问时，Beta可能不同，因此搜索会有不同的值，这是很不合理的。你可能在传递窗口(7, 30)时搜索高出边界，但是传递(7, 50)时，却低出边界。

在实战中，比起遇到偶然的对策错误，以及搜索不稳定性的增加来说，搜索速度的加快重要得多。

一些思想

尝试调整一个不同于2的R值，这是非常有趣的事。你可以试试1、3、4或更大的数，或者根据搜索深度、棋盘上的子力等等因素改变。我从来没有得到比直接用R= 2更好的结果，但是一些研究表明其他值或许会更好，而且有些人至少在搜索树的部分结点上用R= 3的。

通过一些验证式的搜索，我们也可以试图找到残局中使用空着向前裁剪的方法。如果你的空着搜索高出边界，你就减少深度来做常规搜索，看它是否也高出边界。我觉得这看上去有些破费，但是还是值得尝试的。

还有其他的改进方法值得尝试，但是我不想把它们一一列举出来。你可以去看Donninger的文章，看《电脑、象棋与认知》(Computers, Chess and Cognition)的文章，或者看Ernst Heinz的跟空着向前裁剪有关的文章。

【译者有必要在这里介绍一下这两个思想：

(1)根据不同情况来调整R值的做法，称为“适应性空着裁剪”(Adaptive Null-Move Pruning)，它首先由Ernst Heinz发表在1999年的ICCA杂志上。其内容可以概括为：

a.深度小于或等于6时，用R= 2的空着裁剪进行搜索;

b.深度大于8时，用R= 3;

c.深度是6或7时，如果每方棋子都大于或等于3个(译者没注意到是否包括王)，则用R= 3，否则用R= 2。

参阅：Heinz EA:Adaptive Null-Move Pruning, ICCA J.22 (3): 123-132,1999

(2)验证空着裁剪是否安全的做法，称为“带验证的空着裁剪”(Verified Null-Move Pruning)，它首先由Tabibi发表在2002年的ICGA(原ICCA)杂志上。其内容可以概括为：

a.用R= 3的空着裁剪进行搜索;

b.如果高出边界，那么做浅一层的搜索(这就意味着一层的搜索是无法做带验证的空着裁剪的);

c.做浅一层的搜索时，子结点用R= 3的不带验证的空着裁剪;

d.如果浅一层的搜索高出边界，那么带验证的空着裁剪是成功的，否则必须重新做完全的搜索。

参阅：Tabibi OD, Netanyahu NS:Verified Null-Move Pruning, ICGA J.25 (3): 153-161,2002】

原文：brucemo 商业网/compchess/programming/nullmove.htm

译者：象棋百科全书网

类型：全译加译注