【正文】 (piece,startI,startJ,m,n) 。 for (int x = 0。 y++) { int ChessMan = ChessBoard[x][y]。 } if (isRedGo amp。 } if (isValidMove(x, y, x, y 1)) { 。 !isRed(ChessMan)) { continue。amp。 x++) { for (int y = 0。 } 系統(tǒng)的最終目的是要實現(xiàn)人機對戰(zhàn)，人機對戰(zhàn)的核心是使電腦具有人工智能。 } } else { 可否走棋 =false。i=maxI1。 break。 if(().equals(車 ))//車的走棋規(guī)則 { if(startI==endI) { int j=0。本系統(tǒng)通過對象棋規(guī)則的定義以及圖形化的棋子如何在棋盤中消失來實現(xiàn)人人對戰(zhàn)這一功能： public boolean movePieceRule(ChessPiece piece,int startI,int startJ,int endI,int endJ) { =piece。 point[2][10].setPiece(紅馬 1,this)。 紅車 棋子類別 (紅方顏色 )。 unitHeight=h。 addMouseListener(this)。 } } /*棋子的類別 */ public String 紅方顏色 =紅色 ,黑方顏色 =黑色 。c=39。i++) { (+i,i*unitWidth,unitHeight/2)。 (point[4][8].x,point[4][8].y,point[6][y 軸長 ].x,point[6][y 軸長 ].y)。 (point[i][y 軸長 4].x,point[i][y 軸長 4].y,point[i][y 軸長 ].x,point[i][y 軸長 ].y)。i=x 軸長 。 for(int j=1。 } public Color 獲取棋子顏色 () { return foreColor。 (2,2,width2,height2)。 ()。 addMouseMotionListener(board)。 ...... foreColor=fc。 String 顏色類別 =null。界面的設計是供用戶與電腦進行交互，無論是人機對戰(zhàn)還是制作、演示棋譜都是在界面中實現(xiàn)的。對于當前局面，查詢數(shù)據(jù)庫的函數(shù)使用庫中的隨機數(shù)組計算出其哈希值，然后在庫中察看是否有此值所代表的局面。雖然二者查詢的形 式完全相同，但是存儲的內(nèi)容卻大不相同。不管紅還是黑，第一步時總是以 1 表示，以后黑方每走一步數(shù)字就加 1。而且，這 個標記是且只是在該局面緊接的上一步棋是某方剛走兵推進兩格的情況下出現(xiàn) 。 上面的那 P1PlP1PlP，就是表示黑方在第 7 橫線上排有 5 只兵 ； 后面那兩個數(shù)字 9， 就是表示從第 6 到第 5 橫線，雙方一個棋子都不在，是空格 ； 9 個反斜杠 \“ ∧ ” 將第一區(qū)域分成 8 段，因為棋盤有 10 條橫線 ； 其它的照著圖完全可以類推。所有這一切用一行文字符號表示就行了而且非常容易讀。一份標準的局面記號對需要大量交換共享局面數(shù)據(jù)的國際象棋程序設計等工作具有尤其重要的作用。 FEN 是建立在 19世紀由報社記者 S 實現(xiàn)開局庫的主要方法 實現(xiàn)開局 庫的方法一般有兩種：一種是用 FEN 的形式表示的開局庫；另一種是哈希值表示的開局庫。無庸多說，這對于程序節(jié)省思考時間有重大幫助。“好炮位”，即炮要占住子力疏密適中的要點，封鎖對方進攻路線，配合其他子力展開進攻。 另外，空著搜索 (Null Move)也是搜索算法中一種很有效的搜索策略，它的思想是放棄本方的走棋權利，讓對方連續(xù)走棋，如果得到的分數(shù)還大于原來的 β值，就可以簡單地返回 β值，在此分枝下的搜索意義不大，免于搜索。 殺手啟發(fā) (Killer Heuristic)是基于這樣的思想 :在搜索過程中，有許多走法一經(jīng)搜索就引發(fā)了剪枝，且這些走法通常是同一個走法，這樣，為每一層記錄引發(fā)剪枝最多的走法即殺手走法，當下一次搜索到同樣的深度時，如果殺手走法是該局的一個合法走法，就優(yōu)先搜索殺手走法。圍繞著法排序，己經(jīng)出現(xiàn)了許多優(yōu)秀的搜索算法與舉措，例如歷史啟發(fā)，殺手啟發(fā)，置換表等等。 高級搜索算法 極大極小值搜索是所有搜索算法的基礎，而 αβ剪枝搜索是所有剪枝算法的基礎。同理搜索右路分枝，進行剪枝操作。圖 中通過剪枝，最后得到如粗箭頭所示的最佳路徑片斷。 圖 和圖 給 出兩個 剪枝示意圖 ： MAX MIN MAX 圖 α剪枝示意圖 MIN MAX MIN 圖 β剪枝示意圖 在圖 所示的極大極小樹片段中，按照極大極小值搜索規(guī)則，從左路分枝的葉節(jié)點倒推得到第一層 MAX 節(jié)點的值為 5，可表示此時的著法最佳值，記為 α，顯然此 α值可作為 MAX 方著法指標的下界。 上述極 大極小值搜索過程中，遍歷了整個的博弈樹，這樣的搜索算法效率低，搜 索量非常大，如果要減少搜索量，又可能影響搜索效果。在這一方走棋的時候，選擇價值最大的子節(jié)點走法，即實行“ Max 搜索”，另一方走棋則選擇價值最小的子 節(jié)點走法，即實行“ Min 搜索”，這就是象棋博弈中的一個極大極小過程。 基本搜索算法 極大極小值 方法 (Minimax Algorithm)是解決博弈樹問題的基本方法。 (2)選擇性搜索 (Selective Search)，即裁剪搜索，這種搜索略去對一些著法的搜索， 冒著有可能 漏掉最佳走法的風險，而換來局部更深的搜索深度。遺傳算法可以同時維護多組較好的參數(shù)，通過向其中 添加一組新參數(shù)，通常是將從幾組老參數(shù)中選出的值組合在一起作微小的變化，然后同幾組老的參數(shù)比較孰優(yōu)孰劣，將最壞的一組去 除。在優(yōu)化參數(shù)時，類似于爬山法，模擬退火法也是對權重做改變來提高成績，如果所做的改變沒有提高成績 ，也會根據(jù)一個隨機的幾率采納這個改變，試圖跳出局部最優(yōu)。但是人類的知識畢竟具有一定的局限性，評估函數(shù)也不能包含所有情況，參數(shù)之間往往又互相聯(lián)系，調(diào)整某個參數(shù)可能解決了某類問題，但又可能給其它問題的解決帶來麻煩，在這種情況下很難實現(xiàn)全局下的最優(yōu)組合。 (3)交手法 (Hand Tweaking) 這是調(diào)整評估函數(shù)時非常常用的方法，通過讓程序?qū)?，來找到它的?yōu)勢和弱點，猜測哪些參數(shù)會讓程序更好，然后挑選新的參數(shù)。 (2)約束法 (Deduce Constraints) 通過考慮希望電腦作出怎樣的判斷，就可以確定一些參數(shù)。將這些經(jīng)驗放進評估函數(shù)中反復對弈，然后不斷修正參數(shù)，找出一組性能較高的參數(shù)。可以輕易的更換估值函數(shù)，只改動極少的代碼 ； 你也可以隨意使用任何估值方法來評估整個棋盤，最終給出估值，但這種方法的速度較慢 。在同等速度之下，知識量越大性能越高。 估值的速度與博弈性能 開發(fā)人員可以向估值函數(shù)加入大量的棋類知識，使之對于局面的評估更為精確。而如果周圍有己方棋子對其進行了保護，也就是說，對方在理智的情況下不會去吃棋子 1，那么棋子 l 沒有受到威脅，價值不變。如果某一位置同時落在雙方的合法走步上，可以根據(jù)雙方控制該位置的棋子數(shù)量及棋子價值來決定孰優(yōu)孰劣。 可以用下面的表達式求某一方棋子靈活性 : Mobility=Sum(MoveNum*MoveValue)； 其中， MoveNum 是 某種棋子的合法走法數(shù)量， MoveValue 是該種棋子每一走法的價值， sum 是對所有棋子的靈活性價值求和。 棋子靈活性描述的是棋子的活動范圍，即棋子向各處調(diào)動的可能性大小。 可以用下面的表達式求某一方的棋子固定值 SideValue=sum(PieceNum*PieceValue)；其中 PieceNum 是某種棋子的數(shù)量， PieceValue 是該種棋子的價值， sum 是對各種棋子的總價值求和。 棋子固定價值指的是對棋盤中的每一個棋子，根據(jù)它的重要性和走法的豐富程度賦予其一個特定的值。目前在計算機象棋博弈中常用的估值方法主要采用靜態(tài)估值方法。把車的列號和該行棋子的布爾分布作為輸入，把吃子落址和非吃子落址作為輸出，將輸入和輸出的關系寫入一個預置表中，在使用時通過查表，就可以快速構成可行著法，而且可以區(qū)分開吃子著法和非吃子著法。中國象棋每種棋子的行棋規(guī)則不同，生成每種棋子的著法和整個棋盤棋子的分布密切相關，如果建立每種棋子最大可能著法的小型數(shù)據(jù)庫，用查詢?nèi)〈鷱碗s的判斷，那么也可以在很大 程度上加快著法生成的速度。 對馬的著法生成使用模板匹配法時，只要寫出符合馬行棋規(guī)則的模板匹配 數(shù)組和馬腿的模板匹配數(shù)組，在生成著法時通過查找這兩個數(shù)組就可以實現(xiàn)。 通過良好的數(shù)據(jù)結構 和走法預生成，可以顯著地提高生成的速度。 (4) 還可以非常方便的判斷棋子是否在己方。如圖 （紅色格子都被標上“出界”的標志，目標格在這些格子上就說明著法無效）： 圖 擴展的棋盤 這種棋盤的更大的好處是： (1) 它可以防止棋子走出棋盤邊界。 同樣，添加一個棋子時 也需要兩個操作。這就是“棋盤當然也可以把棋盤看作一維的，每個元素保存直接的位置信息。 中國象棋的棋盤表示中最典型的是用一個 10 9 的二維字節(jié) (byte)數(shù)組，數(shù)組中每個元素代表棋盤上的一個交點，其值表明這個交點上放置的是一個什么棋子或是沒有棋子 從棋子的角 度考慮，如果把棋盤看成是一個平面坐標系，可以知道每一個棋子的位置信息 :小于 10 的橫坐標和小于 11 的縱坐標 。 2 系統(tǒng) 的分析和設計 數(shù)據(jù)結構 （ Data structure） 數(shù)據(jù)結構是一個程序的骨架，選擇一種好的數(shù)據(jù)結構可以使程序的運行效率大大提 高。第四 部分實現(xiàn) 了博弈樹的 αβ剪枝算法并簡要介紹各種搜索 策略 。 第二章 第一部分 首先介紹中國象棋 程序的一些基本數(shù)據(jù)結構，著重研究了 擴展 的棋盤 —— 棋子聯(lián)系數(shù)組棋盤 ； 在此基礎上實現(xiàn)所有棋子的 走法預生成數(shù)組，以提高搜索過程中走法產(chǎn)生的效率。 搜索技術 博弈樹搜索技術它很大程度上獨立于具體的計算機博弈程序。然后根據(jù)棋盤表示獲得所有棋子的走法預生成數(shù)組。開局庫一般是采用 zobrist 哈希技術加以實現(xiàn)。目前主要是使用α β 剪枝算法加上迭代深化、置換表、歷史啟發(fā)等策略的 綜合應用。再好的硬件也無法實現(xiàn)“象棋不敗算法”。 評估函數(shù) (Evaluation Function) 評估函數(shù)就是對博弈過程中實際局面的好壞做出判斷或打分，它影響著博弈 局 發(fā)展的趨勢。 著法生成 (Move Generation) 著法生成就是找到某個局面所有合法的走法。雖然如此，但中國象棋的人機博弈的研究比國際象棋還是晚了幾十年，并且在搜索算法等方面的研究還與國際象棋相距甚遠。而且涉足這個領域比較早的是臺灣的一些專家學者。 1982 年廖嘉成發(fā)表的《利用計算機象棋的 實 驗》 就進了一步，包括開局、中局、殘局。在這個時候計算機國際象棋取得重大突 破， 1983 年美國貝爾公司的電腦參加美國人類比賽，取得了不錯的成績，被授予大師稱號。因此對于中國象棋人機博弈問題的研究意義重大。從 1980 開始，電腦博弈便開始逐漸大規(guī)模地向人類智能發(fā)起了挑戰(zhàn)，到了 1997年， IBM 超級電腦 Deeper Blue 擊敗了當時的國際象棋冠軍卡斯帕羅夫，成為了人工智能挑戰(zhàn)人類智能發(fā)展的一個重要里程碑。人人對戰(zhàn)規(guī)則明確，包含了中國象棋所有的著法；人機對戰(zhàn)中電腦棋力分為 簡單、中等、困難三個等級，方便了不同水平人群的選擇；制作和播放棋譜模塊容易操作，方便學習；挑戰(zhàn)英雄榜則為象棋游戲增加了樂趣。 智能中國象棋系統(tǒng)的設計與實現(xiàn)