首頁 > 實(shí)用范文

中國(guó)象棋人機(jī)博弈

更新時(shí)間:2023-03-05 16:15:38 閱讀：評(píng)論：0

初中物理教案-培訓(xùn)就業(yè)

2023年3月5日發(fā)(作者：茶葉排名前十名)

中國(guó)象棋對(duì)弈程序

【摘要】：人機(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ó)象棋；人工智能；博弈樹；Alpha-Beta搜索；歷史啟發(fā)；界面；多線程；計(jì)

時(shí)器；列表框；MFC。

[Abstract]:gonfine-designed

algorithmsandthefastoperationability,computerscandisplayhigh"intelligence"inplayingchess.

Usually,therealizationofachessprogramcanbedecompodintotwomajorparts:theChess

Engine(ArtificialIntelligence)andtheShell(UrInterface&ProgramAssist).Thispaperwill

introducehowtorealizeaChineChessprogram.

[Keywords]:ChineChess;ArtificialIntelligence(AI);GameTree;Alpha-BetaSearch;History

Heuristic;UrInterface;Multithreaded;Timer;ListBox;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è)框架（界面）來作為

引擎的載體，同時(shí)提供一些諸如悔棋，計(jì)時(shí)之類的附屬功能（程序輔助）來為程序增色添彩。

下面分別介紹各部分實(shí)現(xiàn)。由于界面及程序輔助部分涉及內(nèi)容寬泛而又繁瑣，因而本文只

介紹其中重點(diǎn)部分以及我們?cè)陂_發(fā)過程中曾經(jīng)遇到過困難的地方。

二、人工智能部分（計(jì)算機(jī)下棋引擎）

1、概述

程序的基本框架：

從程序的結(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)致走棋方取勝的著

法。在搜索的過程中還可以采用一些輔助手段來提高搜索的效率。其過程如下圖所示：

下面將分別介紹各個(gè)部分。

2、棋局表示

計(jì)算機(jī)下棋的前提是要讓計(jì)算機(jī)讀懂象棋。所謂讀懂，即計(jì)算機(jī)應(yīng)該能夠清楚地了解到棋

盤上的局面（棋盤上棋子的分布情況）以及下棋方所走的每一種著法。因而首先我們需要有一

套數(shù)據(jù)結(jié)構(gòu)來表示棋盤上的局面以及著法。

對(duì)于棋盤局面的表示我們采用了最傳統(tǒng)的同時(shí)也是最為簡(jiǎn)單的“棋盤數(shù)組”。即用一個(gè)

9*10的數(shù)組來存儲(chǔ)棋盤上的信息，數(shù)組的每個(gè)元素存儲(chǔ)棋盤上相應(yīng)位置是何種棋子。這種表

示方法簡(jiǎn)單易行（缺點(diǎn)是效率不是很高）。按此方法棋盤的初始情形如下所示：

BYTECChessBoard[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”表示無棋子，大寫字母表示紅方棋子，小寫

字母表示黑方棋子（所有這些大小寫字母都是用宏定義的整

數(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)來記錄著法的起點(diǎn)和目標(biāo)點(diǎn)。至于是什么

棋子在走，以及是否吃子、吃的是什么子，我們?cè)谥ńY(jié)構(gòu)中并不記錄。這些信息由外部讀取

棋盤上起點(diǎn)、終點(diǎn)的數(shù)據(jù)獲得。著法結(jié)構(gòu)定義如下，其中還包含了對(duì)著法的歷史得分的記錄項(xiàng)，

以供后面要講到的“歷史啟發(fā)”所用。

typedefstruct_cchessmove{

POINTptFrom;//起點(diǎn)

POINTptTo;//目標(biāo)點(diǎn)

intnScore;//該走法的歷史得分

}CCHESSMOVE;//走法結(jié)構(gòu)

有了對(duì)棋盤局面和著法的表示之后，程序才能夠完成以下操作：

1、生成所有合法著法；

2、執(zhí)行著法、撤銷著法；

3、針對(duì)某一局面進(jìn)行評(píng)估。

因而，棋局表示好比是整個(gè)程序（計(jì)算機(jī)下棋引擎部分）的地基，之后所有的操作都將建

立在其基礎(chǔ)上。

3、著法生成

我們的程序需要讓計(jì)算機(jī)在輪到它走子的時(shí)候能夠執(zhí)行一步它認(rèn)為對(duì)它最有利的著法，那

前提就是它要有諸多（也可能是唯一）可供選擇的著法，提供所有候選著法的“清單”就是我

們的著法生成器所要完成的。之后用搜索函數(shù)來搜索“清單”，并用局面評(píng)估函數(shù)來逐一打分，

最后就可以選擇出“最佳著法”并執(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ā)生變化——過河后可

以左右平移）。

2、行子不能越出棋盤的界限。當(dāng)然所有子都不能走到棋盤的外面，同時(shí)某些特定的子還

有自己的行棋界限，如將、士不能出九宮，象不能過河。

3、行子的半路上不能有子阻攔（除了炮需要隔一個(gè)子才能打子之外）以及行子的目的點(diǎn)

