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

班級031221學(xué)號03122014夜繆用了彳彳技/冬本科畢業(yè)設(shè)計論文題目中國象棋人機博弈系統(tǒng)的設(shè)計與實現(xiàn)學(xué) 院 計算機學(xué)院 專 業(yè) 網(wǎng)絡(luò)工程 學(xué)生姓名 李盼舒 摘要中國象棋發(fā)展至今已經(jīng)有了幾千年的歷史，是中華民族燦爛的文化瑰寶，它具有濃厚的趣味性，規(guī)則簡單明了，在中國已經(jīng)成為了一項普遍的棋類運動，是其他棋類遠(yuǎn)遠(yuǎn)無法比擬的，并且目前，中國象棋正在往國外發(fā)展。為了使中國象棋更加具有趣味性，我們在象棋博弈中加入了人機交互，實現(xiàn)了一個中國象棋人機博弈系統(tǒng)，這個系統(tǒng)是將計算機和人工智能結(jié)合起來的一種電腦游戲。本文研究了中國象棋在電腦上的局面表示，走棋過程中走法生成和局面評估、博弈樹搜索等一系列的問題。通過visualC++開發(fā)平臺和MFC文檔視圖體系結(jié)構(gòu)實現(xiàn)了一個包括人人對戰(zhàn)、人機對戰(zhàn)、殘局保存、讀取殘局、悔棋、還原等功能模塊的中國象棋人機博弈系統(tǒng)。本系統(tǒng)為象棋愛好者提供了一個平臺，滿足了玩家對中國象棋的基本需求。關(guān)鍵詞：中國象棋人工智能博弈樹搜索算法估值函數(shù)ABSTRACTABSTRACTChinesechessisagorgeousculturaltreasureofChmesenationwiththousandsofyearshistoiyIthasakeenmteiestandsimplemleswhichhasbeenapopularchessgameinchinathatcan'tbematchedbyanyotherkindsofchess.Whafsmore,nowadays,Chinesechessisrapiddevelopmentmforeigncountries.InordertoadvancmgtheinterestofChinesechess,weaddliunian-computefinteiactionmtochess-playingsystem,makingahuman-computerinteractiongamethatisakuidofcomputergamewhichhasacombinationofcomputerandartificialmtelligence.ThispaperstudiesthepioblemofboaidpositionofChinesechess,movegeneiationandsituationassessment.ItreachesaChinesechessgamesystemwithavaiietyoffimctionalmoduleswhichinvolves“man-manbattle“，“man-machinebattle”,thekeepingandreadingoftheend-game,undomgandlestonngtluougliVisualC++platformandMFC.ThissystemprovidesaplatfbnnfortheChinesechessenthusiasts.ItcanmeetthebasicneedsofplayerstowardsClmiesechess.Keywords:Chinesechessartificialintelligencegameplayingtreealgoritjmevaluatefunction目錄TOC\o"1-5"\h\z\o"CurrentDocument"第一章緒論 1\o"CurrentDocument"選題的背景和意義 1\o"CurrentDocument"國內(nèi)外棋類博弈的發(fā)展現(xiàn)狀 1\o"CurrentDocument"3論文的主要工作 2\o"CurrentDocument"第二章中國象棋簡介 3\o"CurrentDocument"1簡介 3\o"CurrentDocument"2棋盤和棋子 3\o"CurrentDocument"3走棋規(guī)則 4\o"CurrentDocument"第三章系統(tǒng)分析 5\o"CurrentDocument"1MFC簡介 5\o"CurrentDocument"2棋局表示 6\o"CurrentDocument"3走法生成 6\o"CurrentDocument"4局面評估 74.1估值函數(shù) 84.2估值函數(shù)和博弈性能 84.3估值函數(shù)的改進(jìn) 9\o"CurrentDocument"5搜索算法 93.5.1極大極小值搜索算法 103.5.2Alpha-Beta剪枝搜索 103.5.3啟發(fā)式搜索及走法排序 12\o"CurrentDocument"第四章系統(tǒng)設(shè)計與實現(xiàn) 15\o"CurrentDocument"1系統(tǒng)的整體規(guī)劃 15\o"CurrentDocument"2象棋界面的實現(xiàn) 15\o"CurrentDocument"3對弈功能的實現(xiàn) 16\o"CurrentDocument"4悔棋和還原功能 17\o"CurrentDocument"5文件保存和讀取功能 18\o"CurrentDocument"6著法顯示功能 18\o"CurrentDocument"程序說明 18\o"CurrentDocument"系統(tǒng)測試及實驗結(jié)果 19\o"CurrentDocument"第五章總結(jié)與展望 23\o"CurrentDocument"致謝 25\o"CurrentDocument"參考文獻(xiàn) 27第一章緒論選題的背景和意義近幾十年來，隨著計算機硬件和軟件技術(shù)的飛速發(fā)展，電腦游戲產(chǎn)業(yè)展現(xiàn)出了蓬勃發(fā)展的勢頭，已經(jīng)變成與音樂、影視等并駕齊驅(qū)的娛樂產(chǎn)業(yè)。人們也開始對計算機是否可以戰(zhàn)勝人腦產(chǎn)生了興趣。從二十世紀(jì)八十年代起，電腦人工智能開始向人類智能提出了挑戰(zhàn)，到1997年，IBM研究的超級電腦擊敗了當(dāng)時的國際象棋冠軍，成為人類人工智能發(fā)展史上的重要標(biāo)志。人類對于人工智能的探索是從棋類開始的，研究人工智能的學(xué)者們曾經(jīng)表示:如果我們要想深入的了解人類智能的核心技術(shù)，我們就必須掌握棋類的本質(zhì)。中國象棋從古代流傳至今有了幾千年的歷史，是一種古老的文化，集人類科學(xué)、文化、藝術(shù)為一體，有助于開發(fā)人的智力，培養(yǎng)人的思維，鍛煉人的毅力，使人更具有競爭意識。并且相比較于國際象棋，中國象棋更為復(fù)雜，因此對中國象棋人機博弈問題進(jìn)行研究更有意義。如何讓機器變得智能，可以和人類智力進(jìn)行競技，是本文研究的一個重要的問題，通過本文的研究，掌握人工智能的搜索、知識表示、計算，在人工智能領(lǐng)域進(jìn)行一個深度的探索。國內(nèi)外棋類博弈的發(fā)展現(xiàn)狀人類對于機器棋類博弈的研究最早是開始于國際象棋，美國數(shù)學(xué)家香農(nóng)通過幾十年的研究，找到了編寫國際象棋程序的方法，他提出了通過一個函數(shù)評估局面的優(yōu)劣，函數(shù)主要考慮一般棋手會考慮到的一些問題，例如：棋子的棋力、棋子在棋盤上的位置、棋子間的相互制約和棋子的機動性等等。香農(nóng)是國際象棋博弈理論的先驅(qū)。當(dāng)國際象棋博弈已經(jīng)發(fā)展到一個比較成熟的階段，對中國象棋博弈的研究才剛剛開始。直到1981年，張耀騰發(fā)表了第一篇研究中國象棋人機博弈的文章《人造智慧在電腦象棋上的應(yīng)用》。他在他的文章中以殘局做實驗，提出了局面評估函數(shù)是靜態(tài)子力值、棋子機動性、棋子的位置、威脅和保護(hù)等之和，但是缺乏對全局的把握。1982廖嘉成發(fā)表的《利用計算機象棋的實驗》，其中包括對開局、中局和殘局的研究。1983年周玉龍、黃少龍一起開發(fā)的《象棋排局系列軟盤》系統(tǒng)，實現(xiàn)了電腦與人的對弈。這些研究成果為象棋軟件的發(fā)展奠定了基礎(chǔ)。到了九十年代，中國象棋軟件開始發(fā)展起來了，出現(xiàn)了一些比較著名的象棋軟件，如《中國象棋》、《將族1H》、《象棋水滸戰(zhàn)》、《象棋巫師》等，但是當(dāng)時的象棋軟件沒有布局庫，水平上比較弱。進(jìn)入21世紀(jì)以后，中國象棋人機博弈的研究受到越來越多的關(guān)注，并且隨著計算機硬件和軟件水平的不斷提高，象棋軟件得到了很大水平上的提升。目前象棋軟件比較厲害的是《新天機》、《臺風(fēng)引擎》、《象棋名手》、《新小蟲》等，這些象棋軟件基本上都有計算能力強，市局比較深入等優(yōu)點，這也是現(xiàn)在中國象棋計算機博弈的正在進(jìn)行進(jìn)一步研究的地方。論文的主要工作本文的主要工作是將人工智能和中國象棋結(jié)合在一起，通過MFC文檔視圖體系結(jié)構(gòu)和VisualC十十開發(fā)工具，設(shè)計并實現(xiàn)一個中國象棋人機博弈系統(tǒng)。主要的部分是象棋的界面實現(xiàn)部分和博弈引擎部分。界面擁有友好人機交互，主要包括棋盤、菜單、功能按鈕，提供一些悔棋、還原或者走法顯示之類的功能。引擎部分主要是數(shù)據(jù)結(jié)構(gòu)、走法生成、局面評估和搜索算法，是程序的核心部分。第二章中國象棋簡介簡介中國象棋歷史悠久，起源于山西沁縣。戰(zhàn)國時期，已經(jīng)有了關(guān)于象棋的正式記載，如：《說苑》載：“雍門子周以琴見孟嘗君，說：足下千乘之君也，……燕則斗象棋而舞鄭女。《楚辭?招魂》中有“薨蔽象棋，有六簿些；分曹并進(jìn)，遒相迫些；成梟而牟，北周象戲，呼五白些。九因此在戰(zhàn)國時期，象棋就開始在貴族中流傳。中國象棋發(fā)展到唐朝的時候，發(fā)生了巨大的變化，由原先的戰(zhàn)國時期盛行的文博象棋發(fā)展到了有4個兵種，分別是“將、馬、車、卒”，剛開始，和國際象棋一樣的，中國象棋的棋盤也是由黑白相間的64個方格組成。后乂變成和圍棋一樣的90個網(wǎng)格點。經(jīng)過不斷的傳承和演變至宋代，中國象棋才完全定型。增加了“炮”“象”、“士”這三個兵種。記載于宋代的《事林廣記》的象棋棋譜是中國目前所能看到的最早的象棋譜，比西方15世紀(jì)出現(xiàn)的國際象棋譜早200多年。推翻了“中國象棋起源于印度”的言論。到了明代，可能為了方便下棋和記憶，才將一方面的“將”改為“帥”，變得和現(xiàn)代中國象棋一樣了。中國象棋是一種兩人對抗游戲，比賽方法類似于古代打仗。兩軍對戰(zhàn)，排列兩邊，有兵、馬、車、炮，還有將軍和士兵。兵、馬、車、炮作為主要的力量，將（帥）只待在軍帳中指揮，還有衛(wèi)兵保護(hù)他。棋子在網(wǎng)格的交叉點上移動，將對方的棋子“吃掉”，占領(lǐng)對方的交叉點，或者直接進(jìn)行移動都算走了一著，直到將對方的“將”或“帥”擒住，分出勝、負(fù)、和，完成對局。棋盤和棋子中國象棋有三十二個棋子，分為紅黑棋子兩組，紅子十六個、黑子十六個，對弈雙方各一組，棋子的兵種是一樣的，分為七個兵種：紅方分為：帥（一個）、仕（兩個）、相（兩個）、車（兩個）、馬（兩個）、炮（兩個）、兵（四個）；黑方分為將（一個）、±（兩個）、象（兩個）、車（兩個）、馬（兩個）、炮（兩個）、卒（四個）。為了區(qū)分紅黑棋子，方便記憶，有四組兵種的名字是不一樣的，其中帥=將、仕=士、相=象、兵=卒，但是它們兩兩間的作用完全相同?！捌灞P”是棋子的活動場所，就一方來說，棋面由五條橫線和九條直線交義組成。中間中間有一條空白橫道，稱為“楚河漢界”，“楚河漢界”將整個棋盤分為兩部分，兩部分通過河界相連，變成了橫十豎九的完整棋盤，擁有九十個交叉點，棋子就擺放在這些交叉點上。“河界”中間不標(biāo)直線，棋子跨越“河界”，無論是直走橫走或斜走均按有線行棋。棋盤上畫“米”字形方格的地方，叫做“九宮”，“九宮”是“將帥”的王宮，開局時將就待在王宮的最深處。走棋規(guī)則在中國象棋中各種棋子的走法是不一樣的，都有自己的規(guī)則，規(guī)則如下：“帥”（將）每一著只許走一步，前進(jìn)、后退、橫走都可以，但不能走出“九宮九將和帥不準(zhǔn)在同一直線上直接對面，如一方已先占據(jù)，另一方必須回避。“士”（仕）每一步只可以沿對角線方向移動一點，可進(jìn)不可退，而且只能在王宮內(nèi)移動，它是將帥的貼身護(hù)衛(wèi)?！跋蟆保ㄏ啵┎荒茉竭^河界，每一招斜走兩步，可進(jìn)不可退，稱為“象飛田”。另外，如果在移動的過程中“田”中間有棋子，那么象是不能移動的，稱為“塞象眼”。“馬”只能先水平或垂直移動一個交叉點，然后再像對角線的方向移動（如果第一步水平移動時，只能往移動方向的對角線移動；如果第一部是垂直移動，則對角線的移動方向不受約束），稱為“馬走日”。另外，在理想的狀況下，馬可以隨意移動到四周的八個點，故有“八面威風(fēng)”之說。但是如果在橫向或者豎向旁邊的交叉點上有別的棋子擋住，馬就無法往那個方向移動，稱為“蹩馬腿”。“車”可以在水平或著垂直方向移動任意個的點，但是不可以跨子移動。一個車可以橫向和縱向工控制十七個點，故有“一車十子寒”之說?！芭凇币苿拥姆绞胶蛙嚭懿畈欢啵匦柙竭^一個棋子來吃掉敵方的一個棋子，稱為“炮打隔子:“兵”（卒）在過楚河漢界之前，只能向前面移動一點。但是過了楚河漢界之后，兵除了不允許往后移動之外，它可以往左右移動了，故有“過河的卒子頂半個車”之說。第三章系統(tǒng)分析MFC簡介本文用到的開發(fā)工具是VisualC++6.0，簡稱VC或者VC6.0,是微軟推出的一款C編譯器，將“高級語言”翻譯為“機器語言（低級語言）”的程序。VisualC是一個功能強大的可視化軟件開發(fā)工具。同時我們用到的是VisualC++下的MFC文檔視圖體系結(jié)構(gòu)，下面我們對MFC做一個簡單的介紹。首先MFC是一個基礎(chǔ)類庫，這個庫中封裝了很多的WinAPI函數(shù)，它的類的層次結(jié)構(gòu)如圖3.1：圖3.1MFC類層次結(jié)構(gòu)圖由于C++可以繼承類，支持虛函數(shù)，和MFC的消息映射機制，程序員可以通過對類的繼承和擴展來實現(xiàn)特定的功能。另一方面MFC也是由各種類構(gòu)成的一個應(yīng)用程序框架，在VC十十下建立一個新的MFC工程的話，MicrosoftVisuaC++通過AppWizard自動生成許多的文件,這些文件構(gòu)成了一個框架，是用戶接口的標(biāo)準(zhǔn)實現(xiàn)方法，程序員需要做的就是通過生成的接口在這個輪廓當(dāng)中加入應(yīng)用程序要實現(xiàn)的核心內(nèi)容。程序員可以通過資源編輯器設(shè)計用戶界面和接口，也可以通過ClassWizaid向框架文件中添加代碼。同時MFC也可以對工程文件進(jìn)行封裝，簡單方便。棋局表示計算機要下棋首先是要讀懂象棋，意思就是要讓計算機知道當(dāng)前棋盤局面（棋盤上棋子的分布情況）。對于計算機來說，它能讀懂的就是由數(shù)據(jù)結(jié)構(gòu)和算法所組成的程序，所以我們首先要考慮的是用什么樣的數(shù)據(jù)結(jié)構(gòu)來記錄棋子和棋子在棋盤上的位置，用不同的數(shù)據(jù)結(jié)構(gòu)來表示棋盤，程序會產(chǎn)生不同時間、空間復(fù)雜度。采用10x9的二維數(shù)組來存取棋盤信息，是中國象棋棋局最為簡單的一種表示方法。二維數(shù)組的每個元素代表著棋盤上的一個節(jié)點，元素的值代表著這個節(jié)點上放置什么棋子或者沒有棋子。如果把棋盤看做是一個平面坐標(biāo)系，我們可以通過數(shù)組元素的橫坐標(biāo)和縱坐標(biāo)知道每個棋子的位置信息。并且在棋盤上最多32個棋子，所以可以用一個32個字節(jié)的一維數(shù)組表示所有棋子的位置，其中每個字節(jié)的高4位表示該棋子的橫坐標(biāo)，低4位表示棋子的縱坐標(biāo)。而已經(jīng)被吃掉的棋子用坐標(biāo)范圍以外的數(shù)表示。這樣棋盤信息就被裝入這32個字節(jié)中。當(dāng)然也可以把棋盤看作一維的，每個元素保存直接的位置信息。上面介紹的兩個棋盤表示方法，一個是基于棋盤的數(shù)組，一個是基于棋子的數(shù)組。棋盤數(shù)組中通過棋子的位置可以在常數(shù)時間內(nèi)獲得棋子類型，但通過棋子的類型獲得棋子的位置則需要遍歷；在棋子數(shù)組中通過棋子的類型可以在常數(shù)時間內(nèi)獲得棋子的位置，但通過棋子的位置獲得棋子的類型則很麻煩。如果將兩種棋盤表示方法結(jié)合起來，那么我們既可以在常數(shù)時間內(nèi)由棋子位置獲得棋子類型,也可以在常數(shù)時間內(nèi)由棋子類型獲得棋子位置，這就大大提高了搜索的時間這就是“棋子-棋盤聯(lián)系數(shù)組”，這是很多改進(jìn)棋盤的基礎(chǔ)。棋局的表示是整個程序最基礎(chǔ)的部分，之后所做的工作都要建立在這個基礎(chǔ)上。走法生成走法生成就是要通過遍歷產(chǎn)生所有有效的走法，計算機通過程序挑選出最有利的走法，并判斷人類棋手的走子是否符合走棋規(guī)則。走法生成在博弈程序中是特別復(fù)雜和耗費時間的部分，只能靠窮舉來生成所有的走法，同時為了方便搜索，要將所有生成的走法存入一個隊列，并且由于搜索的層數(shù)不同（我們這里將搜索深度定位1-3）,還必須將走法所處的層數(shù)也存入隊列。根據(jù)實戰(zhàn)統(tǒng)計，中國象棋每一步的合法走法大約是五六十中，還可以通過良好的數(shù)據(jù)結(jié)構(gòu)和走法預(yù)生成來提高生成速度。走法預(yù)生成是為了提高走法產(chǎn)生的效率，把每種棋子在某一位置的最大可走步建成一個數(shù)據(jù)庫，在產(chǎn)生走法時直接取出數(shù)據(jù)，然后根據(jù)具體的棋局去除不合法的走法，即以空間換時間的優(yōu)化。走法生成是搜索的前提，優(yōu)化走法生成很大程度上可以提高博弈速度。局面評估對于整個中國象棋博弈程序來說，如果說搜索算法是程序的心臟，那么局面評估就是程序的大腦，這兩個部分都是整個程序的核心。在這里，局面評估的作用是通過象棋知識評價當(dāng)前的棋局進(jìn)行好壞的評價，通過一個函數(shù)將棋局局面進(jìn)行量化，得到一個估值。，正所謂：“象棋似布陣，點子如點兵”，中國象棋知識錯綜復(fù)雜，但是在中國象棋博弈系統(tǒng)中我們要考慮到的棋類知識主要有四點：子力價值和子力總和：子力價值是指某一棋子本身所具有的價值。棋子的子力價值決定棋子能控制的點位的多少。例如，車是象棋中實力最強的棋子，在棋盤上移動與進(jìn)攻都十分方便，所以假設(shè)車的值為10,那比車實力小的馬的值可能就為6,卒值可能就為2等等。但是各個子力價值只是參考，而真正能體現(xiàn)棋局優(yōu)劣的是所剩的子力總和，單車勝不了士象全，而馬炮可以對抗士象全，所以在評估局面時，首先要對雙方的子力總和進(jìn)行一個對比。棋子的位置：棋子的位置是指棋子在棋盤上的位置及可控的區(qū)域，例如，過河卒、沉底炮、以及車占士角等都是較好的棋子位置狀態(tài)，而窩心馬、將離開底線等則屬較差的棋子位置狀態(tài)。棋子的機動性：棋子的機動性是指棋子的靈活性。例如，剛開局時，車的受到的約束較大，移動性較差，下棋講究車早出，故有“輸棋只因出車遲”之說。同樣被四面蹩腳的馬，它是不能移動的，所以它的機動性為0.棋子間的關(guān)系：棋子間的關(guān)系在棋局當(dāng)中是非常復(fù)雜的。一個棋子和其它棋子之間的關(guān)系往往不是一對一的關(guān)系，例如，一個炮可能在攻擊完對方的車之后被對方的馬攻擊。估值函數(shù)在程序中，估值函數(shù)的作用是把局面的質(zhì)量量化成為直觀的數(shù)字，估值函數(shù)可以是簡單的，也可以是復(fù)雜的，這取決于你在程序中加入的知識的數(shù)量。在中國象棋博弈程序中，估值函數(shù)就是各種棋類知識綜合考慮計算之后所得到的值。對于棋子控制區(qū)域的打分我們也可以根據(jù)已經(jīng)定義好的“控制區(qū)域價值表”，然后對其進(jìn)行累加即可。對于子力的打分，我們可以根據(jù)已經(jīng)定義好的“棋子價值表”。“棋子價值表”是由各個棋子的緊要程度和走法綜合考慮得到的值。在估值函數(shù)中，我們可以用這樣的公式來計算一方棋子的子力總和：sideValue（各種棋子的總價值和）=suni（PieceNum（該種棋子的價值）*PieceValue（某種棋子的數(shù)量））；對于棋子的機動性的打分，我們需要給予棋子每種走法一個值，將每種走法的估值相加，就可以得到每個棋子的機動性得分。然后可以用下面的表達(dá)式求某一方棋子機動性：Mobility（棋子的靈活性分?jǐn)?shù)）=Sum（MoveNum（某種棋子的合法走法數(shù)量）*MoveValue（該種棋子每一走法的價值））；通過遍歷棋盤，我們可以完成對控制區(qū)域的打分、子力打分和機動性打分，我們再根據(jù)關(guān)系表來考察棋子的相互關(guān)系，進(jìn)行棋局棋子關(guān)系打分。分析棋子關(guān)系時，由于王的特殊性，王一旦被攻擊，那么整個游戲就結(jié)束了，所以我們要把王拿出來單獨考慮。其次，對其他的棋子，在分析棋子關(guān)系時，我們要考慮到：當(dāng)攻擊者子力價值小于被攻擊者子力價值，攻擊方將愿意換子。例如，一個馬正受到一個兵的攻擊，那我被攻擊方將可以直接放棄對馬的保護(hù)?；蛘呤嵌鄬Χ嗟那闆r，攻擊方的子力總和v被攻擊方的情況下，攻擊方肯定是愿意直接換子的。所以在程序中我們也考慮到要防止雙方兌子過快，但是這里并沒有考慮雙方兌子后局面的變化（要通過大量的數(shù)據(jù)來研究重新考慮兌子過后的局面是否有效），可以在以后的研究中對引擎進(jìn)行改進(jìn)。估值函數(shù)和博弈性能一般來說博弈系統(tǒng)的性能，速度，棋類知識滿足下面的關(guān)系：Peifoimance（性能尸Speed（速度）xKowledge（知識）博弈系統(tǒng)的性能基本上取決于估值的速度和所加入的知識量。但是從客觀的角度來說，并不是完全正相關(guān)的關(guān)系。知識的量上來說，知識越多，我們搜索時考慮的更加全面，所以搜索結(jié)果也是比較優(yōu)的，博弈性能相對來說就好一些，但是當(dāng)加入的知識越多時，搜索的速度就慢下來了，博弈的性能可能就相對降低了。所以我們要想獲得性能優(yōu)異的博弈程序，我們必須在速度和知識二者中間尋求一個平衡。當(dāng)然，由于估值函數(shù)模塊和其他程序模塊的耦合度并不高，我們可以考慮替換很多的估值函數(shù)，最終給出估值，但是這樣做效率比較低，我們應(yīng)該尋求一種比較好的估值函數(shù)來提高博弈性能。本文的是終點估值，即到達(dá)葉子節(jié)點時，使用估值函數(shù)對它進(jìn)行估值，這種方法思路清晰，容易設(shè)計。估值函數(shù)的改進(jìn)目前比較常用到的估值函數(shù)的改進(jìn)方法是通過手工調(diào)整，就是進(jìn)行大量的測試，通過仔細(xì)的比對，通過自身掌握的棋類知識，比如，從經(jīng)驗上可以知道，一個車的價值要比一個兵大，給車賦予比兵大的數(shù)值，馬炮則賦予位于其間的值;馬和炮的地位相當(dāng)，給予它們相當(dāng)?shù)臄?shù)值，以避免盲目換子；如果對弈中使用了一些優(yōu)秀的戰(zhàn)術(shù)配合，那么就給予一定數(shù)值的獎勵，等等。將這些經(jīng)驗放進(jìn)評估函數(shù)中反復(fù)對弈，然后不斷修正參數(shù)，找出一組性能較高的參數(shù)。本文中的估值函數(shù)優(yōu)化方法主要是手工調(diào)整的方法，以后我們對程序的改進(jìn)可以從機器智能計算的方面改進(jìn)。搜索算法搜索算法是整個程序的核心部分，相當(dāng)于程序的心臟，驅(qū)動著整個程序的運行。中國象棋的博弈樹十分巨大，因此搜索算法的好壞很大程度上會影響到計算機的下棋水平（搜索的速率越快，我們可以搜索的深度就越深）。目前，計算機博弈搜索算法一般是圖搜索策略，分為兩類：盲目搜索：乂稱無信息搜索或者窮盡搜索，它包括寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價搜索。這種搜索方法會遍歷整個博弈樹（如果是無限圖的話，那么搜索則永遠(yuǎn)不會終止），然后才能找到最優(yōu)的路徑，只適用于求解簡單的問題。這種搜索方法的代表是極大極小值搜索算法。啟發(fā)式搜索：乂稱為有信息搜索河有序搜索。啟發(fā)式搜索是將一些具體的領(lǐng)域知識作為啟發(fā)信息，對博弈樹上的節(jié)點進(jìn)行有選擇的查找，以簡化搜索過程。極大極小值搜索算法極大極小值算法算法是一種最小化對手最大得益的算法（即一方要做出對自己最有利的選擇）。這種算法一般用在圍棋、五子棋、象棋等棋類程序。結(jié)局有三種可能：勝利、失敗和平局。這個算法對戰(zhàn)雙方所考慮的角度是不一樣的，一方總是選擇對自己最為有利的局面，為另一方總是選擇對對方最為不利的局面，其輸贏的總和為0（有點像能量守恒，就像本身兩個玩家都有1點，最后輸家要將他的1點給贏家，但整體上還是總共有2點）。中國象棋的博弈樹很大的，如果用極大極小值算法來進(jìn)行搜索，我們將必須遍歷整個博弈樹，這樣的搜索效率會很低，搜索量也會非常的巨大，這個過程是不切實際的，但是如果毫無選擇的減少搜索的范圍，乂會影響到搜索的結(jié)果，所以我們要考慮用什么方法對博弈樹進(jìn)行適當(dāng)?shù)牟眉簦瑏斫档退阉鞯臄?shù)量，這就可以選擇Alpha-Beta剪枝算法，Alpha-Beta剪枝算法可以在不影響搜索精度的條件下大幅減少搜索數(shù)目。Alpha-Beta剪枝搜索Alpha-Beta算法是與極大極小值算法非常相似的算法,AlphaBeta剪枝方法是對Mimmax方法的優(yōu)化，它們產(chǎn)生的結(jié)果是完全相同的，只不過運行效率不一樣。一般來說，下棋雙方對棋局肯定有著相似的認(rèn)知，那就是你覺得對你很糟糕的局面，在你的對手看來則是對他很有利的局面，那么某些局面有可能導(dǎo)致很糟糕的局面的節(jié)點，你根本就沒有考慮的必要，它只會把你引向更壞的局面，你應(yīng)該放棄這個節(jié)點和它的子節(jié)點,這樣一來就可以縮小博弈樹，提高搜索速度,這稱為“樹的裁剪”。如圖3.2所示的極大極小樹片段中，按照極大極小值搜索規(guī)則，從左路分枝

