首页 > 实用范文

中国象棋人机博弈

更新时间:2023-03-05 16:15:38 阅读：评论：0

初中物理教案-培训就业

2023年3月5日发(作者：茶叶排名前十名)

中国象棋对弈程序

【摘要】：人机博弈是人工智能研究的经典课题之一。凭借设计优良的算法和计算机的快速运

算能力，计算机可以在人机对弈中表现出相当高的“智能”。通常，一款象棋程序的实现可以

被分为下棋引擎（人工智能）和外壳（界面及程序辅助）两大部分。本文将介绍如何实现一款

中国象棋对弈程序。

【关键词】：中国象棋；人工智能；博弈树；Alpha-Beta搜索；历史启发；界面；多线程；计

时器；列表框；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.

一、前言

我们的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈程序。

该程序功能包括：

*人机对弈；

*盲棋模式；

（注：此功能为创新功能）

*搜索深度设定；

（电脑棋力选择）

*棋子、棋盘样式选择；

*悔棋、还原；

*着法名称显示；

*下棋双方计时；

整个程序的实现可分为两大部分：

一、人工智能部分（计算机下棋引擎）

该部分实现了如何让计算机下中国象棋，其中涉及人机博弈的基本理论及思想，是该程序

的核心部分，同时也是本项目研究的重点所在。

二、界面及程序辅助部分

光有下棋引擎尚不能满足人机交互的基本要求，因此我们还需要一个框架（界面）来作为

引擎的载体，同时提供一些诸如悔棋，计时之类的附属功能（程序辅助）来为程序增色添彩。

下面分别介绍各部分实现。由于界面及程序辅助部分涉及内容宽泛而又繁琐，因而本文只

介绍其中重点部分以及我们在开发过程中曾经遇到过困难的地方。

二、人工智能部分（计算机下棋引擎）

1、概述

程序的基本框架：

从程序的结构上讲，大体上可以将引擎部分划分为四大块：

棋局表示；

着法生成；

搜索算法；

局面评估。

程序的大概的思想是：

首先使用一个数据结构来描述棋局信息，对某一特定的棋局信息由着法生成器生成当前下

棋方所有合法的着法并依次存入着法队列。然后通过搜索算法来逐一读取着法并调用局面评估

函数对该着法所产生的后继局面进行评估打分，从中选出一个最有可能导致走棋方取胜的着

法。在搜索的过程中还可以采用一些辅助手段来提高搜索的效率。其过程如下图所示：

下面将分别介绍各个部分。

2、棋局表示

计算机下棋的前提是要让计算机读懂象棋。所谓读懂，即计算机应该能够清楚地了解到棋

盘上的局面（棋盘上棋子的分布情况）以及下棋方所走的每一种着法。因而首先我们需要有一

套数据结构来表示棋盘上的局面以及着法。

对于棋盘局面的表示我们采用了最传统的同时也是最为简单的“棋盘数组”。即用一个

9*10的数组来存储棋盘上的信息，数组的每个元素存储棋盘上相应位置是何种棋子。这种表

示方法简单易行（缺点是效率不是很高）。按此方法棋盘的初始情形如下所示：

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”表示无棋子，大写字母表示红方棋子，小写

字母表示黑方棋子（所有这些大小写字母都是用宏定义的整

数）。具体如下：

“R”表示红车；“H”表示红马；“E”表示红相；“A”

表示红仕；“K”表示红帅；“C”表示红炮；“P”表示红兵。

“r”表示黑车；“h”表示黑马；“e”表示黑象；“a”

表示黑士；“k”表示黑将；“c”表示黑炮；“p”表示黑卒。

此外这个数组也表明了我们对棋盘进行了如右图所示

的编号，并约定红方棋子总处于棋盘的下方。

对于着法的表示，我们直接借用棋盘数组的下标来记录着法的起点和目标点。至于是什么

棋子在走，以及是否吃子、吃的是什么子，我们在着法结构中并不记录。这些信息由外部读取

棋盘上起点、终点的数据获得。着法结构定义如下，其中还包含了对着法的历史得分的记录项，

以供后面要讲到的“历史启发”所用。

