【正文】 amp。 x 9。 } } if(i==maxI) { 可否走棋 =true。j++) { if(point[startI][j].isPiece()) { 可否走棋 =false。人人對戰(zhàn)功能的實現(xiàn)其實就是一系列象棋規(guī)則的集中體現(xiàn)，譬如“馬走日”、“相走田”、“炮打隔山”等。 ...... 紅車 1=new ChessPiece(車 ,bc,w4,h4,this)。 通過以上兩段本系統(tǒng)就實現(xiàn)了棋盤和棋子的定義，然后通過下面的方法實現(xiàn)棋子在棋盤上的表示： public ChessBoard(int w,int h,int r,int c) { setLayout(null)。A39。 (point[6][1].x,point[6][1].y,point[4][3].x,point[4][3].y)。 } for(int i=1。 } public String getName() { return name。 (2,2,width2,height2)。 public ChessPiece(String name,Color fc,Color bc,int width,int height,ChessBoard board) { =name。 3 系統(tǒng)的實現(xiàn) 系統(tǒng)的整體規(guī)劃 整個智能象棋系統(tǒng)將要實現(xiàn)的主要功能是：人人對戰(zhàn)、人機對戰(zhàn)、制作棋譜、演示棋譜、挑戰(zhàn)英雄榜等，而其中的各個功能又分為幾個小功能模塊，該系統(tǒng)的功能結(jié)構(gòu)圖如圖 所示： 圖 功能結(jié)構(gòu)圖 象棋界面的實現(xiàn) 本系統(tǒng)要實現(xiàn)一個象棋游戲系統(tǒng)，界面是必不可少的 部分。與搜索引擎中的置換表類似，開局庫也是用表示局面的哈希值除以 開局庫的大小作為索引，而表示局面的哈希值作為校驗。如果有，就用具體完成吃過路兵的那個格子坐標(biāo) 表示，顯然對于白兵被吃只可能在第 3 橫線，對于黑兵被吃只可能在第 6 橫線。 FEN 描述了 :棋子位置、輪走棋方、易位可行性、吃過路兵目標(biāo)格、半步計數(shù)、以及總回合數(shù)。 (1) FEN FEN 就是“福斯夫 愛德華茲記號法”（ ForsythEdwards Notation）， 這是一種使用ASCII 碼字符描述國際象棋局面的標(biāo)準(zhǔn) 。 開局庫的作用 象人們記住開局招數(shù)一樣，博弈程序使用一個數(shù)據(jù)庫，里面儲存了開局譜著和局面，于是當(dāng)對局（開局）中的棋步在開局庫中能找到時，它就可以立即取出來走，不用計算。置換表不同于歷史啟發(fā)表和殺手表，不必在每次搜索之前都清空，而是一直維持這些數(shù)據(jù)，作為以后搜索的信息。在搜索的過程中，往往有一些啟發(fā)性的信息可以利用，如果利用這些信息在相似的局面下對走法進(jìn)行優(yōu)化排序，或者對相同的局面不再搜索，而直接返回以前搜索的結(jié)果，都會對搜索產(chǎn)生明顯的加速作用。在搜索中路分枝時，因為第二層著法的選擇是取第三層節(jié)點的最大值，即取 MAX(5， 12，“○” )，而無論“○”中為何值，都不會比 11 小 (至少為 12)，故可以將“ ○ ”表示的節(jié)點及其后繼節(jié)點剪掉，不再考慮此節(jié)點的延伸。 它 是一種基于 αβ搜索的深度優(yōu)先 搜索，是所有剪枝算法的基礎(chǔ)， 它是根據(jù)極大極小搜索規(guī)則進(jìn)行的。在象棋博弈中，極大極小值算法體現(xiàn)在始終站在博弈一方的立場上給棋局估值，有利于這一方的棋局給予一個較高的價值分?jǐn)?shù)，不利于這一方(有利于另一方 )的給予一個較低的價值分?jǐn)?shù)，雙方優(yōu)劣不明顯的局面給予一個中間 值分 數(shù)。 根據(jù)搜索策略，目前應(yīng)用于計算機博弈的搜索算法一般可分為三類 ： (l)窮盡搜索 (Exhaustive Search)，這種搜索是沒有拋棄任何可能成為最佳路徑的搜索，不存在 風(fēng)險，得到的最佳走法肯定是在現(xiàn)有評估函數(shù)下應(yīng)該得 到的，例如極大極 小值 搜索、α β 剪枝搜索及其變種等。 (2)模擬退火 (Simulated Annealing) 模擬退火是一種基于蒙特卡羅 (Monte Carlo)算法的啟發(fā)式隨機搜索算法，它沒有蒙特卡羅算法多次尋優(yōu)的過程，也不像爬山法那 樣依賴初值。在開始設(shè)定權(quán)重值的時候，這個方法通常可以得到合適的值，但是在后面仍然需要做一些調(diào)整。馬和炮的地位相當(dāng)，給予它們相當(dāng)?shù)臄?shù)值，以避免盲目換子 ；如果對弈中使用了一些優(yōu)秀的戰(zhàn)術(shù)配合，那么就給予一定數(shù)值的獎勵，等等。在同等的知識含量下，速度越快，性能越高。如棋子 1 下一步將被吃掉，則應(yīng)該給一個負(fù)的附加值。例如車在縱橫線上遇到障礙物、馬被周圍棋子絆腳等，都降低了靈活性，也降低了威力的發(fā)揮，靈活性的計算是把棋子在棋盤上所能夠移動到達(dá)的位置數(shù)作為靈活性計算，給予評分。在中國象棋的對弈中，由于一般以將死對方的將 (帥 )作為結(jié)束，因此，通常賦值的規(guī)則是為將 (帥 )賦予一個遠(yuǎn)大于其他棋子的子力之和的值。這一過程對具體的棋類知識依賴程度很深，但是仍有一般性的規(guī)律可循。 預(yù)置表法 它是把所有可能的著法預(yù)先存儲起來，在生成著法時，用查表取代計算。 中國象棋大約每一步可以有 45 個著法。所以，人們把“棋盤 —— 棋子聯(lián)系數(shù)組“進(jìn)行擴(kuò)展：把棋盤做成 16 16 的大小，這樣得到行號可以用 16 除，得到列號可以對 16 取余（和 15 進(jìn)行運算），這比除以 10 和對 9 取余操作要快得多。在棋盤上刪除一個棋子，需要做兩個操作 (分別修改棋盤數(shù)組和棋子數(shù)組 )。這樣棋盤信息就被裝入這 32 個字節(jié)中。 第 四章 是全文的總結(jié)及展望 。 論文結(jié)構(gòu) 第一章闡述了選題背景，課題的國內(nèi)外研究現(xiàn)狀及課題的主要工作和文章的章節(jié)安排。 本文 的主要工作 本 文 的主要工作是將博弈策略應(yīng)用到中國象棋程序的設(shè)計與實現(xiàn)上，建立一個完整的中國象棋計算機博弈系統(tǒng)，研究工作主要集中在以下幾個方面 ： 棋盤表示與走法生成 從操作速度 (性能 )以及使用方便與否考慮，本象棋博弈系統(tǒng)從帶位行位列信息的擴(kuò)展棋盤 —— 棋子聯(lián)系數(shù)組著手進(jìn)行研究。如何有選擇地搜索，既瞄準(zhǔn)最有希望的方向局部加深，又不遺漏其它存在最優(yōu)解的可 能。當(dāng)前為了提高著法生 成的效率 通常采用以空間換時間的方法 :與先求出棋子的在某位置的所有走法。 這些都體現(xiàn)了中國象棋的人機博弈的研究的受關(guān)注程度 。但該文主要 以殘局 做實驗，缺乏完整對局的考慮。人工智能的先驅(qū)們曾認(rèn)真的表明： 如果能掌握下棋的本質(zhì)，也許就掌握了人類智能行為的核心；那些能夠存在于下棋活動中的重大原則，或許就存在于其它任何需要人類智能的活動中。 該系統(tǒng)包括人人對戰(zhàn)、人機對戰(zhàn)、制作棋譜、播放棋譜以及挑戰(zhàn)英雄榜等功能模塊 。人人對戰(zhàn)規(guī)則明確，包含了中國象棋所有的著法；人機對戰(zhàn)中電腦棋力分為簡單、中等、困難三個等級，方便了不同水平人群的選擇；制作和播放棋譜模塊容易操作，方便學(xué)習(xí)；挑戰(zhàn)英雄榜則為象棋游戲增加了樂趣。因此對于中國象棋人機博弈問題的研究意義重大。 1982 年廖嘉成發(fā)表的《利用計算機象棋的 實驗》 就進(jìn)了一步，包括開局、中局、殘局。雖然如此，但中國象棋的人機博弈的研究比國際象棋還是晚了幾十年， 并且在搜索算法等方面的研究還與國際象棋相距甚遠(yuǎn)。 評估函數(shù) (Evaluation Function) 評估函數(shù)就是對博弈過程中實際局面的好壞做出判斷或打分，它影響著博弈 局 發(fā)展的趨勢。目前主要是使用α β 剪枝算法加上迭代深化、置換表、歷史啟發(fā)等策略的 綜合應(yīng)用。然后根據(jù)棋盤表示獲得所有棋子的走法預(yù)生成數(shù)組。 第二章 第一部分 首 先介紹中國象棋 程序的一些基本數(shù)據(jù)結(jié)構(gòu)，著重研究了 擴(kuò)展 的棋盤 —— 棋子聯(lián)系數(shù)組棋盤 ； 在此基礎(chǔ)上實現(xiàn)所有棋子的走法預(yù)生成數(shù)組，以提高搜索過程中走法產(chǎn)生的效率。 2 系統(tǒng) 的分析和設(shè)計 數(shù)據(jù)結(jié)構(gòu) （ Data structure） 數(shù)據(jù)結(jié)構(gòu)是一個程序的骨架，選擇一種好的數(shù)據(jù)結(jié)構(gòu)可以使程序的運行效率大大提 高。當(dāng)然也可以把棋盤看作一維的，每個元素保存直接的位置信息。同樣，添加一個棋子時也需要兩個操作。如圖 （紅色格子都被標(biāo)上“出界”的標(biāo)志，目標(biāo)格在這些格子上就說明著法無效）： 圖 擴(kuò)展的棋盤 這種棋盤的更大的好處是： (1) 它可以防止棋子走出棋盤邊界。 通過良好的數(shù)據(jù)結(jié)構(gòu)和走法預(yù)生成，可以顯著地提高生成的速度。中國象棋每種棋子的行棋規(guī)則不同，生成每種棋子的著法和整個棋盤棋子的分布密切相關(guān)，如果建立每種棋子最大可能著法的小型數(shù)據(jù)庫，用查詢?nèi)〈鷱?fù)雜的判斷，那 么也可以在很大 程度上加快著法生成的速度。目前在計算機象棋博弈中常用的估值方法主要采用靜態(tài)估值方法。 可以用下面的表達(dá)式求某一方的棋子固定值 SideValue=sum(PieceNum*PieceValue)；其中 PieceNum 是某種棋子的數(shù)量， PieceValue 是該種棋子的價值， sum 是對各種棋子的總價值求和。 可以用下面的表達(dá)式求某一 方棋子靈活性 : Mobility=Sum(MoveNum*MoveValue)； 其中， MoveNum 是某種棋子的合法走法數(shù)量， MoveValue 是該種棋子每一走法的價值， sum 是對所有棋子的靈活性價值求和。而如果周圍有己方棋子對其進(jìn)行了保護(hù)，也就是說，對方在理智的情況下不會去吃棋子 1，那么棋子 l 沒有受到威脅，價值不變。在同等速度之下，知識量越大性能越高。將這些經(jīng)驗放進(jìn)評估函數(shù)中反復(fù)對弈，然后不斷修正參數(shù)，找出一組性能較高的參數(shù)。 (3)交手法 (Hand Tweaking) 這是調(diào)整評估函數(shù)時非常常用的方法，通過讓程序?qū)模瑏碚业剿膬?yōu)勢和弱點，猜測哪些參數(shù)會讓程序更好，然后挑選新的參數(shù)。在優(yōu)化參數(shù)時，類似于爬山法，模擬退火法也是對權(quán)重做改變來提高成績，如果所做的改變沒有提高成績，也會根據(jù)一個隨機的幾率采納這個改變，試圖跳出局部最優(yōu)。 (2)選擇性搜索 (Selective Search)，即裁剪搜索，這種搜索略去對一些著法的搜索， 冒著有可能 漏掉最佳走法的風(fēng)險，而換來局部更深的搜索深度。在這一方走棋的時候，選擇價值最大的子節(jié)點走法，即實行“ Max 搜索”，另一方走棋則選擇價值最小的子節(jié)點走法，即實行“ Min 搜索”，這就是象棋博弈中的一個極大極小過程。 圖 和圖 給 出兩個剪枝示意圖 ： MAX MIN MAX 圖 α剪枝示意圖 MIN MAX MIN 圖 β剪枝示意圖 在圖 所示的極大極小樹片段中，按照極大極小值搜索規(guī)則， 從左路分枝的葉節(jié)點倒推得到第一層 MAX 節(jié)點的值為 5，可表示此時的著法最佳值，記為 α，顯然此 α值可作為 MAX 方著法指標(biāo)的下界。同理搜索右路分枝，進(jìn)行剪枝操作。圍繞著法排序，己經(jīng)出現(xiàn)了許多優(yōu)秀的搜索算法與舉措，例如歷史啟發(fā)，殺手啟發(fā)，置換表等等。 另外，空著搜索 (Null Move)也是搜索算法中一種很有效的搜索策略，它的思想是放棄本方的走棋權(quán)利，讓對方連續(xù)走棋，如果得到的分?jǐn)?shù)還大于原來的 β值，就可以簡單地返回 β值，在此分枝下的搜索意義不大，免于搜索。無庸多說，這對于程序節(jié)省思考時間有重大幫助。 FEN 是建立在 19世紀(jì)由報社記者 S 所有這一切用一行文字符號表示就行了而且非常容易讀。而且，這 個標(biāo)記是且只是在該局面緊接的上一步棋是某方剛走兵推進(jìn)兩格的情況下出現(xiàn) 。雖然二者查詢的形 式完全相同，但是存儲的內(nèi)容卻大不相同。界面的設(shè)計是供用戶與電腦進(jìn)行交互，無論是人機對戰(zhàn)還是制作、演示棋譜都是在界面中實現(xiàn)的。 ...... foreColor=fc。 ()。 } public Color 獲取棋子顏色 () { return foreColor。i=x 軸長 。 (point[4][8].x,point[4][8].y,point[6][y 軸長 ].x,point[6][y 軸長 ].y)。c=39。 addMouseListener(this)。 紅車 棋子類別 (紅方顏色 )。本系統(tǒng)通過對象棋規(guī)則的定義以及圖形化的棋子如何在棋盤中消失來實現(xiàn)人人對戰(zhàn)這一功能： public boolean movePieceRule(ChessPiece piece,int startI,int startJ,int endI,int endJ) { =piece。 break。 } } else