不能有本方棋子（當(dāng)然不能自己吃自己了）。

4、將帥不能碰面（本程序中只在生成計(jì)算機(jī)的著法時(shí)認(rèn)為將帥碰面是非法的，而對(duì)用戶

所走的導(dǎo)致將帥碰面的著法并不認(rèn)為其非法，而只是產(chǎn)生敗局罷了）。

產(chǎn)生了著法后要將其存入著法隊(duì)列以供搜索之用，由于搜索會(huì)搜索多層（即考慮雙方你來

我往好幾步，這樣才有利于對(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á)到令人無法容忍的地步（這里還需要特別說明的是，搜索的速度也和著法生成的效率

以及局面評(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)可以保

證十分的安全。

著法生成為搜索部分提供了“原料”，接下來的任務(wù)就交給搜索和局面評(píng)估了。

4、搜索算法

搜索算法對(duì)于整個(gè)下棋引擎來說都是至關(guān)重要的。它如同程序的心臟，驅(qū)動(dòng)著整個(gè)程序。

搜索算法的好壞直接影響著程序執(zhí)行的效率（從某種角度上，它影響著計(jì)算機(jī)的下棋水平。因

為，計(jì)算機(jī)必須在有限的時(shí)間內(nèi)完成思考，搜索速度快意味著在相同的時(shí)間內(nèi)程序可以“看”

得更遠(yuǎn)，“想”的更多）。關(guān)于棋類對(duì)弈程序中的搜索算法，經(jīng)前人的努力已形成了非常成熟的

Alpha-Beta搜索算法1以及其它一些輔助增強(qiáng)算法（還有眾多基于Alpha-Beta算法的派生、變

種算法）。鑒于目前我們的知識(shí)儲(chǔ)備、時(shí)間、精力等均達(dá)不到推陳出新、另開爐灶的要求，再

加之前人的算法著實(shí)已相當(dāng)完善，所以我們?cè)谧约旱某绦蛑兄苯咏梃b了Alpha-Beta搜索算法

并輔以了歷史啟發(fā)。本節(jié)先介紹Alpha-Beta搜索算法：

在中國(guó)象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對(duì)方，或者

避免被將死。

由此，我們可以用一棵“博弈樹”（一棵n叉樹）來表示下棋的過程——樹中每一個(gè)結(jié)點(diǎn)

代表棋盤上的一個(gè)局面，對(duì)每一個(gè)局面（結(jié)點(diǎn)）根據(jù)不同的走法又產(chǎn)生不同的局面（生出新的

結(jié)點(diǎn)），如此不斷直到再無可選擇的走法，即到達(dá)葉子結(jié)點(diǎn)（棋局結(jié)束）。中國(guó)象棋的博弈樹的

1Alpha-beta算法，該算法是由匹茲堡大學(xué)的三位科學(xué)家Newell,ShawandSimon于1958年提出的。

模型大概如下圖所示，我們可以把其中連接結(jié)點(diǎn)的線段看作是著法，不同的著法自然產(chǎn)生不同

的局面。

該樹包含三種類型的結(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ī)來下中國(guó)象棋，它應(yīng)當(dāng)選擇一步對(duì)它最有利的著法（最終導(dǎo)致它取勝的著

法）。獲得最佳著法的方法就是“試走”每一種可能的著法，比較它們所產(chǎn)生的不同后果，然

后從中選出能夠產(chǎn)生對(duì)自己最有利的局面的著法。

結(jié)合上面所講的博弈樹，如果我們給每個(gè)結(jié)點(diǎn)都打一個(gè)分值來評(píng)價(jià)其對(duì)應(yīng)的局面（這一任

務(wù)由后面所講的局面評(píng)估來完成），那么我們可以通過比較該分值的大小來判斷局面的優(yōu)劣。

假定甲乙兩方下棋，甲勝的局面是一個(gè)極大值（一個(gè)很大的正數(shù)），那么乙勝的局面就是一個(gè)

極小值（極大值的負(fù)值），和棋的局面則是零值（或是接近零的值）。如此，當(dāng)輪到甲走棋時(shí)他

會(huì)盡可能地讓局面上的分值大，相反輪到乙走棋時(shí)他會(huì)選盡可能地讓局面上的分值小。反映到

博弈樹上，即如果我們假設(shè)奇數(shù)層表示輪到甲方走棋，偶數(shù)層表示輪到乙方走棋。那么由于甲

方希望棋盤上的分值盡可能大，則在偶數(shù)層上我們會(huì)挑選分值最大的結(jié)點(diǎn)——偶數(shù)層的結(jié)點(diǎn)是

甲走完一步棋之后的棋盤局面，反映了甲方對(duì)棋局形勢(shì)的要求。同樣道理，由于乙方希望棋盤

上的分值盡可能小，那么在奇數(shù)層上我們會(huì)選擇分值最小的結(jié)點(diǎn)。這就是“最小-最大”