typedefstruct_cchessmove{

POINTptFrom;//起点

POINTptTo;//目标点

intnScore;//该走法的历史得分

}CCHESSMOVE;//走法结构

有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：

1、生成所有合法着法；

2、执行着法、撤销着法；

3、针对某一局面进行评估。

因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建

立在其基础上。

3、着法生成

我们的程序需要让计算机在轮到它走子的时候能够执行一步它认为对它最有利的着法，那

前提就是它要有诸多（也可能是唯一）可供选择的着法，提供所有候选着法的“清单”就是我

们的着法生成器所要完成的。之后用搜索函数来搜索“清单”，并用局面评估函数来逐一打分，

最后就可以选择出“最佳着法”并执行了。

在着法生成器中，我们采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每

个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型

而相应地找出其所有合法着法并存入着法队列。

这里谈到的“合法着法”包括以下几点：

1、各棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九宫内斜行等等

（这里需要特别注意的是卒（兵）的行子规则会随其所在位置的不同而发生变化——过河后可

以左右平移）。

2、行子不能越出棋盘的界限。当然所有子都不能走到棋盘的外面，同时某些特定的子还

有自己的行棋界限，如将、士不能出九宫，象不能过河。

3、行子的半路上不能有子阻拦（除了炮需要隔一个子才能打子之外）以及行子的目的点

不能有本方棋子（当然不能自己吃自己了）。

4、将帅不能碰面（本程序中只在生成计算机的着法时认为将帅碰面是非法的，而对用户

所走的导致将帅碰面的着法并不认为其非法，而只是产生败局罢了）。

产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来

我往好几步，这样才有利于对局面进行评估以尽可能避免“目光短浅”），所以在把着法存入着

法队列的时候还要同时存储该着法所属的搜索层数。因此我们将着法队列定义为二维数组

MoveList[12][80]，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。

关于搜索层数，我将数组下标设定为12，实际使用的是1到11（在界面中我又将其限定

为1—10）。搜索层数的增加会显著提高电脑的下棋水平（当然计算机的棋力在很大程度上也

依赖于局面评估）。在我的迅驰1.5，736M内存的笔记本上最多只能搜索5层，再多将导致搜

索时间达到令人无法容忍的地步（这里还需要特别说明的是，搜索的速度也和着法生成的效率

以及局面评估的复杂度有关，因为每分析一个结点都要执行这两种操作）。

对于每一层的着法数，也就是当前下棋方针对当前局面的所有可选的合法着法，据有关数

据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数组下标为80，应当可以保

证十分的安全。

着法生成为搜索部分提供了“原料”，接下来的任务就交给搜索和局面评估了。

4、搜索算法

搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。

搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因

为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”

得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，经前人的努力已形成了非常成熟的

Alpha-Beta搜索算法1以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变

种算法）。鉴于目前我们的知识储备、时间、精力等均达不到推陈出新、另开炉灶的要求，再

加之前人的算法着实已相当完善，所以我们在自己的程序中直接借鉴了Alpha-Beta搜索算法

并辅以了历史启发。本节先介绍Alpha-Beta搜索算法：

在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是将死对方，或者

避免被将死。

由此，我们可以用一棵“博弈树”（一棵n叉树）来表示下棋的过程——树中每一个结点

代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的

结点），如此不断直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的

1Alpha-beta算法，该算法是由匹兹堡大学的三位科学家Newell,ShawandSimon于1958年提出的。

模型大概如下图所示，我们可以把其中连接结点的线段看作是着法，不同的着法自然产生不同

的局面。

该树包含三种类型的结点：

1、奇数层的中间结点（以及根结点），表示轮到红方走棋；

2、偶数层的中间结点，表示轮到黑方走棋；

3、叶子结点，表示棋局结束。

现在让计算机来下中国象棋，它应当选择一步对它最有利的着法（最终导致它取胜的着

法）。获得最佳着法的方法就是“试走”每一种可能的着法，比较它们所产生的不同后果，然

后从中选出能够产生对自己最有利的局面的着法。

结合上面所讲的博弈树，如果我们给每个结点都打一个分值来评价其对应的局面（这一任

