畢業(yè)設(shè)計---智能中國象棋系統(tǒng)的設(shè)計與實現(xiàn)

1、<p>　　智能中國象棋系統(tǒng)的設(shè)計與實現(xiàn)</p><p><b>　　摘 要</b></p><p>　　人工智能(AI)中國象棋系統(tǒng)是將計算機知識和中國象棋知識結(jié)合起來的一種新型的游戲方式。智能中國象棋系統(tǒng)在此基礎(chǔ)上實現(xiàn)人與機器的對弈，突破了以往傳統(tǒng)象棋游戲只能人與人對戰(zhàn)的限制，使中國象棋這一古老的游戲形式煥發(fā)出蓬勃朝氣。</p>&l

2、t;p>　　本文結(jié)合在中國象棋機器博弈方面的實踐經(jīng)驗，在分析了中國象棋游戲需求基礎(chǔ)上，設(shè)計并實現(xiàn)了智能中國象棋系統(tǒng)。該系統(tǒng)包括人人對戰(zhàn)、人機對戰(zhàn)、制作棋譜、播放棋譜以及挑戰(zhàn)英雄榜等功能模塊。人人對戰(zhàn)規(guī)則明確，包含了中國象棋所有的著法；人機對戰(zhàn)中電腦棋力分為簡單、中等、困難三個等級，方便了不同水平人群的選擇；制作和播放棋譜模塊容易操作，方便學(xué)習(xí)；挑戰(zhàn)英雄榜則為象棋游戲增加了樂趣。</p><p>　　本系統(tǒng)的

3、實現(xiàn)滿足了人們對中國象棋的基本需求，解決了傳統(tǒng)象棋游戲?qū)W習(xí)性差、棋譜不易保存、不易演示等問題。</p><p>　　關(guān)鍵詞：計算機博弈，中國象棋，人機對戰(zhàn)，制作棋譜，搜索算法</p><p>　　Intelligent Chinese Chess System Design and Implementation</p><p><b>　　Abstract

4、</b></p><p>　　Artificial Intelligence (AI) Chinese Chess System is a new games’ way which combines with computer knowledge and Chinese Chess knowledge. Intelligent Chinese Chess System on the basis of

5、it which completes the game between human and computer , breaking the traditional chess game’s restriction that only can play against people. So that the ancient game of Chinese chess become prosperity . </p><

6、p>　　With the practical experience in Chinese chess computer game, a detailed analysis and research has been done .Based on those, I designed and implemented the Intelligent Chinese Chess System .This system includes t

7、he game against human ,the gme between computer and human ,make chess manual ,play chess manual and hero list functions .The game against human function has all the Chinese Chess rules and they are very clear.In the game

8、 between computer and human function ,computer thinking depth is di</p><p>　　This system satisfied the basic demand of people to Chinese chess and solved the studying hard and the theoretical is not easy to

9、making and playing of the traditional chess game. </p><p>　　Key Words: Computer Game, Chinese Chess, Game between Human and Computer, </p><p>　　Make Chess Manual, Search Tecniques</p>&l

10、t;p><b>　　目 錄</b></p><p><b>　　1 緒論1</b></p><p>　　1.1選題的背景和意義1</p><p>　　1.2發(fā)展動態(tài)及研究現(xiàn)狀1</p><p><b>　　1.3系統(tǒng)概述2</b></p>&l

11、t;p>　　1.4本文的主要工作4</p><p><b>　　1.5論文結(jié)構(gòu)4</b></p><p>　　2 系統(tǒng)的分析和設(shè)計5</p><p>　　2.1數(shù)據(jù)結(jié)構(gòu)（DATA STRUCTURE）5</p><p>　　2.1.1 棋盤的基本表示法（Board Representions）.......

12、.....................................5</p><p>　　2.2 著法生成（MOVE GENERATION）7</p><p>　　2.2.1 模板匹配法.................................................................................................

13、7</p><p>　　2.2.2 預(yù)置表法.....................................................................................................8</p><p>　　2.3 局面評估8</p><p>　　2.3.1 估值函數(shù)（Evaluation Func

14、tion）............................................................9</p><p>　　2.3.2 估值的速度與博弈性能...........................................................................10</p><p>　　2.3.3 估值函數(shù)的優(yōu)化

15、.......................................................................................10</p><p>　　2.4 博弈樹搜索技術(shù)12</p><p>　　2.4.1 基本搜索算法..........................................................

16、.................................13</p><p>　　2.4.2 高級搜索算法...........................................................................................15</p><p>　　2.5 開局庫設(shè)計16</p><p>

17、;　　2.5.1 開局庫的作用...........................................................................................16</p><p>　　2.5.2 實現(xiàn)開局庫的主要方法........................................................................

18、...16</p><p>　　3 系統(tǒng)的實現(xiàn)19</p><p>　　3.1 系統(tǒng)的整體規(guī)劃19</p><p>　　3.2 象棋界面的實現(xiàn)19</p><p>　　3.3 對弈功能的實現(xiàn)24</p><p>　　3.4 制作和演示棋譜的實現(xiàn)28</p><p>　　3.5

19、 象棋英雄榜的實現(xiàn)31</p><p>　　3.6 開局庫的實現(xiàn)32</p><p>　　3.7 程序說明32</p><p>　　3.8 實驗結(jié)果及分析32</p><p><b>　　結(jié)論...34</b></p><p><b>　　致 謝36</b>

20、</p><p><b>　　參考文獻37</b></p><p><b>　　附 錄38</b></p><p><b>　　1 緒論　</b></p><p>　　1.1選題的背景和意義</p><p>　　在人類文明發(fā)展的初期，人們便開

21、始進行棋類博弈的游戲了。近幾十年來，隨著計算機硬件和軟件技術(shù)的不斷發(fā)展，人們開始對計算機能否戰(zhàn)勝人腦這個話題產(chǎn)生了濃厚的興趣。從1980開始，電腦博弈便開始逐漸大規(guī)模地向人類智能發(fā)起了挑戰(zhàn)，到了1997年，IBM超級電腦Deeper Blue 擊敗了當(dāng)時的國際象棋冠軍卡斯帕羅夫，成為了人工智能挑戰(zhàn)人類智能發(fā)展的一個重要里程碑。</p><p>　　許多學(xué)者認(rèn)為，對于人工智能研究而言，象棋的重要作用不亞于遺傳學(xué)研究

22、中的果蠅。人類對機器博弈的研究衍生了大量的研究成果，這些成果對更廣泛的領(lǐng)域產(chǎn)生了重要影響。人工智能的先驅(qū)們曾認(rèn)真的表明：如果能掌握下棋的本質(zhì)，也許就掌握了人類智能行為的核心；那些能夠存在于下棋活動中的重大原則，或許就存在于其它任何需要人類智能的活動中。因此對于中國象棋人機博弈問題的研究意義重大。</p><p>　　而當(dāng)今對中國象棋的研究也正如專家們所期望的那樣在蓬勃地發(fā)展著。中國象棋不僅是中國傳統(tǒng)智慧的體現(xiàn)，同

