象棋人機(jī)博弈系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

象棋人機(jī)博弈J設(shè)計(jì)與實(shí)現(xiàn)LGGROUPsystemofficeroom【LGA16H-LGYY-LGUA8Q8-LGA162】班級(jí)031221本科畢業(yè)設(shè)計(jì)論文題目中國(guó)象棋人機(jī)博弈系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)學(xué) 院計(jì)算機(jī)學(xué)院專(zhuān) 業(yè)網(wǎng)絡(luò)工程學(xué)生姓名李盼舒摘要中國(guó)象棋發(fā)展至今已經(jīng)有了幾千年的歷史，是中華民族燦爛的文化瑰寶，它具有濃厚的趣味性，規(guī)則簡(jiǎn)單明了，在中國(guó)已經(jīng)成為了一項(xiàng)普遍的棋類(lèi)運(yùn)動(dòng)，是其他棋類(lèi)遠(yuǎn)遠(yuǎn)無(wú)法比擬的，并且目前，中國(guó)象棋正在往國(guó)外發(fā)展。為了使中國(guó)象棋更加具有趣味性，我們?cè)谙笃宀┺闹屑尤肓巳藱C(jī)交互，實(shí)現(xiàn)了一個(gè)中國(guó)象棋人機(jī)博弈系統(tǒng)，這個(gè)系統(tǒng)是將計(jì)算機(jī)和人工智能結(jié)合起來(lái)的一種電腦游戲。本文研究了中國(guó)象棋在電腦上的局面表示，走棋過(guò)程中走法生成和局面評(píng)估、博弈樹(shù)搜索等一系列的問(wèn)題。通過(guò)visualC++開(kāi)發(fā)平臺(tái)和MFC文檔視圖體系結(jié)構(gòu)實(shí)現(xiàn)了一個(gè)包括人人對(duì)戰(zhàn)、人機(jī)對(duì)戰(zhàn)、殘局保存、讀取殘局、悔棋、還原等功能模塊的中國(guó)象棋人機(jī)博弈系統(tǒng)。本系統(tǒng)為象棋愛(ài)好者提供了一個(gè)平臺(tái)，滿足了玩家對(duì)中國(guó)象棋的基本需求。關(guān)鍵詞：中國(guó)象棋人工智能博弈樹(shù)搜索算法估值函數(shù)ABSTRACTChinesechessisagorgeousculturaltreasureofChinesenationwiththousandsofyearshistory.Ithasakeeninterestandsimpleruleswhichhasbeenapopularchessgameinchinathatcan’tbematchedbyanyotherkindsofchess.What’smore,nowadays,Chinesechessisrapiddevelopmentinforeigncountries.InordertoadvancingtheinterestofChinesechess,weaddhuman-computerinteractionintochess-playingsystem,makingahuman-computerinteractiongamethatisakindofcomputergamewhichhasacombinationofcomputerandartificialintelligence.ThispaperstudiestheproblemofboardpositionofChinesechess,movegenerationandsituationassessment.ItreachesaChinesechessgamesystemwithavarietyoffunctionalmoduleswhichinvolves“manmanbattle”，“man-machinebattle”，thekeepingandreadingoftheend-game,undoingandrestoringthroughVisualC++platformandMFC.ThissystemprovidesaplatformfortheChinesechessenthusiasts.ItcanmeetthebasicneedsofplayerstowardsChinesechess.Keywords:Chinesechessartificialintelligencegameplayingtreealgoritjmevaluatefunction目錄第一章緒論選題的背景和意義近幾十年來(lái)，隨著計(jì)算機(jī)硬件和軟件技術(shù)的飛速發(fā)展，電腦游戲產(chǎn)業(yè)展現(xiàn)出了蓬勃發(fā)展的勢(shì)頭，已經(jīng)變成與音樂(lè)、影視等并駕齊驅(qū)的娛樂(lè)產(chǎn)業(yè)。人們也開(kāi)始對(duì)計(jì)算機(jī)是否可以戰(zhàn)勝人腦產(chǎn)生了興趣。從二十世紀(jì)八十年代起，電腦人工智能開(kāi)始向人類(lèi)智能提出了挑戰(zhàn)，到1997年，IBM研究的超級(jí)電腦擊敗了當(dāng)時(shí)的國(guó)際象棋冠軍，成為人類(lèi)人工智能發(fā)展史上的重要標(biāo)志。人類(lèi)對(duì)于人工智能的探索是從棋類(lèi)開(kāi)始的，研究人工智能的學(xué)者們?cè)?jīng)表示：如果我們要想深入的了解人類(lèi)智能的核心技術(shù)，我們就必須掌握棋類(lèi)的本質(zhì)。中國(guó)象棋從古代流傳至今有了幾千年的歷史，是一種古老的文化，集人類(lèi)科學(xué)、文化、藝術(shù)為一體，有助于開(kāi)發(fā)人的智力，培養(yǎng)人的思維，鍛煉人的毅力，使人更具有競(jìng)爭(zhēng)意識(shí)。并且相比較于國(guó)際象棋，中國(guó)象棋更為復(fù)雜，因此對(duì)中國(guó)象棋人機(jī)博弈問(wèn)題進(jìn)行研究更有意義。如何讓機(jī)器變得智能，可以和人類(lèi)智力進(jìn)行競(jìng)技，是本文研究的一個(gè)重要的問(wèn)題，通過(guò)本文的研究，掌握人工智能的搜索、知識(shí)表示、計(jì)算，在人工智能領(lǐng)域進(jìn)行一個(gè)深度的探索。國(guó)內(nèi)外棋類(lèi)博弈的發(fā)展現(xiàn)狀人類(lèi)對(duì)于機(jī)器棋類(lèi)博弈的研究最早是開(kāi)始于國(guó)際象棋，美國(guó)數(shù)學(xué)家香農(nóng)通過(guò)幾十年的研究，找到了編寫(xiě)國(guó)際象棋程序的方法，他提出了通過(guò)一個(gè)函數(shù)評(píng)估局面的優(yōu)劣，函數(shù)主要考慮一般棋手會(huì)考慮到的一些問(wèn)題，例如：棋子的棋力、棋子在棋盤(pán)上的位置、棋子間的相互制約和棋子的機(jī)動(dòng)性等等。香農(nóng)是國(guó)際象棋博弈理論的先驅(qū)。當(dāng)國(guó)際象棋博弈已經(jīng)發(fā)展到一個(gè)比較成熟的階段，對(duì)中國(guó)象棋博弈的研究才剛剛開(kāi)始。直到1981年，張耀騰發(fā)表了第一篇研究中國(guó)象棋人機(jī)博弈的文章《人造智慧在電腦象棋上的應(yīng)用》。他在他的文章中以殘局做實(shí)驗(yàn)，提出了局面評(píng)估函數(shù)是靜態(tài)子力值、棋子機(jī)動(dòng)性、棋子的位置、威脅和保護(hù)等之和，但是缺乏對(duì)全局的把握。1982廖嘉成發(fā)表的《利用計(jì)算機(jī)象棋的實(shí)驗(yàn)》，其中包括對(duì)開(kāi)局、中局和殘局的研究。1983年周玉龍、黃少龍一起開(kāi)發(fā)的《象棋排局系列軟盤(pán)》系統(tǒng)，實(shí)現(xiàn)了電腦與人的對(duì)弈。這些研究成果為象棋軟件的發(fā)展奠定了基礎(chǔ)。到了九十年代，中國(guó)象棋軟件開(kāi)始發(fā)展起來(lái)了，出現(xiàn)了一些比較著名的象棋軟件，如《中國(guó)象棋》、《將族III》、《象棋水滸戰(zhàn)》、《象棋巫師》等，但是當(dāng)時(shí)的象棋軟件沒(méi)有布局庫(kù)，水平上比較弱。進(jìn)入21世紀(jì)以后，中國(guó)象棋人機(jī)博弈的研究受到越來(lái)越多的關(guān)注，并且隨著計(jì)算機(jī)硬件和軟件水平的不斷提高，象棋軟件得到了很大水平上的提升。目前象棋軟件比較厲害的是《新天機(jī)》、《臺(tái)風(fēng)引擎》、《象棋名手》、《新小蟲(chóng)》等，這些象棋軟件基本上都有計(jì)算能力強(qiáng)，審局比較深入等優(yōu)點(diǎn)，這也是現(xiàn)在中國(guó)象棋計(jì)算機(jī)博弈的正在進(jìn)行進(jìn)一步研究的地方。論文的主要工作本文的主要工作是將人工智能和中國(guó)象棋結(jié)合在一起，通過(guò)MFC文檔視圖體系結(jié)構(gòu)和VisualC++開(kāi)發(fā)工具，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)中國(guó)象棋人機(jī)博弈系統(tǒng)。主要的部分是象棋的界面實(shí)現(xiàn)部分和博弈引擎部分。界面擁有友好人機(jī)交互，主要包括棋盤(pán)、菜單、功能按鈕，提供一些悔棋、還原或者走法顯示之類(lèi)的功能。引擎部分主要是數(shù)據(jù)結(jié)構(gòu)、走法生成、局面評(píng)估和搜索算法，是程序的核心部分。第二章中國(guó)象棋簡(jiǎn)介簡(jiǎn)介中國(guó)象棋歷史悠久，起源于山西沁縣。戰(zhàn)國(guó)時(shí)期，已經(jīng)有了關(guān)于象棋的正式記載，如：《說(shuō)苑》載：“雍門(mén)子周以琴見(jiàn)孟嘗君，說(shuō)：足下千乘之君也，……燕則斗象棋而舞鄭女?！??！冻o?招魂》中有“蓖蔽象棋，有六簿些；分曹并進(jìn)，遒相迫些；成梟而牟，北周象戲，呼五白些?！?。因此在戰(zhàn)國(guó)時(shí)期，象棋就開(kāi)始在貴族中流傳。中國(guó)象棋發(fā)展到唐朝的時(shí)候，發(fā)生了巨大的變化，由原先的戰(zhàn)國(guó)時(shí)期盛行的文博象棋發(fā)展到了有4個(gè)兵種，分別是“將、馬、車(chē)、卒”，剛開(kāi)始，和國(guó)際象棋一樣的，中國(guó)象棋的棋盤(pán)也是由黑白相間的64個(gè)方格組成。后又變成和圍棋一樣的90個(gè)網(wǎng)格點(diǎn)。經(jīng)過(guò)不斷的傳承和演變至宋代，中國(guó)象棋才完全定型。增加了“炮”“象”、“士”這三個(gè)兵種。記載于宋代的《事林廣記》的象棋棋譜是中國(guó)目前所能看到的最早的象棋譜，比西方15世紀(jì)出現(xiàn)的國(guó)際象棋譜早200多年。推翻了“中國(guó)象棋起源于印度”的言論。到了明代，可能為了方便下棋和記憶，才將一方面的“將”改為“帥”，變得和現(xiàn)代中國(guó)象棋一樣了。中國(guó)象棋是一種兩人對(duì)抗游戲，比賽方法類(lèi)似于古代打仗。兩軍對(duì)戰(zhàn)，排列兩邊，有兵、馬、車(chē)、炮，還有將軍和士兵。兵、馬、車(chē)、炮作為主要的力量，將（帥）只待在軍帳中指揮，還有衛(wèi)兵保護(hù)他。棋子在網(wǎng)格的交叉點(diǎn)上移動(dòng)，將對(duì)方的棋子“吃掉”，占領(lǐng)對(duì)方的交叉點(diǎn)，或者直接進(jìn)行移動(dòng)都算走了一著，直到將對(duì)方的“將”或“帥”擒住，分出勝、負(fù)、和，完成對(duì)局。棋盤(pán)和棋子中國(guó)象棋有三十二個(gè)棋子，分為紅黑棋子兩組，紅子十六個(gè)、黑子十六個(gè)，對(duì)弈雙方各一組，棋子的兵種是一樣的，分為七個(gè)兵種：紅方分為：帥（一個(gè)）、仕（兩個(gè)）、相（兩個(gè)）、車(chē)（兩個(gè)）、馬（兩個(gè)）、炮（兩個(gè)）、兵（四個(gè)）；黑方分為將（一個(gè)）、士（兩個(gè)）、象（兩個(gè)）、車(chē)（兩個(gè)）、馬（兩個(gè)）、炮（兩個(gè)）、卒（四個(gè)）。為了區(qū)分紅黑棋子，方便記憶，有四組兵種的名字是不一樣的，其中帥二將、仕二士、相二象、兵二卒，但是它們兩兩間的作用完全相同?！捌灞P(pán)”是棋子的活動(dòng)場(chǎng)所，就一方來(lái)說(shuō)，棋面由五條橫線和九條直線交叉組成。中間中間有一條空白橫道，稱(chēng)為“楚河漢界”，“楚河漢界”將整個(gè)棋盤(pán)分為兩部分，兩部分通過(guò)河界相連，變成了橫十豎九的完整棋盤(pán)，擁有九十個(gè)交叉點(diǎn)，棋子就擺放在這些交叉點(diǎn)上。“河界”中間不標(biāo)直線，棋子跨越“河界”，無(wú)論是直走橫走或斜走均按有線行棋。棋盤(pán)上畫(huà)“米”字形方格的地方，叫做“九宮”，“九宮”是“將帥”的王宮，開(kāi)局時(shí)將就待在王宮的最深處。走棋規(guī)則在中國(guó)象棋中各種棋子的走法是不一樣的，都有自己的規(guī)則，規(guī)則如下：“帥”（將）每一著只許走一步，前進(jìn)、后退、橫走都可以，但不能走出“九宮”。將和帥不準(zhǔn)在同一直線上直接對(duì)面，如一方已先占據(jù)，另一方必須回避?！笆俊保ㄊ耍┟恳徊街豢梢匝貙?duì)角線方向移動(dòng)一點(diǎn)，可進(jìn)不可退，而且只能在王宮內(nèi)移動(dòng)，它是將帥的貼身護(hù)衛(wèi)?！跋蟆保ㄏ啵┎荒茉竭^(guò)河界，每一招斜走兩步，可進(jìn)不可退，稱(chēng)為“象飛田”。另外，如果在移動(dòng)的過(guò)程中“田”中間有棋子，那么象是不能移動(dòng)的，稱(chēng)為“塞象眼”。“馬”只能先水平或垂直移動(dòng)一個(gè)交叉點(diǎn)，然后再像對(duì)角線的方向移動(dòng)（如果第一步水平移動(dòng)時(shí)，只能往移動(dòng)方向的對(duì)角線移動(dòng)；如果第一部是垂直移動(dòng)，則對(duì)角線的移動(dòng)方向不受約束），稱(chēng)為“馬走日”。另外，在理想的狀況下，馬可以隨意移動(dòng)到四周的八個(gè)點(diǎn)，故有〃八面威風(fēng)〃之說(shuō)。但是如果在橫向或者豎向旁邊的交叉點(diǎn)上有別的棋子擋住，馬就無(wú)法往那個(gè)方向移動(dòng)，稱(chēng)為“蹩馬腿”?！败?chē)”可以在水平或著垂直方向移動(dòng)任意個(gè)的點(diǎn)，但是不可以跨子移動(dòng)。一個(gè)車(chē)可以橫向和縱向工控制十七個(gè)點(diǎn)，故有“一車(chē)十子寒”之說(shuō)。“炮”移動(dòng)的方式和車(chē)很差不多，但它必需越過(guò)一個(gè)棋子來(lái)吃掉敵方的一個(gè)棋子，稱(chēng)為“炮打隔子”。“兵”（卒）在過(guò)楚河漢界之前，只能向前面移動(dòng)一點(diǎn)。但是過(guò)了楚河漢界之后，兵除了不允許往后移動(dòng)之外，它可以往左右移動(dòng)了，故有“過(guò)河的卒子頂半個(gè)車(chē)”之說(shuō)。第三章系統(tǒng)分析MFC簡(jiǎn)介本文用到的開(kāi)發(fā)工具是VisualC++,簡(jiǎn)稱(chēng)VC或者VC6.0,是微軟推出的一款C編譯器，將“高級(jí)語(yǔ)言”翻譯為“機(jī)器語(yǔ)言（低級(jí)語(yǔ)言）”的程序。VisualC是一個(gè)功能強(qiáng)大的可視化軟件開(kāi)發(fā)工具。同時(shí)我們用到的是VisualC++下的MFC文檔視圖體系結(jié)構(gòu)，下面我們對(duì)MFC做一個(gè)簡(jiǎn)單的介紹。首先MFC是一個(gè)基礎(chǔ)類(lèi)庫(kù)，這個(gè)庫(kù)中封裝了很多的WinAPI函數(shù)，它的類(lèi)的層次結(jié)構(gòu)如圖:圖MFO類(lèi)層次結(jié)構(gòu)圖由于C++可以繼承類(lèi)支持虛函數(shù)，和由于C++可以繼承類(lèi)過(guò)對(duì)類(lèi)的繼承和擴(kuò)展來(lái)實(shí)現(xiàn)特定SCOarget過(guò)對(duì)類(lèi)的繼承和擴(kuò)展來(lái)實(shí)現(xiàn)特定SCOarget，CDocument另一方面MFC也是由各種類(lèi)構(gòu)成的一個(gè)應(yīng)用程序框架，在VC++下建立一個(gè)新的tc工程的話，件，這些文件構(gòu)成了MicrosoftVisWadC++通過(guò)AppWizard自動(dòng)生成許多的文，是用戶接口的標(biāo)準(zhǔn)實(shí)現(xiàn)方法，程序員需要做的就是通過(guò)生成的接口在這個(gè)輪廓當(dāng)中加入應(yīng)用程序新的tc工程的話，件，這些文件構(gòu)成了MicrosoftVisWadC++通過(guò)AppWizard自動(dòng)生成許多的文，是用戶接口的標(biāo)準(zhǔn)實(shí)現(xiàn)方法，程序員需要做的就是通過(guò)生成的接口在這個(gè)輪廓當(dāng)中加入應(yīng)用程序要實(shí)現(xiàn)的核心內(nèi)容。程序員可以CFrameWndCView通過(guò)資源編輯器設(shè)計(jì)用戶界面和接口，也可以1加代碼。同時(shí) 可以對(duì)工程文件進(jìn)行封裝CMDIFrameWndCMDIchildWnd有CDialog及控過(guò)Cla^Wizard向框架文件中添棋局表示簡(jiǎn)單方便：CMiniFrameWna計(jì)算機(jī)要下棋首先是要讀懂象棋，意思就是要讓計(jì)算機(jī)知道當(dāng)前棋盤(pán)局面（棋盤(pán)上棋子的分布情況）。對(duì)于計(jì)算機(jī)來(lái)說(shuō)，它能讀懂的就是由數(shù)據(jù)結(jié)構(gòu)和算法所組成的程序，所以我們首先要考慮的是用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄棋子和棋子在棋盤(pán)上的位置，用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)表示棋盤(pán)，程序會(huì)產(chǎn)生不同時(shí)間、空間復(fù)雜度。采用10X9的二維數(shù)組來(lái)存取棋盤(pán)信息，是中國(guó)象棋棋局最為簡(jiǎn)單的一種表示方法。二維數(shù)組的每個(gè)元素代表著棋盤(pán)上的一個(gè)節(jié)點(diǎn)，元素的值代表著這個(gè)節(jié)點(diǎn)上放置什么棋子或者沒(méi)有棋子。如果把棋盤(pán)看做是一個(gè)平面坐標(biāo)系，我們可以通過(guò)數(shù)組元素的橫坐標(biāo)和縱坐標(biāo)知道每個(gè)棋子的位置信息。并且在棋盤(pán)上最多32個(gè)棋子，所以可以用一個(gè)32個(gè)字節(jié)的一維數(shù)組表示所有棋子的位置，其中每個(gè)字節(jié)的高4位表示該棋子的橫坐標(biāo)，低4位表示棋子的縱坐標(biāo)。而已經(jīng)被吃掉的棋子用坐標(biāo)范圍以外的數(shù)表示。這樣棋盤(pán)信息就被裝入這32個(gè)字節(jié)中。當(dāng)然也可以把棋盤(pán)看作一維的，每個(gè)元素保存直接的位置信息。上面介紹的兩個(gè)棋盤(pán)表示方法，一個(gè)是基于棋盤(pán)的數(shù)組，一個(gè)是基于棋子的數(shù)組。棋盤(pán)數(shù)組中通過(guò)棋子的位置可以在常數(shù)時(shí)間內(nèi)獲得棋子類(lèi)型，但通過(guò)棋子的類(lèi)型獲得棋子的位置則需要遍歷；在棋子數(shù)組中通過(guò)棋子的類(lèi)型可以在常數(shù)時(shí)間內(nèi)獲得棋子的位置，但通過(guò)棋子的位置獲得棋子的類(lèi)型則很麻煩。如果將兩種棋盤(pán)表示方法結(jié)合起來(lái)，那么我們既可以在常數(shù)時(shí)間內(nèi)由棋子位置獲得棋子類(lèi)型，也可以在常數(shù)時(shí)間內(nèi)由棋子類(lèi)型獲得棋子位置，這就大大提高了搜索的時(shí)間這就是“棋子-棋盤(pán)聯(lián)系數(shù)組”，這是很多改進(jìn)棋盤(pán)的基礎(chǔ)。棋局的表示是整個(gè)程序最基礎(chǔ)的部分，之后所做的工作都要建立在這個(gè)基礎(chǔ)上。走法生成走法生成就是要通過(guò)遍歷產(chǎn)生所有有效的走法，計(jì)算機(jī)通過(guò)程序挑選出最有利的走法，并判斷人類(lèi)棋手的走子是否符合走棋規(guī)則。走法生成在博弈程序中是特別復(fù)雜和耗費(fèi)時(shí)間的部分，只能靠窮舉來(lái)生成所有的走法，同時(shí)為了方便搜索，要將所有生成的走法存入一個(gè)隊(duì)列，并且由于搜索的層數(shù)不同（我們這里將搜索深度定位1-3），還必須將走法所處的層數(shù)也存入隊(duì)列。根據(jù)實(shí)戰(zhàn)統(tǒng)計(jì)，中國(guó)象棋每一步的合法走法大約是五六十中，還可以通過(guò)良好的數(shù)據(jù)結(jié)構(gòu)和走法預(yù)生成來(lái)提高生成速度。走法預(yù)生成是為了提高走法產(chǎn)生的效率，把每種棋子在某一位置的最大可走步建成一個(gè)數(shù)據(jù)庫(kù)，在產(chǎn)生走法時(shí)直接取出數(shù)據(jù)，然后根據(jù)具體的棋局去除不合法的走法，即以空間換時(shí)間的優(yōu)化。走法生成是搜索的前提，優(yōu)化走法生成很大程度上可以提高博弈速度。局面評(píng)估對(duì)于整個(gè)中國(guó)象棋博弈程序來(lái)說(shuō)，如果說(shuō)搜索算法是程序的心臟，那么局面評(píng)估就是程序的大腦，這兩個(gè)部分都是整個(gè)程序的核心。在這里，局面評(píng)估的作用是通過(guò)象棋知識(shí)評(píng)價(jià)當(dāng)前的棋局進(jìn)行好壞的評(píng)價(jià)，通過(guò)一個(gè)函數(shù)將棋局局面進(jìn)行量化，得到一個(gè)估值。，正所謂：“象棋似布陣，點(diǎn)子如點(diǎn)兵”，中國(guó)象棋知識(shí)錯(cuò)綜復(fù)雜，但是在中國(guó)象棋博弈系統(tǒng)中我們要考慮到的棋類(lèi)知識(shí)主要有四點(diǎn)：子力價(jià)值和子力總和：子力價(jià)值是指某一棋子本身所具有的價(jià)值。棋子的子力價(jià)值決定棋子能控制的點(diǎn)位的多少。例如，車(chē)是象棋中實(shí)力最強(qiáng)的棋子，在棋盤(pán)上移動(dòng)與進(jìn)攻都十分方便，所以假設(shè)車(chē)的值為10，那比車(chē)實(shí)力小的馬的值可能就為6,卒值可能就為2等等。但是各個(gè)子力價(jià)值只是參考，而真正能體現(xiàn)棋局優(yōu)劣的是所剩的子力總和，單車(chē)勝不了士象全，而馬炮可以對(duì)抗士象全，所以在評(píng)估局面時(shí)，首先要對(duì)雙方的子力總和進(jìn)行一個(gè)對(duì)比。棋子的位置：棋子的位置是指棋子在棋盤(pán)上的位置及可控的區(qū)域，例如，過(guò)河卒、沉底炮、以及車(chē)占士角等都是較好的棋子位置狀態(tài)，而窩心馬、將離開(kāi)底線等則屬較差的棋子位置狀態(tài)。棋子的機(jī)動(dòng)性：棋子的機(jī)動(dòng)性是指棋子的靈活性。例如，剛開(kāi)局時(shí)，車(chē)的受到的約束較大，移動(dòng)性較差，下棋講究車(chē)早出，故有“輸棋只因出車(chē)遲”之說(shuō)。同樣被四面蹩腳的馬，它是不能移動(dòng)的，所以它的機(jī)動(dòng)性為0.棋子間的關(guān)系：棋子間的關(guān)系在棋局當(dāng)中是非常復(fù)雜的。一個(gè)棋子和其它棋子之間的關(guān)系往往不是一對(duì)一的關(guān)系，例如，一個(gè)炮可能在攻擊完對(duì)方的車(chē)之后被對(duì)方的馬攻擊。估值函數(shù)在程序中，估值函數(shù)的作用是把局面的質(zhì)量量化成為直觀的數(shù)字，估值函數(shù)可以是簡(jiǎn)單的，也可以是復(fù)雜的，這取決于你在程序中加入的知識(shí)的數(shù)量。在中國(guó)象棋博弈程序中，估值函數(shù)就是各種棋類(lèi)知識(shí)綜合考慮計(jì)算之后所得到的值。對(duì)于棋子控制區(qū)域的打分我們也可以根據(jù)已經(jīng)定義好的“控制區(qū)域價(jià)值表”，然后對(duì)其進(jìn)行累加即可。對(duì)于子力的打分，我們可以根據(jù)已經(jīng)定義好的“棋子價(jià)值表”。“棋子價(jià)值表”是由各個(gè)棋子的緊要程度和走法綜合考慮得到的值。在估值函數(shù)中，我們可以用這樣的公式來(lái)計(jì)算一方棋子的子力總和：sideValue（各種棋子的總價(jià)值和）=sum（PieceNum（該種棋子的價(jià)值）*PieceValue（某種棋子的數(shù)量））；對(duì)于棋子的機(jī)動(dòng)性的打分，我們需要給予棋子每種走法一個(gè)值，將每種走法的估值相加，就可以得到每個(gè)棋子的機(jī)動(dòng)性得分。然后可以用下面的表達(dá)式求某一方棋子機(jī)動(dòng)性：Mobility（棋子的靈活性分?jǐn)?shù)）=Sum（MoveNum（某種棋子的合法走法數(shù)量）*MoveValue（該種棋子每一走法的價(jià)值））；通過(guò)遍歷棋盤(pán)，我們可以完成對(duì)控制區(qū)域的打分、子力打分和機(jī)動(dòng)性打分，我們?cè)俑鶕?jù)關(guān)系表來(lái)考察棋子的相互關(guān)系，進(jìn)行棋局棋子關(guān)系打分。分析棋子關(guān)系時(shí)，由于王的特殊性，王一旦被攻擊，那么整個(gè)游戲就結(jié)束了，所以我們要把王拿出來(lái)單獨(dú)考慮。其次，對(duì)其他的棋子，在分析棋子關(guān)系時(shí)，我們要考慮到：當(dāng)攻擊者子力價(jià)值小于被攻擊者子力價(jià)值，攻擊方將愿意換子。例如，一個(gè)馬正受到一個(gè)兵的攻擊，那我被攻擊方將可以直接放棄對(duì)馬的保護(hù)。或者是多對(duì)多的情況，攻擊方的子力總和〈被攻擊方的情況下，攻擊方肯定是愿意直接換子的。所以在程序中我們也考慮到要防止雙方兌子過(guò)快，但是這里并沒(méi)有考慮雙方兌子后局面的變化（要通過(guò)大量的數(shù)據(jù)來(lái)研究重新考慮兌子過(guò)后的局面是否有效），可以在以后的研究中對(duì)引擎進(jìn)行改進(jìn)。估值函數(shù)和博弈性能一般來(lái)說(shuō)博弈系統(tǒng)的性能，速度，棋類(lèi)知識(shí)滿足下面的關(guān)系：Performance（性能）=Speed（速度）XKowledge（知識(shí)）博弈系統(tǒng)的性能基本上取決于估值的速度和所加入的知識(shí)量。但是從客觀的角度來(lái)說(shuō)，并不是完全正相關(guān)的關(guān)系。知識(shí)的量上來(lái)說(shuō)，知識(shí)越多，我們搜索時(shí)考慮的更加全面，所以搜索結(jié)果也是比較優(yōu)的，博弈性能相對(duì)來(lái)說(shuō)就好一些，但是當(dāng)加入的知識(shí)越多時(shí)，搜索的速度就慢下來(lái)了，博弈的性能可能就相對(duì)降低了。所以我們要想獲得性能優(yōu)異的博弈程序，我們必須在速度和知識(shí)二者中間尋求一個(gè)平衡。當(dāng)然，由于估值函數(shù)模塊和其他程序模塊的耦合度并不高，我們可以考慮替換很多的估值函數(shù)，最終給出估值，但是這樣做效率比較低，我們應(yīng)該尋求一種比較好的估值函數(shù)來(lái)提高博弈性能。本文的是終點(diǎn)估值，即到達(dá)葉子節(jié)點(diǎn)時(shí)，使用估值函數(shù)對(duì)它進(jìn)行估值，這種方法思路清晰，容易設(shè)計(jì)。估值函數(shù)的改進(jìn)目前比較常用到的估值函數(shù)的改進(jìn)方法是通過(guò)手工調(diào)整，就是進(jìn)行大量的測(cè)試，通過(guò)仔細(xì)的比對(duì)，通過(guò)自身掌握的棋類(lèi)知識(shí)，比如，從經(jīng)驗(yàn)上可以知道，一個(gè)車(chē)的價(jià)值要比一個(gè)兵大，給車(chē)賦予比兵大的數(shù)值，馬炮則賦予位于其間的值；馬和炮的地位相當(dāng)，給予它們相當(dāng)?shù)臄?shù)值，以避免盲目換子；如果對(duì)弈中使用了一些優(yōu)秀的戰(zhàn)術(shù)配合，那么就給予一定數(shù)值的獎(jiǎng)勵(lì)，等等。將這些經(jīng)驗(yàn)放進(jìn)評(píng)估函數(shù)中反復(fù)對(duì)弈，然后不斷修正參數(shù)，找出一組性能較高的參數(shù)。本文中的估值函數(shù)優(yōu)化方法主要是手工調(diào)整的方法，以后我們對(duì)程序的改進(jìn)可以從機(jī)器智能計(jì)算的方面改進(jìn)。搜索算法搜索算法是整個(gè)程序的核心部分，相當(dāng)于程序的心臟，驅(qū)動(dòng)著整個(gè)程序的運(yùn)行。中國(guó)象棋的博弈樹(shù)十分巨大，因此搜索算法的好壞很大程度上會(huì)影響到計(jì)算機(jī)的下棋水平（搜索的速率越快，我們可以搜索的深度就越深）。目前，計(jì)算機(jī)博弈搜索算法一般是圖搜索策略，分為兩類(lèi)：盲目搜索：又稱(chēng)無(wú)信息搜索或者窮盡搜索，它包括寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索。這種搜索方法會(huì)遍歷整個(gè)博弈樹(shù)（如果是無(wú)限圖的話，那么搜索則永遠(yuǎn)不會(huì)終止），然后才能找到最優(yōu)的路徑，只適用于求解簡(jiǎn)單的問(wèn)題。

