《对弈程序基本技术》专题
 
期望窗口
 
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