畢業(yè)論文-基于QT的中國象棋游戲界面設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

12、搜索無必要.因而設(shè)定前5回合(十步)進(jìn)行5層搜索,5回合之后到25回合(50步)采用6步搜索.若之后用戶仍未被將死.將采用7步搜索.人機(jī)對弈模式中，界面右下方會以進(jìn)度條顯示AI已搜索結(jié)點(diǎn)的比例。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部分測試功能正確后,交由高楠進(jìn)行GUI的實(shí)現(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編寫(二)運(yùn)行環(huán)境在ubuntu13.04及windows7、winXP操作系統(tǒng)下可流暢運(yùn)行.作者測試游戲所用CPU較為低端,游戲運(yùn)行仍較為流暢.用戶所用CPU性能不錯(cuò)的話,可以考慮一開始就將搜索深度設(shè)為6或者7.2.3 系統(tǒng)功能需求可選的對戰(zhàn)模式_雙人對弈或人機(jī)對弈啟動游戲后, 點(diǎn)擊相應(yīng)button,即可選擇相應(yīng)對戰(zhàn)模式。雙人對弈：若選擇雙人對弈功能,則可雙方交替走子. 系統(tǒng)會自動檢測走子的有效性,不合規(guī)則的走子無法走出.若一方勝利,則系統(tǒng)會彈出對話框告知 “bl

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

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

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

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

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

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

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

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

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

23、.1 棋子對于棋子，用不同數(shù)字表示不同棋子，一個(gè)編碼數(shù)字與一枚棋子一一對應(yīng)，編碼如下表：表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í),經(jīng)常需要遍歷所有棋子,遍歷棋盤數(shù)組上10*9的棋盤是非常不經(jīng)濟(jì)的.因此在棋盤數(shù)組之外引入一個(gè)等價(jià)的冗余數(shù)組棋子數(shù)組short piece48, 其中下標(biāo)015無意義.下標(biāo)1631表征棋子編碼為1631的棋子(即紅方棋子)在棋盤上的位置.3247表征棋子編碼為3247(即黑方)棋子在棋盤上的位置.如此，譬如紅方將一開始是在上圖中c7位置處，則有piece16=0 xc7;piece數(shù)組初始化如下圖:圖3.2 piece數(shù)組board數(shù)組初始化如下圖： 圖3.3 bord數(shù)組初始化(二)走法生成中國象棋中，除了車和炮之外，其他棋子的走法都有棋盤上的固定增量(行增量，列增量)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40、數(shù)組與piece數(shù)組,同時(shí)side=1-side(因?yàn)橐环阶咂搴筝喌搅硪环阶咂?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;偽代碼:對本方的每一個(gè)棋子:

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

42、iece數(shù)組。函數(shù)輸出：若當(dāng)前方被對方馬將軍，則返回true，否則返回false.偽代碼：my_general=(side=0 ? piece16 : piece32);/確定己方將的位置。enemy_horse2=piece5+(side=0 ? 32 :16),piece6+(side=0 ? 32 : 16);/確定敵方馬的位置，piece的下標(biāo)與棋子的編碼一一對應(yīng)。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;輸出:最佳走法對應(yīng)的走法估值，并不更新全局變量mov best_move;偽代碼：if(depth=0)return 局面評估值定義走法棧vector Move_array;定義評估值int value;生成所有走法;若走法棧為空返回負(fù)無窮;/*說明已經(jīng)被將死*/對每一種走法，遍歷：執(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，估值越高，越有可能引起剪枝，因此，在走法生成時(shí)，按照被吃子的固定權(quán)值對走法排序。大大提高了剪枝效率，使得可接受的搜索深度由5提高到6。search調(diào)用時(shí)，alpha取負(fù)無窮，beta取正無窮。PVS搜索算法：在走法生成時(shí)，走法已經(jīng)經(jīng)過排序，以提高剪枝的效率。我們可以如下假設(shè)，經(jīng)過排序后，第一個(gè)走法就剛好是最好的走法。假定最初的(alpha,beta)=(-100,100)，第一個(gè)結(jié)點(diǎn)返回的value值為30，則此時(shí)(alpha,beta)=

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

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

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

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

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

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

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

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

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

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

55、理工大學(xué) 2008任建敏. 中國象棋軟件開局庫和著法生成器的研究D. 燕山大學(xué) 2012郭峰. 中國象棋計(jì)算機(jī)博弈中的判別剪枝搜索研究D. 河北大學(xué) 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è)計(jì)（論文）期間都是在校內(nèi)的陳俊杰老師全面、具體指導(dǎo)下完成進(jìn)行的。老師淵博的學(xué)識、敏銳的思維、民主而嚴(yán)謹(jǐn)?shù)淖黠L(fēng)使學(xué)生受益非淺，并終生難忘。感謝杰普基地的安海龍老師等在畢業(yè)設(shè)計(jì)工作中給予的幫助。感謝我的學(xué)友和朋友對我的關(guān)心和幫助。 外文文獻(xiàn)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