中國象棋游戲的設計與實現(xiàn)-畢業(yè)論文

1、中國象棋游戲的設計與實現(xiàn) - 畢業(yè)論文畢 業(yè) 設 計中國象棋游戲的設計與實現(xiàn)摘要中國象棋發(fā)展至今已有數(shù)千年的歷史了， 它是中華民族智慧的結(jié)晶。 在我國， 中國象棋的普及程度是其它棋類無法比擬的， 大至國際、 國內(nèi)比賽， 小至社區(qū)街 道。如今，僅中國就有 2億人會下中國象棋， 且中國象棋的發(fā)展趨勢日益國際化。 本文首先研究了中國象棋在計算機中的表示問題， 討論如何產(chǎn)生著法等一系列相 關內(nèi)容，其次研究了博弈樹的搜索技術及在此基礎上發(fā)展起來的相關剪枝算法。系統(tǒng)使用MFC文檔視圖體系結(jié)構(gòu)和Visual C+開發(fā)工具，實現(xiàn)了一個具有一定 棋力的中國象棋人機對弈程序。 此博弈程序?qū)崿F(xiàn)了人機博弈， 悔棋，電

2、腦難度設 置，著法名稱生成等功能。關鍵詞：中國象棋 人工智能 博弈樹 Alpha-Beta 搜索1 前言 11.1 中國象棋游戲設計背景和研究意義 11.2 國內(nèi)外象棋軟件發(fā)展概況11.3 中國象棋游戲設計研究方法11.4 本文的主要工作 22 棋局表示和著法生成 22.1 棋盤和棋子的表示 22.2 著法生成 43 走棋和博弈程序的實現(xiàn) 53.1 博弈程序的實現(xiàn) 5 搜索算法 5 著法排序 8 局面評估 93.2 悔棋和還原功能的實現(xiàn) 113.3 著法名稱顯示功能的實現(xiàn) 123.4 勝敗判定 144 界面設計和系統(tǒng)實現(xiàn) 154.1界面設計154.2系統(tǒng)實現(xiàn)175總結(jié) 21參考文獻23ABST

3、RACT24致 謝 2526仲愷農(nóng)業(yè)工程學院畢業(yè)論文 設計 成績評定表1 前言中國象棋游戲設計背景和研究意義 中國象棋游戲流傳至今已經(jīng)有數(shù)千年的歷史了， 是一種古老的文化， 它集文 化、科學、藝術、競技于一體，有利于開發(fā)人的智慧，鍛煉人的思維，培養(yǎng)人的 毅力，增強人的競爭意識。自從計算機發(fā)明，向各個領域發(fā)展，到成為我們現(xiàn)在 每天工作和生活必不可少的一部分的這個過程中， 電子游戲也逐步滲入我們每個 人的娛樂活動中。 在計算機已經(jīng)普及的今天， 對于可以用計算機進行程序編輯的 人來說，開發(fā)屬于自己的游戲， 已經(jīng)不再是夢想， 中國象棋歷史悠久不僅源遠流 長，而且基礎廣泛，作為一項智力運動更成為我們游戲

4、開發(fā)的首選對象。中國象棋是一項智力游戲， 以往都是人和人下棋， 現(xiàn)在有了計算機我們可以 和計算機競技， 人可以與計算機進行對弈。 控制計算機的是人類， 而人工智能是 綜合性很強的一門邊緣學科， 它的中心任務是研究如何使計算機去做那些過去只 能靠人的智力才能做的工作。 因此，對游戲開發(fā)過程中的人工智能技術的研究自 然也就成了業(yè)界的一個熱門研究方向。國內(nèi)外象棋軟件發(fā)展概況 最早的象棋軟件是一副可以外出攜帶的電子棋盤，后來升級到電視游戲機。開始出現(xiàn)的一些容量很小的象棋軟件如： DOS界面將族、WIN31程序的中國 象棋等等， 與其說人類下不過電腦， 倒不如說是沒有耐性等待電腦程序慢吞吞 的搜索算法，

5、 有時甚至懷疑軟件是否在搜索中死掉了。 后來，網(wǎng)絡上先后出現(xiàn)了 真正的WINDOWS口界面的象棋專業(yè)高級軟件棋隱、象棋世家、象棋參謀、 象棋奇兵等?？偠灾黝愊笃遘浖扔凶陨淼膬?yōu)點，也存在共通性的缺 陷，如：中局審勢不夠智能化，走不出棄子取勢的人性化佳構(gòu)，殘局時智力明顯 低于人腦，難以走出殘局例勝的必然著法等。 放眼未來， 象棋軟件已經(jīng)走完了一 波持續(xù)上漲的行情，有可能出現(xiàn)逐步降溫的滑坡趨勢。中國象棋游戲設計研究方法本系統(tǒng)主要用Visual C+進行開發(fā)，里面的MFC類庫，使游戲開發(fā)更加方 便，并利用人工智能相關搜索算法實現(xiàn)人工智能的著法生成， 從而完善整個游戲 的功能。該象棋人機博弈系統(tǒng)

6、實現(xiàn)的功能主要包括：1、選手選擇（人或電腦） ；2、人機對弈（人與電腦競技） ；3、電腦棋力難度選擇（電腦下棋能力難度選擇，共有4 級：按電腦配置選擇難度）；4、悔棋、還原；5、著法名稱顯示（象棋走棋規(guī)范名稱） 。本文的主要工作第一部分主要介紹了中國象棋游戲開發(fā)的背景及意義、 國內(nèi)外象棋軟件的發(fā) 展概況和象棋游戲的設計研究方法；第二部分介紹了棋局表示方法和著法生成； 第三部分介紹了走棋和博弈程序的實現(xiàn)； 第四部分介紹了界面設計和系統(tǒng)的實現(xiàn)。棋局表示和著法生成棋盤和棋子的表示即用一個對于中國象棋棋盤局面的表示可采用傳統(tǒng)而簡單的“棋盤數(shù)組”9*10 的數(shù)組來存儲棋盤上的信息，數(shù)組的每個元素存儲棋盤

