《對弈程序基本技術》專題
 
置換表
 
Bruce Moreland /
 
一個多功能的數據結構
 
  國際象棋的搜索樹可以用圖來表示,而置換結點可以引向以前搜索過的子樹上。置換表可以用來檢測這種情況,從而避免重復勞動。如果“1. e4 d6 2. d4”以后的局面已經搜索過了,那就沒有必要再搜索“1. d4 d6 2. e4”以后的局面了。
  這個原因可能鼓舞著早期的電腦國際象棋程序的設計師們,而現在事實上這還是置換表的次要用途。在某些局面,例如在沒有通路兵的王兵殘局中,檢查到的置換的數量是驚人的,以至于搜索可以在短達時間內達到很深的深度。
  省去重復的工作,這是置換表的一大特色,但是在一般的中局局面里,置換表的另一個作用更為重要。每個散列項里都有局面中最好的著法,我在“迭代加深”這一章里解釋過,首先搜索好的著法可以大幅度提高搜索效率。因此如果你在散列項里找到最好的著法,那么你首先搜索這個著法,這樣會改進你的著法順序,減少分枝因子,從而在短的時間內搜索得更深。
 
實現
 
  主置換表是一個散列數組,每個散列項看上去像這樣:
 
#define hashfEXACT 0
#define hashfALPHA 1
#define hashfBETA 2
typedef struct tagHASHE {
 U64 key;
 int depth;
 int flags;
 int value;
 MOVE best;
} HASHE;
 
  這個散列數組是以“Zobrist鍵值”為指標的。你求得局面的鍵值,除以散列表的項數得到余數,這個散列項就代表該局面。由于很多局面都有可能跟散列表中同一項作用,因此散列項需要包含一個校驗值,它可以用來確認該項就是你要找的。通常校驗值是一個64位的數,也就是上面那個例子的第一個域。
  你從搜索中得到結果后,要保存到散列表中。如果你打算用散列表來避免重復工作,那么重要的是記住搜索有多深。如果你在一個結點上搜索了3層,后來又打算做10層搜索,你就不能認為散列項里的信息是準確的。因此子樹的搜索深度也要記錄。
  在Alpha-Beta搜索中,你很少能得到搜索結點的準確值。AlphaBeta的存在有助你裁剪掉沒有用的子樹,但是用Alpha-Beta有個小的缺點,你通常不會知道一個結點到底有多壞或者有多好,你只是知道它足夠壞或足夠好,從而不需要浪費更多的時間。
  當然,這就引發了一個問題,散列項里到底要保存什么值,并且當你要獲取它時怎樣來做。答案是儲存一個值,另加一個標志來說明這個值是什么含義。在我上面的例子中,比方說你在評價域中保存了16,并且在標志域保存了“hashfEXACT”,這就意味著該結點的評價是準確值16;如果你在標志域中保存了“hashfALPHA”,那么結點的值最多是16;如果保存了“hashfBETA”,這個值就至少是16
  當你在搜索中遇到特定情況時,很容易決定評價和標志應該保存哪些內容。然而避免錯誤是非常重要的,散列表是非常容易犯錯誤的,而且一旦犯下錯誤就很難捕捉出來。
  我的散列項的最后一個域,保存著上次搜索到這個局面時的最佳著法。有時我沒有得到最佳著法,比如任何低出邊界的情況(返回一個小于或等于Alpha的值),而其他情況必定有最佳著法,比如高出邊界的情況(返回一個大于或等于Beta的值)【譯注:只有葉子結點才沒有最佳著法,即便是Alpha結點,所有的著法都是差的,也應該從中找一個最好的著法,它對更深一層的搜索會帶來很大的好處。】
  如果找到最佳著法,那么它應該首先被搜索。
  下面是示范程序,是根據Alpha-Beta函數修改的,改動的地方用醒目的字標出:
 
int AlphaBeta(int depth, int alpha, int beta) {
 int hashf = hashfALPHA;
 if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN) {
  // 【valUNKNOWN必須小于-INFINITY或大于INFINITY,否則會跟評價值混淆。】
  return val;
 }
 if (depth == 0) {
  val = Evaluate();
  RecordHash(depth, val, hashfEXACT);
  return val;
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -AlphaBeta(depth - 1, -beta, -alpha);
  UnmakeMove();
  if (val >= beta) {
   RecordHash(depth, beta, hashfBETA);
   return beta;
  }
  if (val > alpha) {
   hashf = hashfEXACT;
   alpha = val;
  }
 }
 RecordHash(depth, alpha, hashf);
 return alpha;
}
 
  以下就是兩個新的函數的代碼:
 
int ProbeHash(int depth, int alpha, int beta) {
 HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
 if (phashe->key == ZobristKey()) {
  if (phashe->depth >= depth) {
   if (phashe->flags == hashfEXACT) {
    return phashe->val;
   }
   if ((phashe->flags == hashfALPHA) && (phashe->val <= alpha)) {
    return alpha;
   }
   if ((phashe->flags == hashfBETA) && (phashe->val >= beta)) {
    return beta;
   }
  }
  RememberBestMove();
 }
 return valUNKNOWN;
}
 
