《對弈程序基本技術》專題
 
獲取主要變例
 
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
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 其他策略——勝利局面
  • 下一篇 其他策略——重復檢測
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果