（Minimax）2的基本思想。這樣搜索函數(shù)在估值函數(shù)的協(xié)助下可以通過在奇數(shù)層選擇分值最大

（最小）的結(jié)點(diǎn)，在偶數(shù)層選擇分值最小（最大）的結(jié)點(diǎn)的方式來搜索以當(dāng)前局面為根結(jié)點(diǎn)、

限定搜索層數(shù)以內(nèi)的整棵樹來獲得一個(gè)最佳的著法。然而不幸的是，博弈樹相當(dāng)龐大（它會(huì)成

指數(shù)增長(zhǎng)），因而搜索（限定層數(shù)以內(nèi)的）整棵樹是一件相當(dāng)費(fèi)時(shí)的工作——其時(shí)間復(fù)雜度為

O(bn)。其中b是分枝因子，即針對(duì)各種局面的合法著法的數(shù)目的平均值，n是搜索的深度。對(duì)

于中國(guó)象棋而言，在中盤時(shí)平均著法數(shù)目大約是40種左右，那么搜索4層需要檢查250萬條

路線，搜索5層需要檢查1億條路線，搜索6層需要檢查40億條路線！！！

幸運(yùn)的是，Alpha-Beta搜索使得我們能在不影響搜索精度的前提下大幅減少工作量。

因?yàn)椋绻紤]到下棋是一個(gè)你來我往的交替進(jìn)行并且相互“較勁”的過程。由于每一方

2“最小-最大”（Minimax）最早是由JohnvonNuoma（1903-1957，美籍匈牙利數(shù)學(xué)家）在60多年前完整描

述的：

1、假設(shè)有對(duì)局面評(píng)分的方法，來預(yù)測(cè)棋手甲（我們稱為最大者）會(huì)贏，或者對(duì)手（最小者）會(huì)贏，或者

是和棋。評(píng)分用數(shù)字表示，正數(shù)代表最大者領(lǐng)先，負(fù)數(shù)代表最小者領(lǐng)先，零代表誰也不占便宜；

2、最大者的任務(wù)是增加棋盤局面的評(píng)分（即盡量讓評(píng)分最大）；

3、最小者的任務(wù)是減少棋盤局面的評(píng)分（即盡量讓評(píng)分最小）；

4、假設(shè)誰也不會(huì)犯錯(cuò)誤，即他們都走能讓使局面對(duì)自己最有利的著法。

都會(huì)盡可能將局面導(dǎo)向?qū)ψ约河欣鴮?duì)對(duì)方不利的方向（我們假定下棋雙方對(duì)棋局有著同樣的

認(rèn)知，即你認(rèn)為對(duì)你很糟糕的局面，在你的對(duì)手看來則是對(duì)他很有利的局面），那么某些局面

由于能夠產(chǎn)生出很糟糕的局面因而根本沒有再繼續(xù)考慮的價(jià)值。所以當(dāng)你看到某個(gè)局面有可能

產(chǎn)生很糟糕的局面時(shí)（確切地說這里的“很糟糕”是與之前分析的情況相比較而言的），你應(yīng)

當(dāng)立刻停止對(duì)其剩余子結(jié)點(diǎn)的分析——不要對(duì)它再抱任何幻想了，如果你選擇了它，那么你必

將得到那個(gè)很糟糕的局面，甚至可能更糟??這樣一來便可以在很大程度上減少搜索的工作

量，提高搜索效率，這稱為“樹的裁剪”。

下面用圖來進(jìn)一步說明“樹的裁剪”。為了簡(jiǎn)便起見，我將博弈樹進(jìn)行了簡(jiǎn)化——每個(gè)結(jié)

點(diǎn)只有三個(gè)分支，實(shí)際情況中，剛才講過在中盤應(yīng)有大約40個(gè)分支。

我們假定棋盤上的局面發(fā)展到了結(jié)點(diǎn)A（見下圖），現(xiàn)在輪到你走棋了，你是“最大的一

方”——即你希望棋局的分值盡可能的高。讓我們?cè)囍阉鲀蓪觼砜匆豢础皹涞牟眉簟睂?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ì)手——“最小者”

來走棋了，他的目的是使得棋局的分值盡可能的小。依次考察結(jié)點(diǎn)B的各個(gè)子結(jié)點(diǎn)，查看它

們的分值（因?yàn)槲覀兪孪燃s定好了搜索兩層，現(xiàn)在已達(dá)到搜索深度的要求了，所以就停下來調(diào)

用局面評(píng)估函數(shù)來給它打分）。結(jié)點(diǎn)Ｂ的第一個(gè)子結(jié)點(diǎn)（從左到右算起）返回10，第二個(gè)子結(jié)

點(diǎn)返回了-5，第三個(gè)子結(jié)點(diǎn)返回了２。由于結(jié)點(diǎn)Ｂ這層是你的對(duì)手來做選擇，我們假設(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è)賮矸治鼋Y(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)了，因

為結(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)分析過的結(jié)點(diǎn)B所傳回-5相比較，作為“最大一方”的你顯然更不愿意看到-8的局面。所

