《棋战顺序基本手艺》专题
 
主要变例搜索
 
Bruce Moreland /
 
Alpha-Beta的革新
 
  主要变例搜索(PVS, Principal Variation Search)是提升“Alpha-Beta”算法效能的一种要领。
  在Alpha-Beta搜索中,任何结点都属于以下三种类型:
  1. Alpha结点。每一个搜索都邑失掉一个小于或即是Alpha的值,这就意味着这里没有一个着法是好的,多是由于这个局势临于要走的一方太坏了。
  2. Beta结点。最少一个着法会前往大于或即是Beta的值。
  3. 主要变例(PV)结点。有一个或多个着法会前往大于或即是Alpha的值(PV着法),然则没有着法会前往大于或即是Beta的值。
  很多若干时刻你能够很早地剖断出你要处置责罚的是哪类结点。若是你搜索的第一个着法凌驾界限(前往一个大于或即是Beta的值),那末很显著你失掉Beta结点。若是低出界限(前往一个小于或即是Alpha的值),假定你的着法递次异常好,那末你有能够失掉Alpha结点。若是前往值在AlphaBeta之间,你能够失掉PV结点。
  固然,有两种状况你能够会剖断毛病。当你凌驾界限时,你前往Beta,因而你不会出毛病,然则若是第一个着法低出界限也许是PV着法时,依然有能够不才一个着法失掉更高的值。
  主要变例搜索作了假定,若是你在搜索一个结点时找到一个PV着法,那末你就失掉PV结点。也就是说假定你的着法排序以前足够好了,使得你没需要在剩余的着法中找更好的PV着法也许凌驾界限的着法(这就会使结点酿成Beta结点)
  你找到一个着法其值在AlphaBeta之间,那末对剩余的着法,搜索的目的就是证实他们都是坏的。跟要搜索出更好的着法相比,这类搜索能够要快一些。
  若是这个算法发现剖断是错的,即其中一个后续着法比第一个PV着法好,那末它会被再一次搜索,此次运用一样寻常的Alpha-Beta搜索要领。这类状况有时会发作,这样就虚耗时刻了,然则这些时刻一般不会凌驾面所说的“证实是坏着法”所勤俭上去的时刻。
  算法以下,是从Alpha-Beta算法悛改去的,悛改的中央用扎眼的字标出:
 
int AlphaBeta(int depth, int alpha, int beta) {
 BOOL fFoundPv = FALSE;
 if (depth == 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  if (fFoundPv) {
   val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);
   if ((val > alpha) && (val < beta)) { // 搜检失利
    val = -AlphaBeta(depth - 1, -beta, -alpha);
   }
  } else
   val = -AlphaBeta(depth - 1, -beta, -alpha);
  }
  UnmakeMove();
  if (val >= beta) {
   return beta;
  }
  if (val > alpha) {
   alpha = val;
   fFoundPv = TRUE;
  }
 }
 return alpha;
}
 
  算法的中心局部就是函数中央扎眼的“if”块中的内容。若是没有找到PV结点,“AlphaBeta()”函数就一样寻常调用,若是找到了一个,那末状况就变了。不是用通例的窗口(Alpha, Beta),而是用(Alpha, Alpha + 1)来搜索。这样做的条件是,搜索必需前往小于或即是Alpha的值,若是实在这样,那末把窗口的下面局部去掉就会致使更多的截断。固然,若是条件是错的,前往值是Alpha + 1或更高,那末搜索必需用宽的窗口重做。
  据报道PVS能够提升10%的效能。我没有试图检测PVS用在我的顺序里究竟提升了若干,然则实在提升了,以是我用了这个算法。
 
搜索不稳固性的问题
 
  若是你用(Alpha, Alpha + 1)这个窗口去做搜索,前往值凌驾了窗口(然则没有凌驾Beta),你就必需重新搜索。你以为重新搜索的值一定在AlphaBeta之间,然则生怕纷歧定是。这很有多是由“搜索的不稳固性”引发的,我会在其余章节中议论这个问题。
  下面写的谁人顺序对这个状况作了进攻,并对这类状况的发作作了准确的处置责罚。若是你要运用这个顺序而且作一些改动,就要稀奇留神你的搜索是否是总是稳固的。若是你失掉不希冀失掉的前往值,就必需接纳方法制止让顺序堕入毛病。
 
  原文:http://www.seanet.com/~brucemo/topics/pvs.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 低级搜索要领——希冀窗口
  • 下一篇 低级搜索要领——搜索的不稳固性
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com