?? 棋弈軟件基礎——開局庫、哈希表.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0045)http://www.elephantbase.net/computer/book.htm -->
<HTML><HEAD><TITLE>棋弈軟件基礎——開局庫、哈希表</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=棋弈軟件基礎——開局庫、哈希表_files/background.gif>
<P align=center>《<A href="http://www.chessit.net/"
target=_blank>國際象棋譯文苑</A>》文摘</P>
<P align=center><FONT face=隸書 size=6>開局庫、哈希表</FONT></P>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">Aaron Tay</FONT> </CENTER></DT></DIV>
<DT>
<DT><STRONG> </STRONG><FONT face=Arial><STRONG>C1.</STRONG></FONT><FONT
face="Times New Roman"><STRONG> </STRONG></FONT><FONT
face=黑體><STRONG>什么叫開局庫</STRONG></FONT><FONT face=Arial><STRONG>(opening
book)</STRONG></FONT>
<DT> 就象人們記住開局譜著一樣，棋弈程序使用一個數據庫，里面儲存了開局譜著和局面，于是當對局（開局）中的棋步在開局庫中能找到時，它就可以立即取出來走，不用計算。無庸多說，這對于程序節省思考時間有重大幫助。但另一方面，如果開局庫本身不好或部分不好，程序也可能被盲目引到劣勢的局面甚至很快失利。多數<FONT
face="Times New Roman">Winboard</FONT>引擎都可使用開局庫，它們絕大部分都是和程序本身分離的獨立文件<FONT
face="Times New Roman">(</FONT>典型的是以<FONT
face="Times New Roman">.bk</FONT>為后綴<FONT
face="Times New Roman">)</FONT>，也有少部分是內建在程序里面。<FONT
color=#000080>【譯注：但不同的程序尤其商業性的又有不同的規矩。比如</FONT><FONT face="Times New Roman"
color=#000080>Fritz</FONT><FONT color=#000080>等的是</FONT><FONT
face="Times New Roman" color=#000080>.ctg</FONT><FONT
color=#000080>后綴；有些是</FONT><FONT face="Times New Roman"
color=#000080>.bok</FONT><FONT color=#000080>或</FONT><FONT
face="Times New Roman" color=#000080>.book</FONT><FONT
color=#000080>后綴；另外有些程序的開局庫下載下來后甚至還要手動更改后綴才能工作！不一而足】</FONT>
<DT>
<DT> <FONT face=Arial><STRONG>C2.</STRONG></FONT><FONT
face="Times New Roman"> </FONT><FONT
face=黑體><STRONG>什么叫開局學習？</STRONG></FONT><FONT face=Arial><STRONG>(book
learning)</STRONG></FONT>
<DT> 概念簡單，但形式很多樣。總的來說，就是使程序從總是導致劣勢<FONT
face="Times New Roman">(</FONT>失敗<FONT
face="Times New Roman">)</FONT>的那些重復的開局變化中“吸取經驗教訓并自行改正”的功能設置。目前還不是很多<FONT
face="Times New Roman">Winboard</FONT>引擎有這項功能，只有一些較高的比如<FONT
face="Times New Roman">Crafty</FONT>，它不但把結果寫入到開局庫相關文件，甚至產生一個學習文檔反映它究竟“學到了些什么”，使你能與別人交換和引入這些“所學成就”。
<DT>
<DT> <FONT face=Arial><STRONG>C3.</STRONG></FONT><FONT
face="Times New Roman"> </FONT><FONT face=黑體><STRONG>如何使用開局庫？</STRONG></FONT>
<DT> 不同引擎不同，但一般都是把開局庫文件放在和棋弈引擎文件同一目錄下，而且通常還另有一個設置文件<FONT
face="Times New Roman">(</FONT>可能是<FONT
face="Times New Roman">.ini</FONT>后綴，也可能別的，比如<FONT
face="Times New Roman">crafty</FONT>的是<FONT
face="Times New Roman">.rc</FONT>，<FONT
face="Times New Roman">ruffian</FONT>是<FONT
face="Times New Roman">.cfg</FONT>后綴<FONT
face="Times New Roman">)</FONT>，在設置文件里把“開局庫”<FONT
face="Times New Roman">(opening book</FONT>，或者類似這樣的表達<FONT
face="Times New Roman">)</FONT>設為<FONT
face="Times New Roman">ON</FONT>就可以。<FONT
color=#000080>【譯注：當然有些作者喜歡用</FONT><FONT face="Times New Roman"
color=#000080>ON/OFF</FONT><FONT color=#000080>，有些喜歡用</FONT><FONT
face="Times New Roman" color=#000080>1/0</FONT><FONT
color=#000080>或其它，隨他們高興的】</FONT>
<DT>
<DT> <FONT face=Arial><STRONG>C4.</STRONG></FONT><FONT
face="Times New Roman"> </FONT><FONT
face=黑體><STRONG>能令所有引擎使用統一的開局庫嗎？</STRONG></FONT>
<DT> 在<FONT
face="Times New Roman">Fritz</FONT>等中，可注意到不同的引擎可以使用統一的開局庫。但對于<FONT
face="Times New Roman">Winboard</FONT>引擎，目前還沒有統一的開局庫格式，因此不同的引擎有不同格式的開局庫。想達到題目要求，有些變通辦法，但目前在通用性方面還很欠缺。需等待<FONT
face="Times New Roman">Winboard</FONT>的下一個新版協議出來，引入“開局引擎”<FONT
face="Times New Roman">(book engine)</FONT>的概念才有通用性。
<DT> <FONT color=#000080>【譯注：把</FONT><FONT face="Times New Roman"
color=#000080>C5-C11</FONT><FONT color=#000080>點轉到別的譯文或省略；以后不再特別說明】</FONT>
<DT>
<DT> <FONT face=Arial><STRONG>C12.</STRONG></FONT><FONT
face="Times New Roman"> </FONT><FONT
face=黑體><STRONG>什么叫置換/哈希表</STRONG></FONT><FONT
face=Arial><STRONG>(Transposition/Hash tables)</STRONG></FONT>
<DT> 當棋弈引擎開始對一個局面進行分析時，它經常是“試驗”以不同次序去走但到達同樣局面的棋，程序于是把這樣的局面以及對局面的評價值保存在內存中，一旦碰到以別的走棋次序但到達同樣局面的變化時，換句話說，當計算“另一個”變化但到達的局面其實之前已經出現過時，程序就省下了再次估值的時間了。想詳細一點了解，看<FONT
face="Times New Roman">Dann Corbit</FONT>在“<FONT
face="Times New Roman">Winboard</FONT>論壇”中的發言：
<DT> 哈希表是一種加快搜索的數據結構，它本身的原理模型要一點數學或程序設計基礎去理解。<FONT
face="Times New Roman">(</FONT>不是想搞棋弈引擎寫作的可以不管<FONT
face="Times New Roman">)</FONT>
<DT> 哈希表用在棋弈程序中，作用很大。舉例，計算如何走棋時，我可能先走馬后走車，也可能先走車后走馬，假如對手各自相對應的應著不變，那么不同次序走完兩步棋后到達的局面是一模一樣的。
<DT> 如果我已經對局面進行了計算估計，那很好。如果我對已經計算過了的局面還要再次計算估計那就不好了，如果讓電腦這樣做，會占用它很多時間的。
<DT> 哈希表的用途就是在這種情況下迅速查找之前已經完成了的工作<FONT
face="Times New Roman">(</FONT>已經計算過的估值<FONT
face="Times New Roman">)</FONT>。我可以把一個估值加上一個“索引”<FONT
face="Times New Roman">(hash
key)</FONT>保存在表中，這樣做的目的是制造一個“唯一的標識”，而執行過程是很快的。我對當前局面產生一個“索引”，然后看這個索引在表中是否已經有保存了。假如是有，就看表中的值是多少。表中的估值足夠深入因此我不需要再次計算了嗎？如果是這樣，那么我就只需把值從表中取出來，而不用又再來一次計算。這大大節省了時間。
<DT> 哈希表是一種非特殊的數據結構，因此很容易就可作為棋弈程序的其它用途。它對程序的執行速度提高是非常大的，我們認為哈希表是好程序的一個相當必要的功能。
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -