1、 太原理工大學畢業(yè)設計論文 緒論選題的意義中國象棋在中國擁有悠久的歷史，這個游戲需要兩個人進行對弈。由于中國象棋用具簡單、趣味性強，成為流行極為廣泛、老少皆宜的棋藝活動。中國象棋是一種古老的文化，它集文化、科學、藝術、競技于一體，有利于開發(fā)人的智慧，鍛煉人的思維，培養(yǎng)人的毅甚至可以跟電腦對戰(zhàn)，于是就產生了人是否能夠戰(zhàn)勝電腦的疑問。是一個重要的組成部分。人們對人工智能的窺探是從棋類博弈游戲開始的，人們在博弈游戲中，對戰(zhàn)雙方通過對游戲規(guī)則的掌握、豐富的經驗和知識，使游戲的局面有利于自己，這就是人類的思維過程，于是棋類博弈就成了人工智能的實驗品。對機器博弈的研究取得的成果不僅僅只用在棋類游戲上，而且

2、也已廣泛應用于軍事、政治、經濟等多個領域，給人類帶來了極大的社會效益。國內外研究現(xiàn)狀概述機器棋類博弈的研究最早是從國際象棋開始的，1950年美國著名數(shù)學家香農積幾十年的主題是通常一般實力的棋手都能考慮到的一些因素,諸如:棋子實力重疊兵后兵的弱點以及車的通路和其他子力的活動性等等。香農還提出用簡化的估計方法剔除次要的變化。他是計算機國際象棋理論的奠基人。在數(shù)學家和計算機專家的共同努力下20世紀50年代末終于試制出世界上第1臺公開與棋手對弈的電子計算機。1974年，在瑞典的斯德哥爾摩舉行了計算機國際象棋的第1屆世界冠軍賽，8個國家的13種弈棋程序按積分循環(huán)制進行比賽，結果蘇聯(lián)的“卡伊賽”程序獲得冠

3、軍。最出名的是1997 年,卡內基梅隆大學的“深藍”小組研究開發(fā)出“更深的藍”，挑戰(zhàn)人類大師。最后在全世界目光的關注下，“超級深藍”擊敗了棋王卡斯帕羅夫。成為人工智能歷史上里程碑式的事件，也標志著機器博弈的重大成功。1981年張耀騰發(fā)表的人造智慧在電腦象棋上的應用，是第一篇研究中國象棋機器博弈的文章。他在他的畢業(yè)論文中以殘局做實驗，提出審局函數(shù)為靜態(tài)子力值，棋子位置值，棋子靈活度值，威脅與保護等四項之和。1982括開局、中局、殘局。臺灣大學的許舜欽教授被稱為中國計算機象棋之父。在他1991年的兩篇論文中，總結并介紹了到當時為止幾乎所有的搜索算法，他在文中詳細闡述了許多算法的不足之處并且解釋了人

4、們對這些算法的誤解。這些研究成果為以后計算機象棋的發(fā)展做好了鋪墊，至今仍在指導著人們進行計算機象棋的研究和實驗工作。較有代表性的有臺灣的吳身潤的中國象棋、光譜公司出品的將族、晟業(yè)編制的象棋水滸戰(zhàn)等等。 主要研究內容文章主要是研究中國象棋的人機對弈，包括象棋的界面和引擎部分。界面主要是方便人與電腦進行交互的可視化界面。界面包括棋盤區(qū)、菜單項和功能按鈕區(qū)。主要實現(xiàn)棋子的移動、悔棋、記錄棋譜、難度選擇等選項功能。引擎部分主要包括，棋子棋盤的表示即數(shù)據結構，走法的生成，局面優(yōu)劣的評估即評估函數(shù)，搜索算法及其優(yōu)化和改進。文章設計是采用MFC的框架來實現(xiàn)界面部分,主要用到的MFC類有，CWnd：窗口，它是

5、大多數(shù)“看得見的東西”的父類（Windows里幾乎所有看得見的東西都是一個窗口，大窗口里有許多小窗口）。CDC圖就抽象為CDC。CDC與其他GDI作。CDialog對話框類，CPen類，CBrush類等等。象棋對弈其實是一種零和博弈。雙人對弈，輪流走步；信息完備，雙方得到的信息都是一樣的；零和，即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利或無利的棋。所以內核代碼的思路要用到博弈算法。對每一個局面所有可能的著法進行考慮，每一步著法會形成新的局面，這樣就形成了一顆博弈樹。機器博弈就是要從這顆博弈樹中找到最優(yōu)的分支，即要用到搜索算法對整棵樹進行搜索。而中國象棋的博弈樹是一個龐大的集合，

6、如果一毫微秒走一步，也要需要10的一百多次方年才能搜索出必贏的第一步，所以博弈樹是不可能窮舉的。人在思索下棋的時候也不可能對棋局所有的可能計算完全，人往往是憑自己的經驗、知識對棋面的好壞進行評估。通過這種思路我們可以給每個局面打一個分數(shù)來表示棋局對自己的有利程度。如果輪到自己落子的時候，一定會選擇使局面分數(shù)最高的著法，如果輪到對手落子，他一定會選擇使你得分最低的局面。這就是我們經常聽到的極大極小值搜索，而對局面進行估分的函數(shù)就是評估函數(shù)。候選擇得分最小的局面，這樣就使得搜索可以進行，而由于估分的存在我們就可以在搜索進行到可以接受的時間范圍內時結束它。一、系統(tǒng)概述1.1 軟件用途提供了一個PC端

7、的中國象棋游戲。同時發(fā)布了GUI版與CLI版。其中CLI版為象棋AI部分開發(fā)過程中用作測試。但已經具有完整的人機對弈功能與相對友好的界面?？紤]到有些用戶可能相對GUI更偏向命令行操作方式,因此與GUI版本一起發(fā)布。CLI版本只有人機對弈功能,默認黑方(AI)先走。AI原理與GUI版相同,以下文檔只對GUI版作出說明。如無特殊說明, 提到”軟件”時,所指均為GUI版本。軟件具有兩種模式,雙人對弈與人機對弈。 若選擇雙人對弈, 因為此版本暫未開發(fā)聯(lián)機對弈功能, 只能雙人共用一臺PC,紅方先走,黑方后走,有一方被將死,即無棋可走時,電腦會自動判定勝負。若選擇人機對弈,默認用戶執(zhí)紅子,AI執(zhí)黑子。軟件

8、可自動判定勝負。軟件在ubuntu 13。04、windows7、windowsXP平臺下測試性能良好。此版本未實現(xiàn)的功能:長將判負。即假定紅方只剩5個兵與一個將,且全部過河。黑方只剩一個將與一個車。則黑方基本不可能將死紅方。但紅方必定可在有限步之后將死黑方。則黑方為自保,最優(yōu)策略是每一步都用車將紅方的軍,但無法將其將死。此時游戲會陷入循環(huán)。在正式象棋比賽中,任何情況下,長將判負?？紤]到主要是面向人機對弈, 和棋功能無意義, 亦未開發(fā)。此AI與軟件作者對弈,目前AI保持不敗戰(zhàn)績。與其他測試者對弈，也是勝多敗少。與作者ipad上的象棋app對弈,互有勝負,但軟件AI勝少敗多游戲截圖：進場畫面如下

9、圖所示：圖1.1 進場界面游戲界面： 圖1.2 游戲界面1.2 游戲特色最大可達可接受時間內7層搜索深度,AI具有較高棋力。游戲固定權值與棋盤位置分值相結合的評估函數(shù)?；赼lpha-beta搜索,走法排序后PVS搜索策略。1.3 系統(tǒng)開發(fā)過程軟件作者為張哲源與劉豪。張哲源負責開發(fā)系統(tǒng)的AI部分,即局面表示,走法生成,局面評估,Alpha-Beta搜索,搜索策略優(yōu)化。劉豪負責系統(tǒng)GUI的設計與實現(xiàn)。部分GUI設計張哲源亦有參與。 開發(fā)過程:先實現(xiàn)了一個無GUI的搜索策略為alpha-beta剪枝的命令行版本。再實現(xiàn)了一個基本的GUI版本。接下來GUI部分開始開發(fā)regret/restart/搜

10、索進度條 等工作。 AI部分則著重于搜索策略的優(yōu)化。六月份開始進行優(yōu)化, 一共經歷過兩次優(yōu)化,一次走法棧生成時的自動排序使得Alpha-Beta的可接受搜索深度(在10s左右完成搜索)由depth=5提升到depth=6。搜索時引入PVS算法,使得可接受的搜索深度增加為7。文檔的GUI部分為劉豪負責寫作，AI部分由張哲源負責寫作1.4 AI代碼閱讀提示AI部分代碼在kernel文件夾中，建議用戶先閱讀global.h，了解聲明了哪些全局變量。則其余代碼的算法都不復雜，應當較容易閱讀。二、系統(tǒng)需求說明2.1 系統(tǒng)總體功能可以實現(xiàn)雙人對弈與人機博弈.AI會檢查走子的有效性.AI會自動判定勝負具有悔

11、棋功能. 但軟件作者一致認為君子有所為有所不為,落子無悔才是值得提倡的.因此對用戶悔棋功能設置了一些障礙.用戶需連續(xù)點擊彈出的對話框10次之后,同時接受AI的冷嘲熱諷. 才允許悔棋.若用戶終于決定放棄悔棋.關閉對話框即可.若選擇人機對弈,用戶被AI吃子后會提示被吃了哪個子.可以restart,即棋局進行到中局或是一局終了, 用戶想要重新玩一局, 可點擊restart.若用戶被將軍,則必須應將,若不應將,則會彈出對話框提醒用戶.人機對戰(zhàn)模式中,AI會在被將死之前就認輸,即當AI檢測到它幾步之后必然會被將死,就會提前認輸.可接受的時間內搜索深度可達7層alpha-beta搜索.但是一開始就采用7步

12、搜索無必要.因而設定前5回合(十步)進行5層搜索,5回合之后到25回合(50步)采用6步搜索.若之后用戶仍未被將死.將采用7步搜索.人機對弈模式中，界面右下方會以進度條顯示AI已搜索結點的比例。2.2 環(huán)境需求AI部分與GUI部分由兩人分工完成.(一) 開發(fā)環(huán)境AI部分:TOSHIBA C600D-01L筆記本電腦.AMD Athlon(tm)II P320 Dual-Core Processor,Ubuntu13.04操作系統(tǒng),使用vim編寫,測試程序使用g+4.7.4編譯.AI部分測試功能正確后,交由高楠進行GUI的實現(xiàn).GUI開發(fā)環(huán)境:Acer Aspire 4736ZG筆記本電腦.Pe

13、ntium（R） Dual-Core CPU T4500，Windows7 企業(yè)版32位操作系統(tǒng)，使用Qt Creator 4.8編寫(二)運行環(huán)境在ubuntu13.04及windows7、winXP操作系統(tǒng)下可流暢運行.作者測試游戲所用CPU較為低端,游戲運行仍較為流暢.用戶所用CPU性能不錯的話,可以考慮一開始就將搜索深度設為6或者7.2.3 系統(tǒng)功能需求可選的對戰(zhàn)模式_雙人對弈或人機對弈啟動游戲后, 點擊相應button,即可選擇相應對戰(zhàn)模式。雙人對弈：若選擇雙人對弈功能,則可雙方交替走子. 系統(tǒng)會自動檢測走子的有效性,不合規(guī)則的走子無法走出.若一方勝利,則系統(tǒng)會彈出對話框告知 “bl