void RecordHash(int depth, int val, int hashf) {
 HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
 phashe->key = ZobristKey();
 phashe->best = BestMove();
 phashe->val = val;
 phashe->hashf = hashf;
 phashe->depth = depth;
}
 
  你所看到的代碼,并不像航天科學一樣準確,而是很可能有錯誤的,而且細節上的問題我還沒有討論。如果你的程序中有錯誤,或許就是很嚴重的錯誤。
  【以上代碼有個速度上的瓶頸,即“ZobristKey() % TableSize()”這個表達式。由于“電腦一做除法就成了傻瓜”,所以“TableSize”最好是一個2n的常量,只有當除數是2n時除法才可以由右移指令取代。最好的方法是設一個“TableSizeMask”的變量:
 
int TableSizeMask = TableSize() - 1;
HASHE *phashe = &hash_table[ZobristKey() & TableSizeMask];
 
  而這里“TableSize()”也必須是2n。正是這個道理,在很多可以設定置換表大小的國際象棋程序中,允許的設定值總是呈倍數增長的,要么是3M6M12M24M等等(如果每個散列項有12字節),要么是4M8M16M32M等等(如果每個散列項有16字節)。】
 
替換策略
 
  最主要的細節就包括,什么時候該覆蓋散列項。在上面的例子中,我用了“始終替換”的策略,即簡單地覆蓋已經存在的值。這或許不是最好的策略,事實上已經有大量的工作試圖找出哪個策略是最好的。
  另一個策略是“同樣深度或更深時替換”。除非新局面的深度大于或等于散列表中已經有的值,否則已經存在的結點將被保留。
  還有很多試驗的余地。1994年我在Usenet(新聞組網絡系統)的新聞組rec.games.chess(如今是rec.games.chess.computer)上問了這個問題,得到了Ken Thompson的答復。
  他的回答是使用兩個散列表。一個使用“始終替換”策略,另一個使用“同樣深度或更深時替換”。當你做試探時,兩個散列表都去試探,如果其中一個可以產生截斷,那就可以了。如果兩者都不能產生截斷,那么你可能至少得到一個最佳著法,實際上更多的可能是得到兩個不同的著法,兩者都應該首先(或第二個)嘗試。
  記錄的時候,你只要簡單地根據替換策略來執行。
  如果你使用“同樣深度或更深時替換”的策略,那么你的散列表可能最終會被過期的但很深的結點所占滿。解決方案就是每次你走棋時都清除散列表,或者在散列項中加入“順序”這個域,從而使這個策略變成變成“同樣深度,或更深,或原來是舊的搜索,才替換”。
  我在我的程序Ferret中使用了Thompson的策略,并且運行得很好。另一個程序Gerbil也使用這個策略,你可以去看它的源代碼。
  【根據譯者研究的結果,只用“深度優先覆蓋”策略(即“同樣深度或更深時替換”),效果會比“始終替換”好得多,而代碼則并不復雜,只有醒目的部分是新增的:
 
void RecordHash(int depth, int val, int hashf) {
 HASHE *phashe = &hash_table[ZobristKey() & (TableSize() - 1)];
 if (phashe->hashf != hashfEMPTY && phashe->depth > depth) {
  return;
 }
 phashe->key = ZobristKey();
 phashe->best = BestMove();
 phashe->val = val;
 phashe->hashf = hashf;
 phashe->depth = depth;
}
 
  如果使用這個代碼,那么每走一步以前都必須把散列表中所有的標志項置為“hashfEMPTY”。】
 
不穩定性的問題
 
  當你用置換表時,如果你允許搜索過程根據散列項來截斷,那就會產生另一個問題,你的搜索會受“不穩定性”的捆擾。
  不穩定性至少是由以下因素引起的:
  1. 你可能在做6層的搜索,但是如果你在散列項中得到10層搜索的結果,就可能根據這個值來截斷。在后來的搜索中,這個散列項被覆蓋了,因此你在這個結點上得到了兩個不同的值。
  2. Zobrist鍵值無法記錄到達結點的線路,這個結點上不是每條線路都有相同結果的。如果某條線路遇到重復局面,那么散列項的值就會跟路線有關。因為重復局面會導致和局的分值,或者至少不一樣的分值。
  就我所知,還沒有什么辦法能處理這些問題。
  【另外,如果搜索過程中找到殺棋,那么評價值會接近“INFINITY”或“-INFINITY”,此時記錄散列表時不能簡單地記錄這些評價值,在后面介紹的“勝利局面”的處理中,會談到這個問題。】
 
  原文:http://www.seanet.com/~brucemo/topics/hashing.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 基本搜索方法——迭代加深
  • 下一篇 高級搜索方法——簡介()
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果