以，你當(dāng)然不會(huì)選擇相應(yīng)的著法使得局面發(fā)展成為結(jié)點(diǎn)C。因?yàn)槟菢拥脑挘乱徊侥愕膶?duì)手就

會(huì)帶給你一個(gè)分值不高于-8的局面。

由此，我們就在不影響搜索質(zhì)量的前提下避免了搜索“無價(jià)值的”結(jié)點(diǎn)C的剩余子結(jié)點(diǎn)

的大量工作，從而節(jié)省了寶貴時(shí)間，為在同樣機(jī)器配置下搜索更多的層數(shù)提供了可能。

“最小-最大”的思想再加上“對(duì)樹的裁剪”，這就是Alpha-Beta搜索算法的核心。最基本

的Alpha-Beta算法的代碼如下：

intAlphaBeta(intdepth,intalpha,intbeta)

{

if(depth==0)//如果是葉子節(jié)點(diǎn)（到達(dá)搜索深度要求）

returnEvaluate();//則由局面評(píng)估函數(shù)返回估值

GenerateLegalMoves();//產(chǎn)生所有合法著法

while(MovesLeft())//遍歷所有著法

{

MakeNextMove();//執(zhí)行著法

intval=-AlphaBeta(depth-1,-beta,-alpha);//遞歸調(diào)用

UnmakeMove();//撤銷著法

if(val>=beta)//裁剪

returnbeta;

if(val>alpha)//保留最大值

alpha=val;

}

returnalpha;

}

5、歷史啟發(fā)及著法排序（搜索輔助）

既然Alpha-Beta搜索算法是在“最小-最大”的基礎(chǔ)上引入“樹的裁剪”的思想以期提高

效率，那么它的效率將在很大程度上取決于樹的結(jié)構(gòu)——如果搜索了沒多久就發(fā)現(xiàn)可以進(jìn)行

“裁剪”了，那么需要分析的工作量將大大減少，效率自然也就大大提高；而如果直至分析了

所有的可能性之后才能做出“裁剪”操作，那此時(shí)“裁剪”也已經(jīng)失去了它原有的價(jià)值（因?yàn)?/p>

你已經(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)緊要的棋子位

置有所不同）也是較好的。由fer所提出的“歷史啟發(fā)”（HistoryHeuristic）就是建立

在這樣一種觀點(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)，具有較高的效率。

6、局面評(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)估中需要考慮的因素。就不同的棋類可能要考慮的因素略有差

異。在中國(guó)象棋中所要考慮的最基本的幾個(gè)因素包括如下四點(diǎn)：

1、子力總和

子力是指某一棋子本身所具有的價(jià)值。通俗地講就是一個(gè)棋子它值個(gè)什么價(jià)。例如，車值

500的話，那可能馬值300，卒值80等等。所以在評(píng)估局面時(shí)，我們首先要考慮雙方的子力總

和的對(duì)比。比如紅方擁有士象全加車馬炮，而黑方只有殘士象加雙馬，則紅方明顯占優(yōu)。

2、棋子位置（控制區(qū)域）

棋子位置，或稱控制區(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)系（包括攻擊關(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í)際問題對(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)類型

typedefstruct_relationtable{

BYTEnCChessID;

intnUAttackCount;

intnUGuardCount;

BYTEUnderAttack[5];

BYTEUnderGurad[5];

}RelationTable;

RelationTableRelationOfMan[9][10];//關(guān)系表

其中nCChessID給出棋子的類型，nUAttackCount和nUGuardCount分別記錄正攻擊該子

的棋子數(shù)量和正保護(hù)該子的棋子數(shù)量，UnderAttack[5]和UnderGuard[5]則存放攻擊該子和保護(hù)

該子的具體棋子（的類型）。因?yàn)榭紤]到實(shí)戰(zhàn)中幾乎不可能出現(xiàn)同時(shí)有超過五個(gè)棋子攻擊/保護(hù)

一個(gè)子的情況，故數(shù)組下標(biāo)設(shè)定為5。

當(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)在此多做文章??

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í)，程序的界面部分還尚未開工。因此我們暫時(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)的方式來傳送用戶走棋的信息。同樣，程序顯示計(jì)算機(jī)

走棋的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)來做出回應(yīng)）。

此后，等到界面部分初步完成以后，引擎的上述各模塊無需作任何改動(dòng)，仍以.h頭文件的

形式加入界面工程，只要由界面中的某個(gè).cpp文件調(diào)用搜索函數(shù)即可。這種連接方式實(shí)現(xiàn)起來

非常簡(jiǎn)單，基本上不需要其它額外作業(yè)。

三、界面及程序輔助部分

1、界面基本框架

關(guān)于界面，我們建了一個(gè)基于對(duì)話框的MFC應(yīng)用程序。之后主要工作都在對(duì)話框類的兩

個(gè)文件CChessUIDlg.h和下展開。

我們所寫的代碼主要分布于以下三大部分：

一、初始化部分

BOOLCCChessUIDlg::OnInitDialog()

{

}