14、ack_lose”或是”red lose”.人機對弈:選擇人機對弈模式之后,默認用戶執(zhí)紅子先走.同樣會檢測走子有效性,同時還會檢測紅黑雙方是否被將軍,若被將軍,則必須應將,不應將的走法時無效的.即紅黑雙方的將在游戲過程中并不會真正的被吃掉,只要一方的將被將死,則系統(tǒng)會判定勝負.AI會在被將死之前幾步就檢測出自己會被將死而無可補救,此時AI會認輸.退出功能:點擊exit按鈕,可以退出程序.restart功能:點擊restart按鈕,可重新開始棋局.悔棋功能:點擊regret按鈕,彈出對話框勸用戶不要悔棋,用戶執(zhí)意悔棋,則撤銷之前兩步的走法(紅方與黑方的).注意：悔棋是撤銷兩步走法，因此若是在雙人

15、對弈模式，A、B兩人對弈，A走出之后要悔棋，必需在B走完之后才能成功。將軍提醒:用戶被將軍而不應將時,系統(tǒng)會作出提醒.進度條:選擇人機對戰(zhàn)模式時,機器思考時,界面下方會有進度體啊顯示機器搜索的程度.三、系統(tǒng)設計3.1 系統(tǒng)設計決策AI系統(tǒng)設計時,將AI與GUI分開設計.AI根據當前局面進行搜索/決策,產生最優(yōu)走法,將走法傳遞給GUI,GUI刷新界面.GUI部分在用戶界面設計部分會有詳細說明,此處介紹AI的設計.用戶可以通過運行CLI版本的游戲了解AI的整體架構.AI設計策略:一切以程序的運行速度為優(yōu)先考量.為了說明采用這種編碼方式的理由,可以先看一下AI設計完成之后,作者做的一組統(tǒng)計:開局第一

16、步,共有44種走法,作者統(tǒng)計了不同搜索策略走第一步棋時搜索到的葉結點數(shù)目,這里的葉結點數(shù)是指真正會去做局面評估的葉結點.被剪枝的葉結點不在其中.未經走法排序的Alpha-Beta搜索各搜索深度實際搜索葉節(jié)點數(shù)如下表表3.1 Alpha-Beta節(jié)點數(shù)搜索深度1234567結點數(shù)441131277713080466844627速度無法接受速度無法接受經過走法排序后的Alpha-Beta搜索各搜索深度實際搜索葉節(jié)點數(shù)如下表：表3.2 實際搜索葉節(jié)點數(shù)搜索深度1234567結點數(shù)4484166013653136914970891速度無法接受經過走法排序后采用PVS算法的搜索策略各搜索深度實際搜索葉節(jié)

17、點數(shù)如下表：表3.3 pvs搜索深度1234567結點數(shù)44841660120901140808894126482373將上表中走法排序后再reverse一次后的PVS搜索策略各搜索深度實際搜索葉節(jié)點數(shù)如下表：表3.4 reverse一次后的PVS搜索策略各搜索深度實際搜索葉節(jié)點數(shù)搜索深度1234567結點數(shù)48206372295151964014700791速度無法接受速度無法接受注:PVS算法為先用小窗口的alpha-beta試探,若試探失敗,則重新進行搜索.所以排序排的不好,可能訪問結點數(shù)大于實際結點數(shù),如第三張表中搜索深度為1時,實際有44中走法,卻訪問了48個結點.上表中各種搜索策略

18、文檔后面會詳述,但是用戶可以很直觀的感受到:(1)不同搜索策略搜索效率差別很大,甚至可以是數(shù)量級上的差異.(2)搜索量隨搜索深度指數(shù)上升.因而AI部分屬于高計算量的程序,微小的速度差異會在大量的計算過程中被放大.AI的實質是數(shù)學上的決策過程.因而在AI部分編碼過程中,沒有采用面向對象的設計風格。因為AI思考的過程本質上是計算過程而非事件直接消息傳遞的模型。同時,具體實現(xiàn)上,大量的采用輔助數(shù)組等冗余數(shù)據結構，以空間換時間。函數(shù)的參數(shù)通過全局變量傳遞/引用傳遞而非值傳遞傳遞.分支結構盡量采用switch-case結構而非if-else結構.GUIGUI部分的設計包括一個進場畫面，選擇對戰(zhàn)模式，以及

19、實際游戲的棋盤。進場畫面選擇了一個戰(zhàn)爭的場面，因為象棋是模擬戰(zhàn)爭的游戲。棋盤沒有采用一般的象棋的木質擬物設計，而是自己手繪設計了棋盤。棋子也經過重新設計。紅方采用瘦金體，而黑方則采用顏體楷書。進場畫面為游戲三國策壁紙，棋盤采用ipad上的app “Paper”繪制。3.2 系統(tǒng)總體設計3.2.1 設計思想AI與GUI部分分別完成,通過接口實現(xiàn)通信.AI部分AI部分采用bottom-up的方法設計,包括局面表示/走法生成/局面評估/將軍檢測/搜索算法.AI部分代碼在kernel文件夾中.kernel文件夾中代碼的組織與AI的結構同構.表征局面的數(shù)據結構以及其他一些全局變量在global.h中聲明