23、時也具有著比國際象棋更高的復(fù)雜度，如何讓機器具有智能,與人進行對弈成了本課題研究的一個重要問題。通過本課題的研究,掌握智能知識的表示與計算、搜索，不僅是對所學(xué)知識的鍛煉，更是在人工智能領(lǐng)域的有意義的探索</p><p>　　1.2發(fā)展動態(tài)及研究現(xiàn)狀</p><p>　　和國際象棋博弈系統(tǒng)相比，中國象棋博弈系統(tǒng)的研究起步比較晚，是八十年代開始的。在這個時候計算機國際象棋取得重大突破，1983

24、年美國貝爾公司的電腦參加美國人類比賽，取得了不錯的成績，被授予大師稱號。于是有專家學(xué)者想如何將國際象棋電腦技術(shù)移植到中國象棋上來，以帶動中國象棋電腦較快的發(fā)展；同時中國象棋從技術(shù)研究進入理論研究，有關(guān)開局、中局、殘局理論以及象棋對策相繼建立起來，為中國象棋計算機博弈提供了理論基礎(chǔ)。</p><p>　　1981年張耀騰發(fā)表的《人造智慧在電腦象棋上的應(yīng)用》，他提出審局函數(shù)為靜態(tài)子力值，棋子位置值，棋子靈活度值，威脅

25、與保護等四項之和。但該文主要以殘局做實驗，缺乏完整對局的考慮。1982年廖嘉成發(fā)表的《利用計算機象棋的實驗》就進了一步，包括開局、中局、殘局。1983年黃少龍、周玉龍合作制成《象棋排局系列軟盤》專家系統(tǒng)與人對弈。</p><p>　　到了90年代，中國象棋計算機博弈的應(yīng)用開始發(fā)展起來，人們研究出了各種博弈軟件。比較著名的軟件有臺灣的吳身潤的《中國象棋》、光譜公司出品的《將族Ⅲ》、晟業(yè)編制的《象棋水滸戰(zhàn)》、《象棋武

26、林帖》。而且涉足這個領(lǐng)域比較早的是臺灣的一些專家學(xué)者。近幾年，在內(nèi)地也涌現(xiàn)出一批對中國象棋人機博弈問題感興趣的高校、單位及個人，而且進入21世紀(jì)以后，中國象棋計算機博弈的研究受到越來越多的學(xué)者的關(guān)注，比較著名的博弈軟件如表1所示。</p><p>　　表1-1著名中國象棋計算機博弈程序</p><p>　　每年也會有中國象棋計算機博弈的國際奧林匹克大賽，這其中有2003年的世界冠軍“縱馬奔

27、流”，2004年的世界冠軍“謝謝象棋大師”，2005年的世界冠軍“象棋奇兵”，2006、2007年的世界冠軍“棋天大圣”， 2008年的世界冠軍“倚天”。 這些都體現(xiàn)了中國象棋的人機博弈的研究的受關(guān)注程度;雖然如此，但中國象棋的人機博弈的研究比國際象棋還是晚了幾十年，并且在搜索算法等方面的研究還與國際象棋相距甚遠(yuǎn)。</p><p><b>　　1.3系統(tǒng)概述</b></p>&

28、lt;p>　　1、棋盤表示(Board Representations)</p><p>　　棋盤表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來描述棋盤及棋盤上的棋子，以方便計算機處理。中國象棋的棋盤表示還沒有形成統(tǒng)一的或者公認(rèn)的哪種為最佳的數(shù)據(jù)格式。最直觀也是最典型的方式是使用10x9的二維棋盤數(shù)組表示，也有使用棋子數(shù)組，擴展棋盤—棋子數(shù)組等，棋盤的數(shù)據(jù)表示直接影響到程序的時間及空間復(fù)雜度。  2、著法

29、生成(Move Generation)  著法生成就是找到某個局面所有合法的走法。它與棋盤表示的數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，一般需要大量繁瑣的判斷，伴隨著搜索進行，并且調(diào)用頻繁，是相當(dāng)復(fù)雜而且耗費運算時間。在一定程度上形成了程序的性能瓶頸。當(dāng)前為了提高著法生成的效率通常采用以空間換時間的方法:與先求出棋子的在某位置的所有走法。 3、評估函數(shù)(Evaluation Function)</p><p>　

30、　評估函數(shù)就是對博弈過程中實際局面的好壞做出判斷或打分，它影響著博弈局發(fā)展的趨勢。目前象棋程序的靜態(tài)評價函數(shù)主要有子力價值，子力靈活性，子力對棋盤的控制，和一些對棋局影響比較大的重要特征計算幾部分組成。它與著法生成一樣十分耗費運算時間，如何加速評估函數(shù)的速度十分關(guān)鍵。</p><p>　　4、搜索技術(shù)(Search Techniques)</p><p>　　搜索技術(shù)與算法是象棋博弈系統(tǒng)程

31、序的核心，是決定搜索效率的關(guān)鍵所在。再好的硬件也無法實現(xiàn)“象棋不敗算法”。如何在成指數(shù)遞增的狀態(tài)空間中尋求最優(yōu)解，是象棋博弈系統(tǒng)的一個重要的方向。“蠻力搜索”肯定是不可取的。如何有選擇地搜索，既瞄準(zhǔn)最有希望的方向局部加深，又不遺漏其它存在最優(yōu)解的可能。目前主要是使用α-β剪枝算法加上迭代深化、置換表、歷史啟發(fā)等策略的綜合應(yīng)用。</p><p>　　5、開局庫(Opening Book)</p>&l

32、t;p>　　把開局幾步的走法建成數(shù)據(jù)庫供程序直接取用。實踐表明無論搜索引擎如何出色，在開局搜索過若干層后，得到的可能只是一些很笨拙的開局。直接從開局庫中取就可以大大加快開局時的運行速度和提高開局的質(zhì)量。開局庫一般是采用zobrist哈希技術(shù)加以實現(xiàn)。</p><p>　　6、機器自學(xué)習(xí)(Machine Learning)</p><p>　　機器自學(xué)習(xí)之一是針對評估函數(shù)。對弈過程機器

33、自動調(diào)整評估函數(shù)參數(shù)的權(quán)值進行優(yōu)化，發(fā)現(xiàn)一些棋子之間潛在的聯(lián)系:之二是采用模式識別，學(xué)習(xí)的過程是通過對博弈過程的識別統(tǒng)計，自行豐富模式庫中的內(nèi)容，以提高程序的博弈性能。</p><p>　　1.4本文的主要工作</p><p>　　本文的主要工作是將博弈策略應(yīng)用到中國象棋程序的設(shè)計與實現(xiàn)上，建立一個完整的中國象棋計算機博弈系統(tǒng)，研究工作主要集中在以下幾個方面：</p><

34、;p>　　1、棋盤表示與走法生成</p><p>　　從操作速度(性能)以及使用方便與否考慮，本象棋博弈系統(tǒng)從帶位行位列信息的擴展棋盤——棋子聯(lián)系數(shù)組著手進行研究。然后根據(jù)棋盤表示獲得所有棋子的走法預(yù)生成數(shù)組。在產(chǎn)生走法時直接從中取出數(shù)據(jù)，進行少量判斷以得到該棋子的合法走步。</p><p><b>　　2、估值函數(shù)</b></p><p&g