MAXMINMAXMIN的葉節(jié)點倒推得到第一層MAX節(jié)點的值為5,可表示此時的著法最佳值，記為a,顯然此。.值可作為MAX方著法指標(biāo)的下界。在搜索中路分枝時，因為第二層著法的選擇是取第三層節(jié)點的最小值，即取Mm（8,3,“口）而無論“口”中為何值，都不會比5大（最大為3）,故可以將“□”表示的節(jié)點及其后繼節(jié)點剪掉，不再考慮此節(jié)點的延伸。同理搜索右路分枝，也可以進(jìn)行剪枝操作，此類剪枝稱為a-剪枝。如圖3.2所示的極大極小樹片段中，由左路分枝的葉節(jié)點倒推得到第一層MIN節(jié)點的值為n,可表示此時對方著法的鉗制值，記為B。顯然此B值可作為MIN方可能實現(xiàn)著法指標(biāo)的上界。在搜索中路分枝時，因為第二層著法的選擇是取第三層節(jié)點的最大值，即取MAX（5,12,“?！保?，而無論“O”中為何值，都不會比11?。ㄖ辽贋?2）,故可以將表示的節(jié)點及其后繼節(jié)點剪掉，不再考慮此節(jié)點的延伸。同理搜索右路分枝，進(jìn)行剪枝操作。此類剪枝稱為B-剪枝。但是這個算法嚴(yán)重依賴于走法的尋找順序。很明顯，搜索空間的大小和第一節(jié)點的估價值有關(guān)。如果你最先搜到的總是最壞的節(jié)點，那么就不可能找到值比beta還要壞的節(jié)點，就不會有任何裁剪，該算法會和極大極小值算法一樣，遍歷整個博弈樹，搜索效率很低。但是如果我們最先搜到的總是最好的節(jié)點，這就是Alpha-Beta算法的搜索效率最好的情況。在數(shù)學(xué)的角度來看，搜索效率能提高到原來的平方根。在最好的情況下，把搜索的深度設(shè)為d,,節(jié)點的數(shù)量為極大極小值搜索算法的一半。在最壞的情況下，alpha-beta搜索算法和極大極小值搜索算法是一樣的。多大程度的減小搜索空間取決于一個節(jié)點的子節(jié)點在有序的節(jié)點列表中如何發(fā)展下去。為了提高搜索的效率，可以調(diào)整子節(jié)點的節(jié)點列表。這就要涉及到啟發(fā)式搜索了。啟發(fā)式搜索及走法排序我們前面介紹的alpha-beta剪枝搜索是極大極小值搜索的改進(jìn)，在一定程度上提高了效率，但是有著明顯的缺點（在上文中有介紹），如果要提高搜索深度和搜索效率，就要配合搜索過程中得到的一些啟發(fā)信息。利用啟發(fā)信息來決定哪一個是下一步要做擴展的節(jié)點，這種搜索總是選擇“最有希望”的節(jié)點來作為下一個被擴展的節(jié)點。如何快速的找出那個“最有希望”的節(jié)點，靈活的運用啟發(fā)信息，這就需要我們應(yīng)用某些準(zhǔn)則來重新排列節(jié)點列表中節(jié)點的順序。根據(jù)這些搜索要求，我們出現(xiàn)了一些啟發(fā)式搜索的形式。這些策略加快了搜索的速度。如下：歷史啟發(fā)，在搜索的過程中，很有可能會出現(xiàn)一些相似的局面，這些局面可能是前面已經(jīng)出現(xiàn)的，我們可以對它用估值函數(shù)來給予這些局面一個估值，但現(xiàn)在我們有一種更好的辦法可以快速判斷這些局面是否還有繼續(xù)下去的可能性。歷史啟發(fā)這種搜索策略就是在搜索的過程中，如果產(chǎn)生比較好的走法，那么如果以后產(chǎn)生相似的局面，這些走法也是比較好的，所以我們可以將這些走法存儲下來，并給予一個參數(shù)來記錄它的得分，稱為歷史得分，這些局面出現(xiàn)的次數(shù)越多它的歷史得分就越高。當(dāng)我們進(jìn)行一個新的局面評估時，我們要對它們進(jìn)行排列，并且保證歷史得分最高的在前面，這樣就可以盡快的進(jìn)行alpha-beta裁剪，提高搜索速率。殺手啟發(fā)，這種搜索策略是一種特殊的歷史啟發(fā)，和歷史啟發(fā)不同的是殺手啟發(fā)優(yōu)先搜索造成每一層剪枝最多的走法。在搜索的過程中，有一些走法很糟糕,它如果被搜索到就會被剪掉。將這些走法記錄下來，當(dāng)下一次搜索到同一層時，如果殺手走法是當(dāng)前局面的一個合理走法，那就優(yōu)先搜索殺手節(jié)點，然后將其裁剪掉。置換表，這種搜索策略是將搜索過程中的搜索信息記錄下來。在以后的搜索中，如果搜索到的節(jié)點在記錄表中已有記錄，那就可以直接引用記錄。置換表搜索策略和以上兩個搜索策略不同的地方是，這個搜索策略不需要清空記錄表，而是一直保存，為以后所用。在本文文中，我們采用的歷史啟發(fā)這個搜索策略。我們可以使用各種排序算法對于走法進(jìn)行排序，在此程序中采用了歸并排序。歸并排序的時間復(fù)雜度為O(iilog2n),空間復(fù)雜度為O(n),具有較高的效率。第四章系統(tǒng)設(shè)計與實現(xiàn)系統(tǒng)的整體規(guī)劃我們在對象棋博弈系統(tǒng)的做了一個需求分析后進(jìn)行了功能設(shè)計，這個象棋博弈系統(tǒng)應(yīng)該具備的功能是人機對戰(zhàn)、殘局的保存和讀取功能、悔棋和還原功能、走法顯示功能。功能結(jié)構(gòu)圖如圖4.1所示：圖4.1功能結(jié)構(gòu)圖象棋界面的實現(xiàn)本文的界面實現(xiàn)用的是MFC類庫，只需建立一個基于對話框的MFC應(yīng)用程序,然后添加或者刪掉一些菜單欄工具欄就可以了，非常方便。主要分布為兩個部分：(1)界面初始化部分OnlnitDialog。函數(shù)負(fù)責(zé)的是對話框的初始化，同時也可以把中國象棋博弈程序相關(guān)內(nèi)容進(jìn)行初始化。相關(guān)內(nèi)容包括：對棋盤上棋子位置的初始化；對程序輔助部分所用到的一些變量的初始化。包括對悔棋、還原隊列的清空，棋盤、棋子樣式的默認(rèn)形式，下棋模式的默認(rèn)選擇，以及走法名稱列表的初始化等等。(2)界面繪圖部分MakeBoaid()函數(shù)和MB_D【awStai()函數(shù)是完成棋盤界面的繪圖，OnPamt()函數(shù)是完成棋盤界面上棋子的顯示;這三個函數(shù)完成了程序界面棋盤、和走法名稱的顯示。OnPaint()函數(shù)主要貼表示棋子的位圖；MakeBoard()函數(shù)是畫棋盤；MB_DiawStar()是畫星點(為MakeBoard調(diào)用)。但是位圖只能是矩形的，而棋子是圓形的，直接使用的話會留下白色的背景框，所以我們要想通過一些“與”和“異或”操作來屏蔽掉棋子的背景。棋盤和棋子通過數(shù)組連接起來，形成一個完整的界面系統(tǒng)。對弈功能的實現(xiàn)對弈功能是整個博弈系統(tǒng)最主要的功能，本系統(tǒng)包括人人對戰(zhàn)和人機對戰(zhàn)的功能。本系統(tǒng)對于人人對戰(zhàn)的實現(xiàn)是通過象棋規(guī)則的定義和圖形化的棋子如何在棋盤上移動來實現(xiàn)的。Cango()函數(shù)實現(xiàn)了對于棋子走法的定義，根據(jù)棋子走法判斷我們可以定義棋子是否是正確的移動，判斷棋子位置是不是合法，是由IsNormal()函數(shù)實現(xiàn)的。OnLButtonDown()函數(shù)和OnLButtonUp()函數(shù)是用戶動作響應(yīng)部分，實現(xiàn)了棋子在棋盤上的移動。最后由FixManMap()函數(shù)保存棋盤狀態(tài)。當(dāng)用戶點擊鼠標(biāo)時，調(diào)用OnLButtonDown()函數(shù)，第一個參數(shù)表示確定左鍵是否按下，第二個參數(shù)為左鍵按下時點的位置坐標(biāo)。當(dāng)用戶放開鼠標(biāo)是，調(diào)用OiiLButtonUpO函數(shù)，參數(shù)的作用和OnLButtonDown函數(shù)是一樣的。OnLButtonDown函數(shù)里處理的操作是：如果用戶點擊鼠標(biāo)的位置落在己方的棋子上，表示用戶選中了該棋子，下一步將移動該子進(jìn)行走棋(也可能用戶下一步將會選擇己方另外的棋子，總之這一操作會記錄下用戶所選的將要走的棋子)。OnLButtonUp函數(shù)處理的操作是：如果之前用戶已經(jīng)點擊了棋子，那么就可以移動棋子，這是用戶的一次走棋過程。在收到用戶傳達(dá)的走棋信息后，可先判斷該走法是否合理(是否符合中國象棋的走棋規(guī)則)，如果是合理，則執(zhí)行之，如果不合理，則讓棋子回到它原來的位置。系統(tǒng)最終的目的是要實現(xiàn)人機對戰(zhàn)，人機對戰(zhàn)的核心就是人工智能，本文是通過上面第三章介紹的技術(shù)實現(xiàn)人工智能的。實現(xiàn)電腦走棋的邏輯步驟如圖4.2所示：圖4.2人工智能實現(xiàn)流程圖走法生成部分，EnumList()函數(shù)列出了當(dāng)前局面的所有走法。估值函數(shù)部分，首先constintManBPlus[2][12][H]規(guī)定了各個位置的價值，ManBaseValue[32]規(guī)定了棋子的固定價值，然后通過估值函數(shù)Value(),對走法進(jìn)行估值，判斷那種走法價值最大，其中ContactV()函數(shù)是Value()的子函數(shù)，計算各個棋子的活躍度和棋子間的關(guān)系值。搜索部分，通過搜索找到比較好的走法，這里通過SubThnik()函數(shù)對著法進(jìn)行搜索。做完以上的部分后，通過Tlmik()函數(shù)找到最佳走法。悔棋和還原功能的實現(xiàn)悔棋和還原功能是象棋軟件的基本功能。要實現(xiàn)悔棋和還原的功能，在博弈程序中，我們要建立一個走法棧(CStepListm_StepList)來保存每一回合的棋局局面(棋子數(shù)組和棋子位置等等)。還原功能是在悔棋步驟實現(xiàn)之后才能被激活的,博弈雙方對戰(zhàn)一個回合之后，如果沒有進(jìn)行悔棋，那么還原棧是要清空的。在本文中，OnEditRedo()函數(shù)實現(xiàn)了悔棋功能，OnEditUndo()函數(shù)實現(xiàn)了還原功能。下面我們將介紹一下悔棋和還原功能的步驟?；谄骞δ軐崿F(xiàn)的步驟：下棋回合數(shù)減一；走法棧存儲當(dāng)前的棋局信息，可用于還原步驟;把上一回合的著法名稱從走法棧中取出，然后將它顯示成當(dāng)前局面，并將最近的走法從走法棧中刪除掉;將列表框中的最后一列著法名稱存儲到著法名稱隊列中，為還原所用。然后從列表框中刪除它。還原功能實現(xiàn)的步驟：下棋回合數(shù)加一；走法棧存儲當(dāng)前棋局信息，可用于悔棋步驟；從看法隊列中取出最近一次存儲的著法名稱，將這些信息恢復(fù)成棋局局面，并表示出來；從著法隊列中取出最近一次存入的看法名稱，將其重新顯示到列表框中，并在走法棧中存儲。然后將其從著法名稱隊列中剔除。以上就是悔棋和還原的所有步驟，在用戶界面上可以通過添加了事件處理函數(shù)的悔棋和還原按鈕來實現(xiàn)。文件保存和讀取功能的實現(xiàn)MFC中文件的讀取和存儲使用的是CFile與CFileDialog類。CFileDialog類中封裝了windows常用的文件對話框，這個類提供了一種簡單的和Windows標(biāo)準(zhǔn)相一致的文件打開和文件存儲對話框功能。在程序中通過CFileDialog構(gòu)造一個對象之后，初始化對話框控件，然后調(diào)用DoModal成員函數(shù)顯示對話框并使用戶輸入路徑和文件。OiiFileSave()函數(shù)實現(xiàn)了棋譜文件的存儲，OnFileOpen()函數(shù)實現(xiàn)了棋譜文件的打開。著法顯示功能的實現(xiàn)每當(dāng)用戶或者計算機走一步棋時，就會按照中國象棋棋子看法描述規(guī)范在棋盤界面上的列表框控件(ListBox)中顯示棋子著法，例如：兵三進(jìn)一(用戶)，炮8進(jìn)4(電腦)等。在本文中編寫了一個函數(shù)來獲得看法名稱，實現(xiàn)將被移動的棋子的兵種以及棋子的起始坐標(biāo)、終點坐標(biāo)經(jīng)過一定的計算轉(zhuǎn)換成標(biāo)準(zhǔn)的中國象棋著法名稱。我們通過GetStepName()函數(shù)取得走法名稱，然后顯示在ListBox中。當(dāng)列表框中的顯示數(shù)目超過了顯示范圍，列表框會自動加一個滾動條。程序說明CliessDlg.h是象棋相關(guān)定義，其中包括棋盤局面和著法的表示。BaseClasses.h是棋局初始化。BaseDef.h是著法生成器，生成當(dāng)前局面某一方所有合法著法。CoolButton.h是用于繪制主界面右下角的四個按鈕。Resouice.h是資源管理。StepList.h是走法生成存儲。Thmkdef.h是歷史啟發(fā)，Alpha-Beta搜索之補充，以提高搜索效率。Thmkei.h是著法排序，通過啟發(fā)信息對節(jié)點列表中節(jié)點進(jìn)行排序，以提高搜索效率。ThnikOptioiiDlg.h是局面評估，為某一特定局面進(jìn)行評分。MoveList.是搜索部分，使用搜索求出最佳著法。系統(tǒng)測試及實驗結(jié)果系統(tǒng)測試屬于黑盒類測試，是根據(jù)需求文檔對軟件的功能和性能進(jìn)行測試，它不涉及程序的代碼部分，只是通過不同的硬件和外設(shè)條件進(jìn)行兼容性測試，通過測試用例測試功能是否滿足需求文檔,通過測試軟件對軟件進(jìn)行壓力測試等等。我們這里主要是在軟件程序完成時，在windows7系統(tǒng)環(huán)境下測試棋子的走法是否是按照中國象棋的走子規(guī)則是否可以實現(xiàn)人機對弈，是否可以對參數(shù)進(jìn)行設(shè)置，是否保存和讀取棋譜等等。測試用例的設(shè)計，我們可以這樣進(jìn)行設(shè)計，如表4」：表4.1測試用例功能點前置條件動作預(yù)期結(jié)果測試結(jié)果文件保存/點擊保存棋譜文件存儲到電腦棋譜文件存儲到電腦文件讀取電腦有正確的棋譜文件點擊打開選取棋譜文件讀取棋譜文件并顯示棋局讀取棋譜文件并顯示棋局文件讀取/點擊打開選取其他文件無法打開文件無法打開文件棋子走棋棋盤上有棋子按照正確的方式走棋棋子可以移動棋子可以移動棋子走棋棋盤上有棋子按照不正確的方式走棋棋子不可以移動棋子不可以移動悔棋已經(jīng)走棋點擊悔棋按鈕棋局回到上一個局面棋局回到上一個局面還原悔棋已實現(xiàn)點擊還原按鈕棋局回到悔棋前面棋局回到悔棋前局面經(jīng)過不斷的調(diào)試與修改，我們將中國象棋博弈程序?qū)崿F(xiàn)出來了。并且經(jīng)過系統(tǒng)測試，該中國象棋博弈系統(tǒng)完全滿足需求文檔中的功能和性能。首先最重要的

功能是可以實現(xiàn)人機對弈，并且所有的棋子可以都按照標(biāo)準(zhǔn)的中國象棋走子規(guī)則移動，其次滿足悔棋和還原的功能，也可以對參數(shù)進(jìn)行設(shè)置，滿足象棋殘局文件的保存和讀取。如圖4.3是軟件界面的截圖，在界面上所有的功能都一目了然，界面包括棋盤區(qū)域、走法顯示區(qū)域、悔棋按鈕、還原按鈕，但是可能還存在一些不足之處，如外觀不夠美觀，沒有音效。，第5步-紅方-棋手1（人）文件控制幫勖「=II回?!?電腦（X），第5步-紅方-棋手1（人）文件控制幫勖「=II回?!?電腦（X）停止（2）悔根圖4.3中國象棋博弈系統(tǒng)用戶界面截圖圖4.4殘局保存功能截圖如圖4.4是象棋博弈系統(tǒng)的殘局保存功能，在這里我們可以看到我們可以將殘局保存為棋