《对弈程序基本技术》专题
 
空着向前裁剪
 
Bruce Moreland /
 
没有副作用即可获得额外的速度
 
  空着向前裁剪(Null-Move Forward Pruning),运用可能忽视重要路线的冒险策略,使得国际象棋的分枝因子锐减,它导致搜索深度的显著提高,因为大多数情况下它明显降低了搜索的数量。它的工作原理是裁剪大量无用着法而只保留好的。
  这个技术在很多刊物上报道过,但是使得大家都来关注空着的,则是由Chrilly Donniger发表在19939月的ICCA杂志上的一篇文章。
  试想国际象棋搜索树中的某个局面,你的程序将以D层搜索这个局面的每个着法。如果其中任何一个着法的分数超过Beta,你就会马上返回Beta。如果任何一个超过Alpha,但是没有超过Beta,你就要记住着法和分值,因为这有可能是主要变例的一部分。如果它们全部小于或等于Alpha,你就要返回Alpha
  空着向前裁剪是你搜索任何着法之前要做的事。你要问一个问题:“如果我在这里什么都不做,对手能做什么?”
  记得在刚才,你没有问这个问题。你只是去找最佳的着法去打击对手。问对手是否会打击你,这个问题却有所不同。
  但是事实证明很多情况下对手无法打击你。比如说你送了一个车,而其他棋子都没有作用,在这种情况下,对手随便走哪步你都吃亏,因为你丢了一个车。空着向前裁剪的要点,就是简单地去掉那些没用的着法,而不要在这上面多花时间。
  这就好比像打架时,根据自己的能力给对手一个出击的机会,来增加自己的信心。如果任凭对手攻击也无法击倒你,那么你攻击他的时候他会输掉。
  我们不讨论这个策略了,现在来谈它是如何运用在电脑国际象棋中的。在你搜索着法以前(事实上在你生成着法以前),你做一个减少深度的搜索,让对手先走,如果这个搜索的结果大于或等于Beta,那么你简单地返回Beta而不需要搜索任何着法。
  这个思想就给了对手出击的机会,如果你的局面仍然好到超过Beta的程度,你就假设如果你搜索了所有的着法也会超过Beta
  这个方法能节省时间的原因是,开始时用了减少深度的搜索。深度减少因子称为R,因此跟你用深度D搜索所有的着法相比,现在你是先以D - R搜索对手的着法。一个比较好R2,如果你要对所有的着法搜索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)调用了搜索,但是由于递归时必须把AlphaBeta颠倒并取负数,这就变成源代码中的样子了。
  不用说,这个代码在一方被将军时不能发挥作用(因为对手立刻把王吃掉了)。什么地方允许调用空着向前裁剪,必须掌握好分寸,因为如果你允许一次连续地这么做,那么搜索将退化成什么都不做了。一个很简单的尝试,就是当中没有间隔一个实在着法的时候,不要让两个空着搜索连在一起。另一个思想是在一个实在着法之前,允许连续两个空着裁剪。实践证明这两个方法都做得很好。
 
嗯,还是有副作用的
 
  不幸的是,空着向前裁剪在某些地方不能正常运行。我们作了一个重要的假定——假定走了一步棋会比不走棋有更高的分值。不幸的是,这个假定在很多典型的局面上并不成立,这些局面非常普遍,并且有一个名称——无等着局面(Zugzwang)。无等着局面指的是,如果你不走棋,局势会好些,但是你被强迫走子,这使得你的局势会崩溃。下面是个典型的例子:
 
 
  在这个局面里,如果白方被迫走子,他走 Kb2,而黑走 Kd2 助兵变后。如果白方不走棋,那么黑的走 Kc3,局面就是和棋。(事实上这是一个互相的无等着局面,因为双方都被先走棋所困扰,这个问题不在我们的讨论范围内。)
  如果到达这个局面,而且试图用空着向前裁剪,那么可能会认为黑方没有威胁白方,因为现在黑方确实没威胁白方。而现在黑方在等待白方毁掉局势,这就完全不同了。
  由于这个原因,空着向前裁剪不能在残局中使用,或者至少不能直接地使用。如果你试图在残局中用,则会出现很糟糕的事情。
  有一个更困扰人的例子,是这样的:
 
 
  这个局面选自GoetschCampbell的《空着启发的试验》(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)时,却低出边界。
  在实战中,比起遇到偶然的对策错误,以及搜索不稳定性的增加来说,搜索速度的加快重要得多。
 
一些思想
 
  尝试调整一个不同于2R值,这是非常有趣的事。你可以试试134或更大的数,或者根据搜索深度、棋盘上的子力等等因素改变。我从来没有得到比直接用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. 深度是67时,如果每方棋子都大于或等于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
 
  原文:http://www.seanet.com/~brucemo/topics/nullmove.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 高级搜索方法——静态搜索
  • 下一篇 高级搜索方法——期望窗口
  • 返 回 象棋百科全书——电脑象棋
  • www.xqbase.com