7、上是否有棋子。這 種表示方法簡單易行。按此方法棋盤的初始情形如下所示：BYTE CChessBoard910R, 0, 0, P, 0, 0, p, 0, 0, r,H, 0, C, 0, 0, 0, 0, c, 0, h,E, 0, 0, P, 0, 0, p, 0, 0, e,A, 0, 0, 0, 0, 0, 0, 0, 0, a,K, 0, 0, P, 0, 0, p, 0, 0, k,A, 0, 0, 0, 0, 0, 0, 0, 0, a,E, 0, 0, P, 0, 0, p, 0, 0, e,H, 0, C, 0, 0, 0, 0, c, 0, h,R, 0, 0, P, 0,

8、 0, p, 0, 0, rJ給所有棋子定義一個值：#define R_BEGIN R_KING#define R_END R_PAWN#define B_BEGIN B_KING#define B_END B_PAWN#define NOCHESS 0 / 沒有棋子黑方： #define B_KING 1 / 黑帥#define B_CAR 2 / 黑車#define B_HORSE 3 / 黑馬#define B_CANON4 /黑炮#define B_BISHOP5 /黑士#define B_ELEPHANT6 /黑象#define B_PAWN7 /黑卒八、1紅方： #define R

9、_KING8 / 紅將#define R_CAR9 /紅車#define R_HORSE10/紅馬#define R_CANON11/紅炮#define R_BISHOP12/紅士#define R_ELEPHANT13/紅相#define R_PAWN14/紅兵判斷顏色：#define IsBlack x x B_BEGIN & x B_END / 判斷某個棋子是不 是黑色#define IsRed x x R_BEGIN & x R_END / 判斷某個棋子是不 是紅色對于著法的表示， 直接借用棋盤數(shù)組的下標來記錄著法的起點和目標點。 至 于是什么棋子在走，以及是否吃子、吃的是什么子，在著

10、法結(jié)構(gòu)中并不記錄。這 些信息由外部讀取棋盤上起點、 終點的數(shù)據(jù)獲得。 著法結(jié)構(gòu)定義如下， 其中還包 含了對著法的歷史得分的記錄項，以供后面要講到的“歷史啟發(fā)”所用typedef structshort nChessID; /表明是什么棋子CHESSMANPOS From;/起始位置CHESSMANPOS To; / 走到什么位置int Score; /走法的分數(shù)CHESSMOVE;有了對棋盤局面和著法的表示之后，程序才能夠完成以下操作：生成所有合法著法；執(zhí)行著法、撤銷著法；針對某一局面進行評估。因而，棋局表示好比是整個程序（計算機下棋引擎部分）的地基，之后 所有的操作都將建立在其基礎上。著法生

11、成在著法生成器中， 采用的基本思想就是遍歷整個棋盤 （一個接一個地查看棋 盤上的每個位置點），當發(fā)現(xiàn)有當前下棋方的棋子時先判斷它是何種類型的棋子， 然后根據(jù)其棋子類型而相應地找出其所有合法著法并存入著法隊列。這里談到的“合法著法”包括以下幾點：1、各棋子按其行子規(guī)則行子。諸如馬跳“日”字、象走“田”字、士在九 宮內(nèi)斜行等等 （這里需要特別注意的是卒 （兵）的行子規(guī)則會隨其所在位置的不 同而發(fā)生變化過河后可以左右平移） 。2、行子不能越出棋盤的界限。當然所有棋子都不能走到棋盤的外面，同時 某些特定的棋子還有自己的行棋界限，如將、士不能出九宮，象不能過河。3、行子的半路上不能有其它子阻攔（除了炮需

12、要隔一個子才能打子之外）以及行子的目的點不能有本方的棋子（當然不能自己吃自己了）4、將帥不能碰面（本程序中只在生成計算機的著法時認為將帥碰面是非法 的，而對用戶所走的導致將帥碰面的著法并不認為其非法，而只是產(chǎn)生敗局罷 了）。產(chǎn)生了著法后要將其存入著法隊列以供搜索之用， 由于搜索會搜索多層 （即 考慮雙方你來我往好幾步， 這樣才有利于對局面進行評估以盡可能避免 “目光短 淺”），所以在把著法存入著法隊列的時候還要同時存儲該著法所屬的搜索層數(shù)。 因此可以將著法隊列定義為二維數(shù)組 m_MoveList870 ，其中第一個數(shù)組下標 為層數(shù)，第二個數(shù)組下標為每一層的全部著法數(shù)。關于搜索層數(shù)，設定為4,實

13、際使用的是1到3（在界面中將其限定為1 3）。搜索層數(shù)的增加會顯著提高電腦的下棋水平 （當然計算機的棋力在很大程度上也 依賴于局面評估）。在配置為1.5G, 512M內(nèi)存的計算機上最多只能搜索 3層，再 多將導致搜索時間達到令人無法容忍的地步 （這里還需要特別說明的是， 搜索的 速度也和著法生成的效率以及局面評估的復雜度有關， 因為每分析一個結(jié)點都要 執(zhí)行這兩種操作） 。對于每一層的著法數(shù)， 也就是當前下棋方針對當前局面的所有可選的合法著 法，據(jù)有關數(shù)據(jù)統(tǒng)計在象棋實戰(zhàn)中一般最多情況下也就五六十種。 定義第二個數(shù) 組下標為 70，應當可以保證十分的安全。走棋和博弈程序的實現(xiàn)博弈程序的實現(xiàn)搜索算法

