電腦象棋循序漸進
 
象棋百科全書網 ([email protected]) 20084
 
() 質的飛躍
 
  與本文配套的示范程序是“象棋小巫師0.5版,程序清單是:
  (1) XQWL05.CPP——C++源程序;
  (2) XQWLIGHT.RC——資源描述文件;
  (3) RESOURCE.H——資源符號定義文件;
  (4) RES目錄——圖標、圖片、聲音等資源。
 
  在閱讀本章前,建議讀者先閱讀象棋百科全書網計算機博弈專欄的以下幾篇譯文:
  (1) 基本搜索方法——簡介()(David Eppstein)
  (2) 基本搜索方法——置換表(Bruce Moreland)
  (3) 其他策略——勝利局面(Bruce Moreland)
 
5.1 置換表
 
  沒有置換表,就稱不上是完整的計算機博弈程序。
  象棋小巫師的置換表非常簡單,以局面的 Zobrist Key % HASH_SIZE 作為索引值。每個置換表項存儲的內容無非就是:A. 深度,B. 標志,C. 分值,D. 最佳走法,E. Zobrist Lock 校驗碼。置換表的處理函數也很傳統——一個 ProbeHash 和一個 RecordHash 就足夠了。
  先說 RecordHash,即便采用深度優先的替換策略,RecordHash 也非常簡單,在判斷深度后,將 Hash 表項中的每個值填上就是了。
  再看看 ProbeHash 是如何利用置換表信息的:
  (1) 檢查局面所對應的置換表項,如果 Zobrist Lock 校驗碼匹配,那么我們就認為命中(Hit)了;
  (2) 是否能直接利用置換表中的結果,取決于兩個因素:A. 深度是否達到要求,B. PV節點還需要考慮邊界。
  第二種情況是最好的(完全利用)ProbeHash 返回一個非 -MATE_VALUE 的值,這樣就能不對該節點進行展開了。
  如果僅僅符合第一種情況,那么該置換表項的信息仍舊是有意義的——它的最佳走法給了我們一定的啟發(部分利用)
 
5.2 殺棋分數調整
 
  象棋小巫師從學會走棋開始,就已經考慮了殺棋分數。不過增加了置換表以后,這個分數要進行調整——置換表中的分值不能是距離根節點的殺棋分值,而是距離當前(置換表項)節點的分值。所以當分值接近 INFINITY -INFINITY 時,ProbeHash RecordHash 都要做細微的調整:
  (1) 對于RecordHash:置換表項記錄的殺棋步數 = 實際殺棋步數 - 置換表項距離根節點的步數;
  (2) 對于ProbeHash:實際殺棋步數 = 置換表項記錄的殺棋步數 + 置換表項距離根節點的步數。
 
5.3 殺手(Killer)走法
 
  把這個術語取名為Killer真是有些奇怪,但我們還是沿用這個術語。
  殺手走法就是兄弟節點中產生Beta截斷的走法。根據國際象棋的經驗,殺手走法產生截斷的可能性極大,所以我們在中國象棋里吸取了這個經驗。很顯然,兄弟節點中的走法未必在當前節點下能走,所以在嘗試殺手走法以前先要對它進行走法合理性的判斷。我們在0.2版中就寫過 LegalMove 這個函數,這里它將大顯身手。如果殺手走法確實產生截斷了,那么后面耗時更多的 GenerateMove 就可以不用執行了。
  如何保存和獲取“兄弟節點中產生截斷的走法”呢?我們可以把這個問題簡單化——距離根節點步數(nDistance)同樣多的節點,彼此都稱為“兄弟”節點,換句話說,親兄弟、堂表兄弟以及關系更疏遠的兄弟都稱為“兄弟”。
  我們可以把距離根節點的步數(nDistance)作為索引值,構造一個殺手走法表。象棋小巫師的每個殺手走法表項存有兩個殺手走法,走法一比走法二優先:存一個走法時,走法二被走法一替換,走法一被新走法替換;取走法時,先取走法一,后取走法二。
 
5.4 優化走法順序
 
  利用各種信息渠道(如置換表、殺手走法、歷史表等)來優化走法順序的手段稱為“啟發”。象棋小巫師0.5以前,我們只用歷史表作啟發,但從這個版本開始,我們采用了多種啟發方式:
  (1) 如果置換表中有過該局面的數據,但無法完全利用,那么多數情況下它是淺一層搜索中產生截斷的走法,我們可以首先嘗試它;
  (2) 然后是兩個殺手走法(如果其中某個殺手走法與置換表走法一樣,那么可以跳過)
  (3) 然后生成全部走法,按歷史表排序,再依次搜索(可以排除置換表走法和兩個殺手走法)
  這樣,我們就可以構造一個狀態機,來描述走法順序的若干階段:
  我們把狀態機寫在一個叫 Next 的函數中,那么 Alpha-Beta 的循環體就是:
 
…… // 初始化狀態機
while ((mv = Next()) != 0) {
 MakeMove(mv);
 …… // Alpha-Beta遞歸調用
 UndoMakeMove(mv);
 …… // Alpha-Beta邊界判斷
}
 
  在 Next 函數中,我們用了不帶breakswitch ... case結構:
 
switch (nPhase) {
case PHASE_HASH:
 nPhase = PHASE_KILLER_1;
 …… // 如果有置換表走法,就可以返回,再次調用就直接跳到 PHASE_KILLER_1
 // 注意:這里沒有break!
case PHASE_KILLER_1:
 nPhase = PHASE_KILLER_2;
 ……
}
 
  這就是“基于置換表的啟發式Alpha-Beta搜索”,目前頂尖的電腦(國際)象棋程序都逃脫不了這種架構,只不過它們在置換表和啟發算法上更加優化而已。
  • 上一篇 電腦象棋循序漸進():稍微聰明些了
  • 下一篇 電腦象棋循序漸進():精益求精
  • 返 回 象棋百科全書——計算機博弈
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果