《棋战顺序基本手艺》专题
 
空着向前裁剪
 
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