14、搜索算法對于整個下棋引擎來說都是至關重要的。 它如同程序的心臟， 驅(qū)動 著整個程序。搜索算法的好壞直接影響著程序執(zhí)行的效率 （從某種角度上， 它影 響著計算機的下棋水平。 因為，計算機必須在有限的時間內(nèi)完成思考， 搜索速度 快意味著在相同的時間內(nèi)程序可以“看”得更遠， “想”的更多）。關于棋類對弈 程序中的搜索算法，已有成熟的 Alpha-Beta 搜索算法以及其它一些輔助增強算 法（還有眾多基于 Alpha-Beta 算法的派生、 變種算法）。我們在程序中直接借鑒 了 Alpha-Beta 搜索算法并輔以歷史啟發(fā)。 本節(jié)先介紹 Alpha-Beta 搜索算法： 在 中國象棋里，雙方棋手獲得相

15、同的棋盤信息。 他們輪流走棋， 目的就是吃掉對方 的將或帥，或者避免自己的將或帥被吃。圖 1 博弈樹又此，可以用一棵“博弈樹”（圖1）來表示下棋的過程樹中每一個結(jié) 點代表棋盤上的一個局面， 對每一個局面 （結(jié)點） 根據(jù)不同的走法又產(chǎn)生不同的 局面（生出新的結(jié)點） ，如此不斷進行下去直到再無可選擇的走法，即到達葉子 結(jié)點（棋局結(jié)束）。中國象棋的博弈樹的模型大概如下圖所示，可以把其中連接 結(jié)點的線段看作是著法，不同的著法自然產(chǎn)生不同的局面。該樹包含三種類型的結(jié)點：1、奇數(shù)層的中間結(jié)點（以及根結(jié)點） ，表示輪到紅方走棋；2、偶數(shù)層的中間結(jié)點，表示輪到黑方走棋；3、葉子結(jié)點，表示棋局結(jié)束?，F(xiàn)在讓計算機

16、來下中國象棋， 它應當選擇一步對它最有利的著法 （最終導致 它取勝的著法）。獲得最佳著法的方法就是“試走”每一種可能的著法，比較它 們所產(chǎn)生的不同后果，然后從中選出能夠產(chǎn)生對自己最有利的局面的著法結(jié)合上面所講的博弈樹，若給每個結(jié)點都打一個分值來評價其對應的局面 （這一任務由后面所講的局面評估來完成） ，那么可以通過比較該分值的大小來 判斷局面的優(yōu)劣。 假定甲乙兩方下棋， 甲勝的局面是一個極大值 （一個很大的正 數(shù)），那么乙勝的局面就是一個極小值 （極大值的負值），和棋的局面則是零值 （或 是接近零的值）。如此，當輪到甲走棋時他會盡可能地讓局面上的分值大，相反 輪到乙走棋時他會選盡可能地讓局面上

17、的分值小。 反映到博弈樹上， 即如果假設 奇數(shù)層表示輪到甲方走棋， 偶數(shù)層表示輪到乙方走棋。 那么由于甲方希望棋盤上 的分值盡可能大，則在偶數(shù)層上會挑選分值最大的結(jié)點一一偶數(shù)層的結(jié)點是甲走 完一步棋之后的棋盤局面， 反映了甲方對棋局形勢的要求。 同樣道理， 由于乙方 希望棋盤上的分值盡可能小， 那么在奇數(shù)層上會選擇分值最小的結(jié)點。 這是“最 小-最大”（Mini）的基本思想。這樣搜索函數(shù)在估值函數(shù)的協(xié)助下可以通過在奇 數(shù)層選擇分值最大（最小）的結(jié)點，在偶數(shù)層選擇分值最?。ㄗ畲螅┑慕Y(jié)點的方 式來搜索以當前局面為根結(jié)點、 限定搜索層數(shù)以內(nèi)的整棵樹來獲得一個最佳的著 法。然而不幸的是，博弈樹相當龐大

18、（它會成指數(shù)增長） ，因而搜索（限定層數(shù) 以內(nèi)的）整棵樹是一件相當費時的工作一一其時間復雜度為O bn。其中b是分枝因子，即針對各種局面的合法著法的數(shù)目的平均值，n是搜索的深度。對于中國象棋而言，在中盤時平均著法數(shù)目大約是 40種左右，那么搜索 4層需要檢查 250萬條路線，搜索 5 層需要檢查 1 億條路線，搜索 6 層需要檢查 40 億條路線！Alpha-Beta 搜索能在不影響搜索精度的前提下大幅減少工作量。 因為，如果考慮到下棋是一個你來我往的交替進行并且相互 “較勁”的過程。 由于每一方都會盡可能將局面導向?qū)ψ约河欣鴮Ψ讲焕姆较?（假定下棋雙 方對棋局有著同樣的認知， 即你認為

19、對你很糟糕的局面， 在你的對手看來則是對 他很有利的局面），那么某些局面由于能夠產(chǎn)生出很糟糕的局面因而根本沒有再 繼續(xù)考慮的價值。 所以當你看到某個局面有可能產(chǎn)生很糟糕的局面時 （確切地說 這里的“很糟糕”是與之前分析的情況相比較而言的） ，你應當立刻停止對其剩 余子結(jié)點的分析不要對它再抱任何幻想了， 如果你選擇了它， 那么你必將得 到那個很糟糕的局面， 甚至可能更糟。 這樣一來便可以在很大程度上減少搜索的 工作量，提高搜索效率，這稱為“樹的裁剪” 。下面用圖來進一步說明“樹的裁剪” 。為了簡便起見，將博弈樹進行了簡化一一每個結(jié)點只有三個分支，實際情況中，剛才講過在盤中應有大約40個分支。假定