务由后面所讲的局面评估来完成），那么我们可以通过比较该分值的大小来判断局面的优劣。

假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个

极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他

会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到

博弈树上，即如果我们假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲

方希望棋盘上的分值尽可能大，则在偶数层上我们会挑选分值最大的结点——偶数层的结点是

甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘

上的分值尽可能小，那么在奇数层上我们会选择分值最小的结点。这就是“最小-最大”

（Minimax）2的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大

（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、

限定搜索层数以内的整棵树来获得一个最佳的着法。然而不幸的是，博弈树相当庞大（它会成

指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为

O(bn)。其中b是分枝因子，即针对各种局面的合法着法的数目的平均值，n是搜索的深度。对

于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条

路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！！！

幸运的是，Alpha-Beta搜索使得我们能在不影响搜索精度的前提下大幅减少工作量。

因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方

2“最小-最大”（Minimax）最早是由JohnvonNuoma（1903-1957，美籍匈牙利数学家）在60多年前完整描

述的：

1、假设有对局面评分的方法，来预测棋手甲（我们称为最大者）会赢，或者对手（最小者）会赢，或者

是和棋。评分用数字表示，正数代表最大者领先，负数代表最小者领先，零代表谁也不占便宜；

2、最大者的任务是增加棋盘局面的评分（即尽量让评分最大）；

3、最小者的任务是减少棋盘局面的评分（即尽量让评分最小）；

4、假设谁也不会犯错误，即他们都走能让使局面对自己最有利的着法。

都会尽可能将局面导向对自己有利而对对方不利的方向（我们假定下棋双方对棋局有着同样的

认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面

由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能

产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应

当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必

将得到那个很糟糕的局面，甚至可能更糟„„这样一来便可以在很大程度上减少搜索的工作

量，提高搜索效率，这称为“树的裁剪”。

下面用图来进一步说明“树的裁剪”。为了简便起见，我将博弈树进行了简化——每个结

点只有三个分支，实际情况中，刚才讲过在中盘应有大约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算法的代码如下：

intAlphaBeta(intdepth,intalpha,intbeta)

{

if(depth==0)//如果是叶子节点（到达搜索深度要求）

returnEvaluate();//则由局面评估函数返回估值

GenerateLegalMoves();//产生所有合法着法

while(MovesLeft())//遍历所有着法

{

MakeNextMove();//执行着法

intval=-AlphaBeta(depth-1,-beta,-alpha);//递归调用

UnmakeMove();//撤销着法

if(val>=beta)//裁剪

returnbeta;

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

alpha=val;

}

returnalpha;

}

5、历史启发及着法排序（搜索辅助）

既然Alpha-Beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高

效率，那么它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行

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

所有的可能性之后才能做出“裁剪”操作，那此时“裁剪”也已经失去了它原有的价值（因为

你已经分析了所有情况，这时的Alpha-Beta搜索已和“最小-最大”搜索别无二致了）。因而，

要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使

得“裁剪”可以尽可能早地发生。

我们可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局

面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位

置有所不同）也是较好的。由fer所提出的“历史启发”（HistoryHeuristic）就是建立

在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，我们就给该走法累加一个

增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对

于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”

高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索

的效率。

对于着法的排序可以使用各种排序算法，在我们的程序中采用了归并排序。归并排序的空

间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。

6、局面评估

前面已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助），在象棋程序中如果说

搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对

搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。

首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差

异。在中国象棋中所要考虑的最基本的几个因素包括如下四点：

1、子力总和

子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值

500的话，那可能马值300，卒值80等等。所以在评估局面时，我们首先要考虑双方的子力总

和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。

2、棋子位置（控制区域）

棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位置。例如，沉

底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差

的棋子位置状态。

3、棋子的机动性

棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以我们

下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认

为其机动性为零）。

4、棋子的相互关系（包括攻击关系和保护关系）

这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能

在对方的炮的攻击之下同时它又攻击着对方的车。

在我的程序中，估值函数最后返回的是每一方的总分的差值，而各方的总分就是上面所提

到的四个因素的打分的总和。

