殘局庫是經(jīng)特別算法產(chǎn)生的特定格式的、儲存各限定棋子數(shù)目的殘局之所有局面及其估值的數(shù)據(jù)庫文件集合。概述地說，殘局?jǐn)?shù)據(jù)庫是儲存了殘局局面并經(jīng)回溯分析計算過的數(shù)據(jù)庫文件，它使用在棋弈程序上，當(dāng)進(jìn)入殘局時，只要適合使用的殘局?jǐn)?shù)據(jù)庫文件存在，程序?qū)⒆叩梅浅Ｍ昝馈?多數(shù)棋弈引擎并不一定要到達(dá)殘局庫所涵蓋的局面時才使用殘局庫。例如，在到達(dá)如此局面之前幾步，引擎計算（但還沒走棋）一系列交換之后直接進(jìn)入殘局庫里存有的局面。引擎于是搜索探查殘局庫并取得那個設(shè)想局面的結(jié)果。如此當(dāng)然提高了棋力。

在殘局庫的開發(fā)方面，Ken Thompson仍然是先導(dǎo)者。80年代期間，他開始制作4子和5子的殘局庫。一個典型的5子殘局如：王雙象對王單馬，就包含有121,000,000種不同的局面。如果再加一個兵，那么局面數(shù)會增加到335,000,000。為此，Thompson專門編寫了程序，用于生成所有可能的局面并計算出每一個強(qiáng)制性的變化。然后他又通過某種方式將計算數(shù)據(jù)壓縮，使得一張標(biāo)準(zhǔn)的CD-ROM上可以存放20個不同的殘局。

殘局庫格式是多種多樣的，包括肯·托普森式(Ken Thompson)、史蒂文·愛德華茲式(Steven J. Edwards)、歐根尼·納利莫夫式(Eugene Nalimov)以及Chessmaster9000專用的EDGB殘局庫格式。 　不過總的來說它們劃分為兩種殘局庫類型：將殺步數(shù)(DTM)類型和變換步數(shù)(DTC)類型。粗略地以非專業(yè)語言來說，彼此之間區(qū)別如下： 　將殺步數(shù)(DTM)類型：即Distance to mate，這種類型的庫為每一個局面儲存最短的將殺可能(以層，即ply來計算，一層相當(dāng)于半個回合)。例如Nalimov殘局庫。 　變換步數(shù)(DTC)類型：即Distance to conversion，這種類型的庫儲存每一個局面及其一個“轉(zhuǎn)換”之間的最短層數(shù)。所謂一個轉(zhuǎn)換，指或者是兵升變，或者某子被吃去，或者出現(xiàn)將殺。例如Thompson殘局庫。 　另外，無論是DTM還是DTC類型的殘局庫，都不能識別50回合自然限著規(guī)則。為了克服它們的缺點(diǎn)，已經(jīng)提出了DTZ和DTR另外兩種類型。但至今只停留在理論上。 　說到具體每種格式的區(qū)別，還不能簡單就說得清楚的。Crafty的作者于2000年10月在新聞組作過如下解釋： 　“Edwards式：屬于將殺步數(shù)(DTM)類型。Edwards式的主要問題是這種殘局庫體積比其它的龐大。 　“Nalimov式：也屬于將殺步數(shù)(DTM)類型，但Nalimov式的殘局庫文件是壓縮的，也可以以壓縮形式使用而無不利之處。對于擁有全部3、4、5子殘局的殘局庫，別的格式其文件總數(shù)大小超過30G，而使用這種格式的大約只有7.5G。 　“Thompson式：屬于變換步數(shù)(DTC)類型(每當(dāng)發(fā)生吃子，殘局的‘級數(shù)’都變小)。這種格式難以以壓縮形式使用，相對于Nalimov式，它提供的信息也不相同……比如，它告訴你一些信息，卻沒有區(qū)分是負(fù)還是和，而Nalimov式對此則有區(qū)分。 　“Nalimov式是最佳選擇。幾乎每個引擎都支持它……” 　當(dāng)然，他沒有提及僅是Chessmaster9000專用的EDGB格式殘局庫，因?yàn)镋DGB是2002年8月才發(fā)布的。Nalimov式仍然是最流行的在用殘局庫格式，因此我想再多談一點(diǎn)這種格式。 　Nalimov式幾近“完美”，因?yàn)樗殉赃^路兵也考慮進(jìn)去了。但是沒把王車易位也考慮進(jìn)去。只不過，大概只有排局迷才會對此計較。 　總的來說，現(xiàn)代幾乎所有的國際象棋程序包括大多數(shù)Winboard引擎使用Nalimov式殘局庫，一部分原因是它們不設(shè)版權(quán)，一部分原因它們更高效。現(xiàn)在Nalimov式殘局庫已經(jīng)出了部分6子殘局庫。Nalimov式殘局庫有兩種形式，壓縮的和非壓縮的，壓縮的以“emd”為文件后綴。 　多數(shù)現(xiàn)代棋弈程序能解壓使用壓縮的殘局庫，例如Crafty從16.5版本后就支持壓縮的Nalimov式殘局庫。我注意到有個Winboard引擎Esc只能用非壓縮的。 　殘局庫還有其它一些格式，但比較少見。比較著名的，商業(yè)性高級棋弈軟件Nimzo8使用它的Nimzo殘局庫，這種殘局庫放入到內(nèi)存中使用，因此讀取比較快。一直沒有公開發(fā)表但棋力不俗的Ferret也使用它的專用殘局庫。我文章余下部分，除非特別說明，殘局庫都是指Nalimov式。