35、t;　　如何快速有效的對一個局面進行評估需要從速度和知識的兩個角度進行考慮:一般知識越多估值越準(zhǔn)確，但速度也慢下來。本系統(tǒng)采用通用的靜態(tài)估值方式，同時在估值時結(jié)合走法預(yù)生成數(shù)組，使估值的速度有很大提升。</p><p><b>　　3、搜索技術(shù)</b></p><p>　　博弈樹搜索技術(shù)它很大程度上獨立于具體的計算機博弈程序。本文討論了α-β剪枝搜索算法及其各種增強手

36、段：包括窗口原則、置換表(內(nèi)存增強)；歷史啟發(fā)表(節(jié)點順序調(diào)整)；迭代深化(時間控制)等。如何把各種增強手段有機組合起來達到最優(yōu)，文章對基于迭代加深、置換表、歷史啟發(fā)的Negascout算法進行改進。</p><p><b>　　1.5論文結(jié)構(gòu)</b></p><p>　　第一章闡述了選題背景，課題的國內(nèi)外研究現(xiàn)狀及課題的主要工作和文章的章節(jié)安排。</p>

37、<p>　　第二章第一部分首先介紹中國象棋程序的一些基本數(shù)據(jù)結(jié)構(gòu)，著重研究了擴展的棋盤——棋子聯(lián)系數(shù)組棋盤；在此基礎(chǔ)上實現(xiàn)所有棋子的走法預(yù)生成數(shù)組，以提高搜索過程中走法產(chǎn)生的效率。第二部分研究本系統(tǒng)的著法生成，包括預(yù)置表法和模板匹配法，進一步提高了搜索效率。第三部分描述本系統(tǒng)的評價函數(shù)架構(gòu)，著重描述了靜態(tài)估值方法，分析了其不足，并提出了解決之道。包括子力分?jǐn)?shù)、子力靈活度評價、棋盤控制等并與走法預(yù)生成數(shù)組結(jié)合以提高估值速度。

38、第四部分實現(xiàn)了博弈樹的α-β剪枝算法并簡要介紹各種搜索策略。第五部分闡述了開局庫的設(shè)計原理。</p><p>　　第三章給出實驗環(huán)境和程序?qū)崿F(xiàn)。</p><p>　　第四章是全文的總結(jié)及展望。</p><p>　　2 系統(tǒng)的分析和設(shè)計</p><p>　　2.1數(shù)據(jù)結(jié)構(gòu)（Data structure）</p><p>

39、　　數(shù)據(jù)結(jié)構(gòu)是一個程序的骨架，選擇一種好的數(shù)據(jù)結(jié)構(gòu)可以使程序的運行效率大大提高。</p><p>　　2.1.1 棋盤的基本表示法（Board Representions）</p><p>　　棋盤表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來描述棋盤上的信息，以便程序知道博弈的狀態(tài)。棋盤的數(shù)據(jù)表示直接影響到程序的時間及空間復(fù)雜度。為了追求更高效率，研究人員針對中國象棋提出了多種不同的表示方法。</p&

40、gt;<p>　　中國象棋的棋盤表示中最典型的是用一個10×9的二維字節(jié)(byte)數(shù)組，數(shù)組中每個元素代表棋盤上的一個交點，其值表明這個交點上放置的是一個什么棋子或是沒有棋子</p><p>　　從棋子的角度考慮，如果把棋盤看成是一個平面坐標(biāo)系，可以知道每一個棋子的位置信息:小于10的橫坐標(biāo)和小于11的縱坐標(biāo);又在棋盤上最多32個棋子，故可以用一個32個字節(jié)的一維數(shù)組表示所有32個棋子的

41、位置，其中每個字節(jié)的高4位表示該棋子的橫坐標(biāo)，低4位表示棋子的縱坐標(biāo)。而己被吃掉的棋子用坐標(biāo)范圍以外的數(shù)表示。這樣棋盤信息就被裝入這32個字節(jié)中。當(dāng)然也可以把棋盤看作一維的，每個元素保存直接的位置信息。</p><p>　　兩種棋盤表示方法：一是做一個棋盤數(shù)組；二是做一個棋子數(shù)組。棋盤數(shù)組中由棋子的位置獲得棋子的類型可以在常數(shù)時間內(nèi)完成，但由棋子的類型獲得棋子的位置需要遍歷；在棋子數(shù)組中由棋子的類型獲得棋子的位置

42、可以在常數(shù)時間內(nèi)完成，但由棋子的位置獲得棋子的類型操作繁瑣。如果一個程序同時使用這兩個數(shù)組，那么獲得棋子的類型和棋子的位置都可以在常數(shù)時間內(nèi)完成。這就是“棋盤·棋子聯(lián)系數(shù)組”，它的技術(shù)要點是:</p><p>　　(l) 同時用棋盤數(shù)組和棋子數(shù)組表示一個局面，棋盤數(shù)組和棋子數(shù)組之間可以互相轉(zhuǎn)換。 </p><p>　　(2) 隨時保持這兩個數(shù)組之間的聯(lián)系，棋子移動時必須同時更新這

43、兩個數(shù)組。在棋盤上刪除一個棋子，需要做兩個操作(分別修改棋盤數(shù)組和棋子數(shù)組)。同樣，添加一個棋子時也需要兩個操作。</p><p>　　“棋盤·棋子聯(lián)系數(shù)組“最大的優(yōu)勢是：對于著法產(chǎn)生過程，可以逐一查找棋子數(shù)組，如果該子沒有被吃掉，就產(chǎn)生該子的所有合理著法，由于需要查找的棋子數(shù)組的數(shù)量(每方只有16個棋子能走)比棋盤格子的數(shù)量(90個格子)少得多，因此聯(lián)系數(shù)組的速度要比單純的棋盤數(shù)組快很多。同時“棋盤—

44、—棋子聯(lián)系數(shù)組”是很多改進的棋盤的基礎(chǔ)。 </p><p>　　·2.1.2 改進型棋盤結(jié)構(gòu)</p><p>　　在計算機上面，位運算比一般的加減乘除及取余運算快得多。如果能在尋找棋子</p><p>　　和定位棋子上使用位運算代替加減乘除和取余，這將很大程度上提高運算速度。所以，人們把“棋盤——棋子聯(lián)系數(shù)組“進行擴展：把棋盤做成16×16的大

45、小，這樣得到行號可以用16除，得到列號可以對16取余（和15進行運算），這比除以10和對9取余操作要快得多。如圖2.1（紅色格子都被標(biāo)上“出界”的標(biāo)志，目標(biāo)格在這些格子上就說明著法無效）：</p><p>　　圖2.1 擴展的棋盤</p><p>　　這種棋盤的更大的好處是：</p><p>　　(1) 它可以防止棋子走出棋盤邊界。由bool型棋盤數(shù)組（屬于棋盤的位

