【正文】 摘 要 人工智能 (AI)中國象棋系統(tǒng) 是 將 計算 機知識和中國象棋 知識 結(jié)合起來的一種新型的游戲方式 。 該系統(tǒng)包括人人對戰(zhàn)、人機對戰(zhàn)、制作棋譜、播放棋譜以及挑戰(zhàn)英雄榜等功能模塊 。近幾十年來，隨著計算機硬件和軟件技術(shù)的不斷發(fā)展，人們開始對計算機能否戰(zhàn)勝人腦這個話題 產(chǎn)生了濃厚的興趣。人工智能的先驅(qū)們曾認(rèn)真的表明：如果能掌握下棋的本質(zhì)，也許就掌握了人類智能行為的核心；那些能夠存在于下棋活動中的重大原則，或許就存在于其 它任何需要人類智能的活動中。通過本課題的研究 ,掌握智能知識的表示與計算、搜索，不僅是對所學(xué)知識的鍛煉，更是在人工智能領(lǐng)域的有意義的探索 發(fā)展動態(tài)及研究現(xiàn)狀 和國際象棋博弈系統(tǒng)相比，中國象棋博弈系統(tǒng)的研究起步比較晚，是八十年代開始的。但該文主要 以殘局 做實驗，缺乏完整對局的考慮。 比較著名的軟件有臺灣的吳身潤的《中國象棋》、光譜公司出品的《將族Ⅲ》、 晟 業(yè)編制的《象棋水滸戰(zhàn)》、《象棋武林帖》。 這些都體現(xiàn)了中國象棋的人機博弈的研究的受關(guān)注程度 。 最直觀也是最典型的方式是使用 10x9 的二維棋盤數(shù)組表示，也有使用棋子數(shù)組，擴展棋盤 — 棋子數(shù)組等，棋盤的數(shù)據(jù)表示直接影響到程序的時間及空間復(fù)雜度。當(dāng)前為了提高著法生 成的效率 通常采用以空間換時間的方法 :與先求出棋子的在某位置的所有走法。 搜索技術(shù) (Search Techniques) 搜索技術(shù)與算法是象棋博弈系統(tǒng)程序的核心，是決定搜索效率的關(guān)鍵所在。如何有選擇地搜索，既瞄準(zhǔn)最有希望的方向局部加深，又不遺漏其它存在最優(yōu)解的可 能。直接從開局庫中取就可以大大加快開局時的運行速度和提高開局的質(zhì)量。 本文的主要工作 本 文 的主要工作是將博弈策略應(yīng)用到中國象棋程序的設(shè)計與實現(xiàn)上，建立一個完整的中國象棋計算機博弈 系統(tǒng)，研究工作主要集中在以下幾個方面 ： 棋盤表示與走法生成 從操作速度 (性能 )以及使用方便與否考慮，本象棋博弈系統(tǒng)從帶位行位列信息的擴展棋盤 —— 棋子聯(lián)系數(shù)組著手進(jìn)行研究。本系統(tǒng)采用通用的靜態(tài)估值方式，同時在估值時結(jié)合走法預(yù)生成數(shù)組，使估值的速度有很大提升。 論文結(jié)構(gòu) 第一章闡述了選題背景，課題的國內(nèi)外研究現(xiàn)狀及課題的主要工作和文章的章節(jié)安排。 包括子力分?jǐn)?shù)、子力靈活度評價、棋盤 控制等并與走法預(yù)生成數(shù)組結(jié)合以提高估值速度。 第 四章 是全文的總結(jié)及展望 。為了追求更高效率，研究人員針對中國象棋提出了多種不同的表示方法。這樣棋盤信息就被裝入這 32 個字節(jié)中。如果一個程序同時使用這兩個數(shù)組，那么獲得棋子的類型和棋子的位置都可以在常數(shù)時間內(nèi)完成。在棋盤上刪除一個棋子，需要做兩個操作 (分別修改棋盤數(shù)組和棋子數(shù)組 )。同時“棋盤 —— 棋子聯(lián)系數(shù)組”是很多改進(jìn)的棋盤的基礎(chǔ)。所以 ，人們把“棋盤 —— 棋子聯(lián)系數(shù)組“進(jìn)行擴展：把棋盤做成 16 16 的大小，這樣得到行號可以用 16 除，得到列號可以對 16 取余（和 15 進(jìn)行運算），這比除以 10 和對 9 取余操作要快得多。 (3) 判斷是否過河的方法非常簡單：只要設(shè)定特定的表達(dá)式，當(dāng)表達(dá)式為假表示已過河，否則沒過河。 中國象棋大約每一步可以有 45 個著法。 圖 馬的匹配模板 將馬對準(zhǔn)提址，“ O”表示符合“馬走日”規(guī)則的落址，“ x”表示“蹩 馬腿”的制約條件，通過查找模板匹配數(shù)組，實現(xiàn)“本方子則止，對方子則吃”，完成“提 —— 動 —— 落 —— 吃”內(nèi)容的確定。 預(yù)置表法 它是把所有可能的著法預(yù)先存儲起來，在生成著法時，用查表取代計算。圖中顯示，該車位于某行第 4 列，棋子分布的布爾向量形式為 [010100100]，可以看出，此時車可能的吃子著法落址為 [010000100]，非吃子著法的落址為 [f0010110001]。這一過程對具體的棋類知識依賴程度很深，但是仍有一般性的規(guī)律可循。 估值函數(shù) （ Evaluation Function） 本系統(tǒng)的估值函數(shù)包括：棋子固定價值，棋子位置附加值，棋子靈活性，棋子對棋盤的控制，棋子間的關(guān)系幾部分。在中國象棋的對弈中，由于一般以將死對方的將 (帥 )作為結(jié)束，因此，通常賦值的規(guī)則是為將 (帥 )賦予一個遠(yuǎn)大于其他棋子的子力之和的值。 同樣的棋子在不同位置上起的作用是不同的，最明顯的是兵 (卒 )過河之前與之后它的作用和攻擊力以及對對方的威脅顯然是不一 樣的，而當(dāng)兵卒一旦到了底線附近，它對將 (帥 )的威脅度將大大下降。例如車在縱橫線上遇到障礙物、馬被周圍棋子絆腳等，都降低了靈活性，也降低了威力的發(fā)揮，靈活性的計算是把棋子在棋盤上所能夠移動到達(dá)的位置數(shù)作為靈活性計算，給予評分。在象棋中，如果一位置落在某方棋子的合法走步上，就可以認(rèn)為被該方控制。如棋子 1 下一步將被吃掉，則應(yīng)該給一 個負(fù)的附加值。而如果此時輪到黑方走棋，就應(yīng)認(rèn)為紅馬受到的威脅很大，應(yīng)減去一個相對較大的值了。在同等的知識含量下，速度越快，性能越高。這樣的方法思路清晰，容易設(shè)計， 而且模塊間獨立性高，同搜索算法的 耦合 度很低。馬和炮的地位相當(dāng)，給予它們相當(dāng)?shù)臄?shù)值，以避免盲目換子 ；如果對弈中使 用了一些優(yōu)秀的戰(zhàn)術(shù)配合，那么就給予一定數(shù)值的獎勵，等等。這個做法可以減少一個需要設(shè)定的參數(shù)。在開始設(shè)定權(quán)重值的時候，這個方法通常可以得到合適的值，但是在后面仍然需要做一些調(diào)整。通過不斷的試驗、修改參數(shù)值，可以得到不錯的結(jié)果。 (2)模擬退火 (Simulated Annealing) 模擬退火是一種基于蒙特卡羅 (Monte Carlo)算法的啟發(fā)式隨機搜索算法，它沒有蒙特卡羅算法多次尋優(yōu)的過程，也不像爬山法那樣依賴初值。 (3)遺傳算法 (Geic Algorithm， GA) 遺傳算 法 是建立在自然選擇和自然遺傳學(xué)機理基礎(chǔ)上的迭代自適應(yīng)概率性全局優(yōu)化算法，因其模仿生物的遺傳機制而得名，最早由美國密執(zhí)安大學(xué) 于 1975 年提出，它通過染色體的復(fù)制，交叉，變異等操作，實現(xiàn)個體適應(yīng)性的提高。 根據(jù)搜索策略，目前應(yīng)用于計算機博弈的搜索算法一般可分為三類 ： (l)窮盡搜索 (Exhaustive Search)，這種搜索是沒有拋棄任何可能成為最佳路徑的搜索，不存在 風(fēng)險，得到的最佳走法肯定是在現(xiàn)有評估函數(shù)下應(yīng)該得到的，例如極大極 小值 搜索、α β 剪枝搜索及其變種等。中國象棋中的啟發(fā)算法有歷史啟發(fā)、殺手啟發(fā)、置換表等。在象棋博弈中，極大極小值算法體現(xiàn)在始終站在博弈一方的立場上給棋局估值，有利于這一方的棋局給予一個較高的價值分?jǐn)?shù)，不利于這一方(有利于另一方 )的給予一個較低的價值分?jǐn)?shù)，雙方優(yōu)劣不明顯的局面給予一個中間值分 數(shù)。 圖 極大極小值算法示意圖 由于完整的博弈樹過于龐大，程序不能也沒有必要搜索整棵博弈樹的所有節(jié)點，而需要像人類棋 手一樣有選擇性地進(jìn)行搜索，對 于一些已經(jīng)確定不佳的走步可以將以它 根節(jié)點的子樹剪掉 (cutoff/pruning)，以提高單位時間內(nèi)搜索的節(jié)點數(shù)。 它 是一種基于 αβ搜索的深度優(yōu)先 搜索，是所有剪枝算法的基礎(chǔ)， 它是根據(jù)極大極小搜索規(guī)則進(jìn)行的。此類剪枝稱為 α剪枝。在搜 索中路分枝時，因為第二層著法的選擇是取第三層節(jié)點的最大值，即取 MAX(5， 12，“○” )，而無論“○”中為何值，都不會比 11 小 (至少為 12)，故可以將“ ○ ”表示的節(jié)點及其后繼節(jié)點剪掉，不再考慮此節(jié)點的延伸。 αβ 剪枝搜索能夠讓我們省略許多節(jié)點的搜索，不只是節(jié)點本身，而且包括節(jié)點下面的子樹，這樣 αβ剪枝搜索需要遍歷的節(jié)點數(shù)遠(yuǎn)少于極大極小算法所遍歷的節(jié)點，也就節(jié)省了大量的時間開銷，并且仍不失為窮盡搜 索的本性 ， 但 αβ剪枝的剪枝效果即搜 索節(jié)點數(shù)與博弈樹節(jié)點的搜索次序密切相關(guān)。在搜索的過程中，往往有一些啟發(fā)性的信息可以利用，如果利用這些信息在相似的局面 下對走法進(jìn)行優(yōu)化排序，或者對相同的局面不再搜索，而直接返回以前搜索的結(jié)果，都會對搜索產(chǎn)生明顯的加速作用。在 搜索過程中，每找到一個好的著法，就將與該走法相應(yīng)的歷史得分作一 增量，一個多次被搜索并確認(rèn)為好的走法的歷史記錄分值會較高，當(dāng)搜索中間節(jié)點 時，將走法根據(jù)其歷史得分排序，以獲得較佳的排列順序。置換表不同于歷史啟發(fā)表和殺手表，不必在每次搜索之前都清空，而是一直維持這些數(shù)據(jù)，作為以后搜索的信息。“活馬”，即馬與兵陣的配合合理，使馬能有活動的空間 。 開 局庫的作用 象人們記住開局招數(shù)一樣，博弈程序使用一個數(shù)據(jù)庫，里面儲存了開局譜著和局面，于是當(dāng)對局（開局）中的棋步在開局庫中能找到時，它就可以立即取出來走，不用計算。所以如何設(shè)置一個比較好的開局庫，就成了程序設(shè)計中不可或缺的部分。 (1) FEN FEN 就是“福斯夫 愛德華茲記號法”（ ForsythEdwards Notation）， 這是一種使用ASCII 碼字符描述國際象棋局面的標(biāo)準(zhǔn)。后來為了適合象棋軟件的需要 ，由愛德華茲對此做了少許修改。 FEN 描述了 :棋子位置、輪走棋方、易位可行性、吃過路兵目標(biāo)格、半步計數(shù)、以及總回合數(shù)。數(shù)字代表一個橫線上的連續(xù)空格，反斜杠 \“ ∧ ”表示結(jié)束一個橫線的描述。如果有，就用具體完成吃過路兵的那個格子坐標(biāo) 表示，顯然對于白兵被吃只可能在第 3 橫線，對于黑兵被吃只可能在第 6 橫線。 (7) 回合數(shù)（ Fullmove Number） 當(dāng)前要進(jìn)行到的回合數(shù)。與搜索引擎中的置換表類似，開局庫也是用表示局面的哈希值除以 開局庫的大小作為索引，而表示局面的哈希值作為校驗。這也意味著 Zobrist 哈希所要使用的隨機數(shù)組，不能臨時產(chǎn)生，而要包含在開局庫當(dāng)中。 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)，界面是必不可少的部分。 Color backColor=null,foreColor。 public ChessPiece(String name,Color fc,Color bc,int width,int height,ChessBoard board) { =name。 setBackground(bc)。 (2,2,width2,height2)。 ()。 } public String getName() { return name。 } } 然后在棋盤類（ ChessBoard）里定義棋盤的表示、棋子的類別、顏色以及棋子在棋盤上的位置表示： /*棋盤的表示 */ public void paintComponent(Graphics g) { (g)。 } for(int i=1。i!=x 軸長 ) { (point[i][1].x,point[i][1].y,point[i][y 軸長 5].x,point[i][y 軸長5].y)。 (point[6][1].x,point[6][1].y,point[4][3].x,point[4][3].y)。i=x 軸長 。A39。 j++。 通過以上兩段本系統(tǒng)就實現(xiàn)了棋盤和棋子的定義，然后通過下面的方法實現(xiàn)棋子在棋盤上的表示： public ChessBoard(int w,int h,int r,int c) { setLayout(null)。 unitWidth=w。 ...... 紅車 1=new ChessPiece(車 ,bc,w4,h4,this)。 ...... point[1][10].setPiece(紅車 1,this)。人人對戰(zhàn)功能的實現(xiàn)其實就是一系列象棋規(guī)則的集中體現(xiàn)，譬如“馬走日”、“相走田”、“炮打隔山”等。 ...... boolean 可否走棋 =false。j++) { if(point[startI][j].isPiece()) { 可否走棋 =false。 for(i=minI+1。 } } if(i==maxI) { 可否走棋 =true。 (沒吃棋子 )。 x 9。 if (ChessMan != 0) { if (!isRedGo amp。amp