20、棋盤上的局面發(fā)展到了結(jié)點 A （圖2），現(xiàn)在輪到你走棋了，你是“最大 的一方”即你希望棋局的分值盡可能的高。 用搜索兩層來看一看 “樹的裁剪” 對提高搜索效率的幫助。圖中 表示該結(jié)點要取子結(jié)點中的最大值； 表示該結(jié)點要取子結(jié)點中的最 小值。圖 2 樹的裁剪首先，考察結(jié)點A的子結(jié)點B。結(jié)點B所屬的這一層是輪到你的對手一一“最 小者”來走棋了，目的是使得棋局的分值盡可能的小。 依次考察結(jié)點B的各個子 結(jié)點，查看它們的分值 （因為事先約定好了搜索兩層， 現(xiàn)在已達到搜索深度的要 求了，所以就停下來調(diào)用局面評估函數(shù)來給它打分）。結(jié)點B的第一個子結(jié)點（從 左到右算起）返回 -8，第二個子結(jié)點返回了 -2，

21、第三個子結(jié)點返回了 2。由于結(jié)點 B 這層是你的對手來做選擇， 假設他一定會做出明智的選擇 （你不能寄希望于你的對手會走出一步“昏招” ），那么他會選擇返回值為 -2 的那個結(jié)點。 -2 最終也就成了從結(jié)點B傳遞回的值，即倘若你（現(xiàn)在位于結(jié)點A）選擇了產(chǎn)生結(jié)點B的走法，使得局面發(fā)展到了結(jié)點 B。那么下一步，你的對手的選擇就會使得棋局 發(fā)展成為分值為 -2 的那個結(jié)點所表示的局面。再來分析結(jié)點A的第二個子結(jié)點C,結(jié)點C與結(jié)點B同屬一層，它依然是輪 到你的對手作選擇。依次查看結(jié)點C的各個子結(jié)點的分值，其第一個子結(jié)點返回 了 2, 。采用 “裁剪”方法。不必再繼續(xù)考察結(jié)點 C 的剩余子結(jié)點了，因為結(jié)

22、點 C 已經(jīng)夠糟糕的了，不管結(jié)點 C 的剩余子結(jié)點有怎樣的分值，它最多只能傳回 -8（有可能其剩余子結(jié)點中還有分值更小的結(jié)點，因而結(jié)點C還有可能傳回更小的值）。而與前面已經(jīng)分析過的結(jié)點 B所傳回-2相比較，作為“最大一方”的你顯 然更不愿意看到 2 的局面。所以，你當然不會選擇相應的著法使得局面發(fā)展成為 結(jié)點C。因為那樣的話，下一步你的對手就會帶給你一個分值不高于2的局面。由此，在不影響搜索質(zhì)量的前提下避免了搜索“無價值的”結(jié)點C的剩余子 結(jié)點的大量工作， 從而節(jié)省了寶貴時間， 為在同樣機器配置下搜索更多的層數(shù)提 供了可能?！白钚?- 最大”的思想再加上“對樹的裁剪” ，這就是 Alpha-B

23、eta 搜索算法 的核心。最基本的 Alpha-Beta 算法的代碼如下：int AlphaBeta int depth, int alpha, int betaif depth 0/ 如果是葉子節(jié)點（到達搜索深度要求）return Evaluate ;/ 則由局面評估函數(shù)返回估值GenerateLegalMoves ;/ 產(chǎn)生所有合法著法while MovesLeft/ 遍歷所有著法MakeNextMove ; / 執(zhí)行著法int val -AlphaBeta depth - 1, -beta, -alpha ; /遞歸調(diào)用UnmakeMove ; / 撤銷著法if val beta/ 裁剪

24、return beta;if val alpha/ 保留最大值alpha val;return alpha;著法排序Alpha-Beta 搜索算法是在“最小 - 最大”的基礎上引入“樹的裁剪”的思想以期提高效率，它的效率將在很大程度上取決于樹的結(jié)構(gòu)一一如果搜索了沒多久就發(fā)現(xiàn)可以進行“裁剪”了，那么需要分析的工作量將大大減少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此時“裁剪”也已經(jīng)失去了它原有的價值（因為你已經(jīng)分析了所有情況，這時的Alpha-Beta 搜索已和“最小 -最大”搜索別無二致了）。因而，要想保證 Alpha-Beta搜索算法的效率就需要調(diào)整樹

25、的結(jié)構(gòu)， 即調(diào)整待搜索的結(jié)點的順序， 使得“裁剪” 可以盡可能早地發(fā)生因為，通?？梢愿鶕?jù)部分已經(jīng)搜索過的結(jié)果來調(diào)整將要搜索的結(jié)點的順序 當一個局面經(jīng)過搜索被認為較好時， 其子結(jié)點中往往有一些與它相似的局面 （如 個別無關緊要的棋子位置有所不同） 也是較好的。 由 J.Schaeffer 所提出的 “歷 史啟發(fā)”（History Heuristic ）就是建立在這樣一種觀點之上的。在搜索的過程 中，每當發(fā)現(xiàn)一個好的走法，就給該走法累加一個增量以記錄其“歷史得分” ， 一個多次被搜索并認為是好的走法的 “歷史得分” 就會較高。 對于即將搜索的結(jié) 點，按照“歷史得分”的高低對它們進行排序，保證較好的