OnInitDialog()負(fù)責(zé)的是對(duì)話框的初始化。我們把有關(guān)中國(guó)象棋的棋局初始化情況也放在

了這里面。初始化的內(nèi)容包括：

1、對(duì)引擎部分所用到的變量的初始化。包括對(duì)棋盤上的棋子位置進(jìn)行初始化（棋盤數(shù)組

的初始化），對(duì)搜索深度、當(dāng)前走棋方標(biāo)志、棋局是否結(jié)束標(biāo)志等的初始化；

2、對(duì)棋盤、棋子的貼圖位置（即棋盤、棋子在程序中實(shí)際顯示位置）的初始化；

3、對(duì)程序輔助部分所用到的一些變量的初始化。包括對(duì)悔棋、還原隊(duì)列的清空，棋盤、

棋子樣式的默認(rèn)選擇，下棋模式的默認(rèn)選擇，計(jì)時(shí)器顯示的初始化，以及著法名稱列

表的初始化等。

二、繪圖部分

voidCCChessUIDlg::OnPaint()

{

}

OnPaint()函數(shù)負(fù)責(zé)的是程序界面的繪圖。因此，在這里我們要完成棋盤、棋子的顯示（如

果用戶選擇了盲棋模式，則不進(jìn)行棋子的繪圖，而是在屏幕中央給出提示信息表明當(dāng)前為盲棋

模式），走棋起始位置和目標(biāo)位置的提示框的顯示。

由于我們的棋盤、棋子等都是以位圖的形式給出的。所以在OnPaint()函數(shù)里我們做的工

作主要都是在貼位圖。

需要注意的是由于位圖文件不能像GIF文件那樣有透明的背景并且棋子是圓形的而位圖

文件只能是矩形的，所以如果直接貼圖的話會(huì)在棋盤上留下一塊白色的邊框——棋子的背景。

因此，要想讓棋子文件的背景“隱藏”需要通過一些“與”和“異或”操作來屏蔽掉棋子的背

景。

三、走棋部分（用戶動(dòng)作響應(yīng)部分）

為WM_LBUTTONDOWN消息添加消息響應(yīng)事件，可得到如下函數(shù)：

voidCCChessUIDlg::OnLButtonDown(UINTnFlags,CPointpoint)

{

}

當(dāng)用戶在窗口客戶區(qū)按下鼠標(biāo)左鍵時(shí),程序就會(huì)調(diào)用OnLButtonDown(UINTnFlags,CPoint

point)函數(shù)來進(jìn)行響應(yīng)。其中第二個(gè)參數(shù)CPointpoint是我們?cè)诒境绦蛑兴玫降模o

出了當(dāng)鼠標(biāo)左鍵被按下時(shí)，鼠標(biāo)指針的位置坐標(biāo)。我們可以通過這一信息來得知用戶的走法。

在OnLButtonDown函數(shù)里我們處理如下兩種操作：

１、如果用戶點(diǎn)擊鼠標(biāo)的位置落在己方的棋子上，表示用戶選中了該棋子，下一步將移動(dòng)

該子進(jìn)行走棋（也可能用戶下一步將會(huì)選擇己方另外的棋子，總之這一操作會(huì)記錄下用戶所選

的將要走的棋子）。

２、如果之前用戶已經(jīng)選過了棋子，那么這一次的點(diǎn)擊（如果不是另選本方的其它棋子的

話）表達(dá)了用戶的一次走棋過程。在收到用戶傳達(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ù)來顯示棋盤局面的更新）。

以上三部分并非界面程序的全部，而僅僅是與我們的程序密切相關(guān)的部分。此外還有其它

部分對(duì)程序同樣必不可少，但這些部分主要由MFC自動(dòng)生成，無需人為改動(dòng)，故在此不多做

介紹。

2、多線程（程序輔助）

最初，我們的程序中沒有給計(jì)算機(jī)的“思考”另外開辟新的線程。而僅僅是簡(jiǎn)單地按照如

下順序編寫代碼：

用戶走棋—〉計(jì)算機(jī)思考并走棋

按這種方式編寫的程序似乎毫無問題，程序運(yùn)行一切正常。

然而，在我們給程序加入計(jì)時(shí)功能（后面將會(huì)在講到其實(shí)現(xiàn)）后，程序出現(xiàn)了異常：對(duì)用

戶方的計(jì)時(shí)功能完全正確，而對(duì)電腦方的計(jì)時(shí)功能卻根本不起作用！后來，經(jīng)指導(dǎo)老師點(diǎn)撥，

我們找到了問題的所在以及相應(yīng)的解決方案——由于程序在進(jìn)行搜索時(shí)會(huì)占用大量的CPU時(shí)

間，因而阻塞了位于同一線程內(nèi)的計(jì)時(shí)器，使之無法正常工作。解決方案就是另外開一個(gè)線程，

讓搜索與計(jì)時(shí)器分處兩個(gè)線程。

啟動(dòng)一個(gè)新的線程的方法非常簡(jiǎn)單，只需調(diào)用API函數(shù)AfxBeginThread即可，函數(shù)原型：

