【正文】 ...................................................................39 附錄 A： A INTRODUCTION ABOUT CHINESE CHESSA ..................................39 附錄 B：關于中國象棋的一些簡要介紹 .................................................................42 1 緒論 選題的背景和意義 在人類文明發(fā)展的初期，人們便開始進行棋類博弈的游戲了。人類對機器博弈的研究衍生了大量的研究成果，這些成果對更廣泛的領域產(chǎn)生了重要影響。中國象棋不僅是中國傳統(tǒng)智慧的體現(xiàn)，同時也具有著比國際象棋更高的復雜度，如何讓機器具有智能 ,與人進行對弈成了本課題研究的一個重要問題。 1981 年張耀騰發(fā)表的《人造智慧在電腦象棋上的應用》，他提出審局函數(shù)為 靜態(tài)子力值，棋子位置值，棋子靈活度值，威脅與保護等四項之和。 到了 90 年代，中國象棋計算機博弈的應用開始發(fā)展起來，人們研究出了各種博弈軟件。 表 11 著名中國象棋計算機博弈程序 程序 作者 地區(qū) 縱馬奔流 涂志堅 廣州中山大學 謝謝象棋大師 法國電腦公司 法國 ELP 鄭武堯、陳志呂 臺灣 SHIGA（象棋世家） 鄭明政、顏士凈 臺灣 SHCC（神乎棋技） SAI team 美國 Cyclone（象棋旋風） 陳朝陽 北京 CONTEMPLATION 千慮 陳志昌、許舜欽 臺灣 棋天大圣 王驕 東北大學 象棋奇兵 趙明陽 中國 每年也會有中國象棋計算機博弈的國際奧林匹克大賽，這其中有 2020 年的世界冠軍“縱馬奔流”， 2020 年的世界冠軍“謝謝象棋大師”， 2020 年的世界冠軍“象棋奇兵”，20 2020 年的世界冠軍“棋天大圣” ， 2020 年的世界冠軍“倚天”。中國象棋的棋盤表示還沒有形成統(tǒng)一的或者公認的哪種為最佳的數(shù)據(jù)格式。在一定程度上形成了程序的性能瓶頸。它與著法生成一樣十分耗費運算時間，如何加速評估函數(shù)的速度十分關鍵?！靶U力搜索”肯定是不可取的。實踐表明無論搜索引擎如何出色，在開局搜索過若干層后，得到的可能只 是一些 很笨拙 的開局。對弈過程機器自動調(diào)整評估函數(shù)參數(shù)的權 值 進行優(yōu)化，發(fā)現(xiàn)一些棋子之間潛在的聯(lián)系 :之二是采用模式識別，學習的過程是通過對博弈過程的識別統(tǒng)計，自行豐富模式庫中的內(nèi)容，以提高程序的博弈性能。 估值函數(shù) 如何快速有效的對一個局面進行評估需要從速度和知識的兩個角度進行考慮 :一般知識越多估值越準確，但速度也慢下來。如何把各種增強手段有機組合起來達到最優(yōu)，文章對基于迭代加深、置換表、歷史啟發(fā)的 Negascout 算法進行改進。第三部分 描述本系統(tǒng)的評價函數(shù)架構， 著重描述了靜態(tài)估值方法，分析了其不足，并提出了解決之道。 第三章 給出實驗環(huán)境和 程序?qū)崿F(xiàn) 。棋盤的數(shù)據(jù)表示直接影響到程序的時間及空間復雜度。而己被吃掉的棋子用坐標范圍以外的數(shù)表示。棋盤數(shù)組中由棋子的位置獲得棋子的類型可以在常數(shù)時間內(nèi)完成，但由棋 子的類型獲得棋子的位置需要遍歷；在棋子數(shù)組中由棋子的類型獲得棋子的位置可以在常數(shù)時間內(nèi)完成，但由棋子的位置獲得棋子的類型操作繁瑣。 (2) 隨時保持這兩個數(shù)組之間的聯(lián)系，棋子移動時必須同時更新這兩個數(shù)組。棋子聯(lián)系數(shù)組“最大的優(yōu)勢是：對于著法產(chǎn)生過程，可以逐一查找棋子數(shù)組，如果該子沒有被吃掉，就產(chǎn)生該子的所有合理著法，由于需要查找的棋子數(shù)組的數(shù)量 (每方只有 16 個棋子能走 )比棋盤格子的數(shù)量 (90 個格子 )少得多，因此聯(lián)系數(shù)組的速度要比單純的棋盤數(shù)組快很多。如果能在尋找棋子 和定位棋子上使用位運算代替加減乘除和取余，這將很大程度上提高運算速度。 (2) 對于是否在城池內(nèi)可以用 bool 型城池數(shù)組判斷，因為是否在城池內(nèi)的判斷會非常頻繁，直接用該數(shù)組會很高效。著法生成 是博弈程序中一個相當復雜而且耗費運算時間的方面 ，要生成所有著法只能用窮舉 。圖 給出了馬的匹配模板。同樣的，可以對象、將、士、卒使用模板匹配生成著法。 圖 即是以路向行向比特向量為索引的一個車的預置著法表的生成范例。從象棋的棋力上考慮，在搜索之外，局面估值是最重要的部分，因為對實際局面的評價的好壞，影響著今后局勢發(fā)展的趨勢。下面分別從這兩個方面及其關系介紹局面 評估 。根據(jù)經(jīng)驗，可以讓一個 車價值為 500，一個馬價值為 300，一個兵價值為 100 等等。而紅黑雙方的 SideValue 之差越大，紅方的優(yōu)勢也就越大。本方棋子可以走的點越多，說明本方棋子的靈活性越大。 一方 對棋盤控制的棋盤區(qū)域越多，那么他就越具有主動性。 在中國象棋博弈中，每個棋子都不是孤立存在的，他們之間構成了各種相互關系。如果某個紅馬落在黑炮的合法走步之內(nèi)，但此時輪到紅方走棋，應認為紅馬受到的威脅較輕。因此過于簡單的估值函數(shù)和過于復雜的估值函數(shù)同樣性能不佳。使用終點估值 (end—point envaluation)，意思是當葉子節(jié)點到達時，使用估值函數(shù)對一個局面進行評估。這種方法是利用人類的象棋經(jīng)驗知識來調(diào)整參數(shù)值，比如，從經(jīng)驗上可以知道，一個車的價值要比一個兵大，給車賦予比兵大的數(shù)值，馬炮則賦予位于其間的值 。這就意味著，對某個特定的模塊，例如兵的價值，可以硬性設一個值，其他值就可以表示成它們相當于多少個兵。這樣的條件越多，合適的權重組合就越少。 手工調(diào)整是象棋引擎調(diào)整估值參數(shù)的主要手段之一，把人類的知識和經(jīng)驗盡量準確客觀地“教授”給計算機，是提高棋力的普遍做法，雖然比較費時，但是很有效。這種方法很慢，并且受初始采樣值的限制，很容易陷入局部最優(yōu)，即評價可能很差，但是任何很小的改變都會使評價更差。模擬退火法比爬山法更慢， 是最終可能得到比較好的值。 博弈樹搜索技術 中國象棋博弈樹非常龐大，完全建立博弈樹是不可能的，唯一的解決方法就是讓博弈樹擴展到計算機運算可以接受的深度，然后對沒有分出勝負的葉子節(jié)點給出一個盡量準確的打 分，表示此局面下取得勝利的可能性，這個打分是由評估函數(shù)計算給出的，將搜索樹展開是著法生成的功能，而搜索引擎則是盡可能縮小樹的規(guī)模，避免一切冗余的計算，這也是計算機博弈中搜索引擎研究的重點。 (3)啟發(fā)式搜索 (Heuristic search)利用象棋領域的知識 (啟發(fā)信息 )設計搜索算法，著重對走法排序，以簡化和加快搜索過程。 極大極小值算法的原則是 :博弈雙方所要達到的目的相反，一方要尋找的利益是另一 方失去 的利益，博弈的一方總是希望下一步是子節(jié)點中取值最大者，而另一方 希望下一步是子節(jié)點中取值最小者。圖 表示了一個極大極小搜索過程，粗箭頭為最佳路徑片段。這個技術叫αβ剪枝搜索。同理搜索右路分枝，也可以進行剪枝操作。顯然此 β值可作為 MIN 方可能實現(xiàn)著法指標的上界。圖 中通過剪枝，最后得到如粗箭頭所示的最佳路徑片斷。 在 αβ剪枝搜索中，剪枝效率幾乎完全取決于節(jié)點的排列順序，如何調(diào)整待展開的走法的順序，是提高搜索效率的關鍵。根據(jù)經(jīng)驗，一些以前經(jīng)過搜索認為最佳的走法，其后續(xù)走法仍然有很大可能成為最優(yōu)的走法。 置換表 (TransposilionTable)是用一張表把搜索過的信息記錄下來，在后續(xù)的搜索中，察看記錄在表中的這些信息，如 果將要搜索的某個節(jié)點已經(jīng)有記錄，就直接利用記錄下來的結果引入到當前的搜索中，以減少搜索。 開局庫設計 中國象棋 的開局變化極多，每一種走法都能產(chǎn)生出一種新的變化，單就中炮對屏風馬、中炮對反宮馬、中炮對左三步虎等數(shù)十種變化，其格個開局又都有自身的變化，這些開局都遵循開局的規(guī)律 :“明車”，即車路要通 。所以中國象棋開局階段是整個對弈過程中變化最多的階段，開局的好壞對之后的中、殘局意義重大。但另一方面，如果開局庫本身不好或部分不好，程序也可能被盲目引到劣勢的局面甚至很快失利。下面我們來看看什么是 fen 串。福斯夫設計的記錄局面的標準基礎上的。單純的 FEN 記錄文件后綴應該是“ .fen”，比如 :，在中國象棋開局庫的 fen 串形式的開局庫文件后綴為 .DAT。規(guī)則是從第 10 橫線開始順序數(shù)到第 1橫線 (紅方在下，從上數(shù)到下 )，從 a 線開始順次數(shù)到 h 線 ； 紅方棋子以大寫字母 \“ RNBAKABNR\” 功表示，黑方棋子以小寫 \“ rnbakabnr\” 表示，這是英文表示法，每個字母代表的意義與常規(guī)規(guī)定相同。小寫 \“ w\”表示紅方走 棋；小寫 \“ b\”表示黑方走棋；因為起初局面是紅先，所以上面就是 \“ w\” . (5) 吃過路兵目標格（ En Passant Target Square） 如果沒有，就用 \“ \”表示。這個是為了適應 50 步和棋規(guī) 則而定。 這種方法是使用置換表來統(tǒng)計開局 庫中的一些走法的優(yōu)劣。它只存放某 局面的一個哈希值以及對應的走法。 (b)查詢后續(xù)局面 這種開局庫查詢是與搜索結合在一起的，并不是查詢當前局面是否在開局庫中，而是展開根節(jié)點的所有 走法，也就是當前局面下所有可能走法 。首先定義一個棋子類（ ChessPiece），來獲取棋子的顏色以及類別： public class ChessPiece extends JLabel { String name。 int width,height。 setSize(width,height)。 } public void paint(Graphics g) { (foreColor)。 (name,7,height8)。 } public int getHeight() { return height。 } public String 棋子類別 () { return 顏色類別 。j++) { (point[1][j].x,point[1][j].y,point[x 軸長 ][j].x,point[x 軸長 ][j].y)。amp。 } } (point[4][1].x,point[4][1].y,point[6][3].x,point[6][3].y)。 for(int i=1。 for(char c=39。c++) { (+c,unitWidth/4,j*unitHeight)。 ChessPiece 黑車 1,黑車 2,黑馬 1,黑馬 2,黑將 ,黑士 1,黑士 2, 黑卒 1,黑卒 2,黑卒 3,黑卒 4,黑卒 5,黑象 1,黑象 2,黑炮 1,黑炮 2。 Color bc=getBackground()。 y 軸長 =c。 紅車 棋子類別 (紅方顏色 )。 對弈功能的實現(xiàn) 對弈是用戶對象棋游戲最基本的需求，本系統(tǒng)的對弈功能包括人人對戰(zhàn)和人機對戰(zhàn)。 int maxI=(startI,endI)。j=maxJ1。 } } else if(startJ==endJ) { int i=0。 break。 if( ().equals(紅方顏色 )) { } if( ().equals(黑方顏色 )) { }