26、走法（ “歷史得分” 高的走法）排在前面，這樣 Alpha-Beta 搜索就可以盡可能早地進行“裁剪” ，從 而保證了搜索的效率。對于著法的排序可以使用各種排序算法， 在程序中采用了歸并排序。 歸并排 序的空間復雜度為 O n ，時間復雜度為 O nlog2n ，具有較高的效率。局面評估前文已經(jīng)講過了棋局表示、 著法生成、搜索算法（包括搜索輔助“歷史啟發(fā)”）， 在象棋程序中如果說搜索算法是心臟， 那么局面評估就是大腦。 搜索算法負責驅(qū) 動整個程序， 而局面評估則負責對搜索的內(nèi)容進行判斷和評價。 因而搜索與局面 評估是整個下棋引擎的核心。首先，先介紹一下在局面評估中需要考慮的因素。 就不同的棋類

27、可能要考慮 的因素略有差異。在中國象棋中所要考慮的最基本的幾個因素包括如下四點：1、子力總和 子力是指某一棋子本身所具有的價值。通俗地講就是一個棋子它值個什么 價。例如，車值 10 的話，那可能馬值 6，卒值 2 等等。所以在評估局面時，首 先要考慮雙方的子力總和的對比。 比如紅方擁有士象全加車馬炮， 而黑方只有殘士象加雙馬，則紅方明顯占優(yōu)。2、棋子位置棋子位置，或稱控制區(qū)域，是指某一方的棋子在棋盤上所占據(jù)（控制）的位 置。例如，沉底炮、過河卒、以及車占士角等都是較好的棋子位置狀態(tài)，而窩心 馬、將離開底線等則屬較差的棋子位置狀態(tài)。3、棋子的機動性棋子的機動性指棋子的靈活度（可移動性） 。例如，

28、起始位置的車機動性較 差，所以下棋講究早出車。 同樣四面被憋馬腿的死馬機動性也較差 （對于一步也 不能走的棋子，可以認為其機動性為零） 。4、棋子的相互關系這一點的分析較為復雜， 因為一個棋子與其它子之間往往存在多重關系。 如： 一個馬可能在對方的炮的攻擊之下同時它又攻擊著對方的車。在程序中，估值函數(shù)最后返回的是每一方的總分的差值， 而各方的總分就是 上面所提到的四個因素的打分的總和。對于子力打分和控制區(qū)域打分， 只要遍歷棋盤， 當遇到棋子時簡單地去查事 先定義好的“子力價值表”和“控制區(qū)域價值表” ，取出相對應的值進行累加即 可。對于機動性打分， 需要求出各個子總共有多少種走法， 然后根據(jù)各

29、個子所不同的機動性價值每多一種走法就加一次相應的分數(shù)。對棋子間相互關系的打分，要用到以下幾個數(shù)據(jù)：int m_BaseValue15; / 存放棋子基本價值int m_FlexValue15;/ 存放棋子靈活性分值short m_AttackPos109;/ 存放每一位置被威脅的信息BYTE m_GuardPos109; / 存放每一位置被保護的信息BYTE m_FlexibilityPos109;/存放每一位置上棋子的靈活性分值int m_chessValue109; / 存放每一位置上棋子的總價值其中計算機會進行所有棋子值的判斷， AttackPos 和 GuardPos 分別記錄該 棋子

30、受到的威脅和被保護的值。當遍歷一遍棋盤之后，子力打分、控制區(qū)域打分和機動性打分都可以完成， 而關系表也可以填完。 之后， 再根據(jù)關系表來具體考察棋子的相互關系， 進行關 系打分。分析關系時， 首先，對王的攻擊保護應分離出來單獨考慮， 因為對王的保護 沒有任何意義，一旦王被吃掉整個游戲就結(jié)束了。其次，對一個普通子， 當它既受到攻擊又受到保護的時候要注意如下幾個問 題：1、攻擊者子力小于被攻擊者子力，攻擊方將愿意換子。比如，一個車正遭 受一個炮的攻擊，那么任何對車的保護都將失去意義一一對方肯定樂意用一個炮 來換一個車。2、多攻擊 / 單保護的情況， 并且攻擊者最小子力小于被攻擊者子力與保護者 子力

31、之和，則攻擊方可能以一子換兩子。3、三攻擊/兩保護的情況， 并且攻擊者子力較小的二者之和小于被攻擊者子 力與保護者子力之和，則攻擊方可能以兩子換三子。4、攻擊方與保護方數(shù)量相同，并且攻擊者子力小于被攻擊者子力與保護者子力之和再減去保護者中最大子力，則攻擊方可能以 n子換n子。當然，上述四條只是覆蓋了最常見的幾種情況，覆蓋并不全面。而且，在程 序中并沒有直接地重新考慮雙方兌子之后的控制區(qū)域及機動性變化情況 （之所以 說沒有“直接地重新考慮” ，是因為搜索繼續(xù)展開結(jié)點后仍會考慮這些因素，只 是目前不知這樣效果是否受影響考察這兩種方法在效果上的差異需要一定 數(shù)量的試驗數(shù)據(jù)的支持） 。所以，如果今后要

32、對引擎進行改進，提高程序的下棋 水平的話，還應當在此進行研究?；谄搴瓦€原功能的實現(xiàn)悔棋和還原是棋類軟件中較為基本的功能。 要實現(xiàn)悔棋和還原功能， 首先要 明確哪些信息應當被保存以供悔棋和還原所使用。在程序中保存了如下信息：棋局表示中所定義的棋盤數(shù)組；各棋子的貼圖位置； 這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋 子的信息，而只是保存之前一步的走棋信息。 此后當悔棋的時候， 需要撤銷著法； 還原的時候，需要執(zhí)行著法。 然而，在編寫自己的程序時一來考慮到程序的可讀 性和不易出錯性，二來考慮到對當今的計算機的配置來說這點開銷基本上不會對 程序的效率產(chǎn)生什么影響。因此保存了全部棋