這種搜索方法的代表是極大極小值搜索算法。啟發(fā)式搜索：又稱(chēng)為有信息搜索河有序搜索。啟發(fā)式搜索是將一些具體的領(lǐng)域知識(shí)作為啟發(fā)信息，對(duì)博弈樹(shù)上的節(jié)點(diǎn)進(jìn)行有選擇的查找，以簡(jiǎn)化搜索過(guò)程。極大極小值搜索算法極大極小值算法算法是一種最小化對(duì)手最大得益的算法（即一方要做出對(duì)自己最有利的選擇）。這種算法一般用在圍棋、五子棋、象棋等棋類(lèi)程序。結(jié)局有三種可能：勝利、失敗和平局。這個(gè)算法對(duì)戰(zhàn)雙方所考慮的角度是不一樣的，一方總是選擇對(duì)自己最為有利的局面，為另一方總是選擇對(duì)對(duì)方最為不利的局面，其輸贏的總和為0（有點(diǎn)像能量守恒，就像本身兩個(gè)玩家都有1點(diǎn)，最后輸家要將他的1點(diǎn)給贏家，但整體上還是總共有2點(diǎn)）。中國(guó)象棋的博弈樹(shù)很大的，如果用極大極小值算法來(lái)進(jìn)行搜索，我們將必須遍歷整個(gè)博弈樹(shù)，這樣的搜索效率會(huì)很低，搜索量也會(huì)非常的巨大，這個(gè)過(guò)程是不切實(shí)際的，但是如果毫無(wú)選擇的減少搜索的范圍，又會(huì)影響到搜索的結(jié)果，所以我們要考慮用什么方法對(duì)博弈樹(shù)進(jìn)行適當(dāng)?shù)牟眉?，?lái)降低搜索的數(shù)量，這就可以選擇Alpha-Beta剪枝算法，Alpha-Beta剪枝算法可以在不影響搜索精度的條件下大幅減少搜索數(shù)目。Alpha-Beta剪枝搜索Alpha-Beta算法是與極大極小值算法非常相似的算法，AlphaBeta剪枝方法是對(duì)Minimax方法的優(yōu)化，它們產(chǎn)生的結(jié)果是完全相同的，只不過(guò)運(yùn)行效率不一樣。一般來(lái)說(shuō)，下棋雙方對(duì)棋局肯定有著相似的認(rèn)知，那就是你覺(jué)得對(duì)你很糟糕的局面，在你的對(duì)手看來(lái)則是對(duì)他很有利的局面，那么某些局面有可能導(dǎo)致很糟糕的局面的節(jié)點(diǎn)，你根本就沒(méi)有考慮的必要，它只會(huì)把你引向更壞的局面，你應(yīng)該放棄這個(gè)節(jié)點(diǎn)和它的子節(jié)點(diǎn)，這樣一來(lái)就可以縮小博弈樹(shù)，提高搜索速度，這稱(chēng)為“樹(shù)的裁剪”。如圖所示的極大極小樹(shù)片段中，按照極大極小值搜索規(guī)則，從左路分枝MAX 55MIN5

