《對弈程序基本技術》專題
 
開局庫
 
Martin Fierz */
* 瑞士Windisch應用科學學院(Aargau學院)
 
  不管你是否喜歡,開局庫在很多棋類中都是非常重要的。很多棋類已經被人類積累了大量知識(例如國際象棋、西洋跳棋等),而有些棋類是新誕生的(或是因為不普及)因而沒什么發展。對于人類非常精通的棋類(例如國際象棋),建立開局庫有個非常簡單的辦法,即手工產生,選擇高手走的棋。這種方法不是我們感興趣的,而對于一些沒有理論可尋的,或者電腦足以戰勝人類(例如西洋跳棋)的棋類,用這個方法是不可取的。我們將會關注一種沒有人工干預的生成開局庫的方法。
 
從數據庫自動生成
 
  要生成開局庫,有個簡單的方法就是找一個對局數據庫,根據對局結果來選擇可靠的著法。我的國際象棋程序的開局庫就是這樣生成的,很多國際象棋程序也都使用這種方法。對于國際象棋來說,有高質量的數據庫,其中包括很多高等級分棋手下的,因此你可以決定僅僅使用高等級分棋手的對局。對于每個局面,可以生成所有著法的統計數字,例如這步著法的分數,下這步著法的棋手平均等級分,這步著法得到的平均結果,以及用結果衡量和用棋手等級分衡量的不同之處。有的對局會以符號“!(好著)或“!!(妙著)作評論,把這種評論考慮進去也是可行的,但我不知道是否有人這么做。我的國際象棋程序的開局庫只參照統計數字,采用棋手等級分最高的著法。
 
由“脫離棋譜的擴展”自動生成
 
  如果沒有人類積累的棋類理論,那么你就不得不自己計算開局庫了。任何計算開局庫的方法,都需要用稱為“博弈樹”的圖來表達,圖上的每個結點代表一個局面。對于每個局面,你需要計算所有可能著法的值,因此每個候選著法都要擴展。跟這個圖表相應,你還必須找到一個方法來決定哪些結點是需要展開的,也就是說,圖表上的哪個葉子結點需要再添加結點。這里我將介紹一個稱為“脫離棋譜的擴展”(DOEDrop-out Expansion)的方法,它是由Thomas Lincke發明的。DOE的基本思想就是產生一個開局庫,使得比賽時可以盡可能遲地脫離棋譜。建立開局庫時有個策略,每個局面的一些好的著法需要擴展,然后從擴展出的局面繼續,這樣總是會在當前結點處擴展出一些著法(例如固定數量的著法,或者和跟最好著法的評價差距在一定程度內的這些著法)。但是這個策略在遇到不恰當的局面時往往很糟糕,采用這種開局庫的程序通常只會走開局庫中最好的著法,而對手會犯錯誤(要注意對手所謂的錯誤可能也是好的著法,僅僅是對于你的開局庫而言是錯誤的)。因此,開局庫生成器只能對一方生成最好的一些著法,而對方應該能走好的或不好的著法。首先,DOE生成器會需要產生一個圖表,它對每個結點的后續著法都有一個評價。然后需要一個優先函數,對每個可能的路徑(DOE限制下,一方只走最好的著法)都可以給出一個優先值,對優先級高的路徑的葉子結點作擴展。這個策略使得它要做很煩瑣的并行計算,如果你有計算機集群,那么你可以在主機上運行DOE生成器,而眾多子機上對每個局面做精確的計算。路徑優先級的計算相對來說比較隨意,你可以用類似下面的方法來做:
 
delta = sum_of_errors(path);
depth = length(path);
priority = -delta - CONST * depth;
 
  這個優先函數會使對手的好的著法搜索得深一些,對手犯錯誤的著法搜索得淺一些。你可以在優先級的計算中加入其他因素,例如衡量結點重要性的因素。Thomas Lincke在他的優先函數中使用過“策略數”(Conspiracy Number),我的程序則衡量結點的單一性(Singularity),也就是說,最好和次好的著法差距很大,這條路線就搜索得深一些。
 
DOE的現狀
 
  DOE是一個比較新的技術,在西洋跳棋(我和Ed Gilbert的程序)Awari(Thomas Lincke的程序)中用得比較成功。我的西洋跳棋的DOE生成器已經在一臺單機上運行了近2年了,生成的開局庫基本上不再有差錯了(在一臺很快的個人電腦上計算了1年半以后),或許還能夠糾正人們對這種棋類在開局上的錯誤認識。我之所以說“基本上”,是因為目前我知道的著法中沒有錯誤,但是也有可能開局庫的成千上萬個著法里會隱藏著幾個壞的著法。半年前我和Ed Gilbert讓我們的引擎比了624盤棋,我的程序Cake戰績是31負,其余620盤是和棋,和棋率是那么的高!輸的那局揭示了我的開局庫里的一個問題,現在已經修補好了。
 
  原文:http://www.fierz.ch/strategy4.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 其他策略——殘局庫
  • 下一篇 其他策略——策略和技巧
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果