【正文】 走的每一種著法。因而首先需要設(shè)計一套數(shù)據(jù)結(jié)構(gòu)來表示棋盤上的局面以及著法。對于棋盤局面的表示可采用傳統(tǒng)而簡單的“棋盤數(shù)組”。即用一個9*10的數(shù)組來存儲棋盤上的信息，數(shù)組的每個元素存儲棋盤上是否有棋子。這種表示方法簡單易行（缺點(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}。給所有棋子定義一個值：define R_BEGIN R_KINGdefine R_END R_PAWNdefine B_BEGIN B_KINGdefine B_END B_PAWNdefine 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 amp。amp。 x=B_END)//判斷某個棋子是不是黑色define IsRed(x) (x=R_BEGIN amp。amp。 x=R_END)//判斷某個棋子是不是紅色對于著法的表示，直接借用棋盤數(shù)組的下標(biāo)來記錄著法的起點(diǎn)和目標(biāo)點(diǎn)。至于是什么棋子在走，以及是否吃子、吃的是什么子，在著法結(jié)構(gòu)中并不記錄。這些信息由外部讀取棋盤上起點(diǎn)、終點(diǎn)的數(shù)據(jù)獲得。著法結(jié)構(gòu)定義如下，其中還包含了對著法的歷史得分的記錄項，以供后面要講到的“歷史啟發(fā)”所用。typedef struct{ short nChessID。 //表明是什么棋子 CHESSMANPOS From。//起始位置 CHESSMANPOS To。 //走到什么位置 int Score。 //走法的分?jǐn)?shù)}CHESSMOVE。有了對棋盤局面和著法的表示之后，程序才能夠完成以下操作： 生成所有合法著法； 執(zhí)行著法、撤銷著法； 針對某一局面進(jìn)行評估。因而，棋局表示好比是整個程序（計算機(jī)下棋引擎部分）的地基，之后所有的操作都將建立在其基礎(chǔ)上。 著法生成程序需要讓計算機(jī)在輪到它走子的時候能夠執(zhí)行一步它認(rèn)為對它最有利的著法，那前提就是它要有諸多（也可能是唯一）可供選擇的著法，提供所有候選著法的“清單”就是著法生成器所要完成的。之后用搜索函數(shù)來搜索“清單”，并用局面評估函數(shù)來逐一打分，最后就可以選擇出“最佳著法”并執(zhí)行了。在著法生成器中，采用的基本思想就是遍歷整個棋盤（一個接一個地查看棋盤上的每個位置點(diǎn)），當(dāng)發(fā)現(xiàn)有當(dāng)前下棋方的棋子時先判斷它是何種類型的棋子，然后根據(jù)其棋子類型而相應(yīng)地找出其所有合法著法并存入著法隊列。這里談到的“合法著法”包括以下幾點(diǎn)： 各棋子按其行子規(guī)則行子。諸如馬跳“日”字、象走“田”字、士在九宮內(nèi)斜行等等（這里需要特別注意的是卒（兵）的行子規(guī)則會隨其所在位置的不同而發(fā)生變化——過河后可以左右平移）。 行子不能越出棋盤的界限。當(dāng)然所有子都不能走到棋盤的外面，同時某些特定的子還有自己的行棋界限，如將、士不能出九宮，象不能過河。 行子的半路上不能有其它子阻攔（除了炮需要隔一個子才能打子之外）以及行子的目的點(diǎn)不能有本方的棋子（當(dāng)然不能自己吃自己了）。 將帥不能碰面（本程序中只在生成計算機(jī)的著法時認(rèn)為將帥碰面是非法的，而對用戶所走的導(dǎo)致將帥碰面的著法并不認(rèn)為其非法，而只是產(chǎn)生敗局罷了）。產(chǎn)生了著法后要將其存入著法隊列以供搜索之用，由于搜索會搜索多層（即考慮雙方你來我往好幾步，這樣才有利于對局面進(jìn)行評估以盡可能避免“目光短淺”），所以在把著法存入著法隊列的時候還要同時存儲該著法所屬的搜索層數(shù)。因此可以將著法隊列定義為二維數(shù)組m_MoveList[8][80]，其中第一個數(shù)組下標(biāo)為層數(shù)，第二個數(shù)組下標(biāo)為每一層的全部著法數(shù)。關(guān)于搜索層數(shù)，設(shè)定為8，實際使用的是1到7（在界面中將其限定為1—7）。搜索層數(shù)的增加會顯著提高電腦的下棋水平（當(dāng)然計算機(jī)的棋力在很大程度上也依賴于局面評估）。，512M內(nèi)存的計算機(jī)上最多只能搜索4層，再多將導(dǎo)致搜索時間達(dá)到令人無法容忍的地步（這里還需要特別說明的是，搜索的速度也和著法生成的效率以及局面評估的復(fù)雜度有關(guān)，因為每分析一個結(jié)點(diǎn)都要執(zhí)行這兩種操作）。對于每一層的著法數(shù)，也就是當(dāng)前下棋方針對當(dāng)前局面的所有可選的合法著法，據(jù)有關(guān)數(shù)據(jù)統(tǒng)計在象棋實戰(zhàn)中一般最多情況下也就五六十種。定義第二個數(shù)組下標(biāo)為80，應(yīng)當(dāng)可以保證十分的安全。著法生成為搜索部分提供了“原料”，接下來的任務(wù)就交給搜索和局面評估了。 搜索算法搜索算法對于整個下棋引擎來說都是至關(guān)重要的。它如同程序的心臟，驅(qū)動著整個程序。搜索算法的好壞直接影響著程序執(zhí)行的效率（從某種角度上，它影響著計算機(jī)的下棋水平。因為，計算機(jī)必須在有限的時間內(nèi)完成思考，搜索速度快意味著在相同的時間內(nèi)程序可以“看”得更遠(yuǎn)，“想”的更多）。關(guān)于棋類對弈程序中的搜索算法，已有成熟的AlphaBeta搜索算法以及其它一些輔助增強(qiáng)算法（還有眾多基于AlphaBeta算法的派生、變種算法）在程序中直接借鑒了AlphaBeta搜索算法并輔以了歷史啟發(fā)。本節(jié)先介紹AlphaBeta搜索算法：在中國象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對方，或者避免被將死。由此，可以用一棵“博弈樹”（圖2）來表示下棋的過程——樹中每一個結(jié)點(diǎn)代表棋盤上的一個局面，對每一個局面（結(jié)點(diǎn)）根據(jù)不同的走法又產(chǎn)生不同的局面（生出新的結(jié)點(diǎn)），如此不斷直到再無可選擇的走法，即到達(dá)葉子結(jié)點(diǎn)（棋局結(jié)束）。中國象棋的博弈樹的模型大概如下圖所示，可以把其中連接結(jié)點(diǎn)的線段看作是著法，不同的著法自然產(chǎn)生不同的局面。圖 2博弈樹該樹包含三種類型的結(jié)點(diǎn)： 奇數(shù)層的中間結(jié)點(diǎn)（以及根結(jié)點(diǎn)），表示輪到紅方走棋； 偶數(shù)層的中間結(jié)點(diǎn)，表示輪到黑方走棋； 葉子結(jié)點(diǎn)，表示棋局結(jié)束?，F(xiàn)在讓計算機(jī)來下中國象棋，它應(yīng)當(dāng)選擇一步對它最有利的著法（最終導(dǎo)致它取勝的著法）。獲得最佳著法的方法就是“試走”每一種可能的著法，比較它們所產(chǎn)生的不同后果，然后從中選出能夠產(chǎn)生對自己最有利的局面的著法。結(jié)合上面所講的博弈樹，若給