《棋战顺序基本手艺》专题
 
取得主要变例
 
Bruce Moreland /
 
要点
 
  经常一些人问,怎样在搜索完成后收罗主要变例。主要变例是顺序以为的对双方来说都是最好的着法线路。它不会由未修正的“Alpha-Beta函数”来取得,一切的Alpha-Beta都只前往数值。
  咱们要求做的是对一般的Alpha-Beta搜索作修正,使得它能取得主要变例。修正的局部用扎眼的颜色标出:
 
typedef struct tagLINE {
 int cmove;       // 线路中着法的数目;
 MOVE argmove[moveMAX]; // 线路。
} LINE;
 
int AlphaBeta(int depth, int alpha, int beta, LINE *pline) {
 LINE line;
 if (depth == 0) {
  pline->cmove = 0;
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -AlphaBeta(depth - 1, -beta, -alpha, &line);
  UnmakeMove();
  if (val >= beta) {
   return beta;
  }
  if (val > alpha) {
   alpha = val;
   pline->argmove[0] = ThisMove();
   memcpy(pline->argmove + 1, line.argmove, line.cmove * sizeof(MOVE));
   pline->cmove = line.cmove + 1;
  }
 }
 return alpha;
}
 
  这个函数也许效能很低,由于它用到许多的客栈空间,然则代码事情起来其实不慢。有了这些改动后,若是函数前往AlphaBeta之间的值,那末它不但单前往一个值,还包孕能发生这个值的线路(一系列展望的着法)。这关于搜索树的任何结点都是有用的,包孕根结点(它是最值得这么做的)。你能够这么来调用Alpha-Beta
 
val = AlphaBeta(depth, -INFINITY, INFINITY, &line);
 
  你失掉的是局势的值,以及在“line”这个存储区里生存的展望线路。“line”的数据组织是一个着法数组,以组成一个线路,尚有一个整数来通知你线路中有若干着法。
  若是你用深度即是零去调用Alpha-Beta,那末这个函数只调用“Evaluate()”并前往它的值。一个着法也没搜索,因而一个着法也没选择,从而和分值一同前往的线路其长度为零。
  若是你用某个深度调用这个搜索函数,那末你能够找到一个着法其值在AlphaBeta之间,而你失掉的不但单是分值,而且包孕能发生这个值的一系列着法。为了在Alpha-Beta历程当中竖立线路,你拿出这个搜索到的着法,把它存入通报的线路存储区中【译注:即函数中的“*pline”】,并把一般中央的线路存储区【即函数中的“line”】也加到通报的存储区中。
  你能够会问:“如果有传过去的线路存储区,为甚么又要在每次递归的客栈中新分配一个?”由于你在搜索树中找到一个一般中央的线路,那末正本的线路被推翻了,但你不能损坏以前竖立好的线路。若是你找到某个前往值在AlphaBeta之间的结点,你就以为这个结点在搜索树的根结点的线路上,这是纰谬的。有许多细碎的主要变例是被抛弃的。
  使你们感应惊异的是,我在循环内用了“memcpy”这个函数【现实上这也是个循环,因而能够会以为它的效能很低】,它险些不花时刻,由于它很少被执行。
 
其余一个头脑
 
  其余一个一清二楚的要领,就是在搜索值前往后,从主置换表中收罗主要变例。置换表项中有一个区域寄存这局势的最好着法。由于每一个PV结点都有一个值在AlphaBeta之间,散列项中一定生存着“最好着法”。
  从置换表中收罗主要变例,能够顺着散列项组成的链来收罗,这就像吃馅饼一样简朴。
  我知道许多顺序(包孕一些专业顺序)是这样做的,然则我没有试过。
  【状况能够会比想象中的庞大,由于置换表中的数据会被掩盖,这样做就必需选择适宜的掩盖战略。显著根结点是不会被掩盖的(它总是最终一个写入置换表),因而最少能收罗出一个着法(即顺序要走的那步棋),然则后续着法就很难确保了。深度优先的掩盖战略会对照有益,除此之外,也能够斟酌PV结点优先的战略,由于PV结点的数目比Alpha结点和Beta结点少很多,以是这个掩盖战略对置换表不会发生很大的滋扰。
  其余,直接从Alpha-Beta函数收罗的主要变例,会由于置换表的运用而中缀,除非置换内外有一项用来存储主要变例(这不是不能够的,由于PV结点的数目异常少)。若是要失掉完整的主要变例,能够斟酌不在置换表中写入PV结点(某些顺序以至只在置换表中写入Beta结点)。】
 
  原文:http://www.seanet.com/~brucemo/topics/pv.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 其他战略——胜利局势
  • 下一篇 其他战略——一次又一次检测
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com