《對弈程序基本技術》專題
 
Zobrist鍵值
 
Bruce Moreland /
 
比較局面的方法
 
  國際象棋局面包含了棋盤上的棋子、哪一方走棋、是否能易位、是否能吃過路兵等信息。
  在寫國際象棋的程序時,需要比較兩個局面看它們是否相同。如果你比較每個棋子的位置,或許不需要花很多時間,但是實戰中你每秒種需要做成千上萬次比較,因此這樣會使比較操作變成瓶頸的。另外,需要比較的局面數量多得驚人,要存儲每個棋子的位置,需要占用非常大的空間。
  一個解決方案是建立一個標簽,通常是64位。由于64位不足以區別每個局面,所以仍然存在沖突的標簽。但是實戰中這種情況非常罕見,你可以有充分的把握不會發生沖突。
  用32位是否足夠,目前爭論很多,而用64位通常是明智的。
  Zobrist鍵值是一個常用的建立標簽的方法。
 
實現
 
  你必須從多維的64位數組開始,每個數組含有一個隨機數。在C語言中,“rand()”函數返回一個15位的值(0~32767),所以要得到64位的隨機數還需要再加工一下。實際上我已經為你做好了,這個64位隨機數的函數是:
 
U64 rand64(void) {
 return rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^ ((U64)rand() << 45) ^ ((U64)rand() << 60);
}
 
  這個函數用來填滿一個“U64”的元素(你需要自己來定義這個類型,這取決于你的編譯器,試一下“long long”或者“__int64),它是通過調用一系列“rand()”來實現的。
  無論如何你的數組要有三維:棋子的類型、棋子的顏色和棋子的位置:
 
U64 zobrist[pcMAX][coMAX][sqMAX];
 
  程序啟動時就把這個數組用隨機數填滿,隨機數是必須非常隨機的,我看到Usenet(新聞組網絡系統)上很多人說“rand()”用在這里隨機性不是很好,但是我一直都用“rand()”并且沒有出現問題。如果你想使數組更隨機,就去找更強大的隨機函數,但是你要確保它的隨機性不比“rand()”差。
  要為一個局面產生Zobrist鍵值,首先把鍵值設成零,然后找棋盤上的每個子,并且讓鍵值跟“zobrist[pc][co][sq]”做異或(通過“^”運算符)運算。
  如果局面由白方走,那么別去動它,如果是黑方走,你還要在鍵值上異或一個64位的隨機常數。
 
為什么Zobrist鍵值特別有用
 
  用Zobrist技術產生的鍵值,表面上跟局面沒什么關系。如果一個棋子動過了,你會得到完全不同的鍵值,所以這兩個鍵值不會擠在一塊兒或者沖突。當你把它們用作散列表鍵值的時候會非常有效。
  另一個優點在于,鍵值的產生是可以逐步進行的。例如,你的白兵在e5格,那么鍵值里一定異或過一個“zobrist[PAWN][WHITE][E5]”。如果你再次異或這個值,那么根據異或的工作原理,這個兵就從鍵值里刪除了。
  這就是說,如果你有當前局面的鍵值,并且需要把白兵從e5移到e6,你只要異或一個“白兵在e5”的鍵值,把兵從e5格移走,并且異或一個“白兵在e6”的鍵值,把兵放在e6上。比起從頭開始一個個棋子去異或,這樣做可以得到同樣的鍵值。
  如果你要改變著子的一方,只要異或一個“改變著子方”的鍵值就可以了。你可以用類似的方法處理王車易位和吃過路兵的標志。
  用這種方法,你可以在搜索根結點的時候構造一個Zobrist鍵值,在搜索時通過走子函數“MakeMove()”來更新鍵值,一直讓它保持和當前局面同步。
 
Zobrist鍵值的用途
 
  Zobrist鍵值通常用在散列鍵值當中,而散列鍵值在國際象棋程序里有以下幾個作用:
  (1) Zobrist鍵值來實現置換表。置換表是一個巨大的散列表,來保存以前搜索過的局面,讓你節省很多搜索的時間。如果你需要對某個局面搜索9層,你可以從置換表中查找該局面,如果它已經搜索過9層,那么你不必去重復搜索。置換表的一個并不起眼的作用是,它可以幫助你改善著法的順序。
  (2) Zobrist鍵值來實現兵型的散列表。你可以用一個鍵值只記錄棋盤上的兵,對兵型做了很復雜的分析后,在散列表中記錄分析的結果。在實戰中兵型是很少發生變化的,所以這個散列表的命中率會非常高,它可以為你評估兵型節省很多時間。
  (3) 可以用Zobrist鍵值制造一個很小的散列表,來檢測當前著法路線中有沒有重復局面,以便發現長將或其他導致和局的著法。
  (4) 可以用Zobrist鍵值創建支持置換的開局庫。
 
  原文:http://www.seanet.com/~brucemo/topics/zobrist.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 數據結構——0x88著法產生方法
  • 下一篇 基本搜索方法——簡介()
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果