33、子的信息。根據(jù)所要保存的數(shù)據(jù)定義了如下基本結(jié)構(gòu)類型：typedef structCHESSMOVE cmChessMove;short nChessID;/ 被吃掉的棋子UNDOMOVE;在對弈過程中，每一回合都將棋局信息 （這里指前面所說的需要保存的信息） 保存至走法隊列， 以供悔棋所用。 還原功能是與悔棋功能相對應的， 只有當產(chǎn)生 了悔棋功能之后， 還原功能才會被激活。 一個回合的結(jié)束意味著前一次操作沒有 悔棋功能的產(chǎn)生，因此還原隊列也應被清空。在悔棋中主要完成了以下任務：1、下棋回合數(shù)減一；2、將當前局面信息保存至走法隊列，以供還原所用；3、從走法隊列中取出上一回合的棋局信息，恢復到當前

34、局面，然后將其從 隊列中剔除掉；4、將顯示著法名稱的列表框中的本回合的著法名稱保存到一個著法名稱隊 列，以供還原所用。然后從列表框中刪除它。而在還原中所做的剛好和悔棋相反：1、下棋回合數(shù)加一；2、將當前局面信息保存至隊列，以供悔棋所用；3、從隊列中取出最近一次悔棋前的棋局信息，恢復到當前局面，然后將其 從隊列中剔除；4、從走法隊列中取出最近一次存入的著法名稱（兩項，因為每回合會產(chǎn)生 兩步著法），將其重新顯示到列表框中。然后將其從中剔除。以上便是悔棋和還原功能所完成的具體操作， 其代碼分別寫入悔棋和還原按 鈕（ Button ）的事件處理函數(shù)中。著法名稱顯示功能的實現(xiàn)每當下棋者(用戶或是計算機)

35、走一步棋，在棋盤旁邊的一個列表框控件(List Box)中按照中國象棋關于著法描述的規(guī)范要求顯示出該著法的名稱。如:炮八進四、馬二進三此類。為了獲得該著法名稱，我們編寫了一個函數(shù)，其功能 就是將被移動的棋子類型以及走法的起點坐標、 終點坐標這些信息轉(zhuǎn)換成中國象 棋所規(guī)范的著法名稱。實現(xiàn)此功能代碼如下:void CGradientProgressCtrl:OnPaintCPaintDC dc this ; / device context for painting/ TODO: Add your message handler code hereif m_nCurrentPosition m_n

36、Lower | m_nCurrentPosition m_nUpperCRect rect;GetClientRect rect ;CBrush brush;brush.CreateSolidBrush :GetSysColor COLOR_3DFACE dc.FillRect &rect,&brush ;VERIFY brush.DeleteObject ;return;CRect rectClient;GetClientRect rectClient ;float Width float m_nCurrentPosition/ float m_nUpper*floatrectClient.

37、right ;/ 繪制DrawGradient &dc,rectClient, int Width ;/ 顯示進程條進度文字if m_bShowPercentCString percent;floatpercent.Format %d%, int 100* m_nCurrentPosition/m_nUpper ;dc.SetTextColor m_clrText ;dc.SetBkMode TRANSPARENT ;dc.DrawText percent,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE ;/ 顯示其他文字if m_bIsShowT

38、extdc.SetTextColor m_clrText ;dc.SetBkMode TRANSPARENT ;dc.DrawTextm_strShow,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE ;int CGradientProgressCtrl:SetPos int nPos/Set the Position of the Progressm_nCurrentPosition nPos;return CProgressCtrl:SetPos nPos ;int CGradientProgressCtrl:StepItm_nCurrentP

39、osition+ m_nStep;return CProgressCtrl:StepIt ;以下介紹如何對列表框控件（List Box）進行操作，以顯示或刪除著法名稱。首先，在 ChessDlg 下定義以下函數(shù)：this- GetMoveStr nFromX,nFromY,nToX,nToY,nSourceID ;/ 用來獲得剛下的一步棋的走法；void CChessDlg:AddChessRecord int nFromX,int nFromY,int nToX,int nToY,int nUserChessColor,int nSourceID/ 將走法添加進下棋記錄；然后，顯示在 Lis

40、tbox 中。當列表框中的項的數(shù)目超過列表框的顯示范圍時， 列表框會自動添加垂直滾動條（前提是其 VerticalScrollbar屬性要為 True 該屬性默認即為 True）但是顯示的內(nèi)容依然是最早加進來的項。 在控件屬性里選擇 Vertical Scroll 使得列表框可垂直滾動以顯示最新的著法名稱。想要從列表框中刪除項時，可以使用m_lstChessRecord.DeleteString m_lstChessRecord.GetCount -1 ; 減一之后正好是最后一項的行號。勝敗判定勝負判定只要一方將另一方的將或帥吃掉就是勝者。主要代碼如下：int CSearchEngine:Is

41、GameOver BYTE position9, int nDepthint i,j;BOOL RedLive FALSE,BlackLive FALSE;/ 檢查紅方九宮是否有帥for i 7;i 10;i+for j 3;j 6;j+if positionij B_KINGBlackLive TRUE;if positionij R_KINGRedLive TRUE;/ 檢查黑方九宮是否有將for i 0;i 3;i+for j 3;j 6;j+if positionij B_KINGBlackLive TRUE;if positionij R_KINGRedLive TRUE;i m_n

42、Depth-nDepth+1 %2;/ 取當前奇偶標志，奇數(shù)層為電腦方，偶數(shù)層為 用戶方。/ 紅方不在if !RedLiveif ireturn 19990+nDepth; /奇數(shù)層返回極大值elsereturn -19990-nDepth;/偶數(shù)層返回極小值/ 黑方不在if !BlackLiveif ireturn -19990-nDepth;/奇數(shù)層返回極小值elsereturn 19990+nDepth; /偶數(shù)層返回極大值return 0;/ 將帥都在，返回 0 界面設計和系統(tǒng)實現(xiàn)界面設計關于棋盤和棋子，建了一個基于對話框的 MFC應用程序。主要工作都在對話框類的兩個文件 CChess