46、置為true，否則為false），判斷棋子是否走出棋盤邊界只要返回該數(shù)組對應(yīng)的值即可，速度快。</p><p>　　(2) 對于是否在城池內(nèi)可以用bool型城池數(shù)組判斷，因為是否在城池內(nèi)的判斷會非常頻繁，直接用該數(shù)組會很高效。</p><p>　　(3) 判斷是否過河的方法非常簡單：只要設(shè)定特定的表達式，當(dāng)表達式為假表示已過河，否則沒過河。</p><p>　　(4

47、) 還可以非常方便的判斷棋子是否在己方。</p><p>　　2.2 著法生成（Move Generation）</p><p>　　著法生成就是要產(chǎn)生所有有效的著法，讓電腦棋手在這些著法中選擇最好的著法，并判斷人類棋手是否符合走棋規(guī)則。著法生成是博弈程序中一個相當(dāng)復(fù)雜而且耗費運算時間的方面，要生成所有著法只能用窮舉。中國象棋大約每一步可以有45個著法。</p><p&

48、gt;　　通過良好的數(shù)據(jù)結(jié)構(gòu)和走法預(yù)生成，可以顯著地提高生成的速度。</p><p>　　2.2.1 模板匹配法</p><p>　　當(dāng)動子確定以后，其“落址”和“提址”的相對關(guān)系便確定下來了，這樣可以為某些動子設(shè)計其著法生成的“模板”，只要匹配到提址，便可以迅速找到落址。圖2.3給出了馬的匹配模板。</p><p>　　圖2.2 馬的匹配模板</p>

49、<p>　　將馬對準(zhǔn)提址，“O”表示符合“馬走日”規(guī)則的落址，“x”表示“蹩馬腿”的制約條件，通過查找模板匹配數(shù)組，實現(xiàn)“本方子則止，對方子則吃”，完成“提——動——落——吃”內(nèi)容的確定。</p><p>　　對馬的著法生成使用模板匹配法時，只要寫出符合馬行棋規(guī)則的模板匹配數(shù)組和馬腿的模板匹配數(shù)組，在生成著法時通過查找這兩個數(shù)組就可以實現(xiàn)。顯然，這比掃描整個棋盤，通過計算得到合法落址要快速的多。同樣

50、的，可以對象、將、士、卒使用模板匹配生成著法。</p><p>　　2.2.2 預(yù)置表法</p><p>　　它是把所有可能的著法預(yù)先存儲起來，在生成著法時，用查表取代計算。中國象棋每種棋子的行棋規(guī)則不同，生成每種棋子的著法和整個棋盤棋子的分布密切相關(guān)，如果建立每種棋子最大可能著法的小型數(shù)據(jù)庫，用查詢?nèi)〈鷱?fù)雜的判斷，那么也可以在很大程度上加快著法生成的速度。預(yù)置表看起來似乎很大，但是只需在

51、程序開始運行時初始化一次就可以了，這些耗費對整個程序的影響不大，但是對著法生成的作用卻是非常明顯的。</p><p>　　圖2.3即是以路向行向比特向量為索引的一個車的預(yù)置著法表的生成范例。圖中顯示，該車位于某行第4列，棋子分布的布爾向量形式為 [010100100]，可以看出，此時車可能的吃子著法落址為[010000100]，非吃子著法的落址為[f0010110001]。把車的列號和該行棋子的布爾分布作為輸入，

52、把吃子落址和非吃子落址作為輸出，將輸入和輸出的關(guān)系寫入一個預(yù)置表中，在使用時通過查表，就可以快速構(gòu)成可行著法，而且可以區(qū)分開吃子著法和非吃子著法。如圖2.3所示：</p><p>　　圖 2.3 車的著法預(yù)置表范例</p><p><b>　　2.3 局面評估</b></p><p>　　局面估值就是通過既有的棋類知識來評估一個局面優(yōu)劣的過程。

53、從象棋的棋力上考慮，在搜索之外，局面估值是最重要的部分，因為對實際局面的評價的好壞，影響著今后局勢發(fā)展的趨勢。這一過程對具體的棋類知識依賴程度很深，但是仍有一般性的規(guī)律可循。目前在計算機象棋博弈中常用的估值方法主要采用靜態(tài)估值方法。同時由于隨著搜索層數(shù)的加深，葉子節(jié)點的數(shù)目迅速上升，估值函數(shù)被數(shù)以百萬次的調(diào)用，花費大量的運算時間，如何提高估值函數(shù)的速度，也成了博弈性能改進的重要話題。下面分別從這兩個方面及其關(guān)系介紹局面評估。</p

54、><p>　　2.3.1 估值函數(shù)（Evaluation Function）</p><p>　　本系統(tǒng)的估值函數(shù)包括：棋子固定價值，棋子位置附加值，棋子靈活性，棋子對棋盤的控制，棋子間的關(guān)系幾部分。</p><p>　　棋子固定價值指的是對棋盤中的每一個棋子，根據(jù)它的重要性和走法的豐富程度賦予其一個特定的值。在棋盤上，棋子多者占優(yōu)，棋子少者為劣。根據(jù)經(jīng)驗，可以讓一個車

55、價值為500，一個馬價值為300，一個兵價值為100等等。在中國象棋的對弈中，由于一般以將死對方的將(帥)作為結(jié)束，因此，通常賦值的規(guī)則是為將(帥)賦予一個遠(yuǎn)大于其他棋子的子力之和的值。</p><p>　　可以用下面的表達式求某一方的棋子固定值SideValue=sum(PieceNum*PieceValue)；其中 PieceNum是某種棋子的數(shù)量，PieceValue是該種棋子的價值，sum是對各種棋子的總

56、價值求和。如果紅色的棋子價值總和大于黑色的棋子價值總和，通常這意味著紅方的局勢優(yōu)于黑方。而紅黑雙方的SideValue之差越大，紅方的優(yōu)勢也就越大。</p><p>　　同樣的棋子在不同位置上起的作用是不同的，最明顯的是兵(卒)過河之前與之后它的作用和攻擊力以及對對方的威脅顯然是不一樣的，而當(dāng)兵卒一旦到了底線附近，它對將(帥)的威脅度將大大下降。</p><p>　　棋子靈活性描述的是棋子

57、的活動范圍，即棋子向各處調(diào)動的可能性大小。棋子的威力能否充分發(fā)揮，與靈活性直接相關(guān)。本方棋子可以走的點越多，說明本方棋子的靈活性越大。例如車在縱橫線上遇到障礙物、馬被周圍棋子絆腳等，都降低了靈活性，也降低了威力的發(fā)揮，靈活性的計算是把棋子在棋盤上所能夠移動到達的位置數(shù)作為靈活性計算，給予評分。</p><p>　　可以用下面的表達式求某一方棋子靈活性:</p><p>　　Mobility

58、=Sum(MoveNum*MoveValue)；</p><p>　　其中，MoveNum是某種棋子的合法走法數(shù)量，MoveValue是該種棋子每一走法的價值，sum是對所有棋子的靈活性價值求和。Mobility就是所有棋子的靈活性分?jǐn)?shù)。</p><p>　　一方對棋盤控制的棋盤區(qū)域越多，那么他就越具有主動性。在象棋中，如果一位置落在某方棋子的合法走步上，就可以認(rèn)為被該方控制。如果某一位置