CWinThread*AfxBeginThread(

AFX_THREADPROCpfnThreadProc,

LPVOIDpParam,

intnPriority=THREAD_PRIORITY_NORMAL,

UINTnStackSize=0,

DWORDdwCreateFlags=0,

LPSECURITY_ATTRIBUTESlpSecurityAttrs=NULL

);3

該函數(shù)啟動(dòng)一個(gè)新的線程并返回一個(gè)指向該新線程對(duì)象的指針，然后新的線程與啟動(dòng)該新

線程的線程同時(shí)運(yùn)行。該函數(shù)的第一個(gè)參數(shù)AFX_THREADPROCpfnThreadProc指定了線程函數(shù)。

3該函數(shù)原型的描述摘自N版權(quán)所有1987-2002MicrosoftCorporation

線程函數(shù)的內(nèi)容即為新線程所要執(zhí)行的內(nèi)容，線程函數(shù)執(zhí)行完畢，新線程結(jié)束（自動(dòng)銷毀）。

線程函數(shù)必須被定義為全局函數(shù)，其返回值類型必須是UINT，必須有一個(gè)LPVOID類型的

參數(shù)。我們可以把調(diào)用引擎部分的搜索函數(shù)的代碼以及完成走棋動(dòng)作的代碼放入我們所定義的

思考線程內(nèi)，如下：

UINTThinkingThread(LPVOIDpParam)

{

//計(jì)算機(jī)思考并走棋

}

然后，我們只要將原先調(diào)搜索函數(shù)并完成走棋的代碼代之以調(diào)用AfxBeginThread來啟動(dòng)

新線程即可。這樣一來，我們就實(shí)現(xiàn)了程序的多線程，計(jì)算機(jī)方的計(jì)時(shí)器不能正常工作的問題

也就隨之解決了。

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

來區(qū)別它們）。第二個(gè)參數(shù)給出了產(chǎn)生WM_TIMER消息的時(shí)間間隔，單位是毫秒。

當(dāng)不想再繼續(xù)使用該計(jì)時(shí)器時(shí)，可以通過調(diào)用函數(shù)KillTimer(計(jì)時(shí)器ID)來銷毀計(jì)時(shí)器。

如銷毀上面所設(shè)的計(jì)時(shí)器可以寫作如下：

KillTimer(1);

OnTimer函數(shù)是WM_TIMER消息的消息響應(yīng)函數(shù)，通俗地講即每過SetTimer函數(shù)中指定的時(shí)

間間隔，程序就調(diào)用一次OnTimer函數(shù)。它只有一個(gè)參數(shù)，即計(jì)時(shí)器的ID——當(dāng)一個(gè)程序中有

多個(gè)計(jì)時(shí)器時(shí)，OnTimer函數(shù)可以通過識(shí)別不同的計(jì)時(shí)器ID號(hào)來完成不同的操作。

這樣要給程序增加對(duì)雙方下棋時(shí)間的計(jì)時(shí)功能，可以按如下流程編寫程序：

0-棋局正式開始，紅方先行；

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ù)走棋過程

OnTimer函數(shù)則按如下編寫代碼：

OnTimer(計(jì)時(shí)器ID)

{

if計(jì)時(shí)器ID==1then紅方計(jì)時(shí)＋１;

if計(jì)時(shí)器ID==2then黑方計(jì)時(shí)＋１;

}

當(dāng)然，上面的流程及偽碼僅僅說明編寫象棋計(jì)時(shí)器大體思想，實(shí)際情況要比這復(fù)雜的多。

在我們的實(shí)際的程序中還涉及了線程間的通信（因?yàn)槲覀儼延?jì)算機(jī)方的思考和走棋的過程放在

了另一個(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è)列表框控件（ListBox）

中按照中國(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ì)列表框控件（ListBox）進(jìn)行操作，以顯示或刪除著法名稱。

MFC為我們提供了一個(gè)CListBox類，使用該類的成員函數(shù)我們可以非常容易地實(shí)現(xiàn)在

ListBox中添加與刪除“項(xiàng)（item）”。

首先，我們先要定義一個(gè)指向該類的對(duì)象的指針：

CListBox*pLB;

然后，在進(jìn)行程序初始化（對(duì)話框的初始化）時(shí)，我們使用如下語句來讓該指針與對(duì)話框

中的ListBox控件建立起聯(lián)系來（即讓該指針指向?qū)υ捒蛑械腖istBox控件）。

pLB=(CListBox*)GetDlgItem(IDC_LISTCCHESS);

其中IDC_LISTCCHESS是所要建立關(guān)聯(lián)的控件的ID號(hào)。

之后，我們便可調(diào)用成員函數(shù)pLB->AddString(str);來向ListBox控件中添加顯示字符串，

str即為所要添加的字符串。

當(dāng)列表框中的項(xiàng)的數(shù)目超過列表框的顯示范圍時(shí)，列表框會(huì)自動(dòng)添加垂直滾動(dòng)條（前提是

其VerticalScrollbar屬性要為True——該屬性默認(rèn)即為True）。但是顯示的內(nèi)容依然是最早加進(jìn)