MIN5圖a裁剪樹(shù)的葉節(jié)點(diǎn)倒推得到第一層MAX節(jié)點(diǎn)的值為5,可表示此時(shí)的著法最佳值，記為a,顯然此a值可作為MAX方著法指標(biāo)的下界。在搜索中路分枝時(shí)，因?yàn)榈诙又ǖ倪x擇是取第三層節(jié)點(diǎn)的最小值，即取Min（8,3，“口”），而無(wú)論“口”中為何值，都不會(huì)比5大（最大為3），故可以將“口”表示的節(jié)點(diǎn)及其后繼節(jié)點(diǎn)剪掉，不再考慮此節(jié)點(diǎn)的延伸。同理搜索右路分枝，也可以進(jìn)行剪枝操作，此類(lèi)剪枝稱(chēng)為a-剪枝。MINMAX如圖所示的極大極小樹(shù)段中，5圖點(diǎn)剪樹(shù)各分枝的葉節(jié)點(diǎn)倒〕推得到第一層MIN節(jié)點(diǎn)的值為山可表示此時(shí)對(duì)方著法的鉗制值，記為方可能實(shí)現(xiàn)著法指標(biāo)的上9界。在搜索中路分枝時(shí)，因?yàn)榈诙又ǖ倪x擇是取第MINMAX如圖所示的極大極小樹(shù)段中，5圖點(diǎn)剪樹(shù)各分枝的葉節(jié)點(diǎn)倒〕推得到第一層MIN節(jié)點(diǎn)的值為山可表示此時(shí)對(duì)方著法的鉗制值，記為方可能實(shí)現(xiàn)著法指標(biāo)的上9界。在搜索中路分枝時(shí)，因?yàn)榈诙又ǖ倪x擇是取第n，。。顯然此匕B值可作為MIN三層節(jié)點(diǎn)的最大值，即取MAX（5，12，“O”），而無(wú)論“?！敝袨楹沃担疾粫?huì)比11?。ㄖ辽贋?2），故可以將“。”表示的節(jié)點(diǎn)及其后繼節(jié)點(diǎn)剪掉，不再考慮此節(jié)點(diǎn)的延伸。同理搜索右路分枝，進(jìn)行剪枝操作。此類(lèi)剪枝稱(chēng)為B-剪枝。但是這個(gè)算法嚴(yán)重依賴(lài)于走法的尋找順序。很明顯，搜索空間的大小和第一節(jié)點(diǎn)的估價(jià)值有關(guān)。如果你最先搜到的總是最壞的節(jié)點(diǎn)，那么就不可能找到值比beta還要壞的節(jié)點(diǎn)，就不會(huì)有任何裁剪，該算法會(huì)和極大極小值算法一樣，遍歷整個(gè)博弈樹(shù)，搜索效率很低。但是如果我們最先搜到的總是最好的節(jié)點(diǎn)，這就是Alpha-Beta算法的搜索效率最好的情況。在數(shù)學(xué)的角度來(lái)看，搜索效率能提高到原來(lái)的平方根。在最好的情況下，把搜索的深度設(shè)為d，，節(jié)點(diǎn)的數(shù)量為極大極小值搜索算法的一半。在最壞的情況下，alpha-beta搜索算法和極大極小值搜索算法是一樣的。多大程度的減小搜索空間取決于一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)在有序的節(jié)點(diǎn)列表中如何發(fā)展下去。為了提高搜索的效率，可以調(diào)整子節(jié)點(diǎn)的節(jié)點(diǎn)列表。這就要涉及到啟發(fā)式搜索了。啟發(fā)式搜索及走法排序我們前面介紹的alpha-beta剪枝搜索是極大極小值搜索的改進(jìn)，在一定程度上提高了效率，但是有著明顯的缺點(diǎn)(在上文中有介紹)，如果要提高搜索深度和搜索效率，就要配合搜索過(guò)程中得到的一些啟發(fā)信息。利用啟發(fā)信息來(lái)決定哪一個(gè)是下一步要做擴(kuò)展的節(jié)點(diǎn)，這種搜索總是選擇“最有希望”的節(jié)點(diǎn)來(lái)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。如何快速的找出那個(gè)“最有希望”的節(jié)點(diǎn)，靈活的運(yùn)用啟發(fā)信息，這就需要我們應(yīng)用某些準(zhǔn)則來(lái)重新排列節(jié)點(diǎn)列表中節(jié)點(diǎn)的順序。根據(jù)這些搜索要求，我們出現(xiàn)了一些啟發(fā)式搜索的形式。這些策略加快了搜索的速度。如下：歷史啟發(fā)，在搜索的過(guò)程中，很有可能會(huì)出現(xiàn)一些相似的局面，這些局面可能是前面已經(jīng)出現(xiàn)的，我們可以對(duì)它用估值函數(shù)來(lái)給予這些局面一個(gè)估值，但現(xiàn)在我們有一種更好的辦法可以快速判斷這些局面是否還有繼續(xù)下去的可能性。歷史啟發(fā)這種搜索策略就是在搜索的過(guò)程中，如果產(chǎn)生比較好的走法，那么如果以后產(chǎn)生相似的局面，這些走法也是比較好的，所以我們可以將這些走法存儲(chǔ)下來(lái)，并給予一個(gè)參數(shù)來(lái)記錄它的得分，稱(chēng)為歷史得分，這些局面出現(xiàn)的次數(shù)越多它的歷史得分就越高。當(dāng)我們進(jìn)行一個(gè)新的局面評(píng)估時(shí)，我們要對(duì)它們進(jìn)行排列，并且保證歷史得分最高的在前面，這樣就可以盡快的進(jìn)行alpha-beta裁剪，提高搜索速率。殺手啟發(fā)，這種搜索策略是一種特殊的歷史啟發(fā)，和歷史啟發(fā)不同的是殺手啟發(fā)優(yōu)先搜索造成每一層剪枝最多的走法。在搜索的過(guò)程中，有一些走法很糟糕，它如果被搜索到就會(huì)被剪掉。將這些走法記錄下來(lái)，當(dāng)下一次搜索到同一層時(shí)，如果殺手走法是當(dāng)前局面的一個(gè)合理走法，那就優(yōu)先搜索殺手節(jié)點(diǎn)，然后將其裁剪掉。置換表，這種搜索策略是將搜索過(guò)程中的搜索信息記錄下來(lái)。在以后的搜索中，如果搜索到的節(jié)點(diǎn)在記錄表中已有記錄，那就可以直接引用記錄。置換表搜索策略和以上兩個(gè)搜索策略不同的地方是，這個(gè)搜索策略不需要清空記錄表，而是一直保存，為以后所用。在本文文中，我們采用的歷史啟發(fā)這個(gè)搜索策略。我們可以使用各種排序算法對(duì)于走法進(jìn)行排序，在此程序中采用了歸并排序。歸并排序的時(shí)間復(fù)雜度為O(nlog2n)，空間復(fù)雜度為O(n)，具有較高的效率。