59、同時落在雙方的合法走步上，可以根據(jù)雙方控制該位置的棋子數(shù)量及棋子價值來決定孰優(yōu)孰劣。能控制更多位置的一方應(yīng)在這項評分上占優(yōu)。</p><p>　　在中國象棋博弈中，每個棋子都不是孤立存在的，他們之間構(gòu)成了各種相互關(guān)系。如棋子1下一步將被吃掉，則應(yīng)該給一個負(fù)的附加值。而如果周圍有己方棋子對其進行了保護，也就是說，對方在理智的情況下不會去吃棋子1，那么棋子l沒有受到威脅，價值不變。棋子關(guān)系的評估應(yīng)考慮到該誰走棋的問題

60、。如果某個紅馬落在黑炮的合法走步之內(nèi)，但此時輪到紅方走棋，應(yīng)認(rèn)為紅馬受到的威脅較輕。而如果此時輪到黑方走棋，就應(yīng)認(rèn)為紅馬受到的威脅很大，應(yīng)減去一個相對較大的值了。</p><p>　　2.3.2 估值的速度與博弈性能</p><p>　　開發(fā)人員可以向估值函數(shù)加入大量的棋類知識，使之對于局面的評估更為精確。但是，博弈系統(tǒng)的性能，速度，棋類知識一般滿足下面的關(guān)系：</p>&l

61、t;p>　　Performance(性能)=Speed(速度)×Kowledge(知識)</p><p>　　且向估值函數(shù)加入越多的棋類知識，估值函數(shù)的速度也就越慢，因為所要進行的計算也相應(yīng)增加。因此過于簡單的估值函數(shù)和過于復(fù)雜的估值函數(shù)同樣性能不佳。在同等的知識含量下，速度越快，性能越高。在同等速度之下，知識量越大性能越高。在速度和知識量二者的相互作用下，開發(fā)者要尋找的是一種平衡，是能夠使性能最

62、大化的速度和知識量。使用終點估值(end—point envaluation)，意思是當(dāng)葉子節(jié)點到達時，使用估值函數(shù)對一個局面進行評估。這樣的方法思路清晰，容易設(shè)計，而且模塊間獨立性高，同搜索算法的耦合度很低?？梢暂p易的更換估值函數(shù)，只改動極少的代碼；你也可以隨意使用任何估值方法來評估整個棋盤，最終給出估值，但這種方法的速度較慢。</p><p>　　2.3.3 估值函數(shù)的優(yōu)化</p><p&

63、gt;　　目前最長使用的是優(yōu)化估值參數(shù)的方法是利用大量的測試局面進行手工調(diào)整，也是本文在優(yōu)化評估函數(shù)時主要使用的手段。這種方法是利用人類的象棋經(jīng)驗知識來調(diào)整參數(shù)值，比如，從經(jīng)驗上可以知道，一個車的價值要比一個兵大，給車賦予比兵大的數(shù)值，馬炮則賦予位于其間的值;馬和炮的地位相當(dāng)，給予它們相當(dāng)?shù)臄?shù)值，以避免盲目換子；如果對弈中使用了一些優(yōu)秀的戰(zhàn)術(shù)配合，那么就給予一定數(shù)值的獎勵，等等。將這些經(jīng)驗放進評估函數(shù)中反復(fù)對弈，然后不斷修正參數(shù)，找出一

64、組性能較高的參數(shù)。</p><p>　　(1)規(guī)格化(Normalize)</p><p>　　如果只是關(guān)心評價的順序，而不怎么關(guān)心評價值，那么可以把每一項都乘以同樣的常數(shù)。這就意味著，對某個特定的模塊，例如兵的價值，可以硬性設(shè)一個值，其他值就可以表示成它們相當(dāng)于多少個兵。這個做法可以減少一個需要設(shè)定的參數(shù)。</p><p>　　(2)約束法 (Deduce Con

65、straints)</p><p>　　通過考慮希望電腦作出怎樣的判斷，就可以確定一些參數(shù)。例如在對弈中即使賺到一個兵，用車換象或馬還是壞的，但如果能賺到兩個兵那還是好的，因為在考慮子力價值是要防止換單兵，鼓勵換雙兵。這樣的條件越多，合適的權(quán)重組合就越少。在開始設(shè)定權(quán)重值的時候，這個方法通?？梢缘玫胶线m的值，但是在后面仍然需要做一些調(diào)整。</p><p>　　(3)交手法 (Hand Tw

66、eaking)</p><p>　　這是調(diào)整評估函數(shù)時非常常用的方法，通過讓程序?qū)?，來找到它的?yōu)勢和弱點，猜測哪些參數(shù)會讓程序更好，然后挑選新的參數(shù)。這個方法可以很快得到合理的結(jié)果，但是需要對棋類知識有足夠的了解，便于根據(jù)程序的對局來做分析，從而知道程序的問題在哪里。手工調(diào)整是象棋引擎調(diào)整估值參數(shù)的主要手段之一，把人類的知識和經(jīng)驗盡量準(zhǔn)確客觀地“教授”給計算機，是提高棋力的普遍做法，雖然比較費時，但是很有效。通

67、過不斷的試驗、修改參數(shù)值，可以得到不錯的結(jié)果。但是人類的知識畢竟具有一定的局限性，評估函數(shù)也不能包含所有情況，參數(shù)之間往往又互相聯(lián)系，調(diào)整某個參數(shù)可能解決了某類問題，但又可能給其它問題的解決帶來麻煩，在這種情況下很難實現(xiàn)全局下的最優(yōu)組合。</p><p>　　還有一種主要的優(yōu)化方法是機器自學(xué)習(xí)：</p><p>　　(1)爬山法(Hill-Climbing)</p><

68、p>　　爬山法通過對參數(shù)進行小范圍的試探來尋找最優(yōu)解，一次只能對參數(shù)作一點小改變，然后測試博弈程序的性能是否提高了，僅當(dāng)性能提高時才采納這個改變，需要重復(fù)很多次。這種方法很慢，并且受初始采樣值的限制，很容易陷入局部最優(yōu)，即評價可能很差，但是任何很小的改變都會使評價更差。</p><p>　　(2)模擬退火 (Simulated Annealing)</p><p>　　模擬退火是一種

69、基于蒙特卡羅 (Monte Carlo)算法的啟發(fā)式隨機搜索算法，它沒有蒙特卡羅算法多次尋優(yōu)的過程，也不像爬山法那樣依賴初值。在優(yōu)化參數(shù)時，類似于爬山法，模擬退火法也是對權(quán)重做改變來提高成績，如果所做的改變沒有提高成績，也會根據(jù)一個隨機的幾率采納這個改變，試圖跳出局部最優(yōu)。這個方法需要給定一些幾率，從幾率高、梯度大的條件開始，然后逐漸減小。模擬退火法比爬山法更慢，是最終可能得到比較好的值。</p><p>　　(

70、3)遺傳算法 (Genetic Algorithm，GA)</p><p>　　遺傳算法是建立在自然選擇和自然遺傳學(xué)機理基礎(chǔ)上的迭代自適應(yīng)概率性全局優(yōu)化算法，因其模仿生物的遺傳機制而得名，最早由美國密執(zhí)安大學(xué)J.H.Holland于1975年提出，它通過染色體的復(fù)制，交叉，變異等操作，實現(xiàn)個體適應(yīng)性的提高。遺傳算法可以同時維護多組較好的參數(shù)，通過向其中添加一組新參數(shù)，通常是將從幾組老參數(shù)中選出的值組合在一起作微小

