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

中國象棋游戲的設(shè)計(jì)與實(shí)現(xiàn)中國象棋游戲的設(shè)計(jì)與實(shí)現(xiàn) 摘摘 要要 象棋程序的實(shí)現(xiàn)可以被分為人工智能和界面程序輔助兩大部分。人工智能 部分主要體現(xiàn)計(jì)算機(jī)的下棋思路，既計(jì)算機(jī)如何進(jìn)行思考并以最佳走法完成下 一步，先由相應(yīng)的搜索算法進(jìn)行搜索，并對(duì)各種可能的走法進(jìn)行估值，從中選 擇勝利面最大的一步；而界面及程序輔助部分主要便于用戶通過以前的下棋步 驟，更好地調(diào)整下棋思路，著法顯示使用戶能夠清楚地知道下棋過程，更準(zhǔn)確 地把握整個(gè)局面。 本文首先研究了中國象棋在計(jì)算機(jī)中的表示問題，接著討論如何產(chǎn)生著法 一系列相關(guān)內(nèi)容。其次研究了博弈樹的極小極大搜索技術(shù)及在此基礎(chǔ)上發(fā)展起 來的 Alpha-Beta 剪枝算法，使用 MFC 文檔視圖體系結(jié)構(gòu)和 Visual C+開發(fā)工具， 實(shí)現(xiàn)了一個(gè)具有一定棋力的中國象棋人機(jī)對(duì)弈程序。 關(guān)鍵詞：關(guān)鍵詞：中國象棋；人工智能；博弈樹；Alpha-Beta 搜索 The Design and Implementation of Chinese Chess Abstract The implementation of a chess program can be decomposed into two major parts: the artificial intelligence and the user interface and program assist. The part of artificial intelligence shows the way of computer thinking, and which step is the best step would be decided by it. Firstly, the computer uses search algorithms to search, and then evaluates every impossible step, finally choses the best one, the other part is used for the player to adjust his thought to the currently phases. The display of step list makes player know the process of chess distinctly, and let player make a better choice. This paper firstly studies how to represent a chess board in computer, then discusses how to generate legal moves. Secondly, this paper studies the mini-max searching procedure of Game Tree, and the Alpha-Beta pruning algorithm. A Chess- playing system is designed and developed, which is built on the integrated computer MFC SDI document view architecture by using Visual C+. Key words: Chinese chess; Artificial Intelligence; Game tree; Alpha-Beta searching 目目 錄錄 論文總頁數(shù)：22 頁 1引言.1 1.1象棋設(shè)計(jì)背景和研究意義 .1 1.2象棋設(shè)計(jì)研究方法 .1 2人工智能算法設(shè)計(jì).2 2.1棋局表示 .3 2.2著法生成 .4 2.3搜索算法 .5 2.4歷史啟發(fā)及著法排序 .9 2.5局面評(píng)估 .9 2.6程序組裝 .11 3界面及程序輔助設(shè)計(jì).12 3.1界面基本框架 .12 3.2多線程 .13 3.3著法名稱顯示 .14 3.4悔棋和還原 .15 4系統(tǒng)實(shí)現(xiàn).16 結(jié) 論.19 參考文獻(xiàn).20 致 謝.21 聲 明.22 1引言引言 1.1 象棋設(shè)計(jì)背景和研究意義象棋設(shè)計(jì)背景和研究意義 電腦游戲行業(yè)經(jīng)過二十年的發(fā)展，已經(jīng)成為與影視、音樂等并駕齊驅(qū)的全 球最重要的娛樂產(chǎn)業(yè)之一，其年銷售額超過好萊塢的全年收入。游戲，作為一 種娛樂活動(dòng)。早期的人類社會(huì)由于生產(chǎn)力及科技的制約，只能進(jìn)行一些戶外的 游戲。隨著生產(chǎn)力的發(fā)展和科技進(jìn)步，一種新的游戲方式電子游戲也隨之 誕生。 當(dāng)計(jì)算機(jī)發(fā)明以后，電子游戲又多了一個(gè)新的載體。電子游戲在整個(gè)計(jì)算 機(jī)產(chǎn)業(yè)的帶動(dòng)下不斷地創(chuàng)新、發(fā)展著。自從計(jì)算機(jī)發(fā)明，向各個(gè)領(lǐng)域發(fā)展，到 成為我們現(xiàn)在每天工作和生活必不可少的一部分的這個(gè)過程中，電子游戲也逐 步滲入我們每個(gè)人的娛樂活動(dòng)中。而計(jì)算機(jī)已經(jīng)普及的今天，對(duì)于可以用計(jì)算 機(jī)進(jìn)行程序編輯的人來說，開發(fā)屬于自己的游戲，已經(jīng)不再是夢想。事實(shí)上， 個(gè)人計(jì)算機(jī)軟件市場的大約 80%銷售份額是來自游戲軟件。棋牌游戲?qū)儆谛蓍e 類游戲，相對(duì)于角色扮演類游戲和即時(shí)戰(zhàn)略類游戲等其它游戲，具有上手快、 游戲時(shí)間短的特點(diǎn)，更利于用戶進(jìn)行放松休閑，為人們所喜愛，特別是棋類游 戲，方便、快捷、操作簡單，在休閑娛樂中占主要位置。作為中華民族悠久文 化的代表之一，中國象棋不僅源遠(yuǎn)流長，而且基礎(chǔ)廣泛，作為一項(xiàng)智力運(yùn)動(dòng)， 中國象棋開始走向世界。 隨著計(jì)算機(jī)處理速度的飛速提高，人們很早就提出了疑問：計(jì)算機(jī)是否會(huì) 超越人類？世界國際象棋大師已被計(jì)算機(jī)打敗，計(jì)算機(jī)已經(jīng)超過了人類？而人 工智能是綜合性很強(qiáng)的一門邊緣學(xué)科，它的中心任務(wù)是研究如何使計(jì)算機(jī)去做 那些過去只能靠人的智力才能做的工作。因此，對(duì)游戲開發(fā)過程中的人工智能 技術(shù)的研究自然也就成了業(yè)界的一個(gè)熱門研究方向。 1.2 象棋設(shè)計(jì)研究方法象棋設(shè)計(jì)研究方法 對(duì)于象棋來說，核心設(shè)計(jì)主要包括人工智能算法的以及整個(gè)游戲中界面及 程序輔助部分的實(shí)現(xiàn)，主要用 Visual C+ 進(jìn)行開發(fā)，里面的 MFC 類庫，使游 戲開發(fā)更加方便，并利用人工智能相關(guān)搜索算法實(shí)現(xiàn)人工智能的著法生成，從 而完善整個(gè)游戲的功能。 本文的目標(biāo)是實(shí)現(xiàn)一款有著一定下棋水平且交互友好的中國象棋人機(jī)對(duì)弈 程序。 該程序功能包括： *人機(jī)對(duì)弈； *搜索深度設(shè)定； （電腦棋力選擇） *悔棋、還原； *著法名稱顯示； 整個(gè)程序的實(shí)現(xiàn)可分為兩大部分： 一、人工智能算法設(shè)計(jì)（計(jì)算機(jī)下棋引擎） 該部分實(shí)現(xiàn)了如何讓計(jì)算機(jī)下中國象棋，其中涉及人機(jī)對(duì)弈的基本理論及 思想，是該程序的核心部分，同時(shí)也是本項(xiàng)目研究的重點(diǎn)所在。 二、界面及程序輔助設(shè)計(jì) 光有下棋引擎尚不能滿足人機(jī)交互的基本要求，因此還需要一個(gè)框架（界 面）來作為引擎的載體，同時(shí)提供一些諸如悔棋，還原之類的附屬功能（程序 輔助） 。 下面分別介紹各部分實(shí)現(xiàn)。由于界面及程序輔助部分涉及內(nèi)容寬泛而又繁 瑣，因而本文只介紹其中重點(diǎn)部分。 2人工智能算法設(shè)計(jì)人工智能算法設(shè)計(jì) 程序的基本框架： 從程序的結(jié)構(gòu)上講，大體上可以將引擎部分劃分為四大塊： 棋局表示； 著法生成； 搜索算法； 局面評(píng)估。 程序的大概的思想是： 首先使用一個(gè)數(shù)據(jù)結(jié)構(gòu)來描述棋局信息，對(duì)某一特定的棋局信息由著法生 成器生成當(dāng)前下棋方所有合法的著法并依次存入著法隊(duì)列。然后通過搜索算法 來逐一讀取著法并調(diào)用局面評(píng)估函數(shù)對(duì)該著法所產(chǎn)生的后繼局面進(jìn)行評(píng)估打分， 從中選出一個(gè)最有可能導(dǎo)致走棋方取勝的著法。在搜索的過程中還可以采用一 些輔助手段來提高搜索的效率。其過程如下所示（圖 1）： 當(dāng)前棋局 著法生成器 m1m2m3. mn 搜索算法 搜索輔助 局面評(píng)估 著法隊(duì)列 圖 1 程序結(jié)構(gòu)圖 下面將分別介紹程序各個(gè)部分： 2.1 棋局表示棋局表示 計(jì)算機(jī)下棋的前提是要讓計(jì)算機(jī)讀懂象棋。所謂讀懂，即計(jì)算機(jī)應(yīng)該能夠 清楚地了解到棋盤上的局面（棋盤上棋子的分布情況）以及下棋方所走的每一 種著法。因而首先需要設(shè)計(jì)一套數(shù)據(jù)結(jié)構(gòu)來表示棋盤上的局面以及著法。 對(duì)于棋盤局面的表示可采用傳統(tǒng)而簡單的“棋盤數(shù)組” 。即用一個(gè) 9*10 的 數(shù)組來存儲(chǔ)棋盤上的信息，數(shù)組的每個(gè)元素存儲(chǔ)棋盤上是否有棋子。這種表示 方法簡單易行（缺點(diǎn)是效率不是很高） 。按此方法棋盤的初始情形如下所示： BYTE CChessBoard910 = R, 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, 0, p, 0, 0, r ; 給所有棋子定義一個(gè)值： #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_CANON 4 /黑炮 #define B_BISHOP 5 /黑士 #define B_ELEPHANT 6 /黑象 #define B_PAWN 7 /黑卒 紅方：#define R_KING 8 /紅將 #define R_CAR 9 /紅車 #define R_HORSE 10/紅馬 #define R_CANON 11/紅炮 #define R_BISHOP 12/紅士 #define R_ELEPHANT 13/紅相 #define R_PAWN 14/紅兵 判斷顏色： #define IsBlack(x) (x=B_BEGIN if (val alpha)/保留最大值 alpha = val; return alpha; 2.4 歷史啟發(fā)及著法排序歷史啟發(fā)及著法排序 既然 Alpha-Beta 搜索算法是在“最小-最大”的基礎(chǔ)上引入“樹的裁剪” 的思想以期提高效率，那么它的效率將在很大程度上取決于樹的結(jié)構(gòu)如果 搜索了沒多久就發(fā)現(xiàn)可以進(jìn)行“裁剪”了，那么需要分析的工作量將大大減少， 效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪” 操作，那此時(shí)“裁剪”也已經(jīng)失去了它原有的價(jià)值（因?yàn)槟阋呀?jīng)分析了所有情 況，這時(shí)的 Alpha-Beta 搜索已和“最小-最大”搜索別無二致了） 。因而，要想 保證 Alpha-Beta 搜索算法的效率就需要調(diào)整樹的結(jié)構(gòu)，即調(diào)整待搜索的結(jié)點(diǎn)的 順序，使得“裁剪”可以盡可能早地發(fā)生。 可以根據(jù)部分已經(jīng)搜索過的結(jié)果來調(diào)整將要搜索的結(jié)點(diǎn)的順序。因?yàn)?，?常當(dāng)一個(gè)局面經(jīng)過搜索被認(rèn)為較好時(shí)，其子結(jié)點(diǎn)中往往有一些與它相似的局面 （如個(gè)別無關(guān)緊要的棋子位置有所不同）也是較好的。由 J.Schaeffer 所提出 的“歷史啟發(fā)” （History Heuristic）就是建立在這樣一種觀點(diǎn)之上的。在搜 索的過程中，每當(dāng)發(fā)現(xiàn)一個(gè)好的走法，就給該走法累加一個(gè)增量以記錄其“歷 史得分” ，一個(gè)多次被搜索并認(rèn)為是好的走法的“歷史得分”就會(huì)較高。對(duì)于即 將搜索的結(jié)點(diǎn)，按照“歷史得分”的高低對(duì)它們進(jìn)行排序，保證較好的走法 （“歷史得分”高的走法）排在前面，這樣 Alpha-Beta 搜索就可以盡可能早地 進(jìn)行“裁剪” ，從而保證了搜索的效率。 對(duì)于著法的排序可以使用各種排序算法，在程序中采用了歸并排序。歸并 排序的空間復(fù)雜度為 O(n)，時(shí)間復(fù)雜度為 O(nlog2n)，具有較高的效率。 2.5 局面評(píng)估局面評(píng)估 前文已經(jīng)講過了棋局表示、著法生成、搜索算法（包括搜索輔助） ， 在象 棋程序中如果說搜索算法是心臟，那么局面評(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)估中需要考慮的因素。就不同的棋類可能要考 慮的因素略有差異。在中國象棋中所要考慮的最基本的幾個(gè)因素包括如下四點(diǎn)： 1、子力總和 子力是指某一棋子本身所具有的價(jià)值。通俗地講就是一個(gè)棋子它值個(gè)什么 價(jià)。例如，車值 500 的話，那可能馬值 300，卒值 80 等等。所以在評(píng)估局面時(shí)， 首先要考慮雙方的子力總和的對(duì)比。比如紅方擁有士象全加車馬炮，而黑方只 有殘士象加雙馬，則紅方明顯占優(yōu)。 2、棋子位置 棋子位置，或稱控制區(qū)域，是指某一方的棋子在棋盤上所占據(jù)（控制）的 位置。例如，沉底炮、過河卒、以及車占士角等都是較好的棋子位置狀態(tài)，而 窩心馬、將離開底線等則屬較差的棋子位置狀態(tài)。 3、棋子的機(jī)動(dòng)性 棋子的機(jī)動(dòng)性指棋子的靈活度（可移動(dòng)性） 。例如，起始位置的車機(jī)動(dòng)性較 差，所以下棋講究早出車。同樣四面被憋馬腿的死馬機(jī)動(dòng)性也較差（對(duì)于一步 也不能走的棋子，可以認(rèn)為其機(jī)動(dòng)性為零） 。 4、棋子的相互關(guān)系 這一點(diǎn)的分析較為復(fù)雜，因?yàn)橐粋€(gè)棋子與其它子之間往往存在多重關(guān)系。 如：一個(gè)馬可能在對(duì)方的炮的攻擊之下同時(shí)它又攻擊著對(duì)方的車。 在程序中，估值函數(shù)最后返回的是每一方的總分的差值，而各方的總分就 是上面所提到的四個(gè)因素的打分的總和。 對(duì)于子力打分和控制區(qū)域打分，只要遍歷棋盤，當(dāng)遇到棋子時(shí)簡單地去查 事先定義好的“子力價(jià)值表”和“控制區(qū)域價(jià)值表” ，取出相對(duì)應(yīng)的值進(jìn)行累加 即可（這些值的具體設(shè)定參考了前人的程序并作了適當(dāng)?shù)恼{(diào)整,今后仍應(yīng)根據(jù)電 腦下棋所反映出的實(shí)際問題對(duì)這些值作適當(dāng)修改） 。 對(duì)于機(jī)動(dòng)性打分，需要求出各個(gè)子總共有多少種走法，然后根據(jù)各個(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 分別記錄該 棋子受到的威脅和被保護(hù)的值。 當(dāng)遍歷一遍棋盤之后，子力打分、控制區(qū)域打分和機(jī)動(dòng)性打分都可以完成， 而關(guān)系表也可以填完。之后，再根據(jù)關(guān)系表來具體考察棋子的相互關(guān)系，進(jìn)行 關(guān)系打分。 分析關(guān)系時(shí)，首先，對(duì)王的攻擊保護(hù)應(yīng)分離出來單獨(dú)考慮，因?yàn)閷?duì)王的保 護(hù)沒有任何意義，一旦王被吃掉整個(gè)游戲就結(jié)束了。 其次，對(duì)一個(gè)普通子，當(dāng)它既受到攻擊又受到保護(hù)的時(shí)候要注意如下幾個(gè) 問題： 1、攻擊者子力小于被攻擊者子力,攻擊方將愿意換子。比如，一個(gè)車正遭 受一個(gè)炮的攻擊，那么任何對(duì)車的保護(hù)都將失去意義對(duì)方肯定樂意用一個(gè) 炮來換一個(gè)車。 2、多攻擊單保護(hù)的情況，并且攻擊者最小子力小于被攻擊者子力與保護(hù) 者子力之和,則攻擊方可能以一子換兩子。 3、三攻擊兩保護(hù)的情況，并且攻擊者子力較小的二者之和小于被攻擊者 子力與保護(hù)者子力之和,則攻擊方可能以兩子換三子。 4、攻擊方與保護(hù)方數(shù)量相同，并且攻擊者子力小于被攻擊者子力與保護(hù)者 子力之和再減去保護(hù)者中最大子力,則攻擊方可能以 n 子換 n 子。 當(dāng)然，上述四條只是覆蓋了最常見的幾種情況，覆蓋并不全面。而且，在 程序中并沒有直接地重新考慮雙方兌子之后的控制區(qū)域及機(jī)動(dòng)性變化情況（之 所以說沒有“直接地重新考慮” ，是因?yàn)樗阉骼^續(xù)展開結(jié)點(diǎn)后仍會(huì)考慮這些因素， 只是目前不知這樣效果是否受影響考察這兩種方法在效果上的差異需要一 定數(shù)量的試驗(yàn)數(shù)據(jù)的支持） 。所以，如果今后要對(duì)引擎進(jìn)行改進(jìn)，提高程序的下 棋水平的話，還應(yīng)當(dāng)在此進(jìn)行研究。 2.6 程序組裝程序組裝 至此，已具備了實(shí)現(xiàn)一款中國象棋對(duì)弈程序引擎部分的所有要素，將上述 模塊分別寫作.h 頭文件。如下： Define.h 象棋相關(guān)定義。包括棋盤局面和著法的表示。 CMoveGenerator.h 著法生成器。就當(dāng)前局面生成某一方所有合法著法。 CSearchEngine.h 搜索部分。使用搜索求出最佳著法。 HistoryHeuristic.h 歷史啟發(fā)。Alpha-Beta 搜索之補(bǔ)充，以提高搜索效率。 著法排序。對(duì)著法按其歷史得分進(jìn)行降序排序，以提高搜索效率。 CEveluate.h 局面評(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é)果， 便可簡單的測試引擎了（采用輸入著法的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)的方式來傳送用 戶走棋的信息。同樣，程序顯示計(jì)算機(jī)走棋的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)來做出回應(yīng)） 。 此后，等到界面部分初步完成，引擎的上述各模塊無需作任何改動(dòng)，仍以. h 頭文件的形式加入界面工程，只要由界面中的某個(gè).cpp 文件調(diào)用搜索函數(shù)即 可。這種連接方式實(shí)現(xiàn)起來非常簡單。 3界面及程序輔助設(shè)計(jì)界面及程序輔助設(shè)計(jì) 3.1 界面基本框架界面基本框架 關(guān)于界面，建了一個(gè)基于對(duì)話框的 MFC 應(yīng)用程序。主要工作都在對(duì)話框類 的兩個(gè)文件 CChessDlg.h 和 CChessDlg.cpp 下展開。 代碼主要分布于以下三大部分： 一、初始化部分 BOOL CCChessUIDlg:OnInitDialog() OnInitDialog()負(fù)責(zé)的是對(duì)話框的初始化?？梢园延嘘P(guān)中國象棋的棋局初 始化情況也放在了這里面。初始化的內(nèi)容包括： 對(duì)引擎部分所用到的變量的初始化。包括對(duì)棋盤上的棋子位置進(jìn)行初始化 （棋盤數(shù)組的初始化） ，對(duì)搜索深度、當(dāng)前走棋方標(biāo)志、棋局是否結(jié)束標(biāo)志等的 初始化； 對(duì)棋盤、棋子的貼圖位置（即棋盤、棋子在程序中實(shí)際顯示位置）的初始 化； 對(duì)程序輔助部分所用到的一些變量的初始化。包括對(duì)悔棋、還原隊(duì)列的清 空，棋盤、棋子樣式的默認(rèn)形式，下棋模式的默認(rèn)選擇，以及著法名稱列表的 初始化等。 二、繪圖部分 void CCChessUIDlg:OnPaint() OnPaint()函數(shù)負(fù)責(zé)的是程序界面的繪圖。因此，在這里將要完成棋盤、棋 子的顯示走棋起始位置和目標(biāo)位置的提示框的顯示。 由于棋盤、棋子等都是以位圖的形式給出的。所以在 OnPaint()函數(shù)里做 的工作主要都是在貼位圖。 需要注意的是由于位圖文件不能像 GIF 文件那樣有透明的背景并且棋子是 圓形的而位圖文件只能是矩形的，所以如果直接貼圖的話會(huì)在棋盤上留下一塊 白色的邊框棋子的背景。因此，要想讓棋子文件的背景“隱藏”需要通過 一些“與”和“異或”操作來屏蔽掉棋子的背景。 三、走棋部分（用戶動(dòng)作響應(yīng)部分） 為 WM_LBUTTONDOWN 消息添加消息響應(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ù)來進(jìn)行響應(yīng)。其中第二個(gè)參數(shù) CPoint point 是在 本程序中所要用到的，它給出了當(dāng)鼠標(biāo)左鍵被按下時(shí)，鼠標(biāo)指針的位置坐標(biāo)。 可以通過這一信息來得知用戶的走法。 在 OnLButtonDown 函數(shù)里處理如下兩種操作： 1、如果用戶點(diǎn)擊鼠標(biāo)的位置落在己方的棋子上，表示用戶選中了該棋子， 下一步將移動(dòng)該子進(jìn)行走棋（也可能用戶下一步將會(huì)選擇己方另外的棋子，總 之這一操作會(huì)記錄下用戶所選的將要走的棋子） 。 2、如果之前用戶已經(jīng)選過了棋子，那么這一次的點(diǎn)擊（如果不是另選本方 的其它棋子的話）表達(dá)了用戶的一次走棋過程。在收到用戶傳達(dá)的走棋信息后， 可先判斷該著法是否合法（是否符合中國象棋的游戲規(guī)則） ，如果合法，則執(zhí)行 之。緊接著調(diào)用引擎的搜索函數(shù)計(jì)算出計(jì)算機(jī)對(duì)用戶著法的應(yīng)著，然后執(zhí)行該 應(yīng)著。 如此，在 OnLButtonDown 函數(shù)里，實(shí)現(xiàn)了人與機(jī)器的對(duì)弈（當(dāng)然每走一步 棋，也還需要繪圖函數(shù)來顯示棋盤局面的更新） 。 以上三部分并非界面程序的全部，而僅僅是與程序密切相關(guān)的部分。此外 還有其它部分對(duì)程序同樣必不可少，但這些部分主要由 MFC 自動(dòng)生成，無需人 為改動(dòng)，故在此不多做介紹。 3.2 多線程多線程 如采用單線程方式，按照如下順序編寫代碼： 用戶走棋 計(jì)算機(jī)思考并走棋 按這種方式編寫的程序似乎毫無問題，程序運(yùn)行一切正常。 然而，在給程序加入這些功能（后面將會(huì)在講到其實(shí)現(xiàn)）后，程序出現(xiàn)了 異常：有時(shí)對(duì)用戶方的功能完全正確，而對(duì)電腦方的有些功能卻不起作用！是 由于程序在進(jìn)行搜索時(shí)會(huì)占用大量的 CPU 時(shí)間，因而阻塞了位于同一線程內(nèi)的 其他指令，使之無法正常工作。解決方案就是另外開一個(gè)線程，讓各程序分開 于多個(gè)線程。 啟動(dòng)一個(gè)新的線程的方法非常簡單，只需調(diào)用函數(shù) AfxBeginThread 即可， 函數(shù)原型： CWinThread* AfxBeginThread( AFX_THREADPROC ThinkProc, LPVOID pParam, int nPriority = THREAD_PRIORITY_NORMAL, UINT nStackSize = 0, DWORD dwCreateFlags = 0, LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL ); 該函數(shù)啟動(dòng)一個(gè)新的線程并返回一個(gè)指向該新線程對(duì)象的指針，然后新的 線程與啟動(dòng)該新線程的線程同時(shí)運(yùn)行。該函數(shù)的第一個(gè)參數(shù) AFX_THREADPROC ThinkProc 指定了線程函數(shù)。線程函數(shù)的內(nèi)容即為新線程所要執(zhí)行的內(nèi)容，線 程函數(shù)執(zhí)行完畢，新線程結(jié)束（自動(dòng)銷毀） 。 線程函數(shù)必須被定義為全局函數(shù)，其返回值類型必須是 UINT，必須有一個(gè) LPVOID 類型的參數(shù)?？梢园颜{(diào)用引擎部分的搜索函數(shù)的代碼以及完成走棋動(dòng)作 的代碼放入所定義的思考線程內(nèi)，如下： DWORD WINAPI ThinkProc(LPVOID pParam) CChessDlg* pDlg=(CChessDlg*)pParam; pDlg-Think(); /計(jì)算機(jī)思考并走棋 return 0; 然后，只要將原先調(diào)搜索函數(shù)并完成走棋的代碼代之以調(diào)用 AfxBeginThread 來啟動(dòng)新線程即可，實(shí)現(xiàn)了程序的多線程，不能正常工作的問 題也就隨之解決了。 3.3 著法名稱顯示著法名稱顯示 每當(dāng)下棋方（用戶或是計(jì)算機(jī)）走一步棋，在棋盤旁邊的一個(gè)列表框控件 （List Box）中按照中國象棋關(guān)于著法描述的規(guī)范要求顯示出該著法的名稱。 如：紅炮二平五、黑馬 8 進(jìn) 7 此類。為了獲得該著法名稱，寫了一個(gè)六百余行 的函數(shù)。其功能就是將被移動(dòng)的棋子類型以及走法的起點(diǎn)坐標(biāo)、終點(diǎn)坐標(biāo)這些 信息轉(zhuǎn)換成中國象棋所規(guī)范的著法名稱。由于該函數(shù)主要涉及的是中國象棋關(guān) 于著法表示的規(guī)范要求，故在此不對(duì)其具體實(shí)現(xiàn)做額外的解釋。主要討論的是 如何對(duì)列表框控件（List Box）進(jìn)行操作，以顯示或刪除著法名稱。 首先，在 ChessDlg 下定義以下函數(shù)： this-GetMoveStr(nFromX,nFromY,nToX,nToY,nSourceID); /用來獲得剛下的一步棋的走法； void CChessDlg:AddChessRecord(int nFromX,int nFromY,int nToX,int nToY,int nUserChessColor,int nSourceID) /將走法添加進(jìn)下棋記錄； 然后，顯示在 Listbox 中。 當(dāng)列表框中的項(xiàng)的數(shù)目超過列表框的顯示范圍時(shí)，列表框會(huì)自動(dòng)添加垂直 滾動(dòng)條（前提是其 VerticalScrollbar 屬性要為 True該屬性默認(rèn)即為 True） 。但是顯示的內(nèi)容依然是最早加進(jìn)來的項(xiàng)。在控件屬性里選擇 Vertical Scroll，使得列表框可垂直滾動(dòng)以顯示最新的著法名稱。 想要從列表框中刪除項(xiàng)時(shí)，可以使用 m_lstChessRecord.DeleteString(m_lstChessRecord.GetCount()-1); 減一之后正好是最后一項(xiàng)的行號(hào)。 3.4 悔棋和還原悔棋和還原 悔棋和還原是棋類軟件中較為基本的功能。要實(shí)現(xiàn)悔棋和還原功能，首先 要明確哪些信息應(yīng)當(dāng)被保存以供悔棋和還原所使用。 在程序中保存了如下信息： 棋局表示中所定義的棋盤數(shù)組； 各棋子的貼圖位置。 這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋 子的信息，而只是保存之前一步的走棋信息。此后當(dāng)悔棋的時(shí)候，需要撤銷著 法；還原的時(shí)候，需要執(zhí)行著法。然而，在編寫自己的程序時(shí)一來考慮到程序 的可讀性和不易出錯(cuò)性，二來考慮到對(duì)當(dāng)今的計(jì)算機(jī)的配置來說這點(diǎn)開銷基本 上不會(huì)對(duì)程序的效率產(chǎn)生什么影響。因此保存了全部棋子的信息。 根據(jù)所要保存的數(shù)據(jù)定義了如下基本結(jié)構(gòu)類型： typedef struct CHESSMOVE cmChessMove; short nChessID;/被吃掉的棋子 UNDOMOVE; 在對(duì)弈過程中，每一回合都將棋局信息（這里指前面所說的需要保存的信 息）保存至走法隊(duì)列，以供悔棋所用。還原功能是與悔棋功能相對(duì)應(yīng)的，只有 當(dāng)產(chǎn)生了悔棋功能之后，還原功能才會(huì)被激活。一個(gè)回合的結(jié)束意味著前一次 操作沒有悔棋功能的產(chǎn)生，因此還原隊(duì)列也應(yīng)被清空。 在悔棋中主要完成了以下任務(wù)： 1.下棋回合數(shù)減一； 2.將當(dāng)前局面信息保存至走法隊(duì)列，