第四章系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)系統(tǒng)的整體規(guī)劃我們?cè)趯?duì)象棋博弈系統(tǒng)的做了一個(gè)需求分析后進(jìn)行了功能設(shè)計(jì)，這個(gè)象棋博弈系統(tǒng)應(yīng)該具備的功能是人機(jī)對(duì)戰(zhàn)、殘局的保存和讀取功能、悔棋和還原功能、走法顯示功能。功能結(jié)構(gòu)圖如圖所示：用戶界面圖功能結(jié)構(gòu)圖人人對(duì)戰(zhàn)象棋界面的實(shí)現(xiàn)"對(duì)戰(zhàn)本文的界面實(shí)現(xiàn)用的是MFC人人對(duì)戰(zhàn)象棋界面的實(shí)現(xiàn)"對(duì)戰(zhàn)本文的界面實(shí)現(xiàn)用的是MFC類(lèi)庫(kù)，只需建立一個(gè)基于對(duì)話框的MFC應(yīng)用程序然后添加或者刪掉，主要分布為兩一些還原欄工具"以了，保存嚇。/ ―示讀取界面初始化部分OnInitDialog()函數(shù)負(fù)責(zé)的是對(duì)話框的初始化，同時(shí)也可以把中國(guó)象棋博弈程序相關(guān)內(nèi)容進(jìn)行初始化。相關(guān)內(nèi)容包括：對(duì)棋盤(pán)上棋子位置的初始化；對(duì)程序輔助部分所用到的一些變量的初始化。包括對(duì)悔棋、還原隊(duì)列的清空，棋盤(pán)、棋子樣式的默認(rèn)形式，下棋模式的默認(rèn)選擇，以及走法名稱(chēng)列表的初始化等等。界面繪圖部分MakeBoard()函數(shù)和MB_DrawStar()函數(shù)是完成棋盤(pán)界面的繪圖，OnPaint()函數(shù)是完成棋盤(pán)界面上棋子的顯示;這三個(gè)函數(shù)完成了程序界面棋盤(pán)、和走法名稱(chēng)的顯示。OnPaint()函數(shù)主要貼表示棋子的位圖；MakeBoard()函數(shù)是畫(huà)棋盤(pán)；MB_DrawStar()是畫(huà)星點(diǎn)(為MakeBoard調(diào)用)。但是位圖只能是矩形的，而棋子是圓形的，直接使用的話會(huì)留下白色的背景框，所以我們要想通過(guò)一些“與”和“異或”操作來(lái)屏蔽掉棋子的背景。棋盤(pán)和棋子通過(guò)數(shù)組連接起來(lái)，形成一個(gè)完整的界面系統(tǒng)。對(duì)弈功能的實(shí)現(xiàn)對(duì)弈功能是整個(gè)博弈系統(tǒng)最主要的功能，本系統(tǒng)包括人人對(duì)戰(zhàn)和人機(jī)對(duì)戰(zhàn)的功能。本系統(tǒng)對(duì)于人人對(duì)戰(zhàn)的實(shí)現(xiàn)是通過(guò)象棋規(guī)則的定義和圖形化的棋子如何在棋盤(pán)上移動(dòng)來(lái)實(shí)現(xiàn)的。Cango（）函數(shù)實(shí)現(xiàn)了對(duì)于棋子走法的定義，根據(jù)棋子走法判斷我們可以定義棋子是否是正確的移動(dòng)，判斷棋子位置是不是合法，是由IsNormal（）函數(shù)實(shí)現(xiàn)的。OnLButtonDown（）函數(shù)和OnLButtonUp（）函數(shù)是用戶動(dòng)作響應(yīng)部分，實(shí)現(xiàn)了棋子在棋盤(pán)上的移動(dòng)。最后由FixManMap（）函數(shù)保存棋盤(pán)狀態(tài)。當(dāng)用戶點(diǎn)擊鼠標(biāo)時(shí)，調(diào)用OnLButtonDown（）函數(shù)，第一個(gè)參數(shù)表示確定左鍵是否按下，第二個(gè)參數(shù)為左鍵按下時(shí)點(diǎn)的位置坐標(biāo)。當(dāng)用戶放開(kāi)鼠標(biāo)是，調(diào)用OnLButtonUp（）函數(shù)，參數(shù)的作用和OnLButtonDown函數(shù)是一樣的。OnLButtonDown函數(shù)里處理的操作是：如果用戶點(diǎn)擊鼠標(biāo)的位置落在己方的棋子上，表示用戶選中了該棋子，下一步將移動(dòng)該子進(jìn)行走棋（也可能用戶下一步將會(huì)選擇己方另外的棋子，總之這一操作會(huì)記錄下用戶所選的將要走的棋子）。OnLButtonUp函數(shù)處理的操作是：如果之前用戶已經(jīng)點(diǎn)擊了棋子，那么就可以移動(dòng)棋子，這是用戶的一次走棋過(guò)程。在收到用戶傳達(dá)的走棋信息后，可先判斷該走法是否合理（是否符合中國(guó)象棋的走棋規(guī)則），如果是合理，則執(zhí)行之，如果不合理，則讓棋子回到它原來(lái)的位置。系統(tǒng)最終的目的是要實(shí)現(xiàn)人機(jī)對(duì)戰(zhàn)，人機(jī)對(duì)戰(zhàn)的核心就是人工智能，本文是通過(guò)上面第三章介紹的技術(shù)實(shí)現(xiàn)人工智能的。實(shí)現(xiàn)電腦走棋的邏輯步驟如圖所示：找到合適