20、,在define_global.cpp中定義.move文件夾中為走法生成的函數(shù).check文件夾中為將軍檢測函數(shù).eval文件夾中為局面評估函數(shù).search文件夾中為搜索函數(shù).每個文件夾中都有test.cpp及makefile,為相應函數(shù)的測試代碼.用戶可到相應文件夾中運行make,然后執(zhí)行可執(zhí)行文件查看測試結果(makefile在linux環(huán)境下寫成)AI部分概述:以長度為256的一維數(shù)組表示棋盤,其中90個數(shù)字表征棋盤,其余部分為冗余數(shù)據,置零.棋盤的表示還有相關冗余數(shù)據結構. 棋子以數(shù)字編碼.走法生成函數(shù)生成走法,搜索算法調用評估函數(shù),給出局面估值及最佳走法.搜索基于alpha-bet

21、a剪枝算法.剪枝效率與遍歷走法棧的順序關系很大,因此生成走法時按照一定規(guī)則對走法棧排序.還采用了PVS算法對alpha-beta算法進行優(yōu)化.GUI部分/*/3.2.2 系統(tǒng)體系結構分為AI部分，AI部分沒有使用面向對象的方法，只以文字說明。GUI部分有類圖等描述(一)局面表示建議用戶閱讀global.h頭文件.其他文件中的代碼大抵知道函數(shù)功能即可.表征局面/走法等的數(shù)據結構均在global.h中聲明,在define_global.cpp中定義.其中 short side表示當前走棋一方,side=0,表示紅方,side=1,表示黑方.局面的表征主要通過兩個數(shù)組，棋盤數(shù)組board和棋子數(shù)組p

22、iece，這兩個數(shù)組是等價的，在AI思考過程中保持同步。之所以設置兩個數(shù)組，是因為不同情況下使用不同數(shù)組更加方便或者運算速度更高。采用short board256 表征棋盤,非棋盤位置0.棋盤上無棋子的位置也為0.采用256長度的數(shù)組,可以方便的像使用二位數(shù)組那樣使用一維數(shù)組,如想要表征第三行第四列,只需使用board0 x34即可.對每一個棋子,有一個(對兵來說,有兩個,紅黑有別)合法位置數(shù)組,也是長256的一維數(shù)組.若棋盤上的一個位置是該棋子的合法位置,則為1,否則則為0.棋子在board數(shù)組中位置為board數(shù)組元素下標。棋盤為9*10，因此是嵌在board數(shù)組中。如圖所示3.1： 圖3

23、.1 棋子對于棋子，用不同數(shù)字表示不同棋子，一個編碼數(shù)字與一枚棋子一一對應，編碼如下表：表3.5 棋子編碼紅方帥仕相馬車炮兵表示數(shù)1617,1819,2021,2223,2425,2627,28,29,30,31黑方將士象馬車炮卒表示數(shù)3233,3435,3637,3839,4041,4243,44,45,46,47如此，譬如紅方將一開始是在上圖中c7位置處，則有board0 xc7=16。這樣編碼的好處：令side_tag=(side=0 ? 16 :32)則紅方編碼 & 16 =16, 紅方編碼 & 32=0,黑方編碼 & 16 = 0, 黑方編碼 & 32 =32,則可非常方便快速的判定

24、棋子顏色.生成走法棧時,經常需要遍歷所有棋子,遍歷棋盤數(shù)組上10*9的棋盤是非常不經濟的.因此在棋盤數(shù)組之外引入一個等價的冗余數(shù)組棋子數(shù)組short piece48, 其中下標015無意義.下標1631表征棋子編碼為1631的棋子(即紅方棋子)在棋盤上的位置.3247表征棋子編碼為3247(即黑方)棋子在棋盤上的位置.如此，譬如紅方將一開始是在上圖中c7位置處，則有piece16=0 xc7;piece數(shù)組初始化如下圖:圖3.2 piece數(shù)組board數(shù)組初始化如下圖： 圖3.3 bord數(shù)組初始化(二)走法生成中國象棋中，除了車和炮之外，其他棋子的走法都有棋盤上的固定增量(行增量，列增量)

25、，因此比較容易處理。如紅方過河的兵，有三個增量(-0 x10,+0 x01,-0 x01)，分別對應向前、向右和向左。則對每一個棋子，設置增量數(shù)組，除兵以外的棋子紅方黑方增量數(shù)組可以公用，除此之外，還要設置合法性數(shù)組，如將的合法區(qū)域只能在九宮格內。對于象和馬，還要確定馬腿、香眼的增量數(shù)組。先介紹相關數(shù)據定義，在介紹相關函數(shù)。首先定義了一個mov的class,表征一個走法，在global.h中。如下圖所示：圖3.4 定義Short from為走法起始的棋盤位置,即棋子在board的下標. to為走法目的地址對應棋盤位置. capture為該走法所吃子的棋子編碼,若走法未吃子,則capture等于

26、0.重載了大于號操作符,在生成vectorMove_array時會調用sort函數(shù)排序.至于為何排序,以何種依據排序,排序的目的與好處,將會在介紹評估函數(shù)與搜索結點策略時再講到.定義了走法生成時每個棋子的輔助數(shù)組,因為數(shù)組結構相似,只以馬和兵為例進行說明.其他棋子的輔助數(shù)組可閱讀global.h。馬的輔助數(shù)組定義如下圖所示：圖3.5 馬const short Horse_direction8:倘使已知一個馬在board數(shù)組中的位置,則它一共有八個可走的方向,8個方向存在Horse_directoin數(shù)組中,舉個例子,馬要向上走兩格后向右走一格(走一個日字形,方向為由紅方向黑方),在棋子數(shù)組上,

27、向上走兩格為-0 x20,向右走一格為+01,則新的位置可如下計算:new_pos=now_pos-0 x1f. Horse_direction中存的是馬走到的新位置相對于舊位置的偏移量.Horse_leg:理解了Horse_direction之后,Horse_leg數(shù)組的定義也容易理解,即馬腿位置相對于當前位置的偏移量.Horse_leg的下標與Horse_direction的下標一一對應,即Horse_legi是Horse_directioni這一走法對應的馬腿位置.Horse_legal數(shù)組為馬在棋盤上的合法位置,馬可以踏遍整個棋盤,因而整個棋盤都是合法位置.兵的輔助數(shù)組如下圖所示:圖3

28、.6 兵數(shù)組的意義與馬的數(shù)組名意義相同,一個為direction數(shù)組,一個為legal數(shù)組.不同的是,兵的紅黑雙方數(shù)組不同,紅方只能向黑方走,黑方只能向紅方走,因而定義了一個二維數(shù)組.接下來講述相關函數(shù)的作用：Move.cpp中定義了兩個函數(shù):void Save_move(short from,short to,vector& Move_array)函數(shù).此函數(shù)接受兩個整數(shù)表示的位置值,生成一個mov類型的變量,檢測這個走法是否會造成本方(通過side判斷)被將軍.若不會被將軍,則將這個mov類型的變量push進Move_array中.Void Gen_All_Move(vector& Mov

29、e_array)函數(shù),接受一個vector&的變量,生成當前局面當前方的所有合法且不會被將軍的走法,所有走法保存進Move_array中,在按照class mov定義中重載的大于號操作符對Move_array進行排序.move文件夾中其他代碼文件,為特定棋子的走法生成函數(shù),如chariot_move.cpp,就是生成當前局面當前方的車的所有可能走法,并push進Move_array中去.Gen_All_Move函數(shù)就是通過調用這些函數(shù)來完成走法生成功能.(三)將軍檢測將軍檢測功能的相關函數(shù)在check文件夾中.checkmate.cpp調用check文件夾中的其他函數(shù),檢測當前方(檢查side

30、)/當前局面(檢查地方的攻擊性棋子)是否本方被將軍.若是返回true,否則返回false.可以造成將軍的棋子有對方的車/對方的馬/對方的兵/對方的炮,另外,有不能對將的規(guī)定.因而對general/chariot/cannon/horse/soldier這五類棋子各寫了一個檢測函數(shù),它們都被checkmate.cpp中的bool checkmate()調用.(四)局面評估局面評估函數(shù)是一個象棋AI的核心,直接決定AI的智能程度,如曾經戰(zhàn)勝卡斯帕羅夫的IBM的”深藍”計算機,它的國際象棋博弈程序的評估函數(shù)有4000多個參數(shù).毫無疑問,評估函數(shù)越復雜,AI就越智能,但是在搜索過程中,對搜索到的葉結點

31、會做局面評估,局面評估函數(shù)越復雜,搜索速度就越慢,搜索層數(shù)就越少.因此必須在搜索速度與評估函數(shù)智能程度之間作出權衡.本程序采用棋子固定權值結合棋子位置權值的評估策略.棋子固定權值即依照經驗為不同的棋子設定一個固定的權值,在global.h中定義const數(shù)組piece_weight存儲,數(shù)組長度48,前16位無意義,之后數(shù)組下標與跟下標編碼相同的棋子一一對應.piece_weight定義如下:圖3.7 piece weight定義棋子將仕象馬車炮兵權值10000200200400900450100在class mov的定義中,重載的大于號操作符就是判斷兩個走法的被吃子的權值比較.棋子位置分值為

32、認定不同棋子在棋盤不同位置的價值是不一樣的,一個顯而易見的例子是,兵到了對方的九宮格內之后,價值會大大增加.對每種棋子,設置長256的pos_weight數(shù)組表征其位置分值.其中,將/仕/象/紅黑雙方數(shù)組可共用,兵/車/馬/炮需要為紅黑雙方各設置一個位置分值數(shù)組.以將/馬為例,其他數(shù)組用戶可自行閱讀global.h將的位置分值如下圖：圖3.8 將紅馬的位置分值:圖3.9 紅馬可以看出,靠近黑方九宮格的位置,權值較高黑馬的位置分值:圖3.9 黑馬通過以上輔助數(shù)組,我們現(xiàn)在可以評估一個局面,遍歷piece數(shù)組中的棋子,對每個棋子,其分值為固定分值加上位置分值,進一步將紅方棋子分值求和,黑方棋子分值

33、求和,若side=0,則返回(red_value-black_value),若side=1,則返回(black_value-red_value).(五) Alpha-Beta搜索采用深度優(yōu)先搜索,配合Alpha-Beta剪枝策略.相關代碼在search文件夾中,包括Alpha-Beta.cpp/PVS.cpp/try_move.cppAlpha-Beta.cpp中定義了int search(short depth,int alpha,int beta)根據傳入參數(shù)搜索深度進行搜索,給出當前局面搜索后的評分,但是并不產生最優(yōu)走法.Alpha-Beta搜索的剪枝效率對搜索的順序十分敏感,若走法棧中

34、好的走法排在前面,則剪枝效率高,因此在走法生成部分對走法按照被吃子的固定權值進行了排序.明顯提高了剪枝效率.try_move.cpp中定義了void Make_move(mov mv)與Un_move(mov mv)函數(shù),分別是根據當前局面與傳入的mov類型的走法數(shù)據,執(zhí)行一步走法,更改board數(shù)組與piece數(shù)組.void Un_make(mov mv)則是撤銷一步走法.最優(yōu)走法的生成在PVS.cpp中定義的int PVS(short depth,int alpha,int beta)函數(shù)中產生.其基本思想是這樣的:走法經過排序后,可以假設最優(yōu)走法出現(xiàn)在走法棧的起始位置處,則在對Move_

35、array進行遍歷/搜索時,可以先假定Move_array0就是最優(yōu)走法.則對其他的走法,先進行一個窗口寬度為0的alpha-beta搜索( search(depth-1,-alpha-1,-alpha) ),根據返回的結果判定假設是否成立,若假設不成立,則再進行一次正常的alpha-beta搜索.PVS算法根據當前局面,返回對當前方(根據side判斷)的局面評分,并更改一個聲明在global.h中的全局變量mov best_move. best_move被GUI程序調用,即機器要作出的走法.(六)GUI部分類圖描述如下圖：圖3.10 類圖主要的類有Choose，info和MainWindow

36、三個，分別繼承自QDialog，QDialog和QMainwindow。其中MainWindow是最為主要的一個類，具體介紹見后文的“主要的類”。3.2.3 系統(tǒng)動態(tài)行為順序圖如下圖所示（以人機對弈為例）圖3.11 順序圖對應的狀態(tài)圖為：圖3.12 狀態(tài)圖3.3 用戶界面設計用戶界面如下圖所示：圖3.13 主界面此為程序打開的第一個界面，兩個按鈕來選擇對戰(zhàn)模式。選擇模式后進入下圖所示的主界面:圖3.14 界面主程序界面主要包括這樣幾部分：棋盤，棋盤背景，棋子，三個功能按鈕和一個提示消息。另外在走棋過程中，為了方便觀察AI行棋，給出了用于定位走法的邊框。如果出現(xiàn)吃子，將在走棋提示的文字下方顯示被

37、吃掉的棋子。若用戶的走法為非法，則不予執(zhí)行，同時，若對方將軍，則必須應將。3.4 系統(tǒng)部件AI部分AI部分沒有采用面向對象的方法,走法棧生成/局面評價/搜索剪枝均通過相關函數(shù)的定義來實現(xiàn).通過改變全局變量board數(shù)組與全局變量piece數(shù)組來刷新棋盤.以下為相關函數(shù)的詳述:kernel/board.cpp中:定義了兩個函數(shù),string get_piece(short &piece_num)/void display(),用于CLI版本的游戲中打印棋盤,只是相當于打印board數(shù)組而已,無技術含量,不講.kernel/define_global.cpp:global.cpp中聲明的全局變量均

38、在此處定義.走法生成分為3部分,每個棋子的走法生成函數(shù)/走法保存函數(shù)/走法棧生成函數(shù).對應棋盤上當前走棋方的所有棋子,調用其 棋子走法生成函數(shù),生成走法并保存人走法棧.下面介紹馬的走法生成函數(shù)Horse_move()/Save_move/Gen_All_Move()這三個函數(shù),其他棋子的走法生成函數(shù)與馬的走法生成函數(shù)相類似.Horse_move():函數(shù)參數(shù):馬的當前位置pos,表征當前走棋方的Side_tag,/*Side_tag=(side=0 ? 16 :32) */走法棧向量的引用 vector& Move_array輸出:無返回值輸出,將走法(mov類型變量push進Move_arr

39、ay中)偽代碼:對馬的8個可走方向:leg=pos+Horse_legi;next=pos+Horse_directioni;如果next是合法位置:如果沒有馬腿:如果next位置上沒有本方的棋子保存走法;/#Save_move()函數(shù)參數(shù):整數(shù)類型的走法起始位置from;整數(shù)類型的走法終點位置to;走法棧引用vector& Move_array;函數(shù)輸出:無返回值輸出;改變Move_array;偽代碼:capture=boardto/確定被吃棋子的編碼;mov mv=from,to,capture;/定義一個mv變量,對應傳入的走法Make_move(mv)/*走一步這個走法,更新board

