《棋战顺序基本手艺》专题
 
希冀窗口
 
Bruce Moreland /
 
  希冀窗口是对迭代加深的革新。迭代加深的最简朴的完成要领是这样的:
 
for (depth = 1; ; depth ++) {
 val = AlphaBeta(depth, -INFINITY, INFINITY);
 if (TimedOut()) {
  break;
 }
}
 
  这里调用了一个“窗口”为正负无限大的Alpha-Beta搜索,以假定前往值多是很大的正数或正数。
  假定下一次迭代时,搜索的值不会比上一次有太多的更改,那末就能够够对上述的顺序作革新,代码以下:
 
#define valWINDOW 50 // 【译注:valWINDOW是窗口的半宽,在国际象棋中一般是半个兵的价值。】
alpha = -INFINITY;
beta = INFINITY;
for (depth = 1; ; ) {
 val = AlphaBeta(depth, alpha, beta);
 if (TimedOut()) {
  break;
 }
 if ((val <= alpha) || (val >= beta)) {
  alpha = -INFINITY;
  beta = INFINITY;
  continue;
 }
 alpha = val - valWINDOW;
 beta = val + valWINDOW;
 depth ++;
}
 
  这个代码有点烂,若是能够的话你能够把“continue”前面的局部改一下试试。这个头脑是用前一次Alpha-Beta迭代的值来功用到此次的迭代中。大少数状况下你失掉的前往值会在AlphaBeta之间。若是没有,那末你能够实验一个宽一些的窗口。
  我的重新搜索其实不那末有用,然则我置信你能够做得更好。一个很显著的头脑是,若是前往值大于或即是Beta,你就扩展Beta,若是前往值小于即是Alpha,你就扩展Alpha,而不是我所做的AlphaBeta都扩展。
 
搜索不稳固性的问题
 
  这是你要注意搜索不稳固性的其余一个中央。当我首次在我的国际象棋顺序中加入希冀窗口时,我想象若是前往值大于或即是Beta,那末重新搜索的效果就应当失掉更大的值。完整错了,我的顺序堕入了异常严重的毛病!下面是它的代码:
 
alpha = -INFINITY;
beta = INFINITY;
for (depth = 1; ; ) {
 val = AlphaBeta(depth, alpha, beta);
 if (TimedOut()) {
  break;
 }
 if (val <= alpha) { // 错!
  alpha = -INFINITY;
  beta = val + 1;  // 【这行没有就对了,但效能会低许多。】
  continue;
 }
 if (val >= beta) { // 错!
  beta = INFINITY;
  alpha = val - 1;
  continue;
 }
 alpha = val - valWINDOW;
 beta = val + valWINDOW;
 depth++;
}
 
  若是你能确认重新搜索会有效果,那末下面的代码会异常有用的。然则在我这里状况却是:
  1. 搜索(Alpha, Beta)时凌驾界限;
  2. 重新搜索(Beta - 1, INFINITY)时低出界限;
  3. 重新搜索(-INFINITY, Alpha + 1)时凌驾界限;
  4. 等等,等等……
  不论怎样你必需制止发作这类状况。
 
《棋战顺序基本手艺》专题
 
搜索的不稳固性
 
Bruce Moreland /
 
没有这个,生涯会更有趣
 
  当你试图写很强或很完善的顺序时,搜索的不稳固性就能够够显现。有许多缘由能够致使不稳固性,当我议论搜索的诸多革新要领时,特地议论了它们是怎样致使搜索不稳固的。其他我没有议论的搜索窍门也必需斟酌不稳固的能够。
  不稳固的搜索会前往有效的值,你用(5, 25)Alpha-Beta窗口会凌驾界限,因而你用(24, INFINITY)重新搜索,却低出界限。这不应当发作,由于凌驾界限很显著说明前往值应当是25也许更高,那怎样又会低出界限呢?
  现实就是这样,许多事情可以让国际象棋顺序运转得更快或更好,然则它们也许会做一些蠢事,在用分歧的窗口做搜索时前往稍微分歧的值。若是你没有失掉你所希冀的值,那末你的顺序能够会堕入毛病,也许发生一个使你的顺序走出昏着的毛病。
  一些国际象棋的顺序设想师没有掌握好搜索不稳固性的头脑,他们宁肯不用异常好的搜索算法,以免这类状况的发作,也许他们以为这样就能够够制止。
  我希冀有能够完整扫除搜索的不稳固性,然则就现在运用的异常基本的手艺而言,很存在问题。我想处置责罚设施就是对毛病作一些进攻,而别去深究不稳固性的缘由。
 
  原文:http://www.seanet.com/~brucemo/topics/instability.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 低级搜索要领——主要变例搜索
  • 下一篇 局势评价函数——简介()
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com
      【译者研讨以为,在用了前面要谈到的“主要变例搜索”以后,希冀窗口就险些没有用用了,因而许多顺序都没有运用这个手艺,只管它的头脑异常显著,看上去似乎能够起到好的效果。】
     
      原文:http://www.seanet.com/~brucemo/topics/aspiration.htm
      译者:象棋百科全书网 (webmaster@xqbase.com)
      类型:全译加译注
  • 上一篇 低级搜索要领——空着裁剪
  • 下一篇 低级搜索要领——主要变例搜索
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com