的走法圖人工智能實(shí)現(xiàn)流程圖走法生成部分，EnumList（）函數(shù)列出了當(dāng)前局面的所有走法。估值函數(shù)部分，首先constintManBPlus[2][12][11]規(guī)定了各個(gè)位置的價(jià)值，ManBaseValue[32]規(guī)定了棋子的固定價(jià)值，然后通過(guò)估值函數(shù)Value（），對(duì)走法進(jìn)行估值，判斷那種走法價(jià)值最大，其中ContactV（）函數(shù)是Value（）的子函數(shù)，計(jì)算各個(gè)棋子的活躍度和棋子間的關(guān)系值。搜索部分，通過(guò)搜索找到比較好的走法，這里通過(guò)SubThink（）函數(shù)對(duì)著法進(jìn)行搜索。做完以上的部分后，通過(guò)Think（）函數(shù)找到最佳走法?；谄搴瓦€原功能的實(shí)現(xiàn)悔棋和還原功能是象棋軟件的基本功能。要實(shí)現(xiàn)悔棋和還原的功能，在博弈程序中，我們要建立一個(gè)走法棧（CStepListm_StepList）來(lái)保存每一回合的棋局局面（棋子數(shù)組和棋子位置等等）。還原功能是在悔棋步驟實(shí)現(xiàn)之后才能被激活的，博弈雙方對(duì)戰(zhàn)一個(gè)回合之后，如果沒(méi)有進(jìn)行悔棋，那么還原棧是要清空的。在本文中，OnEditRedo（）函數(shù)實(shí)現(xiàn)了悔棋功能，OnEditUndo（）函數(shù)實(shí)現(xiàn)了還原功能。下面我們將介紹一下悔棋和還原功能的步驟?；谄骞δ軐?shí)現(xiàn)的步驟：下棋回合數(shù)減一；走法棧存儲(chǔ)當(dāng)前的棋局信息，可用于還原步驟；把上一回合的著法名稱(chēng)從走法棧中取出，然后將它顯示成當(dāng)前局面，并將最近的走法從走法棧中刪除掉;將列表框中的最后一列著法名稱(chēng)存儲(chǔ)到著法名稱(chēng)隊(duì)列中，為還原所用。然后從列表框中刪除它。還原功能實(shí)現(xiàn)的步驟：下棋回合數(shù)加一；走法棧存儲(chǔ)當(dāng)前棋局信息，可用于悔棋步驟；從著法隊(duì)列中取出最近一次存儲(chǔ)的著法名稱(chēng)，將這些信息恢復(fù)成棋局局面，并表示出來(lái)；從著法隊(duì)列中取出最近一次存入的著法名稱(chēng)，將其重新顯示到列表框中，并在走法棧中存儲(chǔ)。然后將其從著法名稱(chēng)隊(duì)列中剔除。以上就是悔棋和還原的所有步驟，在用戶界面上可以通過(guò)添加了事件處理函數(shù)的悔棋和還原按鈕來(lái)實(shí)現(xiàn)。文件保存和讀取功能的實(shí)現(xiàn)MFC中文件的讀取和存儲(chǔ)使用的是CFile與CFileDialog類(lèi)。CFileDialog類(lèi)中封裝了windows常用的文件對(duì)話框，這個(gè)類(lèi)提供了一種簡(jiǎn)單的和Windows標(biāo)準(zhǔn)相一致的文件打開(kāi)和文件存儲(chǔ)對(duì)話框功能。在程序中通過(guò)CFileDialog構(gòu)造一個(gè)對(duì)象之后，初始化對(duì)話框控件，然后調(diào)用DoModal成員函數(shù)顯示對(duì)話框并使用戶輸入路徑和文件。OnFileSave（）函數(shù)實(shí)現(xiàn)了棋譜文件的存儲(chǔ)，OnFileOpen（）函數(shù)實(shí)現(xiàn)了棋譜文件的打開(kāi)。著法顯示功能的實(shí)現(xiàn)每當(dāng)用戶或者計(jì)算機(jī)走一步棋時(shí)，就會(huì)按照中國(guó)象棋棋子著法描述規(guī)范在棋盤(pán)界面上的列表框控件（ListBox）中顯示棋子著法，例如：兵三進(jìn)一（用戶），炮8進(jìn)4（電腦）等。在本文中編寫(xiě)了一個(gè)函數(shù)來(lái)獲得著法名稱(chēng)，實(shí)現(xiàn)將被移動(dòng)的棋子的兵種以及棋子的起始坐標(biāo)、終點(diǎn)坐標(biāo)經(jīng)過(guò)一定的計(jì)算轉(zhuǎn)換成標(biāo)準(zhǔn)的中國(guó)象棋著法名稱(chēng)。我們通過(guò)GetStepName（）函數(shù)取得走法名稱(chēng)，然后顯示在ListBox中。當(dāng)列表框中的顯示數(shù)目超過(guò)了顯示范圍，列表框會(huì)自動(dòng)加一個(gè)滾動(dòng)條。程序說(shuō)明是象棋相關(guān)定義，其中包括棋盤(pán)局面和著法的表示。是棋局初始化。是著法生成器，生成當(dāng)前局面某一方所有合法著法。是用于繪制主界面右下角的四個(gè)按鈕。是資源管理。是走法生成存儲(chǔ)。是歷史啟發(fā)，Alpha-Beta搜索之補(bǔ)充，以提高搜索效率。是著法排序，通過(guò)啟發(fā)信息對(duì)節(jié)點(diǎn)列表中節(jié)點(diǎn)進(jìn)行排序，以提高搜索效率。是局面評(píng)估，為某一特定局面進(jìn)行評(píng)分。MoveList.是搜索部分，使用搜索求出最佳著法。系統(tǒng)測(cè)試及實(shí)驗(yàn)結(jié)果系統(tǒng)測(cè)試屬于黑盒類(lèi)測(cè)試，是根據(jù)需求文檔對(duì)軟件的功能和性能進(jìn)行測(cè)試，它不涉及程序的代碼部分，只是通過(guò)不同的硬件和外設(shè)條件進(jìn)行兼容性測(cè)試，通過(guò)測(cè)試用例測(cè)試功能是否滿足需求文檔，通過(guò)測(cè)試軟件對(duì)軟件進(jìn)行壓力測(cè)試等等。我們這里主要是在軟件程序完成時(shí)，在windows7系統(tǒng)環(huán)境下測(cè)試棋子的走法是否是按照中國(guó)象棋的走子規(guī)則是否可以實(shí)現(xiàn)人機(jī)對(duì)弈，是否可以對(duì)參數(shù)進(jìn)行設(shè)置，是否保存和讀取棋譜等等。測(cè)試用例的設(shè)計(jì)，我們可以這樣進(jìn)行設(shè)計(jì)，如表：表測(cè)試用例功能點(diǎn)前置條件動(dòng)作預(yù)期結(jié)果測(cè)試結(jié)果文件保存/點(diǎn)擊保存棋譜文件存儲(chǔ)到電腦棋譜文件存儲(chǔ)到電腦文件讀取電腦有正確的棋譜文件點(diǎn)擊打開(kāi)選取棋譜文件讀取棋譜文件并顯示棋局讀取棋譜文件并顯示棋局文件讀取/點(diǎn)擊打開(kāi)選取其他文件無(wú)法打開(kāi)文件無(wú)法打開(kāi)文件棋子走棋棋盤(pán)上有棋子按照正確的方式走棋棋子可以移動(dòng)棋子可以移動(dòng)棋子走棋棋盤(pán)上有棋子按照不正確的方式走棋棋子不可以移動(dòng)棋子不可以移動(dòng)悔棋已經(jīng)走棋點(diǎn)擊悔棋按鈕棋局回到上一個(gè)局面棋局回到上一個(gè)局面還原悔棋已實(shí)現(xiàn)點(diǎn)擊還原按鈕棋局回到悔棋前局面棋局回到悔棋前局面經(jīng)過(guò)不斷的調(diào)試與修改，我們將中國(guó)象棋博弈程序?qū)崿F(xiàn)出來(lái)了。并且經(jīng)過(guò)系統(tǒng)測(cè)試，該中國(guó)象棋博弈系統(tǒng)完全滿足需求文檔中的功能和性能。首先最重要的功能是可以實(shí)現(xiàn)人機(jī)對(duì)弈，并且所有的棋子可以都按照標(biāo)準(zhǔn)的中國(guó)象棋走子規(guī)則移動(dòng)，其次滿足悔棋和還原的功能，也可以對(duì)參數(shù)進(jìn)行設(shè)置，滿足象棋殘局文件的保存和讀取。如圖是軟件界面的截圖，在界面上所有的功能都一目了然，界面包括棋盤(pán)區(qū)域、走法顯示區(qū)域、悔棋按鈕、還原按鈕，但是可能還存在一些不足之處，如外觀不夠美觀，沒(méi)有音效。圖中國(guó)象棋博弈系統(tǒng)用戶界面截圖圖殘局保存功能截圖如圖是象棋博弈系統(tǒng)的殘局保存功能，在這里我們可以看到我們可以將殘局保存為棋譜類(lèi)型，保存到電腦上，之后可以讀取后再進(jìn)行切磋。如圖是象棋博弈系統(tǒng)的棋譜