國際象棋譯文苑》文摘

開局庫、哈希表

Aaron Tay
 
  C1. 什么叫開局庫(opening book)
  就象人們記住開局譜著一樣,棋弈程序使用一個數據庫,里面儲存了開局譜著和局面,于是當對局(開局)中的棋步在開局庫中能找到時,它就可以立即取出來走,不用計算。無庸多說,這對于程序節省思考時間有重大幫助。但另一方面,如果開局庫本身不好或部分不好,程序也可能被盲目引到劣勢的局面甚至很快失利。多數Winboard引擎都可使用開局庫,它們絕大部分都是和程序本身分離的獨立文件(典型的是以.bk為后綴),也有少部分是內建在程序里面。【譯注:但不同的程序尤其商業性的又有不同的規矩。比如Fritz等的是.ctg后綴;有些是.bok.book后綴;另外有些程序的開局庫下載下來后甚至還要手動更改后綴才能工作!不一而足】
 
  C2. 什么叫開局學習?(book learning)
  概念簡單,但形式很多樣。總的來說,就是使程序從總是導致劣勢(失敗)的那些重復的開局變化中“吸取經驗教訓并自行改正”的功能設置。目前還不是很多Winboard引擎有這項功能,只有一些較高的比如Crafty,它不但把結果寫入到開局庫相關文件,甚至產生一個學習文檔反映它究竟“學到了些什么”,使你能與別人交換和引入這些“所學成就”。
 
  C3. 如何使用開局庫?
  不同引擎不同,但一般都是把開局庫文件放在和棋弈引擎文件同一目錄下,而且通常還另有一個設置文件(可能是.ini后綴,也可能別的,比如crafty的是.rcruffian.cfg后綴),在設置文件里把“開局庫”(opening book,或者類似這樣的表達)設為ON就可以。【譯注:當然有些作者喜歡用ON/OFF,有些喜歡用1/0或其它,隨他們高興的】
 
  C4. 能令所有引擎使用統一的開局庫嗎?
  在Fritz等中,可注意到不同的引擎可以使用統一的開局庫。但對于Winboard引擎,目前還沒有統一的開局庫格式,因此不同的引擎有不同格式的開局庫。想達到題目要求,有些變通辦法,但目前在通用性方面還很欠缺。需等待Winboard的下一個新版協議出來,引入“開局引擎”(book engine)的概念才有通用性。
  【譯注:把C5-C11點轉到別的譯文或省略;以后不再特別說明】
 
  C12. 什么叫置換/哈希表(Transposition/Hash tables)
  當棋弈引擎開始對一個局面進行分析時,它經常是“試驗”以不同次序去走但到達同樣局面的棋,程序于是把這樣的局面以及對局面的評價值保存在內存中,一旦碰到以別的走棋次序但到達同樣局面的變化時,換句話說,當計算“另一個”變化但到達的局面其實之前已經出現過時,程序就省下了再次估值的時間了。想詳細一點了解,看Dann Corbit在“Winboard論壇”中的發言:
  哈希表是一種加快搜索的數據結構,它本身的原理模型要一點數學或程序設計基礎去理解。(不是想搞棋弈引擎寫作的可以不管)
  哈希表用在棋弈程序中,作用很大。舉例,計算如何走棋時,我可能先走馬后走車,也可能先走車后走馬,假如對手各自相對應的應著不變,那么不同次序走完兩步棋后到達的局面是一模一樣的。
  如果我已經對局面進行了計算估計,那很好。如果我對已經計算過了的局面還要再次計算估計那就不好了,如果讓電腦這樣做,會占用它很多時間的。
  哈希表的用途就是在這種情況下迅速查找之前已經完成了的工作(已經計算過的估值)。我可以把一個估值加上一個“索引”(hash key)保存在表中,這樣做的目的是制造一個“唯一的標識”,而執行過程是很快的。我對當前局面產生一個“索引”,然后看這個索引在表中是否已經有保存了。假如是有,就看表中的值是多少。表中的估值足夠深入因此我不需要再次計算了嗎?如果是這樣,那么我就只需把值從表中取出來,而不用又再來一次計算。這大大節省了時間。
  哈希表是一種非特殊的數據結構,因此很容易就可作為棋弈程序的其它用途。它對程序的執行速度提高是非常大的,我們認為哈希表是好程序的一個相當必要的功能。
  根據程序的不同,這種表的類型有多種。首先有殘局庫哈希表[原注:其實叫做緩存更準確些],根據Yace的設計者Dieter Buerssner的解釋,它是“和磁盤緩存類似的工作原理,避免過多磁盤存取動作,所以在殘局后段提高程序的速度。”
  有些棋弈程序[例如Goliath]除了殘局庫哈希表之外只有一個主哈希表,而其它[比如Crafty]在主表之外還使用兵結構哈希表。有個棋弈程序Bringer則除了殘局庫表之外還有三個,分別是兵、估值和局面哈希表。
 
  C13. 那我應該給哈希表分配多少內存空間?
  為哈希表分配更多內存空間一般來說提高棋的質量。對于時限較長的對局以及你的CPU較快,哈希表很快被充滿,所以設得大些有幫助。但是,如果對局時限很短,設過大的空間非但沒有幫助,反而可能降低棋力,因為存在過多的存取動作。即使這些不利沒有發生,對于某些引擎(比如某些版本的Crafty,和Chessmaster8000),它們每走一步棋都清除哈希表,這樣對于大型的哈希表來說甚至導致幾秒鐘的延遲(打了補丁的Chessmaster8000Chessmaster9000沒有這個問題)。如果是下很快的對局,這當然不利。【譯注:嚴格來說Chessmaster8000/9000不能說是“引擎”,而應是“軟件”,或“程序”也行。但作者假定讀者應該對這些基本概念了解清楚了,就沒那么嚴格】
  那么多大才是過大呢?
  為chessbase寫作的史蒂夫·洛佩茲,他推薦的計算公式是:2xCPU速度(Mhz數計算)x對局每步平均秒數,得出結果然后除以1000換算成以M數標識的大小,就是你該為哈希表分配的內存空間大小。舉例,如果你讓引擎走5分鐘40步的快棋,使用的CPU速度是 1 Ghz(1000Mhz),根據公式應該為哈希表分配的內存空間數是=2x1000x(5x60/40)=15000 K,除以1000換算就是15M
  但問題接著來了,這樣為每種不同引擎算出的哈希表大小都是相同的,而沒有考慮不同引擎每秒鐘搜索的速度【哪怕它們水平相近,搜索速度也可能相差很大的】。引擎的搜索以每秒計算多少個“節點”(Node)來衡量。
  寫作Chessmaster的約翰·梅里諾提出另一條公式,哈希表大小=2x引擎每秒搜索節點數(NPS)x每步平均秒數。
  盡管這只是他們為Chessmaster而推薦的,但似乎也能很好適應多數引擎,因為這樣直接把已搜索節點數與因此而需要的哈希表大小一起衡量。不過,這依然是個粗略建議,我發現它通常比上一個公式得出的結果低,但不清楚是否這才更準確。【譯注:但如果按上兩個公式計算,結果都比默認的偏小甚至偏小很多。另外這也與下面的簡便設置方法有矛盾,所以只作參考】
  另外,如果你不是讓引擎對戰引擎,你大可以把哈希表設為你的內存最多一半。剩下的是留給Windows操作系統使用,剩下的不能過小,以免系統本身不夠用而出現頻繁硬盤存取。如果你讓引擎對戰引擎,就把它們的哈希表大小之和設為內存的一半。但我必須說明,這是對低內存用戶的限制,比方少于256M內存的用戶。Windows本身使用的內存資源數都有限定的了,所以如果你擁有大內存,就不必遵守“50%”規則。比方你有512M內存,大概可以設置到總數420M
  而如果有同時兩種以上哈希表還加上殘局庫哈希表,那么每種哈希表要分別分配多少內存更難確定。我認為沒有絕對的捷徑,要通過對不同的引擎一次次的試驗和總結經驗后確定。
  我們必須注意到,不同的引擎是不一樣的。有些引擎甚至硬性規定了固定大小的哈希表,不能更改。其它的,很多都允許修改大小而且分配可能的任意數值都行。而Crafty則介于兩者之間,它允許修改哈希表的大小,但只能是以整數值遞增()
 
  出處:Aaron's Winboard and Chess Engines FAQ
  譯者:michael
  類型:節譯
  • 上一篇 先進國際象棋
  • 下一篇 棋弈軟件基礎——殘局庫
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果