電腦象棋循序漸進
 
象棋百科全書網 ([email protected]) 20084
 
() 精益求精
 
  與本文配套的示范程序是“象棋小巫師0.6版,程序清單是:
  (1) XQWL06.CPP——C++源程序;
  (2) XQWLIGHT.RC——資源描述文件;
  (3) RESOURCE.H——資源符號定義文件;
  (4) RES目錄——圖標、圖片、聲音等資源;
  (5) BOOK.DAT——開局庫文件。
 
  在閱讀本章前,建議讀者先閱讀象棋百科全書網計算機博弈專欄的以下幾篇譯文:
  (1) 高級搜索方法——主要變例搜索(Bruce Moreland)
  (2) 高級搜索方法——搜索的不穩定性(Bruce Moreland)
 
  盡管我們的程序在架構上已經接近完整,但細節上存在不少問題:
  (1) 對于同一個局面,總是走固定的走法;
  (2) 搜索算法是否能更優化一些(某些讀者聽說過PVSNega-Scout之類的算法)
  (3) 有些殺棋局面會走出莫名其妙的走法。
  本章我們將把這些問題一一解決。
 
6.1 開局庫
 
  開局庫幾乎是每個象棋程序必備的部件,它的好處是:
  (1) 即使再笨的程序,開局庫能使得它們在開局階段看上去不那么業余;
  (2) 通過隨機選擇走法,讓開局靈活多變,增加對弈的趣味性。
  象棋小巫師使用開源象棋程序 ElephantEye 的開局庫,開局庫文件 BOOK.DAT 的結構是:
 
struct BookItem {
 DWORD dwLock;
 WORD wmv, wvl;
} BookTable[BOOK_SIZE];
 
  其中,dwLock 記錄了局面 Zobrist 校驗碼中的 dwLock1wmv 是走法,wvl 是權重(隨機選擇走法的幾率,僅當兩個相同的 dwLock 有不同的 wmv 時,wvl 的值才有意義)
  搜索一個局面時,首先不做Alpha-Beta搜索,而是查找 BookTable 中有沒有對應的項,有的話就直接返回一個走法。由于 ElephantEye 在制作開局庫時是按照 dwLock 排序的,因此可以用二分查找。找到一項以后,把它前后 dwLock 相同的所有項都取出,從中隨機選擇一個 wmv
  ElephantEye 為了壓縮開局庫的容量,所有對稱的局面只用一項,所以當一個局面在 BookTable 中找不到時,還應該試一下它的對稱局面是否在 BookTable 中。
 
6.2 根節點的特殊處理
 
  現在我們的程序一開局不會總是跳正馬了,根據 ElephantEye 提供的開局庫,它大部分時候走中炮,有時也走仙人指路(進兵)或飛相。可是當它脫離開局庫時,仍然擺脫不了思維的單一性,例如我們第一步走邊兵(開局庫中當然沒有這個局面),它仍舊只會跳同一邊的正馬。
  一個解決辦法是:在根節點處,讓一個不是最好的走法也能在一定的幾率取代前一個走法。我們的程序是這樣寫的:
 
if (vl > vlBest) {
 vlBest = vl;
 對vlBest作小范圍的隨機浮動;
}
 
  我們把根節點的搜索函數單獨分離,這樣做有很多好處:
  (1) 處理思考的隨機性;
  (2) 沒有必要嘗試 Beta 截斷(根節點處 Beta 始終是 +INFINITY)
  (3) 省略了檢查重復局面、獲取置換表、空步裁剪等步驟。
 
6.3 PVS
 
  很多計算機博弈的資料都介紹了PVS算法,但它只有當走法順序充分優化時才能帶來明顯的好處,因此象棋小巫師直到最后一個版本才用了這種算法。
 
6.4 長將判負策略
 
  由于單方面長將不變作負的規則,0.6以前的版本如果發生這種情況,想當然地給予-MATE_VALUE的值,再根據殺棋步數作調整。但是由于長將判負并不是對某個單純局面的評分,而是跟路線有關的,所以使用置換表時就會產生非常嚴重的后果——某個局面的信息可能來自另一條不同的路線。
  象棋小巫師的解決辦法就是:獲取置換表時把“利用長將判負策略搜索到的局面”過濾掉。為此這個版本中我們把長將判負的局面定為BAN_VALUE(MATE_VALUE - 100),如果某個局面分值在WIN_VALUE(MATE_VALUE - 200)BAN_VALUE之間,那么這個局面就是“利用長將判負策略搜索到的局面”。
  我們仍舊把部分“利用長將判負策略搜索到的局面”記錄到置換表,因為這些局面提供的最佳走法是有啟發價值的。反過來說,如果“利用長將判負策略搜索到的局面”沒有最佳走法,那么這種局面就沒有必要記錄到置換表了。
  經過這種處理,我們的程序在殺棋階段不再會走出莫名其妙的走法了,最后一個疑難雜癥終于攻克了。
  • 上一篇 電腦象棋循序漸進():質的飛躍
  • 下一篇
  • 返 回 象棋百科全書——計算機博弈
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果