40、數(shù)組與piece數(shù)組,同時side=1-side(因為一方走棋后輪到另一方走棋,side也會變*/side=1-side/將side改回本方check=checkmate()/檢查這一步走出后是否會將軍side=1-side/再次更改sideUnmove(mv)/撤銷走法,更新board數(shù)組,piece數(shù)組,更改side如果沒有被將軍:Move_array.push_back(mv);#Gen_all_move()函數(shù)參數(shù):走法棧向量引用vector& Move_array;全局變量side/board/piece/函數(shù)輸出:無返回值輸出.更新Move_array;偽代碼:對本方的每一個棋子:

41、如果該棋子還在棋盤上沒有被吃掉:生成該棋子走法;對生成的走法棧排序;將軍檢測將軍檢測部分的代碼在kernel/check文件夾中。包括對將、兵、車、馬、炮的檢查函數(shù)。最后在checkmate.cpp中定義的bool checkmate() 函數(shù)調用這些檢測函數(shù)。下面給出checkmate()和馬的檢測函數(shù)check_horse()的偽代碼。將、兵、車、炮的算法用戶可自行閱讀源代碼。checkmate()函數(shù)輸入：無參數(shù)傳入。函數(shù)輸出：若當前方被將軍，則返回true，否則返回false.偽代碼代碼本身太簡單，直接貼代碼吧。check_horse()函數(shù)輸入：無，檢查side以及board數(shù)組，p

42、iece數(shù)組。函數(shù)輸出：若當前方被對方馬將軍，則返回true，否則返回false.偽代碼：my_general=(side=0 ? piece16 : piece32);/確定己方將的位置。enemy_horse2=piece5+(side=0 ? 32 :16),piece6+(side=0 ? 32 : 16);/確定敵方馬的位置，piece的下標與棋子的編碼一一對應。for(i=0;i2;i+)pos=enemy_horsei;if(pos)/若馬沒有被吃掉for(k=0;kalpha，則更新alpha，搜索過程中搜索到了大于beta的值，則剪枝。alpha-beta搜索的偽代碼如下：函

43、數(shù)形式 ：int search(short depth, int alpha, int beta);輸入：搜索深度depth， alpha,beta;輸出:最佳走法對應的走法估值，并不更新全局變量mov best_move;偽代碼：if(depth=0)return 局面評估值定義走法棧vector Move_array;定義評估值int value;生成所有走法;若走法棧為空返回負無窮;/*說明已經被將死*/對每一種走法，遍歷：執(zhí)行走法;value= -1 * search(depth-1,-beta,-alpha);撤銷走法;if(value =beta)return beta;if(va

44、lue alpha)alpha=value;return alpha;alpha-beta搜索的效率高低取決于剪枝的效率。剪枝的條件是value=beta，估值越高，越有可能引起剪枝，因此，在走法生成時，按照被吃子的固定權值對走法排序。大大提高了剪枝效率，使得可接受的搜索深度由5提高到6。search調用時，alpha取負無窮，beta取正無窮。PVS搜索算法：在走法生成時，走法已經經過排序，以提高剪枝的效率。我們可以如下假設，經過排序后，第一個走法就剛好是最好的走法。假定最初的(alpha,beta)=(-100,100)，第一個結點返回的value值為30，則此時(alpha,beta)=

45、(30,100)。若假設成立，則之后的結點的搜索值都不會大于30。則我們以(30,31)作為搜索區(qū)間試探。返回值value可能有3中情況：value=100 說明返回值比原有的beta還大，應該剪枝30value100，說明走法比第一個走法好，假設不成立，應該以(30,100)為區(qū)間重新進行搜索。函數(shù)形式：int PVS(short depth,int alpha,int beta)輸入:搜索深度depth,alpha,beta輸出：改變全局變量best_move,輸出最佳走法對應的局面估值。偽代碼：搜索標志 pv_flag=false;定義走法棧Move_array;定義局面估值value;

46、if(depth=0)return Weight_value();Gen_All_Move(Move_array);if(Move_array.size()=0)return 負無窮;/*已經被將死*/for(i=0; ialpha & value=beta)return value;if(valuealpha)alpha=value;pv_flag=true;if(depth=max_depth)/max_depth為全局變量，主函數(shù)調用pvs時，就是以max_depth為搜索深度best_move=Move_arrayi;return alpha;GUI部分系統(tǒng)開發(fā)過程中，算法和GUI的設

47、計實現(xiàn)幾乎是分開實現(xiàn)的，后期進行整合。在算法部分未使用面向對象的編程方法，大部分是以函數(shù)調用來實現(xiàn)。而GUI部分則較多的應用到了面向對象的方法，同時將某些算法中的函數(shù)納入到了GUI的類中。以下介紹主要的類：圖3.17 主要類Info和Choose繼承自QDialog，分別用來實現(xiàn)彈出的提示窗口和進入程序的選擇窗口。MainWindow繼承自QMainWindow，為主窗口，程序的主要部分均在此實現(xiàn)。接下來介紹各個類的成員：圖3.17 個各類 Choose類中包含有構造函數(shù)和兩個槽，以及兩個button用來選擇模式。圖3.18 Choose類Info類中有一個用于關閉的按鈕和一個用于顯示信息的L

48、abel。圖3.18 info類以上為MainWindow類的公有成員函數(shù)和槽，分別為，構造函數(shù)，刷新界面，電腦走棋，勝負判定的顯示，以及PVS（原為算法中的函數(shù)，由于引進了進度條需要PVS中的數(shù)據對進度條修改，所以將PVS納入MainWindow類），以及負責完成悔棋和重新開局的槽。圖3.19 MainWindow類以上為MainWindow中的私有或保護成員。labelMousePos為界面下方的提示字符（對于用戶沒有用處，早期調試時使用，正式提交可能會刪除）。red和black1，black2為提示棋子位置的邊框，chess32為32個棋子，tips為右側提示走棋方的文字，eat提示被吃

49、掉的棋子。oregret,result,anticheck分別為悔棋，顯示勝負，提醒應將的對話框。Exit,restart, regret三個按鈕分別為位于屏幕右上方退出，重來和悔棋按鈕。Pic34為程序中使用的圖片。Size為每個格子的尺寸，flag為識別鼠標點擊的標志。更新中添加了control變量，為了控制判定勝負后不允許再走棋。Trans為記錄用戶當前走法的一個mov型變量。mousePressEvent和paintEvent分別為鼠標點擊的響應函數(shù)和繪制圖形的函數(shù)。主要函數(shù)：GUI設計中的主要函數(shù)（未列舉的函數(shù)較為簡單，解釋見代碼注釋）：圖3.20 電腦走棋的函數(shù)該函數(shù)為電腦走棋的函

50、數(shù)。為防止走棋過慢，對不同回合數(shù)采用了不同深度的搜索。此函數(shù)主要完成的功能有：電腦走棋，圖標跟蹤，界面刷新，進度條顯示。圖3.21 鼠標響應函數(shù)此函數(shù)為重定義的鼠標響應函數(shù)，其主要功能為響應鼠標在棋盤范圍內的點擊，通過標志flag來判斷走法是否合法，并調用走棋和刷新界面等函數(shù)。更新中將if(m!=0)改為if(m!=0&control=0)用來控制分出勝負后不允許再走棋。為了實現(xiàn)該功能，在dialog-slot.cpp文件中修改了end()函數(shù)。Main.cpp中的三個外部函數(shù)。函數(shù)體較簡單，實現(xiàn)的功能分別為Num:將鼠標點擊的坐標值轉換為棋盤數(shù)組的下標Posx,posy：將棋盤數(shù)組下標轉換為

51、橫縱坐標值方便定位。圖3.22 重定義的paintEvent重定義的paintEvent函數(shù)，進行棋盤繪制。圖3.23 悔棋函數(shù)悔棋函數(shù)。從history向量中pop出兩步歷史走法進行棋盤的重新刷新，同時將被吃掉的棋子顯示出來，清除掉跟蹤棋子的標志。（若history中mov少于兩個，悔棋會被置為不可用）3.5系統(tǒng)出錯處理設計在MainWindow中添加了一個info類型的變量exception，用來在棋子圖片導入失敗的時候顯示圖片導入異常彈窗。再有，將數(shù)組長度設為256，而不是棋盤大小9*10，棋盤周圍用冗余數(shù)組元素包圍，再以legal數(shù)組判定合法性，這樣避免了數(shù)組越界的問題。3.6 后續(xù)可

52、能的更新因為時間限制，許多特性還都沒有引入。之后有機會更新的話可以進一步優(yōu)化搜索算法，應當將alpht-beta搜索算法建立在置換表之上，并引入mtdf算法，還可以使用迭代加深的策略以及可以引入開局庫、殘局庫?？梢岳妹看蜗缕宓臍v史記錄，使AI具有自學習功能，不會被同一種走法將死兩次。 總結經過對整個中國象棋計算機游戲的設計構思以及到代碼的實現(xiàn)，的確讓我學習到很多的東西。在吸取別人的經驗之上，結合自己的理解實現(xiàn)了一個可以人機對弈的中國象棋程32個字節(jié)來表示32個棋子的位置，可以用每個字節(jié)的高四位來表示棋子的橫坐標，用低四位來表示棋子的縱坐標，如果棋子被吃掉了我們可以用棋盤外的數(shù)據來表示。這樣可

53、以省下很多的空間，雖然對于現(xiàn)在的計算機來說這可能是沒必要的，但是這可以使得我們追求思維的精致，體味到科學的嚴謹。而在象棋程序中最重要的就是搜索算法。極大值極小值算法是給解決計算機的思考模式提供了方法，但是它的效率時不高的。而alpha-beta的道路，但它的能力也是有限的，所以我們會用到各種各樣的改進來提高計算機的效率，這就是算法的精妙之處。中國象棋的界面設計借用了MFC框架編程，利用MFC編寫Windows應用程序是十分交流比賽，而象棋巫師為這一標準的制定作出了努力。最后也說到了開局庫，要想建立一個非常理想的開局庫，也就是包含了所有應對走法的開局庫是有一定難度的，只有我們不斷研究使得開局庫更

54、加完善。中國象棋的計算機研究相對于國際象棋來說會晚很多，但是有越來越多的人投入到了中國象棋的研究之中，即使中國象棋的計算機實現(xiàn)現(xiàn)在還不是很成熟，但是在眾多愛好者的共同努力之下，它一定會迅速地發(fā)展，它的理論也會得到完善。參考文獻至少10篇，其中外文至少3篇。格式不能修改。張紅軍至少10篇，其中外文至少3篇。格式不能修改。于超. 博弈算法在中國象棋上的應用D. 中國海洋大學 2011王友政. 基于局勢變化的計算機中國象棋研究D. 東北大學 2008高強. 一種混合博弈樹算法在中國象棋人機博弈中的應用研究D. 大連交通大學 2007謝艷茹. 中國象棋計算機博弈數(shù)據結構與評估函數(shù)的研究和實現(xiàn)D. 西安

55、理工大學 2008任建敏. 中國象棋軟件開局庫和著法生成器的研究D. 燕山大學 2012郭峰. 中國象棋計算機博弈中的判別剪枝搜索研究D. 河北大學 2009Claude E. Shannon.Programming a Computer for Playing Chess. Philosophical Magazine . 1950Chen J R.Chinese Chess Open-game Database Design. . 1997Fang H R.Chinese Chess Endgame Database and Related Applications. . 1996 致謝本

56、人在設計（論文）期間都是在校內的陳俊杰老師全面、具體指導下完成進行的。老師淵博的學識、敏銳的思維、民主而嚴謹?shù)淖黠L使學生受益非淺，并終生難忘。感謝杰普基地的安海龍老師等在畢業(yè)設計工作中給予的幫助。感謝我的學友和朋友對我的關心和幫助。 外文文獻Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950.XXII. Programming a Computer for Playing Chess 1By CLAUDE E. SHANNONBell Telephone Laboratories, Inc., Murray Hill, N.

57、J. 2Received November 8, 19491. INTRODUCTIONThis paper is concerned with the problem of constructing a computing routine or program for a modern general purpose computer which will enable it to play chess. Although perhaps of no practical importance, the question is of theoretical interest, and it i

58、s hoped that a satisfactory solution of this problem will act as a wedge in attacking other problems of a similar nature and of greater significance. Some possibilities in this direction are: -(1)Machines for designing filters, equalizers, etc.(2)Machines for designing relay and switching circuits.(

59、3)Machines which will handle routing of telephone calls based on the individual circumstances rather than by fixed patterns.(4)Machines for performing symbolic (non-numerical) mathematical operations.(5)Machines capable of translating from one language to another.(6)Machines for making strategic dec

60、isions in simplified military operations.(7)Machines capable of orchestrating a melody.(8)Machines capable of logical deduction.It is believed that all of these and many other devices of a similar nature are possible developments in the immediate future. The techniques developed for modern electroni