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