43、DIg.h和CChessDIg.cpp下展開。代碼主要分布于以下三大部分：1、初始化部分BOOL CCChessUIDIg:OnInitDiaIogOnInitDiaIog 負責的是對話框的初始化。 可以把有關中國象棋的棋局初始 化情況也放在了這里面。初始化的內(nèi)容包括：對引擎部分所用到的變量的初始化。包括對棋盤上的棋子位置進行初始化 （棋盤數(shù)組的初始化） ，對搜索深度、當前走棋方標志、棋局是否結(jié)束標志等的 初始化；對棋盤、棋子的貼圖位置 （即棋盤、棋子在程序中實際顯示位置） 的初始化； 對程序輔助部分所用到的一些變量的初始化。 包括對悔棋、還原隊列的清空， 棋盤、棋子樣式的默認形式， 下棋模式

44、的默認選擇， 以及著法名稱列表的初始化 等。2、繪圖部分void CCChessUIDlg:OnPaintOnPaint 函數(shù)負責的是程序界面的繪圖。因此，在這里將要完成棋盤、棋 子的顯示走棋起始位置和目標位置的提示框的顯示。由于棋盤、棋子等都是以位圖的形式給出的。所以在 OnPaint 函數(shù)里做的 工作主要都是在貼位圖。需要注意的是由于位圖文件不能像 GIF 文件那樣有透明的背景并且棋子是 圓形的而位圖文件只能是矩形的， 所以如果直接貼圖的話會在棋盤上留下一塊白 色的邊框一一棋子的背景。因此，要想讓棋子文件的背景“隱藏”需要通過一些 “與”和“異或”操作來屏蔽掉棋子的背景。3、走棋部分（用戶

45、動作響應部分）為WM_LBUTTONDOW添加消息響應事件，可得到如下函數(shù)：void CCChessUIDlg:OnLButtonDown UINT nFlags, CPoint point當用戶在窗口客戶區(qū)按下鼠標左鍵時，程序就會調(diào)用 OnLButtonDown UINT nFlags, CPoint point 函數(shù)來進行響應。其中第二個參數(shù) CPoint point 是在本 程序中所要用到的， 它給出了當鼠標左鍵被按下時， 鼠標指針的位置坐標。 可以通過這一信息來得知用戶的走法在OnLButtonDown函數(shù)里處理如下兩種操作：1、如果用戶點擊鼠標的位置落在己方的棋子上，表示用戶選中了該

46、棋子， 下一步將移動該子進行走棋 （也可能用戶下一步將會選擇己方另外的棋子， 總之 這一操作會記錄下用戶所選的將要走的棋子） 。2、如果之前用戶已經(jīng)選過了棋子，那么這一次的點擊（如果不是另選本方 的其它棋子的話）表達了用戶的一次走棋過程。在收到用戶傳達的走棋信息后， 可先判斷該著法是否合法（是否符合中國象棋的游戲規(guī)則） ，如果合法，則執(zhí)行 之。緊接著調(diào)用引擎的搜索函數(shù)計算出計算機對用戶著法的應著， 然后執(zhí)行該應 著。如此，在On LButt on Down函數(shù)里，實現(xiàn)了人與機器的對弈（當然每走一步棋， 也還需要繪圖函數(shù)來顯示棋盤局面的更新） 。以上三部分并非界面程序的全部， 而僅僅是與程序密切

47、相關的部分。 此外還 有其它部分對程序同樣必不可少，但這些部分主要由MFC自動生成，無需人為改 動，故在此不多做介紹。系統(tǒng)實現(xiàn)現(xiàn)在已具備了實現(xiàn)一款中國象棋對弈程序引擎部分的所有要素， 將上述模塊 分別寫作 .h 頭文件。如下：ChessDlg.h象棋相關定義。包括棋盤局面和著法的表示。BaseClasses.h著法生成器。就當前局面生成某一方所有合法著法。MoveList.h搜索部分。使用搜索求出最佳著法。Thinkdef.h歷史啟發(fā)。 Alpha-Beta 搜索之補充，以提高搜索效率。Thinker.h著法排序。對著法按其歷史得分進行降序排序，以提高搜索效率。ThinkOptionDlg.h

48、局面評估。為某一特定局面進行評分。當實現(xiàn)了引擎部分的各要素時， 可先建立一個 Win32 控制臺項目， 之后只要 再添加一個 .cpp 文件負責接受用戶的輸入、調(diào)用搜索函數(shù)、顯示搜索結(jié)果，便 可簡單的測試引擎了 （采用輸入著法的起點坐標和終點坐標的方式來傳送用戶走 棋的信息。同樣，程序顯示計算機走棋的起點坐標和終點坐標來做出回應） 。此后，等到界面部分初步完成，引擎的上述各模塊無需作任何改動， 仍以.h 頭文件的形式加入界面工程， 只要由界面中的某個 .cpp 文件調(diào)用搜索函數(shù)即可。 這種連接方式實現(xiàn)起來非常簡單。首先，執(zhí)行該軟件，系統(tǒng)并不需要很高的配置，CPU在 1.5G以上，內(nèi)存在512M