对于子力打分和控制区域打分，只要遍历棋盘，当遇到棋子时简单地去查事先定义好的“子

力价值表”和“控制区域价值表”，取出相对应的值进行累加即可（这些值的具体设定参考了

前人的程序并作了适当的调整,今后仍应根据电脑下棋所反映出的实际问题对这些值作适当修

改）。

对于机动性打分，需要求出各个子总共有多少种走法，然后根据各个子所不同的机动性价

值每多一种走法就加一次相应的分数。

对棋子间相互关系的打分，我先定义了一个关系表的结构类型

typedefstruct_relationtable{

BYTEnCChessID;

intnUAttackCount;

intnUGuardCount;

BYTEUnderAttack[5];

BYTEUnderGurad[5];

}RelationTable;

RelationTableRelationOfMan[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和下展开。

我们所写的代码主要分布于以下三大部分：

一、初始化部分

BOOLCCChessUIDlg::OnInitDialog()

{

}

OnInitDialog()负责的是对话框的初始化。我们把有关中国象棋的棋局初始化情况也放在

了这里面。初始化的内容包括：

1、对引擎部分所用到的变量的初始化。包括对棋盘上的棋子位置进行初始化（棋盘数组

的初始化），对搜索深度、当前走棋方标志、棋局是否结束标志等的初始化；

2、对棋盘、棋子的贴图位置（即棋盘、棋子在程序中实际显示位置）的初始化；

3、对程序辅助部分所用到的一些变量的初始化。包括对悔棋、还原队列的清空，棋盘、

棋子样式的默认选择，下棋模式的默认选择，计时器显示的初始化，以及着法名称列

表的初始化等。

二、绘图部分

voidCCChessUIDlg::OnPaint()

{

}

OnPaint()函数负责的是程序界面的绘图。因此，在这里我们要完成棋盘、棋子的显示（如

果用户选择了盲棋模式，则不进行棋子的绘图，而是在屏幕中央给出提示信息表明当前为盲棋

模式），走棋起始位置和目标位置的提示框的显示。

由于我们的棋盘、棋子等都是以位图的形式给出的。所以在OnPaint()函数里我们做的工

作主要都是在贴位图。

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

文件只能是矩形的，所以如果直接贴图的话会在棋盘上留下一块白色的边框——棋子的背景。

因此，要想让棋子文件的背景“隐藏”需要通过一些“与”和“异或”操作来屏蔽掉棋子的背

景。

三、走棋部分（用户动作响应部分）

为WM_LBUTTONDOWN消息添加消息响应事件，可得到如下函数：

voidCCChessUIDlg::OnLButtonDown(UINTnFlags,CPointpoint)

{

}

当用户在窗口客户区按下鼠标左键时,程序就会调用OnLButtonDown(UINTnFlags,CPoint

point)函数来进行响应。其中第二个参数CPointpoint是我们在本程序中所要用到的，它给

出了当鼠标左键被按下时，鼠标指针的位置坐标。我们可以通过这一信息来得知用户的走法。

在OnLButtonDown函数里我们处理如下两种操作：

１、如果用户点击鼠标的位置落在己方的棋子上，表示用户选中了该棋子，下一步将移动

该子进行走棋（也可能用户下一步将会选择己方另外的棋子，总之这一操作会记录下用户所选

的将要走的棋子）。

２、如果之前用户已经选过了棋子，那么这一次的点击（如果不是另选本方的其它棋子的

话）表达了用户的一次走棋过程。在收到用户传达的走棋信息后，我们先判断该着法是否合法

（是否符合中国象棋的游戏规则），如果合法，则执行之。紧接着我们调用引擎的搜索函数计

算出计算机对用户着法的应着，然后执行该应着。

如此，在OnLButtonDown函数里，我们实现了人与机器的对弈（当然每走一步棋，也还需

要绘图函数来显示棋盘局面的更新）。

以上三部分并非界面程序的全部，而仅仅是与我们的程序密切相关的部分。此外还有其它

部分对程序同样必不可少，但这些部分主要由MFC自动生成，无需人为改动，故在此不多做

介绍。

2、多线程（程序辅助）

最初，我们的程序中没有给计算机的“思考”另外开辟新的线程。而仅仅是简单地按照如

下顺序编写代码：

用户走棋—〉计算机思考并走棋

按这种方式编写的程序似乎毫无问题，程序运行一切正常。

然而，在我们给程序加入计时功能（后面将会在讲到其实现）后，程序出现了异常：对用

户方的计时功能完全正确，而对电脑方的计时功能却根本不起作用！后来，经指导老师点拨，

我们找到了问题的所在以及相应的解决方案——由于程序在进行搜索时会占用大量的CPU时

间，因而阻塞了位于同一线程内的计时器，使之无法正常工作。解决方案就是另外开一个线程，

让搜索与计时器分处两个线程。

启动一个新的线程的方法非常简单，只需调用API函数AfxBeginThread即可，函数原型：

CWinThread*AfxBeginThread(

AFX_THREADPROCpfnThreadProc,

LPVOIDpParam,

intnPriority=THREAD_PRIORITY_NORMAL,

UINTnStackSize=0,

DWORDdwCreateFlags=0,

LPSECURITY_ATTRIBUTESlpSecurityAttrs=NULL

);3

该函数启动一个新的线程并返回一个指向该新线程对象的指针，然后新的线程与启动该新

线程的线程同时运行。该函数的第一个参数AFX_THREADPROCpfnThreadProc指定了线程函数。

线程函数的内容即为新线程所要执行的内容，线程函数执行完毕，新线程结束（自动销毁）。

线程函数必须被定义为全局函数，其返回值类型必须是UINT，必须有一个LPVOID类型的

参数。我们可以把调用引擎部分的搜索函数的代码以及完成走棋动作的代码放入我们所定义的

思考线程内，如下：

UINTThinkingThread(LPVOIDpParam)

{

//计算机思考并走棋

}

然后，我们只要将原先调搜索函数并完成走棋的代码代之以调用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==1then红方计时＋１;

if计时器ID==2then黑方计时＋１;

}

