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

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

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

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

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

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

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

7、上是否有棋子。這 種表示方法簡(jiǎn)單易行。按此方法棋盤(pán)的初始情形如下所示：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給所有棋子定義一個(gè)值：#define R_BEGIN R_KING#define R_END R_PAWN#define B_BEGIN B_KING#define B_END B_PAWN#define NOCHESS 0 / 沒(méi)有棋子黑方： #define B_KING 1 / 黑帥#define B_CAR 2 / 黑車(chē)#define B_HORSE 3 / 黑馬#define B_CANON4 /黑炮#define B_BISHOP5 /黑士#define B_ELEPHANT6 /黑象#define B_PAWN7 /黑卒八、1紅方： #define R

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、走一步棋，在棋盤(pán)旁邊的一個(gè)列表框控件(List Box)中按照中國(guó)象棋關(guān)于著法描述的規(guī)范要求顯示出該著法的名稱。如:炮八進(jìn)四、馬二進(jìn)三此類(lèi)。為了獲得該著法名稱，我們編寫(xiě)了一個(gè)函數(shù)，其功能 就是將被移動(dòng)的棋子類(lèi)型以及走法的起點(diǎn)坐標(biāo)、 終點(diǎn)坐標(biāo)這些信息轉(zhuǎn)換成中國(guó)象 棋所規(guī)范的著法名稱。實(shí)現(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 ;/ 顯示進(jìn)程條進(jìn)度文字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 ;以下介紹如何對(duì)列表框控件（List Box）進(jìn)行操作，以顯示或刪除著法名稱。首先，在 ChessDlg 下定義以下函數(shù)：this- GetMoveStr nFromX,nFromY,nToX,nToY,nSourceID ;/ 用來(lái)獲得剛下的一步棋的走法；void CChessDlg:AddChessRecord int nFromX,int nFromY,int nToX,int nToY,int nUserChessColor,int nSourceID/ 將走法添加進(jìn)下棋記錄；然后，顯示在 Lis

40、tbox 中。當(dāng)列表框中的項(xiàng)的數(shù)目超過(guò)列表框的顯示范圍時(shí)， 列表框會(huì)自動(dòng)添加垂直滾動(dòng)條（前提是其 VerticalScrollbar屬性要為 True 該屬性默認(rèn)即為 True）但是顯示的內(nèi)容依然是最早加進(jìn)來(lái)的項(xiàng)。 在控件屬性里選擇 Vertical Scroll 使得列表框可垂直滾動(dòng)以顯示最新的著法名稱。想要從列表框中刪除項(xiàng)時(shí)，可以使用m_lstChessRecord.DeleteString m_lstChessRecord.GetCount -1 ; 減一之后正好是最后一項(xiàng)的行號(hào)。勝敗判定勝負(fù)判定只要一方將另一方的將或帥吃掉就是勝者。主要代碼如下：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;/ 取當(dāng)前奇偶標(biāo)志，奇數(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 界面設(shè)計(jì)和系統(tǒng)實(shí)現(xiàn)界面設(shè)計(jì)關(guān)于棋盤(pán)和棋子，建了一個(gè)基于對(duì)話框的 MFC應(yīng)用程序。主要工作都在對(duì)話框類(lèi)的兩個(gè)文件 CChess

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

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

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

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

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

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

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

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

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

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

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

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