49、以上就可以很流暢地執(zhí)行。下面簡單介紹一下象棋相關規(guī)則：對局時，由執(zhí)紅棋的一方先走，雙方輪流各走一著，直至分出勝、負、和， 對局即終了。 輪到走棋的一方， 將某個棋子從一個交叉點走到另一個交叉點， 或 者吃掉對方的棋子而占領其交叉點， 都算走一著。 雙方各走一著， 稱為一個回合。 如果有一方的主帥被對方吃了，就算那一方輸。各種棋子的走法：帥（將）：帥和將是棋中的首腦，是雙方竭力爭奪的目標。它只能在“九宮” 之內(nèi)活動，可上可下，可左可右，每次走動只能按豎線或橫線走動一格。帥與將 不能在同一直線上直接對面，否則走方判負。仕（士）：仕（士）是帥（將）的貼身保鏢，它也只能在九宮內(nèi)走動。它的 行棋路徑只能

50、是九宮內(nèi)的斜線。相（象）：相（象）的主要作用是防守，保護自己的帥（將） 。它的走法是每 次循對角線走兩格，俗稱“象走田” 。相（象）的活動范圍限于“河界”以內(nèi)的 本方陣地，不能過河，且如果它走的“田”字中央有一個棋子，就不能走，俗稱 “塞象眼”。車：車在象棋中威力最大，無論橫線、豎線均可行走，只要無子阻攔，步 數(shù)不受限制。因此，一車可以控制十七個點，故有“一車十子寒”之稱。炮：炮在不吃子的時候，走動與車完全相同。 馬：馬走動的方法是一直一斜， 即先橫著或直著走一格， 然后再斜著走一個 對角線，俗稱“馬走日”。馬一次可走的選擇點可以達到四周的八個點， 故有“八 面威風”之說。如果在要去的方向有別

51、的棋子擋住，馬就無法走過去，俗稱“蹩 馬腿”。兵（卒）：兵（卒）在未過河前，只能向前一步步走，過河以后，除不能后 退外，允許左右移動，但也只能一次一步。在懂的以上規(guī)則之后并可進行游戲， 執(zhí)行該軟件后， 并可進入游戲界面。 棋 盤界面（圖 3）所示：圖 3 棋盤界面從界面上方的菜單欄中可以進行相關設置參數(shù)設置界面（圖 4）如下：圖 4 參數(shù)設置界面 等你將參數(shù)設置完畢之后，既可進入游戲。走法記錄界面（圖 5）如下：圖 5 走法記錄界面其他輔助功能界面（圖 6）如下：圖 6 其他輔助功能界面 你可以通過上面四個輔助功能對棋局進行研究，從而提高你的下棋水平。例如，您是紅方，第一步走的是兵七進一或兵三

52、進一，電腦則會炮 2 進 4 或炮 8 進 4（圖 7）：圖 7 程序運行界面以上是系統(tǒng)實現(xiàn)的所有界面及功能測試?？偨Y(jié)2009年 2 月，我開始了我的畢業(yè)論文工作，時至今日，論文基本完成。從 最初的茫然， 到慢慢的進入狀態(tài)， 再到對思路逐漸的清晰， 整個寫作過程難以用 語言來表達。歷經(jīng)了幾個月的奮戰(zhàn)，緊張而又充實的畢業(yè)設計終于落下了帷幕。 回想這段日子的經(jīng)歷和感受， 我感慨萬千， 在這次畢業(yè)設計的過程中， 我擁有了 無數(shù)難忘的回憶和收獲。腳踏實地，認真嚴謹，實事求是的學習態(tài)度，不怕困難、堅持不懈、吃苦耐 勞的精神是我在這次設計中最大的收益。 我想這是一次意志的磨練， 是對我實際 能力的一次提升

53、，也會對我未來的學習和工作有很大的幫助。在這次畢業(yè)設計中也使我們的同學關系更進一步了， 同學之間互相幫助， 有 什么不懂的大家在一起商量， 聽聽不同的看法對我們更好的理解知識， 所以在這 里非常感謝幫助我的同學。在此更要感謝我的導師和專業(yè)老師， 是你們的細心指導和關懷， 使我能夠順 利的完成畢業(yè)論文。 在我的學業(yè)和論文的研究工作中無不傾注著老師們辛勤的汗 水和心血。老師的嚴謹治學態(tài)度、淵博的知識、無私的奉獻精神使我深受啟迪。 從尊敬的導師身上， 我不僅學到了扎實、 寬廣的專業(yè)知識， 也學到了做人的道理。 在此我要向我的導師致以最衷心的感謝和深深的敬意。本論文對計算機博弈技術進行了研究， 在深入

54、研究了機器下中國象棋方法理 論基礎上， 實現(xiàn)了一個具有一定棋力的人機對弈中國象棋程序。然而，由于時間關系，程序也存在著幾點不足：第一：沒對計算機下棋引擎部分作更深一步的挖掘和研究。 對于諸如位棋盤(BitBoard )、迭代加深(Iterative Deepening)、機器學習(Machine Learning ) 等當今棋類對弈程序中所采用的先進技術和思想， 在程序中并未涉及。 這在一定 程度上影響了程序中下棋引擎的工作效率。第二：由于對人工智能算法的不熟悉，在 Alpha-Beta 搜索算法上花了大量 的時間和精力來了解，導致程序進度的緩慢。盡管，這些問題最終都得以解決，但卻影響了程序開發(fā)的進程。第三、程序仍在局面檢測和貼圖刷新上存在著隨機性的出錯可能 (出錯幾率 很小)參考文獻1 王小春.PC游戲編程（人機博弈）M.重慶：重慶大學出版社，2002.2 網(wǎng)冠科技.Visual C+.NET 小游戲開發(fā)時尚編程百例M.西安：機械 工業(yè)出版社， 2004.3 陳建春 .Visual C+ 高級編程技術開發(fā)實例剖析 M. 西安： 電子工 業(yè)出版社， 1999.4 涂光平等.V