当然，上面的流程及伪码仅仅说明编写象棋计时器大体思想，实际情况要比这复杂的多。

在我们的实际的程序中还涉及了线程间的通信（因为我们把计算机方的思考和走棋的过程放在

了另一个线程之内），时间的刷新显示，分、秒、时的进位换算等等。而且为了提高计时精度，

我们还将SetTimer函数的第二个参数设为了100，即每0.1秒做一次计时（有时计算机思考

和走棋的时间还不足1秒，如果按每秒钟计一次时，则该不足1秒的时间将被遗漏），当然实

际显示的时候还是只显示到秒。

4、着法名称显示（程序辅助）

每当下棋方（用户或是计算机）走一步棋，我们就在棋盘旁边的一个列表框控件（ListBox）

中按照中国象棋关于着法描述的规范要求显示出该着法的名称。如：红炮二平五、黑马８进７

此类。为了获得该着法名称，我们写了一个六百余行的函数。其功能就是将被移动的棋子类型

以及走法的起点坐标、终点坐标这些信息转换成中国象棋所规范的着法名称。由于该函数主要

涉及的是中国象棋关于着法表示的规范要求，故在此我们不对其具体实现做额外的解释。这里

我们主要讨论的是如何对列表框控件（ListBox）进行操作，以显示或删除着法名称。

MFC为我们提供了一个CListBox类，使用该类的成员函数我们可以非常容易地实现在

ListBox中添加与删除“项（item）”。

首先，我们先要定义一个指向该类的对象的指针：

CListBox*pLB;

然后，在进行程序初始化（对话框的初始化）时，我们使用如下语句来让该指针与对话框

中的ListBox控件建立起联系来（即让该指针指向对话框中的ListBox控件）。

pLB=(CListBox*)GetDlgItem(IDC_LISTCCHESS);

其中IDC_LISTCCHESS是所要建立关联的控件的ID号。

之后，我们便可调用成员函数pLB->AddString(str);来向ListBox控件中添加显示字符串，

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

当列表框中的项的数目超过列表框的显示范围时，列表框会自动添加垂直滚动条（前提是