71、的變化，然后同幾組老的參數(shù)比較孰優(yōu)孰劣，將最壞的一組去除。遺傳算法是從幾組參數(shù)開始，而不是一組參數(shù)，具有很好的全局搜索能力，搜索速度也很快，而且此算法能將搜索重點集中于性能高的部分，能較快地求出最佳參數(shù)，魯棒性也明顯優(yōu)于前兩種算法，所以在計算機博弈中最有可能取得成功。</p><p>　　2.4 博弈樹搜索技術(shù)</p><p>　　中國象棋博弈樹非常龐大，完全建立博弈樹是不可能的，唯一的解

72、決方法就是讓博弈樹擴展到計算機運算可以接受的深度，然后對沒有分出勝負(fù)的葉子節(jié)點給出一個盡量準(zhǔn)確的打分，表示此局面下取得勝利的可能性，這個打分是由評估函數(shù)計算給出的，將搜索樹展開是著法生成的功能，而搜索引擎則是盡可能縮小樹的規(guī)模，避免一切冗余的計算，這也是計算機博弈中搜索引擎研究的重點。</p><p>　　根據(jù)搜索策略，目前應(yīng)用于計算機博弈的搜索算法一般可分為三類：</p><p>　　(

73、l)窮盡搜索 (Exhaustive Search)，這種搜索是沒有拋棄任何可能成為最佳路徑的搜索，不存在風(fēng)險，得到的最佳走法肯定是在現(xiàn)有評估函數(shù)下應(yīng)該得到的，例如極大極小值搜索、α-β剪枝搜索及其變種等。</p><p>　　(2)選擇性搜索 (Selective Search)，即裁剪搜索，這種搜索略去對一些著法的搜索，</p><p>　　冒著有可能漏掉最佳走法的風(fēng)險，而換來局部更深

74、的搜索深度。中國象棋中最常用裁剪算法是空著裁剪(Null Move)等。</p><p>　　(3)啟發(fā)式搜索 (Heuristic search)利用象棋領(lǐng)域的知識(啟發(fā)信息)設(shè)計搜索算法，著重對走法排序，以簡化和加快搜索過程。中國象棋中的啟發(fā)算法有歷史啟發(fā)、殺手啟發(fā)、置換表等。</p><p>　　2.4.1 基本搜索算法</p><p>　　極大極小值方法(M

75、inimax Algorithm)是解決博弈樹問題的基本方法。香農(nóng)教授早在1950年首先提出了“極大極小算法”，奠定了計算機博弈理論的基礎(chǔ)。</p><p>　　極大極小值算法的原則是:博弈雙方所要達到的目的相反，一方要尋找的利益是另一</p><p>　　方失去的利益，博弈的一方總是希望下一步是子節(jié)點中取值最大者，而另一方希望下一步是子節(jié)點中取值最小者。在象棋博弈中，極大極小值算法體現(xiàn)在

76、始終站在博弈一方的立場上給棋局估值，有利于這一方的棋局給予一個較高的價值分?jǐn)?shù)，不利于這一方(有利于另一方)的給予一個較低的價值分?jǐn)?shù)，雙方優(yōu)劣不明顯的局面給予一個中間值分?jǐn)?shù)。在這一方走棋的時候，選擇價值最大的子節(jié)點走法，即實行“Max搜索”，另一方走棋則選擇價值最小的子節(jié)點走法，即實行“Min搜索”，這就是象棋博弈中的一個極大極小過程。例如，如果紅方為走棋方，它在偶數(shù)層的著法選擇是要在其全部子節(jié)點中找到評估值最大的一個，實行“Max搜索”

77、，稱為MAX方，而其敵對方即黑方在奇數(shù)層的著法選擇則是在其全部子節(jié)點中要找到評估值最小的一個，實行“Min搜索”，稱為MIN方。圖2.4表示了一個極大極小搜索過程，粗箭頭為最佳路徑片段。</p><p>　　圖 2.4 極大極小值算法示意圖</p><p>　　由于完整的博弈樹過于龐大，程序不能也沒有必要搜索整棵博弈樹的所有節(jié)點，而需要像人類棋手一樣有選擇性地進行搜索，對于一些已經(jīng)確定不佳

78、的走步可以將以它根節(jié)點的子樹剪掉(cut-off/pruning)，以提高單位時間內(nèi)搜索的節(jié)點數(shù)。</p><p>　　上述極大極小值搜索過程中，遍歷了整個的博弈樹，這樣的搜索算法效率低，搜索量非常大，如果要減少搜索量，又可能影響搜索效果。但假如將葉節(jié)點的評估計算與樹的展開同時進行，然后對博弈樹進行必要的裁剪，就可能大量減少所需搜索的節(jié)點數(shù)目，并且保持搜索效果不變。這個技術(shù)叫α-β剪枝搜索。它是一種基于α-β搜索

79、的深度優(yōu)先搜索，是所有剪枝算法的基礎(chǔ)，它是根據(jù)極大極小搜索規(guī)則進行的。圖2.5和圖2.6給出兩個剪枝示意圖：</p><p><b>　　MAX</b></p><p><b>　　MIN</b></p><p><b>　　MAX</b></p><p>　　圖 2.5 α剪

80、枝示意圖</p><p><b>　　MIN</b></p><p><b>　　MAX</b></p><p><b>　　MIN</b></p><p>　　圖2.6 β剪枝示意圖</p><p>　　在圖2.5所示的極大極小樹片段中，按照極大極小

81、值搜索規(guī)則，從左路分枝的葉節(jié)點倒推得到第一層MAX節(jié)點的值為5，可表示此時的著法最佳值，記為α，顯然此α值可作為MAX方著法指標(biāo)的下界。在搜索中路分枝時，因為第二層著法的選擇是取第三層節(jié)點的最小值，即取M州(8，3，“□”)，而無論“□”中為何值，都不會比5大(最大為3)，故可以將“□”表示的節(jié)點及其后繼節(jié)點剪掉，不再考慮此節(jié)點的延伸。同理搜索右路分枝，也可以進行剪枝操作。此類剪枝稱為α-剪枝。圖2.5中通過剪枝，最后得到如粗箭頭所示的

