- 相關推薦
免費vc中國象棋軟件(一)
【摘要】：人機博弈是人工智能研究的經典課題之一。憑借設計優良的算法和計算機的快速運算能力，計算機可以在人機對弈中表現出相當高的“智能”。通常，一款象棋程序的實現可以被分為下棋引擎（人工智能）和外殼（界面及程序輔助）兩大部分。本文將介紹如何實現一款中國象棋對弈程序。
【關鍵詞】：中國象棋；人工智能；博弈樹；Alpha-Beta搜索；歷史啟發；界面；多線程；計時器；列表框；MFC。
一、前 言
我們的目標是實現一款有著一定下棋水平且交互友好的中國象棋人機對弈程序。
該程序功能包括：
*人機對弈；
*盲棋模式；
（注：此功能為創新功能）
*搜索深度設定；
（電腦棋力選擇）
*棋子、棋盤樣式選擇；
*悔棋、還原；
*著法名稱顯示；
*下棋雙方計時；
整個程序的實現可分為兩大部分：
一、人工智能部分（計算機下棋引擎）
該部分實現了如何讓計算機下中國象棋，其中涉及人機博弈的基本理論及思想，是該程序的核心部分，同時也是本項目研究的重點所在。
二、界面及程序輔助部分
光有下棋引擎尚不能滿足人機交互的基本要求，因此我們還需要一個框架（界面）來作為引擎的載體，同時提供一些諸如悔棋，計時之類的附屬功能（程序輔助）來為程序增色添彩。
下面分別介紹各部分實現。由于界面及程序輔助部分涉及內容寬泛而又繁瑣，因而本文只介紹其中重點部分以及我們在開發過程中曾經遇到過困難的地方。
二、人工智能部分（計算機下棋引擎）
1、概 述
程序的基本框架：
從程序的結構上講，大體上可以將引擎部分劃分為四大塊：
棋局表示；
著法生成；
搜索算法；
局面評估。
程序的大概的思想是：
首先使用一個數據結構來描述棋局信息，對某一特定的棋局信息由著法生成器生成當前下棋方所有合法的著法并依次存入著法隊列。然后通過搜索算法來逐一讀取著法并調用局面評估函數對該著法所產生的后繼局面進行評估打分，從中選出一個最有可能導致走棋方取勝的著法。在搜索的過程中還可以采用一些輔助手段來提高搜索的效率。其過程如下圖所示：
下面將分別介紹各個部分。
2、棋局表示
計算機下棋的前提是要讓計算機讀懂象棋。所謂讀懂，即計算機應該能夠清楚地了解到棋盤上的局面（棋盤上棋子的分布情況）以及下棋方所走的每一種著法。因而首先我們需要有一套數據結構來表示棋盤上的局面以及著法。
對于棋盤局面的表示我們采用了最傳統的同時也是最為簡單的“棋盤數組”。即用一個9*10的數組來存儲棋盤上的信息，數組的每個元素存儲棋盤上相應位置是何種棋子。這種表示方法簡單易行（缺點是效率不是很高）。按此方法棋盤的初始情形如下所示：
BYTE CChessBoard[9][10] = {
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
};
其中“0”表示無棋子，大寫字母表示紅方棋子，小寫字母表示黑方棋子（所有這些大小寫字母都是用宏定義的整數）。具體如下：
“R”表示紅車；“H”表示紅馬；“E”表示紅相；“A”表示紅仕；“K”表示紅帥；“C”表示紅炮；“P”表示紅兵。
“r”表示黑車；“h”表示黑馬；“e”表示黑象；“a”表示黑士；“k”表示黑將；“c”表示黑炮；“p”表示黑卒。
此外這個數組也表明了我們對棋盤進行了如右圖所示的編號，并約定紅方棋子總處于棋盤的下方。
對于著法的表示，我們直接借用棋盤數組的下標來記錄著法的起點和目標點。至于是什么棋子在走，以及是否吃子、吃的是什么子，我們在著法結構中并不記錄。這些信息由外部讀取棋盤上起點、終點的數據獲得。著法結構定義如下，其中還包含了對著法的歷史得分的記錄項，以供后面要講到的“歷史啟發”所用。
typedef struct _cchessmove{
POINT ptFrom; // 起點
POINT ptTo; // 目標點
int nScore; // 該走法的歷史得分
} CCHESSMOVE ; // 走法結構
有了對棋盤局面和著法的表示之后，程序才能夠完成以下操作：
生成所有合法著法；
執行著法、撤銷著法；
針對某一局面進行評估。
因而，棋局表示好比是整個程序（計算機下棋引擎部分）的地基，之后所有的操作都將建立在其基礎上。
3、著法生成
我們的程序需要讓計算機在輪到它走子的時候能夠執行一步它認為對它最有利的著法，那前提就是它要有諸多（也可能是唯一）可供選擇的著法，提供所有候選著法的“清單”就是我們的著法生成器所要完成的。之后用搜索函數來搜索“清單”，并用局面評估函數來逐一打分，最后就可以選擇出“最佳著法”并執行了。
在著法生成器中，我們采用的基本思想就是遍歷整個棋盤（一個接一個地查看棋盤上的每個位置點），當發現有當前下棋方的棋子時先判斷它是何種類型的棋子，然后根據其棋子類型而相應地找出其所有合法著法并存入著法隊列。
這里談到的“合法著法”包括以下幾點：
1、 各棋子按其行子規則行子。諸如馬跳“日”字、象走“田”字、士在九宮內斜行等等（這里需要特別注意的是卒（兵）的行子規則會隨其所在位置的不同而發生變化——過河后可以左右平移）。
2、 行子不能越出棋盤的界限。當然所有子都不能走到棋盤的外面，同時某些特定的子還有自己的行棋界限，如將、士不能出九宮，象不能過河。
3、 行子的半路上不能有子阻攔（除了炮需要隔一個子才能打子之外）以及行子的目的點不能有本方棋子（當然不能自己吃自己了）。
4、 將帥不能碰面（本程序中只在生成計算機的著法時認為將帥碰面是非法的，而對用戶所走的導致將帥碰面的著法并不認為其非法，而只是產生敗局罷了）。
產生了著法后要將其存入著法隊列以供搜索之用，由于搜索會搜索多層（即考慮雙方你來我往好幾步，這樣才有利于對局面進行評估以盡可能避免“目光短淺”），所以在把著法存入著法隊列的時候還要同時存儲該著法所屬的搜索層數。因此我們將著法隊列定義為二維數組MoveList[12][80]，其中第一個數組下標為層數，第二個數組下標為每一層的全部著法數。
關于搜索層數，我將數組下標設定為12，實際使用的是1到11（在界面中我又將其限定為1—10）。搜索層數的增加會顯著提高電腦的下棋水平（當然計算機的棋力在很大程度上也依賴于局面評估）。在我的迅馳1.5，736M內存的筆記本上最多只能搜索5層，再多將導致搜索時間達到令人無法容忍的地步（這里還需要特別說明的是，搜索的速度也和著法生成的效率以及局面評估的復雜度有關，因為每分析一個結點都要執行這兩種操作）。
對于每一層的著法數，也就是當前下棋方針對當前局面的所有可選的合法著法，據有關數據統計在象棋實戰中一般最多情況下也就五六十種。定義第二個數組下標為80，應當可以保證十分的安全。
著法生成為搜索部分提供了“原料”，接下來的任務就交給搜索和局面評估了。
4、搜索算法
搜索算法對于整個下棋引擎來說都是至關重要的。它如同程序的心臟，驅動著整個程序。搜索算法的好壞直接影響著程序執行的效率（從某種角度上，它影響著計算機的下棋水平。因為，計算機必須在有限的時間內完成思考，搜索速度快意味著在相同的時間內程序可以“看”得更遠，“想”的更多）。關于棋類對弈程序中的搜索算法，經前人的努力已形成了非常成熟的Alpha-Beta搜索算法[ Alpha-beta算法，該算法是由匹茲堡大學的三位科學家Newell, Shaw and Simon于1958年提出的。]以及其它一些輔助增強算法（還有眾多基于Alpha-Beta算法的派生、變種算法）。鑒于目前我們的知識儲備、時間、精力等均達不到推陳出新、另開爐灶的要求，再加之前人的算法著實已相當完善，所以我們在自己的程序中直接借鑒了Alpha-Beta搜索算法并輔以了歷史啟發。本節先介紹Alpha-Beta搜索算法：
在中國象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對方，或者避免被將死。
由此，我們可以用一棵“博弈樹”（一棵n叉樹）來表示下棋的過程——樹中每一個結點代表棋盤上的一個局面，對每一個局面（結點）根據不同的走法又產生不同的局面（生出新的結點），如此不斷直到再無可選擇的走法，即到達葉子結點（棋局結束）。中國象棋的博弈樹的模型大概如下圖所示，我們可以把其中連接結點的線段看作是著法，不同的著法自然產生不同的局面。
該樹包含三種類型的結點：
奇數層的中間結點（以及根結點），表示輪到紅方走棋；
偶數層的中間結點，表示輪到黑方走棋；
葉子結點，表示棋局結束。
現在讓計算機來下中國象棋，它應當選擇一步對它最有利的著法（最終導致它取勝的著法）。獲得最佳著法的方法就是“試走”每一種可能的著法，比較它們所產生的不同后果，然后從中選出能夠產生對自己最有利的局面的著法。
結合上面所講的博弈樹，如果我們給每個結點都打一個分值來評價其對應的局面（這一任務由后面所講的局面評估來完成），那么我們可以通過比較該分值的大小來判斷局面的優劣。假定甲乙兩方下棋，甲勝的局面是一個極大值（一個很大的正數），那么乙勝的局面就是一個極小值（極大值的負值），和棋的局面則是零值（或是接近零的值）。如此，當輪到甲走棋時他會盡可能地讓局面上的分值大，相反輪到乙走棋時他會選盡可能地讓局面上的分值小。反映到博弈樹上，即如果我們假設奇數層表示輪到甲方走棋，偶數層表示輪到乙方走棋。那么由于甲方希望棋盤上的分值盡可能大，則在偶數層上我們會挑選分值最大的結點——偶數層的結點是甲走完一步棋之后的棋盤局面，反映了甲方對棋局形勢的要求。同樣道理，由于乙方希望棋盤上的分值盡可能小，那么在奇數層上我們會選擇分值最小的結點。這就是“最小-最大”（Minimax）[ “最小-最大”（Minimax）最早是由John von Nuoma（1903-1957，美籍匈牙利數學家）在60多年前完整描述的：
1、假設有對局面評分的方法，來預測棋手甲（我們稱為最大者）會贏，或者對手（最小者）會贏，或者是和棋。評分用數字表示，正數代表最大者領先，負數代表最小者領先，零代表誰也不占便宜；
2、最大者的任務是增加棋盤局面的評分（即盡量讓評分最大）；
3、最小者的任務是減少棋盤局面的評分（即盡量讓評分最�。�；
4、假設誰也不會犯錯誤，即他們都走能讓使局面對自己最有利的著法。]的基本思想。這樣搜索函數在估值函數的協助下可以通過在奇數層選擇分值最大（最�。┑慕Y點，在偶數層選擇分值最�。ㄗ畲螅┑慕Y點的方式來搜索以當前局面為根結點、限定搜索層數以內的整棵樹來獲得一個最佳的著法。然而不幸的是，博弈樹相當龐大（它會成指數增長），因而搜索（限定層數以內的）整棵樹是一件相當費時的工作——其時間復雜度為O(bn)。其中b是分枝因子，即針對各種局面的合法著法的數目的平均值，n是搜索的深度。對于中國象棋而言，在中盤時平均著法數目大約是40種左右，那么搜索4層需要檢查250萬條路線，搜索5層需要檢查1億條路線，搜索6層需要檢查40億條路線�。�！
幸運的是，Alpha-Beta搜索使得我們能在不影響搜索精度的前提下大幅減少工作量。
因為，如果考慮到下棋是一個你來我往的交替進行并且相互“較勁”的過程。由于每一方都會盡可能將局面導向對自己有利而對對方不利的方向（我們假定下棋雙方對棋局有著同樣的認知，即你認為對你很糟糕的局面，在你的對手看來則是對他很有利的局面），那么某些局面由于能夠產生出很糟糕的局面因而根本沒有再繼續考慮的價值。所以當你看到某個局面有可能產生很糟糕的局面時（確切地說這里的“很糟糕”是與之前分析的情況相比較而言的），你應當立刻停止對其剩余子結點的分析——不要對它再抱任何幻想了，如果你選擇了它，那么你必將得到那個很糟糕的局面，甚至可能更糟……這樣一來便可以在很大程度上減少搜索的工作量，提高搜索效率，這稱為“樹的裁剪”。
下面用圖來進一步說明“樹的裁剪”。為了簡便起見，我將博弈樹進行了簡化——每個結點只有三個分支，實際情況中，剛才講過在中盤應有大約40個分支。
我們假定棋盤上的局面發展到了結點A（見下圖），現在輪到你走棋了，你是“最大的一方”——即你希望棋局的分值盡可能的高。讓我們試著搜索兩層來看一看“樹的裁剪”對提高搜索效率的幫助。
圖中表示該結點要取子結點中的最大值；表示該結點要取子結點中的最小值。
首先，我們考察結點A的子結點B。結點B所屬的這一層是輪到你的對手——“最小者”來走棋了，他的目的是使得棋局的分值盡可能的小。依次考察結點B的各個子結點，查看它們的分值（因為我們事先約定好了搜索兩層，現在已達到搜索深度的要求了，所以就停下來調用局面評估函數來給它打分）。結點Ｂ的第一個子結點（從左到右算起）返回10，第二個子結點返回了-5，第三個子結點返回了２。由于結點Ｂ這層是你的對手來做選擇，我們假設他一定會做出明智的選擇（你不能寄希望于你的對手會走出一步“昏招”），那么他會選擇返回值為-5的那個結點。-5最終也就成了從結點B傳遞回的值，即倘若你（現在位于結點A）選擇了產生結點B的走法，使得局面發展到了結點B。那么下一步，你的對手的選擇就會使得棋局發展成為分值為-5的那個結點所表示的局面。
我們再來分析結點A的第二個子結點C，結點C與結點B同屬一層，它依然是輪到你的對手作選擇。依次查看結點C的各個子結點的分值，其第一個子結點返回了-8……
好了，該是“裁剪”登場的時候了。你已經不必再繼續考察結點C的剩余子結點了，因為結點C已經夠糟糕的了，不管結點C的剩余子結點有怎樣的分值，它最多只能傳回-8（有可能其剩余子結點中還有分值更小的結點，因而結點C還有可能傳回更小的值）。而與前面已經分析過的結點B所傳回-5相比較，作為“最大一方”的你顯然更不愿意看到-8的局面。所以，你當然不會選擇相應的著法使得局面發展成為結點C。因為那樣的話，下一步你的對手就會帶給你一個分值不高于-8的局面。
由此，我們就在不影響搜索質量的前提下避免了搜索“無價值的”結點C的剩余子結點的大量工作，從而節省了寶貴時間，為在同樣機器配置下搜索更多的層數提供了可能。
“最小-最大”的思想再加上“對樹的裁剪”，這就是Alpha-Beta搜索算法的核心。最基本的Alpha-Beta算法的代碼如下：
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0) //如果是葉子節點（到達搜索深度要求）
return Evaluate(); //則由局面評估函數返回估值
GenerateLegalMoves(); //產生所有合法著法
while (MovesLeft()) //遍歷所有著法
{
MakeNextMove(); //執行著法
int val = -AlphaBeta(depth - 1, -beta, -alpha); //遞歸調用 UnmakeMove(); //撤銷著法
if (val >= beta) //裁剪
return beta;
if (val > alpha) //保留最大值
alpha = val;
}
return alpha;
}
5、歷史啟發及著法排序（搜索輔助）
既然Alpha-Beta搜索算法是在“最小-最大”的基礎上引入“樹的裁剪”的思想以期提高效率，那么它的效率將在很大程度上取決于樹的結構——如果搜索了沒多久就發現可以進行“裁剪”了，那么需要分析的工作量將大大減少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此時“裁剪”也已經失去了它原有的價值（因為你已經分析了所有情況，這時的Alpha-Beta搜索已和“最小-最大”搜索別無二致了）。因而，要想保證Alpha-Beta搜索算法的效率就需要調整樹的結構，即調整待搜索的結點的順序，使得“裁剪”可以盡可能早地發生。
我們可以根據部分已經搜索過的結果來調整將要搜索的結點的順序。因為，通常當一個局面經過搜索被認為較好時，其子結點中往往有一些與它相似的局面（如個別無關緊要的棋子位置有所不同）也是較好的。由J.Schaeffer所提出的“歷史啟發”（History Heuristic）就是建立在這樣一種觀點之上的。在搜索的過程中，每當發現一個好的走法，我們就給該走法累加一個增量以記錄其“歷史得分”，一個多次被搜索并認為是好的走法的“歷史得分”就會較高。對于即將搜索的結點，按照“歷史得分”的高低對它們進行排序，保證較好的走法（“歷史得分”高的走法）排在前面，這樣Alpha-Beta搜索就可以盡可能早地進行“裁剪”，從而保證了搜索的效率。
對于著法的排序可以使用各種排序算法，在我們的程序中采用了歸并排序。歸并排序的空間復雜度為O(n)，時間復雜度為O(nlog2n)，具有較高的效率。
6、局面評估
前面已經講過了棋局表示、著法生成、搜索算法（包括搜索輔助）， 在象棋程序中如果說搜索算法是心臟，那么局面評估就是大腦。搜索算法負責驅動整個程序，而局面評估則負責對搜索的內容進行判斷和評價。因而搜索與局面評估是整個下棋引擎的核心。
首先，先介紹一下在局面評估中需要考慮的因素。就不同的棋類可能要考慮的因素略有差異。在中國象棋中所要考慮的最基本的幾個因素包括如下四點：
1、子力總和
子力是指某一棋子本身所具有的價值。通俗地講就是一個棋子它值個什么價。例如，車值500的話，那可能馬值300，卒值80等等。所以在評估局面時，我們首先要考慮雙方的子力總和的對比。比如紅方擁有士象全加車馬炮，而黑方只有殘士象加雙馬，則紅方明顯占優。
2、棋子位置（控制區域）
棋子位置，或稱控制區域，是指某一方的棋子在棋盤上所占據（控制）的位置。例如，沉底炮、過河卒、以及車占士角等都是較好的棋子位置狀態，而窩心馬、將離開底線等則屬較差的棋子位置狀態。
3、棋子的機動性
棋子的機動性指棋子的靈活度（可移動性）。例如，起始位置的車機動性較差，所以我們下棋講究早出車。同樣四面被憋馬腿的死馬機動性也較差（對于一步也不能走的棋子，可以認為其機動性為零）。
4、棋子的相互關系（包括攻擊關系和保護關系）
這一點的分析較為復雜，因為一個棋子與其它子之間往往存在多重關系。如：一個馬可能在對方的炮的攻擊之下同時它又攻擊著對方的車。
在我的程序中，估值函數最后返回的是每一方的總分的差值，而各方的總分就是上面所提到的四個因素的打分的總和。
對于子力打分和控制區域打分，只要遍歷棋盤，當遇到棋子時簡單地去查事先定義好的“子力價值表”和“控制區域價值表”，取出相對應的值進行累加即可（這些值的具體設定參考了前人的程序并作了適當的調整,今后仍應根據電腦下棋所反映出的實際問題對這些值作適當修改）。
對于機動性打分，需要求出各個子總共有多少種走法，然后根據各個子所不同的機動性價值每多一種走法就加一次相應的分數。
對棋子間相互關系的打分，我先定義了一個關系表的結構類型
typedef struct _relationtable{
BYTE nCChessID ;
int nUAttackCount ;
int nUGuardCount ;
BYTE UnderAttack[5];
BYTE UnderGurad[5];
} RelationTable;
RelationTable RelationOfMan[9][10]; // 關系表
其中nCChessID給出棋子的類型，nUAttackCount和nUGuardCount分別記錄正攻擊該子的棋子數量和正保護該子的棋子數量，UnderAttack[5]和UnderGuard[5]則存放攻擊該子和保護該子的具體棋子（的類型）。因為考慮到實戰中幾乎不可能出現同時有超過五個棋子攻擊/保護一個子的情況，故數組下標設定為5。
當遍歷一遍棋盤之后，子力打分、控制區域打分和機動性打分都可以完成，而關系表也可以填完。之后，再根據關系表來具體考察棋子的相互關系，進行關系打分。
分析關系時，首先，對王的攻擊保護應分離出來單獨考慮，因為對王的保護沒有任何意義，一旦王被吃掉整個游戲就結束了。
其次，對一個普通子，當它既受到攻擊又受到保護的時候要注意如下幾個問題：
1、攻擊者子力小于被攻擊者子力,攻擊方將愿意換子。比如，一個車正遭受一個炮的攻擊，那么任何對車的保護都將失去意義——對方肯定樂意用一個炮來換一個車。
2、多攻擊\單保護的情況，并且攻擊者最小子力小于被攻擊者子力與保護者子力之和,則攻擊方可能以一子換兩子。
3、三攻擊\兩保護的情況，并且攻擊者子力較小的二者之和小于被攻擊者子力與保護者子力之和,則攻擊方可能以兩子換三子。
4、攻擊方與保護方數量相同，并且攻擊者子力小于被攻擊者子力與保護者子力之和再減去保護者中最大子力,則攻擊方可能以n子換n子。
當然，上述四條只是覆蓋了最常見的幾種情況，覆蓋并不全面。而且，在我們的程序中并沒有直接地重新考慮雙方兌子之后的控制區域及機動性變化情況（之所以說沒有“直接地重新考慮”，是因為搜索繼續展開結點后仍會考慮這些因素，只是目前我們尚不知這樣效果是否受影響——考察這兩種方法在效果上的差異需要一定數量的試驗數據的支持）。所以，如果今后要對引擎進行改進，提高程序的下棋水平的話，還應當在此多做文章……
7、程序組裝
至此，我們已具備了實現一款中國象棋對弈程序引擎部分的所有要素，我將上述模塊分別寫作.h頭文件。如下：
CChessDef.h
——象棋相關定義。包括棋盤局面和著法的表示。
CChessMove.h
——著法生成器。就當前局面生成某一方所有合法著法。
CChessSearch.h
——搜索部分。使用Alpha-Beta搜索求出最佳著法。
HistoryHeuristic.h
——歷史啟發。Alpha-Beta搜索之補充，以提高搜索效率。
SortMove.h
——著法排序。對著法按其歷史得分進行降序排序，以提高搜索效率。
CChessEvaluate.h
——局面評估。為某一特定局面進行評分。
當實現了引擎部分的各要素時，程序的界面部分還尚未開工。因此我們暫時先建了一個Win32控制臺項目（這是我們所最熟悉的，也是我們在課堂上一直用的），之后只要再添加一個.cpp文件負責接受用戶的輸入、調用搜索函數、顯示搜索結果，便可簡單的測試引擎了（我們采用輸入著法的起點坐標和終點坐標的方式來傳送用戶走棋的信息。同樣，程序顯示計算機走棋的起點坐標和終點坐標來做出回應）。
此后，等到界面部分初步完成以后，引擎的上述各模塊無需作任何改動，仍以.h頭文件的形式加入界面工程，只要由界面中的某個.cpp文件調用搜索函數即可。這種連接方式實現起來非常簡單，基本上不需要其它額外作業。
三、界面及程序輔助部分
1、界面基本框架
關于界面，我們建了一個基于對話框的MFC應用程序。之后主要工作都在對話框類的兩個文件CChessUIDlg.h和CChessUIDlg.cpp下展開。
我們所寫的代碼主要分布于以下三大部分：
一、初始化部分
BOOL CCChessUIDlg::OnInitDialog()
{
}
OnInitDialog()負責的是對話框的初始化。我們把有關中國象棋的棋局初始化情況也放在了這里面。初始化的內容包括：
對引擎部分所用到的變量的初始化。包括對棋盤上的棋子位置進行初始化（棋盤數組的初始化），對搜索深度、當前走棋方標志、棋局是否結束標志等的初始化；
對棋盤、棋子的貼圖位置（即棋盤、棋子在程序中實際顯示位置）的初始化；
對程序輔助部分所用到的一些變量的初始化。包括對悔棋、還原隊列的清空，棋盤、棋子樣式的默認選擇，下棋模式的默認選擇，計時器顯示的初始化，以及著法名稱列表的初始化等。
二、繪圖部分
void CCChessUIDlg::OnPaint()
{
}
OnPaint()函數負責的是程序界面的繪圖。因此，在這里我們要完成棋盤、棋子的顯示（如果用戶選擇了盲棋模式，則不進行棋子的繪圖，而是在屏幕中央給出提示信息表明當前為盲棋模式），走棋起始位置和目標位置的提示框的顯示。
由于我們的棋盤、棋子等都是以位圖的形式給出的。所以在OnPaint()函數里我們做的工作主要都是在貼位圖。
需要注意的是由于位圖文件不能像GIF文件那樣有透明的背景并且棋子是圓形的而位圖文件只能是矩形的，所以如果直接貼圖的話會在棋盤上留下一塊白色的邊框——棋子的背景。因此，要想讓棋子文件的背景“隱藏”需要通過一些“與”和“異或”操作來屏蔽掉棋子的背景。
三、走棋部分（用戶動作響應部分）
為WM_LBUTTONDOWN消息添加消息響應事件，可得到如下函數：
void CCChessUIDlg::OnLButtonDown(UINT nFlags,CPoint point)
{
}
當用戶在窗口客戶區按下鼠標左鍵時,程序就會調用OnLButtonDown(UINT nFlags, CPoint point)函數來進行響應。其中第二個參數CPoint point是我們在本程序中所要用到的，它給出了當鼠標左鍵被按下時，鼠標指針的位置坐標。我們可以通過這一信息來得知用戶的走法。
在OnLButtonDown函數里我們處理如下兩種操作：
１、如果用戶點擊鼠標的位置落在己方的棋子上，表示用戶選中了該棋子，下一步將移動該子進行走棋（也可能用戶下一步將會選擇己方另外的棋子，總之這一操作會記錄下用戶所選的將要走的棋子）。
２、如果之前用戶已經選過了棋子，那么這一次的點擊（如果不是另選本方的其它棋子的話）表達了用戶的一次走棋過程。在收到用戶傳達的走棋信息后，我們先判斷該著法是否合法（是否符合中國象棋的游戲規則），如果合法，則執行之。緊接著我們調用引擎的搜索函數計算出計算機對用戶著法的應著，然后執行該應著。
如此，在OnLButtonDown函數里，我們實現了人與機器的對弈（當然每走一步棋，也還需要繪圖函數來顯示棋盤局面的更新）。
以上三部分并非界面程序的全部，而僅僅是與我們的程序密切相關的部分。此外還有其它部分對程序同樣必不可少，但這些部分主要由MFC自動生成，無需人為改動，故在此不多做介紹。
2、多線程（程序輔助）
最初，我們的程序中沒有給計算機的“思考”另外開辟新的線程。而僅僅是簡單地按照如下順序編寫代碼：
用戶走棋 —〉計算機思考并走棋
按這種方式編寫的程序似乎毫無問題，程序運行一切正常。
然而，在我們給程序加入計時功能（后面將會在講到其實現）后，程序出現了異常：對用戶方的計時功能完全正確，而對電腦方的計時功能卻根本不起作用！后來，經指導老師點撥，我們找到了問題的所在以及相應的解決方案——由于程序在進行搜索時會占用大量的CPU時間，因而阻塞了位于同一線程內的計時器，使之無法正常工作。解決方案就是另外開一個線程，讓搜索與計時器分處兩個線程。
啟動一個新的線程的方法非常簡單，只需調用API函數AfxBeginThread即可，函數原型：
CWinThread* AfxBeginThread(
AFX_THREADPROC pfnThreadProc,
LPVOID pParam,
int nPriority = THREAD_PRIORITY_NORMAL,
UINT nStackSize = 0,
DWORD dwCreateFlags = 0,
LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL
);[ 該函數原型的描述摘自Visual Studio .NET MSDN 版權所有 1987-2002 Microsoft Corporation]
該函數啟動一個新的線程并返回一個指向該新線程對象的指針，然后新的線程與啟動該新線程的線程同時運行。該函數的第一個參數AFX_THREADPROC pfnThreadProc指定了線程函數。線程函數的內容即為新線程所要執行的內容，線程函數執行完畢，新線程結束（自動銷毀）。
線程函數必須被定義為全局函數，其返回值類型必須是UINT，必須有一個LPVOID類型的參數。我們可以把調用引擎部分的搜索函數的代碼以及完成走棋動作的代碼放入我們所定義的思考線程內，如下：
UINT ThinkingThread(LPVOID pParam)
{
//計算機思考并走棋
}
然后，我們只要將原先調搜索函數并完成走棋的代碼代之以調用AfxBeginThread來啟動新線程即可。這樣一來，我們就實現了程序的多線程，計算機方的計時器不能正常工作的問題也就隨之解決了。
3、計時器（程序輔助）
我們要給程序添加計時功能（分別記錄下棋雙方的“思考時間”），可以使用SetTimer函數、KillTimer函數以及OnTimer函數，SetTimer函數可寫成如下：
SetTimer(1,1000,NULL);
其中第一個參數指明了計時器的ID（可以在同一個程序中建立多個計時器，用計時器ID來區別它們）。第二個參數給出了產生WM_TIMER消息的時間間隔，單位是毫秒。
當不想再繼續使用該計時器時，可以通過調用函數KillTimer(計時器ID)來銷毀計時器。如銷毀上面所設的計時器可以寫作如下：
KillTimer(1);
OnTimer函數是WM_TIMER消息的消息響應函數，通俗地講即每過SetTimer函數中指定的時間間隔，程序就調用一次OnTimer函數。它只有一個參數，即計時器的ID——當一個程序中有多個計時器時，OnTimer函數可以通過識別不同的計時器ID號來完成不同的操作。
這樣要給程序增加對雙方下棋時間的計時功能，可以按如下流程編寫程序：
0 - 棋局正式開始，紅方先行；
1 - SetTimer(1,1000,NULL);
2 - 紅方思考；
3 - 紅方走棋；
4 - KillTimer(1);
5 - SetTimer(2,1000,NULL);
6 - 黑方思考；
7 - 黑方走棋；
8 - KillTimer(2);
9 - 跳轉至1，重復走棋過程
OnTimer函數則按如下編寫代碼：
OnTimer(計時器ID)
{
if 計時器ID == 1 then 紅方計時＋１;
if 計時器ID == 2 then 黑方計時＋１;
}
當然，上面的流程及偽碼僅僅說明編寫象棋計時器大體思想，實際情況要比這復雜的多。在我們的實際的程序中還涉及了線程間的通信（因為我們把計算機方的思考和走棋的過程放在了另一個線程之內），時間的刷新顯示，分、秒、時的進位換算等等。而且為了提高計時精度，我們還將SetTimer函數的第二個參數設為了100，即每0.1秒做一次計時（有時計算機思考和走棋的時間還不足1秒，如果按每秒鐘計一次時，則該不足1秒的時間將被遺漏），當然實際顯示的時候還是只顯示到秒。
4、著法名稱顯示（程序輔助）
每當下棋方（用戶或是計算機）走一步棋，我們就在棋盤旁邊的一個列表框控件（List Box）中按照中國象棋關于著法描述的規范要求顯示出該著法的名稱。如：紅炮二平五、黑馬８進７此類。為了獲得該著法名稱，我們寫了一個六百余行的函數。其功能就是將被移動的棋子類型以及走法的起點坐標、終點坐標這些信息轉換成中國象棋所規范的著法名稱。由于該函數主要涉及的是中國象棋關于著法表示的規范要求，故在此我們不對其具體實現做額外的解釋。這里我們主要討論的是如何對列表框控件（List Box）進行操作，以顯示或刪除著法名稱。
MFC為我們提供了一個CListBox類，使用該類的成員函數我們可以非常容易地實現在List Box中添加與刪除“項（item）”。
首先，我們先要定義一個指向該類的對象的指針：
CListBox* pLB;
然后，在進行程序初始化（對話框的初始化）時，我們使用如下語句來讓該指針與對話框中的List Box控件建立起聯系來（即讓該指針指向對話框中的List Box控件）。
pLB = (CListBox*)GetDlgItem(IDC_LISTCCHESS);
其中IDC_LISTCCHESS是所要建立關聯的控件的ID號。
之后，我們便可調用成員函數pLB->AddString(str);來向List Box控件中添加顯示字符串，str即為所要添加的字符串。
當列表框中的項的數目超過列表框的顯示范圍時，列表框會自動添加垂直滾動條（前提是其VerticalScrollbar屬性要為True——該屬性默認即為True）。但是顯示的內容依然是最早加進來的項。也就是說，垂直滾動條不會自動向下滾。為了能讓列表框中始終能自動顯示出最新的著法名稱（所謂自動，即不需用戶去手動地滾動垂直滾動條來查看最新的著法名稱），我們可以使用pLB->PostMessage(WM_VSCROLL,SB_BOTTOM,0);語句來發送一個讓垂直滾動條處于最底端的消息，使得列表框自動滾動垂直滾動條以顯示最新的著法名稱。
當我們想要從列表框中刪除項時，我們可以使用pLB->DeleteString(n);參數n指明了要刪除的行數。最早加入列表框中的項記為第0行，以后逐次遞增。若要刪除最后一行內容（在悔棋功能中需要用到這一操作），則可以使用pLB->DeleteString(pLB->GetCount()-1);其中pLB->GetCount()返回的是列表框中的項的數目，減一之后正好是最后一項的行號。
5、悔棋、還原（程序輔助）
悔棋和還原是棋類軟件中較為基本的功能。要實現悔棋和還原功能，首先我們要明確哪些信息應當被保存以供悔棋和還原所使用。
在我們的程序中保存了如下信息：
棋局表示中所定義的棋盤數組；
各棋子的貼圖位置。
這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后當悔棋的時候，需要撤銷著法；還原的時候，需要執行著法。然而，我們在編寫自己的程序時一來考慮到程序的可讀性和不易出錯性，二來考慮到對當今的計算機的配置來說這點開銷基本上不會對程序的效率產生什么影響。因此索性保存了全部棋子的信息。
根據所要保存的數據我們定義了如下基本結構類型：
typedef struct{
BYTE CChessBoard[9][10];
POINT ptChess[32];
} CCChess; // 供悔棋、還原保存用的信息結構
并隨之定義了兩個隊列以供悔棋和還原所用：
vector<CCChess> vBackQueue; //悔棋保存隊列
vector<CCChess> vForwardQueue;//還原保存隊列
在對弈過程中，每一回合我們都將棋局信息（這里指前面所說的需要保存的信息）保存至vBackQueue隊列，以供悔棋所用。同時，若vForwardQueue不為空的話，我們還將清空它。因為還原功能是與悔棋功能相對應的，只有當產生了悔棋功能之后，還原功能才會被激活。一個回合的結束意味著前一次操作沒有悔棋功能的產生，因此還原隊列也應被清空。
在悔棋中我們主要完成了以下任務：
下棋回合數減一；
將當前局面信息保存至vForwardQueue隊列，以供還原所用；
從vBackQueue隊列中取出上一回合的棋局信息，恢復到當前局面，然后將其從vBackQueue隊列中剔除掉；
將顯示著法名稱的列表框中的本回合的著法名稱保存到一個著法名稱隊列（我們將其定義為vector<CString> vNameQueue;），以供還原所用。然后從列表框中刪除它。
而在還原中我們所做的剛好和悔棋相反：
下棋回合數加一；
將當前局面信息保存至vBackQueue隊列，以供悔棋所用；
從vForwardQueue隊列中取出最近一次悔棋前的棋局信息，恢復到當前局面，然后將其從vForwardQueue隊列中剔除；
從著法名稱隊列vNameQueue中取出最近一次存入的著法名稱（兩項，因為每回合會產生兩步著法），將其重新顯示到列表框中。然后將其從vNameQueue中剔除。
以上便是悔棋和還原功能所完成的具體操作，其代碼分別寫入悔棋和還原按鈕（Button）的BN_CLICKED事件處理函數中。
四、總 結
下面簡單地總結一下。
首先，在指導老師的熱心幫助下，小組成員協同工作最終順利實現了程序。整個程序近6000行代碼，內容涉及人工智能的基本理論以及開發MFC應用程序的一些基礎知識。無論是從程序難度上講還是從程序規模上講都是我們之前所未遇到過的。該程序的順利完成為我們積累了相當可觀的運用理論知識解決實際問題的經驗。特別是當程序運行過程中發現錯誤的時候，找出問題所在并解決問題更是一個積累經驗，提高實際編程能力的過程。得益于此次編寫該中國象棋對弈程序，我們對人工智能有了一個初步的認識——這為我們以后選擇進一步學習或研究的方向也提供了一定的參考價值。此外，我們還實踐了用MFC編寫基本的Windows應用程序，為今后從事開發Windows應用程序也起到了一定的入門幫助作用。
然而，我們的程序也存在著幾點遺憾：
第一、由于我們對使用MFC編寫Windows程序的不熟悉，導致我們在界面及附屬功能部分花費了大量的時間和精力。因而沒能夠對計算機下棋引擎部分作更深一步的挖掘和研究。對于諸如位棋盤（BitBoard）、置換表（Hash Table）、迭代加深（Iterative Deepening）、機器學習（Machine Learning）等當今棋類對弈程序中所采用的先進技術和思想，在我們的程序中并未涉及。這在一定程度上影響了我們的程序中下棋引擎的工作效率。
第二、之前我們寫程序都是單兵作戰，缺乏團隊合作的經驗。這使得我們在協同開發的過程中遇到了一些問題。其中包括：
１、起初對小組各成員的分工上不夠明確；
２、由于事先沒有嚴格規定好編寫代碼的規范，以及對各部分的接口的規范強調的力度不夠，導致不同人員所完成的作業在組裝和銜接時需要花費額外的工作。
盡管，這些問題最終都得以解決，但卻影響了程序開發的進程。
第三、程序總體缺乏對面向對象思想的貫徹和使用。在我們的程序當中，在界面和程序輔助部分，由于要使用MFC，因而“不可避免”地使用了類（class）。然而，整個下棋引擎部分沒有一點類的影子。這也是由于我本人最初在編寫引擎部分時一心只想盡快看到成果，因而從一開始就按照自己先前的程序習慣（——面向過程）來編寫代碼。到了開發后期，又缺少時間和精力來用面向對象思想重新改寫程序，最終導致我們的引擎部分與類“無緣”。
第四、在本文即將交稿之際，我們程序仍在勝利局面檢測和貼圖刷新上存在著隨機性的出錯可能（出錯幾率很小）。本文交稿后我們會繼續努力查找出錯原因，爭取在程序發布時消除掉這些bug。
最后，特別感謝指導老師對我們科技小組的支持。最終我們能夠順利完成程序，離不開組員們的合作，更離不開指導老師的指導與幫助！
【免費vc中國象棋軟件(一)】相關文章：
免費vc++航空客運訂票系統+論文(一)11-22
免費vc++網上尋呼QICQ源代碼（附帶論文）(一)11-22
游戲軟件開發VC++12-27
知識的一致性檢測研究與實現VC11-23
課堂點名軟件(一)11-22
人臉的檢測定位MFC+VC++03-08
網絡智能游戲的設計與實現VC++11-23