其VerticalScrollbar属性要为True——该属性默认即为True）。但是显示的内容依然是最早加进

来的项。也就是说，垂直滚动条不会自动向下滚。为了能让列表框中始终能自动显示出最新的

着法名称（所谓自动，即不需用户去手动地滚动垂直滚动条来查看最新的着法名称），我们可

以使用pLB->PostMessage(WM_VSCROLL,SB_BOTTOM,0);语句来发送一个让垂直滚动条处于最底

端的消息，使得列表框自动滚动垂直滚动条以显示最新的着法名称。

当我们想要从列表框中删除项时，我们可以使用pLB->DeleteString(n);参数n指明了要

删除的行数。最早加入列表框中的项记为第0行，以后逐次递增。若要删除最后一行内容（在

悔棋功能中需要用到这一操作），则可以使用pLB->DeleteString(pLB->GetCount()-1);其中

pLB->GetCount()返回的是列表框中的项的数目，减一之后正好是最后一项的行号。

5、悔棋、还原（程序辅助）

悔棋和还原是棋类软件中较为基本的功能。要实现悔棋和还原功能，首先我们要明确哪些

信息应当被保存以供悔棋和还原所使用。

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

1、棋局表示中所定义的棋盘数组；

2、各棋子的贴图位置。

这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息，而只

是保存之前一步的走棋信息。此后当悔棋的时候，需要撤销着法；还原的时候，需要执行着法。

然而，我们在编写自己的程序时一来考虑到程序的可读性和不易出错性，二来考虑到对当今的

计算机的配置来说这点开销基本上不会对程序的效率产生什么影响。因此索性保存了全部棋子

的信息。

根据所要保存的数据我们定义了如下基本结构类型：

typedefstruct{

BYTECChessBoard[9][10];

POINTptChess[32];

}CCChess;//供悔棋、还原保存用的信息结构

并随之定义了两个队列以供悔棋和还原所用：

vectorvBackQueue;//悔棋保存队列

vectorvForwardQueue;//还原保存队列

在对弈过程中，每一回合我们都将棋局信息（这里指前面所说的需要保存的信息）保存至

vBackQueue队列，以供悔棋所用。同时，若vForwardQueue不为空的话，我们还将清空它。因为

还原功能是与悔棋功能相对应的，只有当产生了悔棋功能之后，还原功能才会被激活。一个回

合的结束意味着前一次操作没有悔棋功能的产生，因此还原队列也应被清空。

在悔棋中我们主要完成了以下任务：

1、下棋回合数减一；

2、将当前局面信息保存至vForwardQueue队列，以供还原所用；

3、从vBackQueue队列中取出上一回合的棋局信息，恢复到当前局面，然后将其从

vBackQueue队列中剔除掉；

4、将显示着法名称的列表框中的本回合的着法名称保存到一个着法名称队列（我们将其

定义为vectorvNameQueue;），以供还原所用。然后从列表框中删除它。

而在还原中我们所做的刚好和悔棋相反：

1、下棋回合数加一；

2、将当前局面信息保存至vBackQueue队列，以供悔棋所用；

3、从vForwardQueue队列中取出最近一次悔棋前的棋局信息，恢复到当前局面，然后将

其从vForwardQueue队列中剔除；

4、从着法名称队列vNameQueue中取出最近一次存入的着法名称（两项，因为每回合会产

生两步着法），将其重新显示到列表框中。然后将其从vNameQueue中剔除。

以上便是悔棋和还原功能所完成的具体操作，其代码分别写入悔棋和还原按钮（Button）

的BN_CLICKED事件处理函数中。

四、总结

下面简单地总结一下。

首先，在指导老师的热心帮助下，小组成员协同工作最终顺利实现了程序。整个程序近

6000行代码，内容涉及人工智能的基本理论以及开发MFC应用程序的一些基础知识。无论是

从程序难度上讲还是从程序规模上讲都是我们之前所未遇到过的。该程序的顺利完成为我们积

累了相当可观的运用理论知识解决实际问题的经验。特别是当程序运行过程中发现错误的时

候，找出问题所在并解决问题更是一个积累经验，提高实际编程能力的过程。得益于此次编写