來的項(xiàng)。也就是說，垂直滾動(dòng)條不會(huì)自動(dòng)向下滾。為了能讓列表框中始終能自動(dòng)顯示出最新的

著法名稱（所謂自動(dòng)，即不需用戶去手動(dòng)地滾動(dòng)垂直滾動(dòng)條來查看最新的著法名稱），我們可

以使用pLB->PostMessage(WM_VSCROLL,SB_BOTTOM,0);語句來發(fā)送一個(gè)讓垂直滾動(dòng)條處于最底

端的消息，使得列表框自動(dòng)滾動(dòng)垂直滾動(dòng)條以顯示最新的著法名稱。

當(dāng)我們想要從列表框中刪除項(xiàng)時(shí)，我們可以使用pLB->DeleteString(n);參數(shù)n指明了要

刪除的行數(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)被保存以供悔棋和還原所使用。

在我們的程序中保存了如下信息：

1、棋局表示中所定義的棋盤數(shù)組；

2、各棋子的貼圖位置。

這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋子的信息，而只

是保存之前一步的走棋信息。此后當(dāng)悔棋的時(shí)候，需要撤銷著法；還原的時(shí)候，需要執(zhí)行著法。

然而，我們?cè)诰帉懽约旱某绦驎r(shí)一來考慮到程序的可讀性和不易出錯(cuò)性，二來考慮到對(duì)當(dāng)今的

計(jì)算機(jī)的配置來說這點(diǎn)開銷基本上不會(huì)對(duì)程序的效率產(chǎn)生什么影響。因此索性保存了全部棋子

的信息。

根據(jù)所要保存的數(shù)據(jù)我們定義了如下基本結(jié)構(gòu)類型：

typedefstruct{

BYTECChessBoard[9][10];

POINTptChess[32];

}CCChess;//供悔棋、還原保存用的信息結(jié)構(gòu)

并隨之定義了兩個(gè)隊(duì)列以供悔棋和還原所用：

vectorvBackQueue;//悔棋保存隊(duì)列

vectorvForwardQueue;//還原保存隊(duì)列

在對(duì)弈過程中，每一回合我們都將棋局信息（這里指前面所說的需要保存的信息）保存至

vBackQueue隊(duì)列，以供悔棋所用。同時(shí)，若vForwardQueue不為空的話，我們還將清空它。因?yàn)?/p>

還原功能是與悔棋功能相對(duì)應(yīng)的，只有當(dāng)產(chǎn)生了悔棋功能之后，還原功能才會(huì)被激活。一個(gè)回

合的結(jié)束意味著前一次操作沒有悔棋功能的產(chǎn)生，因此還原隊(duì)列也應(yīng)被清空。

在悔棋中我們主要完成了以下任務(wù)：

1、下棋回合數(shù)減一；

2、將當(dāng)前局面信息保存至vForwardQueue隊(duì)列，以供還原所用；

3、從vBackQueue隊(duì)列中取出上一回合的棋局信息，恢復(fù)到當(dāng)前局面，然后將其從

vBackQueue隊(duì)列中剔除掉；

4、將顯示著法名稱的列表框中的本回合的著法名稱保存到一個(gè)著法名稱隊(duì)列（我們將其

定義為vectorvNameQueue;），以供還原所用。然后從列表框中刪除它。

而在還原中我們所做的剛好和悔棋相反：

1、下棋回合數(shù)加一；

2、將當(dāng)前局面信息保存至vBackQueue隊(duì)列，以供悔棋所用；

3、從vForwardQueue隊(duì)列中取出最近一次悔棋前的棋局信息，恢復(fù)到當(dāng)前局面，然后將

其從vForwardQueue隊(duì)列中剔除；

4、從著法名稱隊(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)容涉及人工智能的基本理論以及開發(fā)MFC應(yīng)用程序的一些基礎(chǔ)知識(shí)。無論是

從程序難度上講還是從程序規(guī)模上講都是我們之前所未遇到過的。該程序的順利完成為我們積

累了相當(dāng)可觀的運(yùn)用理論知識(shí)解決實(shí)際問題的經(jīng)驗(yàn)。特別是當(dāng)程序運(yùn)行過程中發(fā)現(xiàn)錯(cuò)誤的時(shí)

候，找出問題所在并解決問題更是一個(gè)積累經(jīng)驗(yàn)，提高實(shí)際編程能力的過程。得益于此次編寫

該中國(guó)象棋對(duì)弈程序，我們對(duì)人工智能有了一個(gè)初步的認(rèn)識(shí)——這為我們以后選擇進(jìn)一步學(xué)習(xí)

或研究的方向也提供了一定的參考價(jià)值。此外，我們還實(shí)踐了用MFC編寫基本的Windows

應(yīng)用程序，為今后從事開發(fā)Windows應(yīng)用程序也起到了一定的入門幫助作用。

然而，我們的程序也存在著幾點(diǎn)遺憾：