殘局庫是通過特定算法生成的滿足某一子力條件的全部局面的勝負(fù)和判定信息，一般也包括在區(qū)分勝負(fù)時距離將死或吃子最近的步數(shù)的信息。

原理：后退式算法。以炮兵單士象對士象全為例說明如何生成。以下的文字只闡述殘局庫算法的最一般的原理和思想，不能保證細(xì)節(jié)上與現(xiàn)存的各殘局庫計算程序的代碼完全吻合。
1 將全部的炮兵單士象（紅）對士象全（黑）的局面以及可能由炮兵士象全對士象全的局面通過吃子得到的局面編號，區(qū)分紅先黑先。
2 標(biāo)識出以上局面中，黑方被將死或者困斃的局面。
3 選擇出輪紅走，可以形成2中局面的局面，稱為紅一步勝局面。
4 從輪黑走的余下的（指不包含2中局面）局面中選擇出無論走哪一步下一步均會進(jìn)入紅一步勝局面的局面，稱為黑兩步負(fù)的局面。
5 從輪紅走的余下的局面（指不包含3）中選擇出能夠保證下一步進(jìn)入黑兩步負(fù)的局面，稱為紅三步勝局面。
6 從輪黑走的余下的局面中（指不包含2、4)選擇出無論走哪一步下一步均會進(jìn)入紅三步勝的局面，稱為黑四步負(fù)局面。
.
2k+3 從輪紅走的余下的局面中選擇出能夠保證下一步進(jìn)入黑2k步負(fù)的局面，稱為紅2k+1步勝局面。
2k+4 從輪黑走的余下的局面中選擇出無論走哪一步下一步均會進(jìn)入紅2k+1步勝的局面，稱為黑2k+2步負(fù)局面。
如此下去，由于總的局面數(shù)有限，一定會出現(xiàn)某一步，以上的步驟不再生成新的局面。那么以上的全部局面則是全部的紅先必勝，黑先必敗的局面。其余的局面均為和棋。

實(shí)際上，由于存在吃子關(guān)系，大多數(shù)殘局庫一般都是由較少子力往上生成的而不是直接按照以上的步驟一次性生成可能存在若干次吃子的殘局庫。我們一般首先算子力較少時的殘局庫，然后往上增加子力。在生成子力較多的殘局庫時可以利用子數(shù)較少的殘局庫。如生成炮兵士象對士象全的殘局庫時，首先需要選出炮兵士象及士象全都在盤面上時的將死及困斃的局面，以及可能通過一次吃子進(jìn)入的必勝必敗局面，即由炮兵士象對士象全局面，紅通過一次吃子，進(jìn)入的炮兵士象對單缺士等的黑必敗的局面（已經(jīng)算好并儲存在相應(yīng)的殘局庫），或者黑無法避免通過一次吃子，形成炮或者兵士象對士象全的紅必勝的局面（已經(jīng)算好并儲存在相應(yīng)的殘局庫）。然后運(yùn)用上面所述的倒推的算法將全部的必勝必敗的局面算出。顯然，這里面直接算出的步子是局面轉(zhuǎn)化的步子，而不是直接距離將死的步驟。這樣的計算較為經(jīng)濟(jì)節(jié)省。但是缺點(diǎn)也很明顯，無法直接說出某個紅（或黑）必勝的局面距離將死的步數(shù)，只能說出距離吃子最近的步數(shù)。有時候二者還是有區(qū)別的。