82、最佳路徑片斷。</p><p>　　圖2.6所示的極大極小樹片段中，由左路分枝的葉節(jié)點倒推得到第一層MIN節(jié)點的值為n，可表示此時對方著法的鉗制值，記為β。顯然此β值可作為MIN方可能實現(xiàn)著法指標(biāo)的上界。在搜索中路分枝時，因為第二層著法的選擇是取第三層節(jié)點的最大值，即取MAX(5，12，“○”)，而無論“○”中為何值，都不會比11小(至少為12)，故可以將“○”表示的節(jié)點及其后繼節(jié)點剪掉，不再考慮此節(jié)點的延伸。同

83、理搜索右路分枝，進行剪枝操作。此類剪枝稱為β-剪枝。圖2.7中通過剪枝，最后得到如粗箭頭所示的最佳路徑片斷。</p><p>　　α-β剪枝搜索能夠讓我們省略許多節(jié)點的搜索，不只是節(jié)點本身，而且包括節(jié)點下面的子樹，這樣α-β剪枝搜索需要遍歷的節(jié)點數(shù)遠(yuǎn)少于極大極小算法所遍歷的節(jié)點，也就節(jié)省了大量的時間開銷，并且仍不失為窮盡搜索的本性，但α-β剪枝的剪枝效果即搜索節(jié)點數(shù)與博弈樹節(jié)點的搜索次序密切相關(guān)。</p&g

84、t;<p>　　2.4.2 高級搜索算法</p><p>　　極大極小值搜索是所有搜索算法的基礎(chǔ)，而α-β剪枝搜索是所有剪枝算法的基礎(chǔ)。但在實際的博弈系統(tǒng)設(shè)計中，要提高程序的搜索速度和搜索深度，還必須利用搜中得到的一些啟發(fā)式信息來加快搜索，目前己經(jīng)有很多對基本搜索算法的增強算法。</p><p>　　在α-β剪枝搜索中，剪枝效率幾乎完全取決于節(jié)點的排列順序，如何調(diào)整待展開的走

85、法的順序，是提高搜索效率的關(guān)鍵。在搜索的過程中，往往有一些啟發(fā)性的信息可以利用，如果利用這些信息在相似的局面下對走法進行優(yōu)化排序，或者對相同的局面不再搜索，而直接返回以前搜索的結(jié)果，都會對搜索產(chǎn)生明顯的加速作用。圍繞著法排序，己經(jīng)出現(xiàn)了許多優(yōu)秀的搜索算法與舉措，例如歷史啟發(fā)，殺手啟發(fā)，置換表等等。</p><p>　　歷史啟發(fā)(History Heuristic)實際上就是記錄搜索過的好的走法，并在后續(xù)著法中優(yōu)先

86、搜索。根據(jù)經(jīng)驗，一些以前經(jīng)過搜索認(rèn)為最佳的走法，其后續(xù)走法仍然有很大可能成為最優(yōu)的走法。在搜索過程中，每找到一個好的著法，就將與該走法相應(yīng)的歷史得分作一增量，一個多次被搜索并確認(rèn)為好的走法的歷史記錄分值會較高，當(dāng)搜索中間節(jié)點時，將走法根據(jù)其歷史得分排序，以獲得較佳的排列順序。</p><p>　　殺手啟發(fā)(Killer Heuristic)是基于這樣的思想:在搜索過程中，有許多走法一經(jīng)搜索就引發(fā)了剪枝，且這些走法

87、通常是同一個走法，這樣，為每一層記錄引發(fā)剪枝最多的走法即殺手走法，當(dāng)下一次搜索到同樣的深度時，如果殺手走法是該局的一個合法走法，就優(yōu)先搜索殺手走法。殺手啟發(fā)是一種特殊的歷史啟發(fā)，它不依賴于人類的知識，具有普遍性。</p><p>　　置換表 (TransposilionTable)是用一張表把搜索過的信息記錄下來，在后續(xù)的搜索中，察看記錄在表中的這些信息，如果將要搜索的某個節(jié)點已經(jīng)有記錄，就直接利用記錄下來的結(jié)果

88、引入到當(dāng)前的搜索中，以減少搜索。置換表不同于歷史啟發(fā)表和殺手表，不必在每次搜索之前都清空，而是一直維持這些數(shù)據(jù)，作為以后搜索的信息。</p><p>　　另外，空著搜索(Null Move)也是搜索算法中一種很有效的搜索策略，它的思想是放棄本方的走棋權(quán)利，讓對方連續(xù)走棋，如果得到的分?jǐn)?shù)還大于原來的β值，就可以簡單地返回β值，在此分枝下的搜索意義不大，免于搜索?？罩阉髅黠@降低了搜索的數(shù)量，導(dǎo)致搜索深度顯著提高，并

89、且危險性比較小，實現(xiàn)較為簡單。</p><p><b>　　2.5 開局庫設(shè)計</b></p><p>　　中國象棋的開局變化極多，每一種走法都能產(chǎn)生出一種新的變化，單就中炮對屏風(fēng)馬、中炮對反宮馬、中炮對左三步虎等數(shù)十種變化，其格個開局又都有自身的變化，這些開局都遵循開局的規(guī)律:“明車”，即車路要通;“活馬”，即馬與兵陣的配合合理，使馬能有活動的空間;“好炮位”，即炮

90、要占住子力疏密適中的要點，封鎖對方進攻路線，配合其他子力展開進攻。另外當(dāng)進行快棋賽時，棋手還會選擇一些冷門開局，使局面很快“脫譜”，迅速進入到中、殘局。所以中國象棋開局階段是整個對弈過程中變化最多的階段，開局的好壞對之后的中、殘局意義重大。</p><p>　　2.5.1 開局庫的作用</p><p>　　象人們記住開局招數(shù)一樣，博弈程序使用一個數(shù)據(jù)庫，里面儲存了開局譜著和局面，于是當(dāng)對局

91、（開局）中的棋步在開局庫中能找到時，它就可以立即取出來走，不用計算。無庸多說，這對于程序節(jié)省思考時間有重大幫助。這對于整個博弈系統(tǒng)來說有三點好處：一是防止戰(zhàn)略性錯誤；二是形成較為穩(wěn)妥和有利的局面；三是節(jié)省了大量的搜索時間。但另一方面，如果開局庫本身不好或部分不好，程序也可能被盲目引到劣勢的局面甚至很快失利。所以如何設(shè)置一個比較好的開局庫，就成了程序設(shè)計中不可或缺的部分。</p><p>　　2.5.2 實現(xiàn)開局庫

92、的主要方法</p><p>　　實現(xiàn)開局庫的方法一般有兩種：一種是用FEN的形式表示的開局庫；另一種是哈希值表示的開局庫。</p><p>　　用FEN串表示開局庫的方法比較簡單，該方法僅僅是將開局庫中的存儲的棋盤狀態(tài)與當(dāng)前棋盤的狀態(tài)進行比較，若相同，則程序根據(jù)庫中的走法走一步。下面我們來看看什么是fen串。</p><p><b>　　(1) FEN&l