第一、由于我們對(duì)使用MFC編寫Windows程序的不熟悉，導(dǎo)致我們?cè)诮缑婕案綄俟δ懿?/p>

分花費(fèi)了大量的時(shí)間和精力。因而沒能夠?qū)τ?jì)算機(jī)下棋引擎部分作更深一步的挖掘和研究。對(duì)

于諸如位棋盤（BitBoard）、置換表（HashTable）、迭代加深（IterativeDeepening）、機(jī)器學(xué)習(xí)

（MachineLearning）等當(dāng)今棋類對(duì)弈程序中所采用的先進(jìn)技術(shù)和思想，在我們的程序中并未

涉及。這在一定程度上影響了我們的程序中下棋引擎的工作效率。

第二、之前我們寫程序都是單兵作戰(zhàn)，缺乏團(tuán)隊(duì)合作的經(jīng)驗(yàn)。這使得我們?cè)趨f(xié)同開發(fā)的過

程中遇到了一些問題。其中包括：

１、起初對(duì)小組各成員的分工上不夠明確；

２、由于事先沒有嚴(yán)格規(guī)定好編寫代碼的規(guī)范，以及對(duì)各部分的接口的規(guī)范強(qiáng)調(diào)的力度不

夠，導(dǎo)致不同人員所完成的作業(yè)在組裝和銜接時(shí)需要花費(fèi)額外的工作。

盡管，這些問題最終都得以解決，但卻影響了程序開發(fā)的進(jìn)程。

第三、程序總體缺乏對(duì)面向?qū)ο笏枷氲呢瀼睾褪褂谩Ｔ谖覀兊某绦虍?dāng)中，在界面和程序輔

助部分，由于要使用MFC，因而“不可避免”地使用了類（class）。然而，整個(gè)下棋引擎部分

沒有一點(diǎn)類的影子。這也是由于我本人最初在編寫引擎部分時(shí)一心只想盡快看到成果，因而從

一開始就按照自己先前的程序習(xí)慣（——面向過程）來編寫代碼。到了開發(fā)后期，又缺少時(shí)間

和精力來用面向?qū)ο笏枷胫匦赂膶懗绦颍罱K導(dǎo)致我們的引擎部分與類“無緣”。

第四、在本文即將交稿之際，我們程序仍在勝利局面檢測(cè)和貼圖刷新上存在著隨機(jī)性的出

錯(cuò)可能（出錯(cuò)幾率很小）。本文交稿后我們會(huì)繼續(xù)努力查找出錯(cuò)原因，爭(zhēng)取在程序發(fā)布時(shí)消除

掉這些bug。

最后，特別感謝指導(dǎo)老師對(duì)我們科技小組的支持。最終我們能夠順利完成程序，離不開組

員們的合作，更離不開指導(dǎo)老師的指導(dǎo)與幫助！

參考文獻(xiàn)：

[1]王小春：《PC游戲編程（人機(jī)博弈）》，2002年，第一版，重慶大學(xué)出版社

[2]網(wǎng)冠科技：《VisualC++.NET小游戲開發(fā)時(shí)尚編程百例》，2004年，第一版，機(jī)械工業(yè)出版

社

[3]陳建春：《VisualC++高級(jí)編程技術(shù)——開發(fā)實(shí)例剖析》，1999年，第一版，電子工業(yè)出

版社

[4]涂光平等：《VisualC++.NET基礎(chǔ)教程與上機(jī)指導(dǎo)》，2005年，第一版，清華大學(xué)出版社

[5]伍紅兵：《VisualC++編程深入引導(dǎo)》，2002年，第一版，中國(guó)水利水電出版社

[6]FredericFriedel（譯者：michael）：《電腦國(guó)際象棋簡(jiǎn)史》，

詳見/~auntyellow/computer/，

最后瀏覽日期：2006年5月7日

[7]Fran?oisDominicLaramée（譯者：黃晨）：《國(guó)際象棋程序設(shè)計(jì)(一)：引言》，

詳見/~auntyellow/computer/basic_，

最后瀏覽日期：2005年8月5日

[8]Fran?oisDominicLaramée（譯者：黃晨）：《國(guó)際象棋程序設(shè)計(jì)(三)：著法的產(chǎn)生》，

詳見/~auntyellow/computer/basic_，

最后瀏覽日期：2005年8月5日

[9]Fran?oisDominicLaramée（譯者：黃晨）：《國(guó)際象棋程序設(shè)計(jì)(四)：基本搜索方法》，

詳見/~auntyellow/computer/basic_，

最后瀏覽日期：2005年8月5日

[10]Fran?oisDominicLaramée（譯者：黃晨）：《國(guó)際象棋程序設(shè)計(jì)(六)：局面評(píng)估函數(shù)》，

詳見/~auntyellow/computer/basic_，

最后瀏覽日期：2005年8月5日

[11]DavidEppstein（譯者：黃晨）：《棋盤的表示》，

詳見/~auntyellow/computer/struct_，

最后瀏覽日期：2005年8月5日

[12]DavidEppstein（譯者：黃晨）：《最小-最大和負(fù)值最大搜索》，