另外，中國象棋存在一個復(fù)雜的因素，即禁止長將長捉等等循環(huán)的攻擊性著法。以上的殘局庫算法不能考慮到這一點(diǎn)，必須進(jìn)行修正。對于亞洲棋規(guī)來講相對還比較簡單，先按照以上的步驟生成允許長將長捉的殘局庫。然后標(biāo)識出紅或者黑可以進(jìn)行長將的局面。從中選取變招則進(jìn)入必敗的局面。然后向后遞推，直到不能生成新的局面。將以上的局面標(biāo)記成order=1的紅勝或負(fù)的局面。然后從長將的局面中選取出，變招則進(jìn)入order=1的局面的的局面，繼續(xù)后推，直到封閉，生成order=2的局面。如此向后，直到窮盡全部的長將長捉的局面。那么余下的全部局面就是亞規(guī)的真正的和棋局面。當(dāng)然，這樣的算法導(dǎo)致步數(shù)的計算十分復(fù)雜，是殘局庫有時候不能正確給出距離吃子最近乃至距離將死最近的招法的根源。但是，關(guān)于勝負(fù)和的信息依然是絕對正確的。而中國棋規(guī)就過于復(fù)雜，目前基本不能在殘局庫層面實(shí)現(xiàn)。

殘局庫和棋軟的區(qū)別，為何殘局庫能夠計算出某些長達(dá)幾百步的勝局而棋軟不行。

通過殘局庫計算出長達(dá)幾百步的勝局，乃是中國象棋和國際象棋共有的情況。由于殘局庫算法的科學(xué)性，這些結(jié)論是不需要被質(zhì)疑的。但是有人會問，為強(qiáng)機(jī)強(qiáng)棋軟都很難在殘局局面算超過50步，殘局庫怎么可能在雙核機(jī)上算出200步的勝局？根源還是在算法的根本不同。殘局庫的計算量主要取決于局面總數(shù)，一般來說類似于炮兵士象全對士象全的殘局，局面總數(shù)即使是極度粗糙的包含大量冗余的估算，也就10^10數(shù)量級。而棋軟的計算主要是向后遍歷博弈樹，計算量主要取決于分支數(shù)和回合數(shù)。還是這個殘局，一個回合的變化數(shù)大致在150至200(炮兵方20左右，士象全方7-10）上下。那么要是窮舉計算僅僅10回合的全部變化就已經(jīng)在10^21量級，可以說是大大高于殘局庫的計算復(fù)雜度，即使是現(xiàn)有的棋軟都有非常有效的裁剪，基本上也很難支撐100步以上，更何況裁剪在這種情況下往往是有害的。這也是為什么強(qiáng)軟強(qiáng)機(jī)也不能算出數(shù)百回合的必勝，而殘局庫算法在弱機(jī)上就能算出來的原因。

現(xiàn)有殘局庫能夠算出哪些殘局，算不出哪些。

一般來說64G內(nèi)存能夠在可容忍的時間內(nèi)算出的殘局局面能夠復(fù)雜到車兵對馬炮雙士這樣的量級。這個殘局庫的大小已經(jīng)有4.6G。 像馬炮全對馬全這樣的殘局，乃至局面總數(shù)更多的，所需的內(nèi)存已經(jīng)達(dá)到3800多G，短期內(nèi)是不能被算出來的。大多數(shù)江湖殘局的主體局面都是目前不能被殘局庫解決的。如大征西的主體局面車炮兵對車炮相，要3800多G內(nèi)存，帶子入朝的主體局面車卒象對車雙兵士，需要2700G內(nèi)存。顯然它們在可預(yù)見的時間入殘局庫的可能性是零。

然而，殘局庫依然解決了不少靠人力難以解決的深度驚人的實(shí)用殘局。如炮高兵單士象必勝士象全就是個著名例子。只是由于亞規(guī)允許一將一捉等，導(dǎo)致不少有車殘局算出的和局存在著劣勢方實(shí)負(fù)的可能，但是算出的必勝是絕對正確的。

參考資料

https://tieba.baidu.com/p/3463112599?red_tag=1810576185
https://baike.baidu.com/item/%E6%AE%8B%E5%B1%80%E5%BA%93/8728859?fr=aladdin
http://www.zgxqds.com/blog/article.asp?id=24031

總結(jié)

以上是生活随笔為你收集整理的中国象棋残局库构建[抄]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。