该中国象棋对弈程序，我们对人工智能有了一个初步的认识——这为我们以后选择进一步学习

或研究的方向也提供了一定的参考价值。此外，我们还实践了用MFC编写基本的Windows

应用程序，为今后从事开发Windows应用程序也起到了一定的入门帮助作用。

然而，我们的程序也存在着几点遗憾：

第一、由于我们对使用MFC编写Windows程序的不熟悉，导致我们在界面及附属功能部

分花费了大量的时间和精力。因而没能够对计算机下棋引擎部分作更深一步的挖掘和研究。对

于诸如位棋盘（BitBoard）、置换表（HashTable）、迭代加深（IterativeDeepening）、机器学习

（MachineLearning）等当今棋类对弈程序中所采用的先进技术和思想，在我们的程序中并未

涉及。这在一定程度上影响了我们的程序中下棋引擎的工作效率。

第二、之前我们写程序都是单兵作战，缺乏团队合作的经验。这使得我们在协同开发的过

程中遇到了一些问题。其中包括：

１、起初对小组各成员的分工上不够明确；

２、由于事先没有严格规定好编写代码的规范，以及对各部分的接口的规范强调的力度不

够，导致不同人员所完成的作业在组装和衔接时需要花费额外的工作。

尽管，这些问题最终都得以解决，但却影响了程序开发的进程。

第三、程序总体缺乏对面向对象思想的贯彻和使用。在我们的程序当中，在界面和程序辅

助部分，由于要使用MFC，因而“不可避免”地使用了类（class）。然而，整个下棋引擎部分

没有一点类的影子。这也是由于我本人最初在编写引擎部分时一心只想尽快看到成果，因而从

一开始就按照自己先前的程序习惯（——面向过程）来编写代码。到了开发后期，又缺少时间

和精力来用面向对象思想重新改写程序，最终导致我们的引擎部分与类“无缘”。

第四、在本文即将交稿之际，我们程序仍在胜利局面检测和贴图刷新上存在着随机性的出

错可能（出错几率很小）。本文交稿后我们会继续努力查找出错原因，争取在程序发布时消除

掉这些bug。

最后，特别感谢指导老师对我们科技小组的支持。最终我们能够顺利完成程序，离不开组

员们的合作，更离不开指导老师的指导与帮助！

参考文献：

[1]王小春：《PC游戏编程（人机博弈）》，2002年，第一版，重庆大学出版社

[2]网冠科技：《VisualC++.NET小游戏开发时尚编程百例》，2004年，第一版，机械工业出版

社

[3]陈建春：《VisualC++高级编程技术——开发实例剖析》，1999年，第一版，电子工业出

版社

[4]涂光平等：《VisualC++.NET基础教程与上机指导》，2005年，第一版，清华大学出版社

[5]伍红兵：《VisualC++编程深入引导》，2002年，第一版，中国水利水电出版社

[6]FredericFriedel（译者：michael）：《电脑国际象棋简史》，

详见/~auntyellow/computer/，

最后浏览日期：2006年5月7日

[7]FrançoisDominicLaramée（译者：黄晨）：《国际象棋程序设计(一)：引言》，

详见/~auntyellow/computer/basic_，

最后浏览日期：2005年8月5日

[8]FrançoisDominicLaramée（译者：黄晨）：《国际象棋程序设计(三)：着法的产生》，

详见/~auntyellow/computer/basic_，

最后浏览日期：2005年8月5日

[9]FrançoisDominicLaramée（译者：黄晨）：《国际象棋程序设计(四)：基本搜索方法》，

详见/~auntyellow/computer/basic_，

最后浏览日期：2005年8月5日

[10]FrançoisDominicLaramée（译者：黄晨）：《国际象棋程序设计(六)：局面评估函数》，

详见/~auntyellow/computer/basic_，

最后浏览日期：2005年8月5日

[11]DavidEppstein（译者：黄晨）：《棋盘的表示》，

详见/~auntyellow/computer/struct_，

最后浏览日期：2005年8月5日

[12]DavidEppstein（译者：黄晨）：《最小-最大和负值最大搜索》，