93、t;/b></p><p>　　FEN就是“福斯夫-愛德華茲記號法”（Forsyth-Edwards Notation），這是一種使用ASCII碼字符描述國際象棋局面的標(biāo)準(zhǔn)。FEN是建立在19世紀(jì)由報社記者S·D·福斯夫設(shè)計的記錄局面的標(biāo)準(zhǔn)基礎(chǔ)上的。后來為了適合象棋軟件的需要，由愛德華茲對此做了少許修改。一份標(biāo)準(zhǔn)的局面記號對需要大量交換共享局面數(shù)據(jù)的國際象棋程序設(shè)計等工作具有尤其重要的作

94、用。</p><p><b>　　(2) 結(jié)構(gòu)描述</b></p><p>　　一個FEN記錄使用長度可不同的一行來表示，由六個區(qū)域組成。單純的FEN記錄文件后綴應(yīng)該是“.fen”，比如:kk-1.fen，在中國象棋開局庫的fen串形式的開局庫文件后綴為.DAT。FEN描述了:棋子位置、輪走棋方、易位可行性、吃過路兵目標(biāo)格、半步計數(shù)、以及總回合數(shù)。所有這一切用一行文字

95、符號表示就行了而且非常容易讀。</p><p>　　看看一個FEN的五個區(qū)域及其含義，以中國象棋為例：</p><p>　　Rnbakabnr/9/1C5C1/P1P1P1P1P/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w—0 1</p><p>　　這就是每盤常規(guī)對局的最初局面，一個子都沒有動，如圖2.7：</p><p

96、>　　圖 2.7 象棋初始局面</p><p>　　(3) 棋子位置數(shù)值區(qū)域（Piece placement data）</p><p>　　就是表示雙方棋子各在棋盤哪個格子上的。規(guī)則是從第10橫線開始順序數(shù)到第1橫線(紅方在下，從上數(shù)到下)，從a線開始順次數(shù)到h線；紅方棋子以大寫字母</p><p>　　\“RNBAKABNR\”功表示，黑方棋子以小寫\“r

97、nbakabnr\”表示，這是英文表示法，每個字母代表的意義與常規(guī)規(guī)定相同。數(shù)字代表一個橫線上的連續(xù)空格，反斜杠\“∧”表示結(jié)束一個橫線的描述。</p><p>　　上面的那P1PlP1PlP，就是表示黑方在第7橫線上排有5只兵；后面那兩個數(shù)字9，</p><p>　　就是表示從第6到第5橫線，雙方一個棋子都不在，是空格；9個反斜杠\“∧”將第一區(qū)域分成8段，因為棋盤有10條橫線；其它的照

98、著圖完全可以類推。</p><p>　　(4) 輪走棋方（Active Color）</p><p>　　表示目前局面誰該走棋。小寫\“w\”表示紅方走棋；小寫\“b\”表示黑方走棋；因為起初局面是紅先，所以上面就是\“w\”.</p><p>　　(5) 吃過路兵目標(biāo)格（En Passant Target Square）</p><p>　

99、　如果沒有，就用\“-\”表示。如果有，就用具體完成吃過路兵的那個格子坐標(biāo)表示，顯然對于白兵被吃只可能在第3橫線，對于黑兵被吃只可能在第6橫線。而且，這個標(biāo)記是且只是在該局面緊接的上一步棋是某方剛走兵推進兩格的情況下出現(xiàn)。</p><p>　　(6) 半回合數(shù)（Halfmove Clock）</p><p>　　用一個非負(fù)數(shù)表示自從上一次動兵或吃子之后目前走了的半回合數(shù)。這個是為了適應(yīng)50

100、步和棋規(guī)則而定。</p><p>　　(7) 回合數(shù)（Fullmove Number）</p><p>　　當(dāng)前要進行到的回合數(shù)。不管紅還是黑，第一步時總是以1表示，以后黑方每走一步數(shù)字就加1。用哈希值開局庫的文件的后綴通常為“.BIN”。 這種方法是使用置換表來統(tǒng)計開局庫中的一些走法的優(yōu)劣。與搜索引擎中的置換表類似，開局庫也是用表示局面的哈希值除以開局庫的大小作為索引，而表示局面的哈希值

101、作為校驗。雖然二者查詢的形式完全相同，但是存儲的內(nèi)容卻大不相同。置換表存儲的內(nèi)容主要用于搜索，開局庫存儲的內(nèi)容主要是走法的權(quán)重、輸贏比率，用于選擇最佳的走法。它只存放某局面的一個哈希值以及對應(yīng)的走法。這也意味著Zobrist哈希所要使用的隨機數(shù)組，不能臨時產(chǎn)生，而要包含在開局庫當(dāng)中。對于當(dāng)前局面，查詢數(shù)據(jù)庫的函數(shù)使用庫中的隨機數(shù)組計算出其哈希值，然后在庫中察看是否有此值所代表的局面。此種開局庫的實現(xiàn)方法:</p><

102、p>　　(a) 查詢當(dāng)前局面</p><p>　　開局庫中存儲的哈希值表示的是當(dāng)前局面，查詢到開局庫中所儲存的各種走法，并在各種走法中隨機提取一個走法執(zhí)行，走法選擇的幾率與其權(quán)重成正比。</p><p><b>　　(b)查詢后續(xù)局面</b></p><p>　　這種開局庫查詢是與搜索結(jié)合在一起的，并不是查詢當(dāng)前局面是否在開局庫中，而是展

103、開根節(jié)點的所有走法，也就是當(dāng)前局面下所有可能走法。</p><p><b>　　3 系統(tǒng)的實現(xiàn)</b></p><p>　　3.1 系統(tǒng)的整體規(guī)劃</p><p>　　整個智能象棋系統(tǒng)將要實現(xiàn)的主要功能是：人人對戰(zhàn)、人機對戰(zhàn)、制作棋譜、演示棋譜、挑戰(zhàn)英雄榜等，而其中的各個功能又分為幾個小功能模塊，該系統(tǒng)的功能結(jié)構(gòu)圖如圖3.1所示：</p&

104、gt;<p>　　圖3.1 功能結(jié)構(gòu)圖</p><p>　　3.2 象棋界面的實現(xiàn)</p><p>　　本系統(tǒng)要實現(xiàn)一個象棋游戲系統(tǒng)，界面是必不可少的部分。界面的設(shè)計是供用戶與電腦進行交互，無論是人機對戰(zhàn)還是制作、演示棋譜都是在界面中實現(xiàn)的。</p><p>　　運行完成的程序，本系統(tǒng)界面如圖3.2所示：</p><p>　　

105、圖3.2 象棋系統(tǒng)界面</p><p>　　界面的實現(xiàn)分為棋盤的表示和棋子的表示兩部分，棋盤和棋子通過數(shù)組連接起來，形成一個完整的界面系統(tǒng)。首先定義一個棋子類（ChessPiece），來獲取棋子的顏色以及類別：</p><p>　　public class ChessPiece extends JLabel</p><p><b>　　{</b>

106、;</p><p>　　String name;</p><p>　　Color backColor=null,foreColor;</p><p>　　String 顏色類別=null;</p><p>　　ChessBoard board=null;</p><p>　　int width,height;</

107、p><p>　　public ChessPiece(String name,Color fc,Color bc,int width,int height,ChessBoard board)</p><p><b>　　{</b></p><p>　　this.name=name;</p><p><b>　　...