毕 业 设 计
中国象棋游戏的设计与实现
中国象棋发展至今已有数千年的历史了，它是中华民族智慧的结晶。在我国，中国象棋的普及程度是其它棋类无法比拟的，大至国际、国内比赛，小至社区街道。如今，仅中国就有2亿人会下中国象棋，且中国象棋的发展趋势日益国际化。本文首先研究了中国象棋在计算机中的表示问题，讨论如何产生着法等一系列相关内容，其次研究了博弈树的搜索技术及在此基础上发展起来的相关剪枝算法。系统使用MFC 文档视图体系结构和Visual C++开发工具，实现了一个具有一定棋力的中国象棋人机对弈程序。此博弈程序实现了人机博弈，悔棋，电脑难度设置，着法名称生成等功能。
关键词：中国象棋 人工智能 博弈树 Alpha-Beta 搜索
1 前言 .................................................................... 1
1.1 中国象棋游戏设计背景和研究意义 . ........................................ 1
1.2 国内外象棋软件发展概况 . ................................................ 1
1.3 中国象棋游戏设计研究方法 . .............................................. 1
1.4 本文的主要工作 . ........................................................ 2
2 棋局表示和着法生成 . ...................................................... 2
2.1 棋盘和棋子的表示 . ...................................................... 2
2.2 着法生成 . .............................................................. 4
3 走棋和博弈程序的实现 . .................................................... 5
3.1 博弈程序的实现 . ........................................................ 5
3.1.1 搜索算法 . ............................................................ 5
3.1.2 着法排序 . ............................................................ 9
3.1.3 局面评估 . ........................................................... 10
3.2 悔棋和还原功能的实现 . ................................................. 12
3.3 着法名称显示功能的实现 . ............................................... 13
3.4 胜败判定 . ............................................................. 16
4 界面设计和系统实现 . ..................................................... 17
4.1 界面设计 . ............................................................. 17
4.2 系统实现 . ............................................................. 19
5 总结 . ................................................................... 23
参 考 文 献 ........................................................... 25
ABSTRACT ................................................................. 26 致 谢 ................................................. 错误！未定义书签。 仲恺农业工程学院毕业论文(设计) 成绩评定表 ................. 错误！未定义书签。
1 前言
1.1 中国象棋游戏设计背景和研究意义
中国象棋游戏流传至今已经有数千年的历史了，是一种古老的文化，它集文化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人的思维，培养人的毅力，增强人的竞争意识。自从计算机发明，向各个领域发展，到成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐步渗入我们每个人的娱乐活动中。在计算机已经普及的今天，对于可以用计算机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想，中国象棋历史悠久不仅源远流长，而且基础广泛，作为一项智力运动更成为我们游戏开发的首选对象。
中国象棋是一项智力游戏，以往都是人和人下棋，现在有了计算机我们可以和计算机竞技，人可以与计算机进行对弈。控制计算机的是人类，而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。
1.2 国内外象棋软件发展概况
最早的象棋软件是一副可以外出携带的电子棋盘，后来升级到电视游戏机。开始出现的一些容量很小的象棋软件如：DOS 界面《将族》、WIN31程序的《中国象棋》等等，与其说人类下不过电脑，倒不如说是没有耐性等待电脑程序慢吞吞的搜索算法，有时甚至怀疑软件是否在搜索中死掉了。后来，网络上先后出现了真正的WINDOWS 窗口界面的象棋专业高级软件《棋隐》、《象棋世家》、《象棋参谋》、《象棋奇兵》等。总而言之，各类象棋软件既有自身的优点，也存在共通性的缺陷，如：中局审势不够智能化，走不出弃子取势的人性化佳构，残局时智力明显低于人脑，难以走出残局例胜的必然着法等。放眼未来，象棋软件已经走完了一波持续上涨的行情，有可能出现逐步降温的滑坡趋势。
1.3 中国象棋游戏设计研究方法
本系统主要用 Visual C++ 进行开发，里面的MFC 类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。
该象棋人机博弈系统实现的功能主要包括：
1、选手选择（人或电脑）；
2、人机对弈（人与电脑竞技）；
3、电脑棋力难度选择（电脑下棋能力难度选择，共有4级：按电脑配置选择难度）；
4、悔棋、还原；
5、着法名称显示（象棋走棋规范名称）。
1.4 本文的主要工作
第一部分主要介绍了中国象棋游戏开发的背景及意义、国内外象棋软件的发展概况和象棋游戏的设计研究方法；
第二部分介绍了棋局表示方法和着法生成；
第三部分介绍了走棋和博弈程序的实现；
第四部分介绍了界面设计和系统的实现。
2 棋局表示和着法生成
2.1 棋盘和棋子的表示
对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”。即用一个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
};
给所有棋子定义一个值：
#define R_BEGIN R_KING
#define R_END R_PAWN
#define B_BEGIN B_KING
#define B_END B_PAWN
#define 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 && x
#define IsRed(x) (x>=R_BEGIN && x
对于着法的表示，直接借用棋盘数组的下标来记录着法的起点和目标点。至于是什么棋子在走，以及是否吃子、吃的是什么子，在着法结构中并不记录。这些信息由外部读取棋盘上起点、终点的数据获得。着法结构定义如下，其中还包含了对着法的历史得分的记录项，以供后面要讲到的“历史启发”所用。 typedef struct
{
short nChessID; //表明是什么棋子 CHESSMANPOS From;//起始位置 CHESSMANPOS To; //走到什么位置 int Score; //走法的分数
}CHESSMOVE;
有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：
生成所有合法着法；
执行着法、撤销着法；
针对某一局面进行评估。
因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建立在其基础上。
2.2 着法生成
在着法生成器中，采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。
这里谈到的“合法着法”包括以下几点：
1、各棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九宫内斜行等等（这里需要特别注意的是卒（兵）的行子规则会随其所在位置的不同而发生变化——过河后可以左右平移）。
2、行子不能越出棋盘的界限。当然所有棋子都不能走到棋盘的外面，同时某些特定的棋子还有自己的行棋界限，如将、士不能出九宫，象不能过河。
3、行子的半路上不能有其它子阻拦（除了炮需要隔一个子才能打子之外）以及行子的目的点不能有本方的棋子（当然不能自己吃自己了）。
4、将帅不能碰面（本程序中只在生成计算机的着法时认为将帅碰面是非法的，而对用户所走的导致将帅碰面的着法并不认为其非法，而只是产生败局罢了）。
产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来我往好几步，这样才有利于对局面进行评估以尽可能避免“目光短浅”），所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。
因此可以将着法队列定义为二维数组m_MoveList[8][70]，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。
关于搜索层数，设定为4，实际使用的是1到3（在界面中将其限定为1—3）。搜索层数的增加会显著提高电脑的下棋水平（当然计算机的棋力在很大程度上也依赖于局面评估）。在配置为1.5G ，512M 内存的计算机上最多只能搜索3层，再多将导致搜索时间达到令人无法容忍的地步（这里还需要特别说明的是，搜索的速度也和着法生成的效率以及局面评估的复杂度有关，因为每分析一个结点都要执行这两种操作）。
对于每一层的着法数，也就是当前下棋方针对当前局面的所有可选的合法着法，据有关数据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数组下标为70，应当可以保证十分的安全。
3 走棋和博弈程序的实现
3.1 博弈程序的实现
3.1.1 搜索算法
搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta 搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta 算法的派生、变种算法）。我们在程序中直接借鉴了Alpha-Beta 搜索算法并辅以历史启发。本节先介绍Alpha-Beta 搜索算法：在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是吃掉对方的将或帅，或者避免自己的将或帅被吃。
图1 博弈树
又此，可以用一棵“博弈树”（图1）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断进行下去直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的模型大概如下图所示，可以把其中连接结点的线段看作是着法，不同的着法自然产生不同的局面。
该树包含三种类型的结点：
1、奇数层的中间结点（以及根结点），表示轮到红方走棋；
2、偶数层的中间结点，表示轮到黑方走棋；
3、叶子结点，表示棋局结束。
现在让计算机来下中国象棋，它应当选择一步对它最有利的着法（最终导致它取胜的着法）。获得最佳着法的方法就是“试走”每一种可能的着法，比较它们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的着法。
结合上面所讲的博弈树，若给每个结点都打一个分值来评价其对应的局面（这一任务由后面所讲的局面评估来完成），那么可以通过比较该分值的大小来判断局面的优劣。假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果
假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上会挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上会选择分值最小的结点。这是“最小-最大”（Minimax ）的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O(bn)。其中b 是分枝因子，即针对各种局面的合法着法的数目的平均值，n 是搜索的深度。对于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！
Alpha-Beta 搜索能在不影响搜索精度的前提下大幅减少工作量。
因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向（假定下棋双方对棋局有着同样的认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟。这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。
下面用图来进一步说明“树的裁剪”。为了简便起见，将博弈树进行了简化——每个结点只有三个分支，实际情况中，刚才讲过在盘中应有大约40个分支。
假定棋盘上的局面发展到了结点A （图2），现在轮到你走棋了，你是“最大的一方”——即你希望棋局的分值尽可能的高。用搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。
图中表示该结点要取子结点中的最大值；表示该结点要取子结点中的
最小值。
图2 树的裁剪
首先，考察结点A 的子结点B 。结点B 所属的这一层是轮到你的对手——“最小者”来走棋了，目的是使得棋局的分值尽可能的小。依次考察结点B 的各个子结点，查看它们的分值（因为事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点B 的第一个子结点（从左到右算起）返回-8，第二个子结点返回了-2，第三个子结点返回了2。由于结点B 这层是你的对手来做选择，假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为-2的那个结点。-2最终也就成了从结点B 传递回的值，即倘若你（现在位于结点A ）选择了产生结点B 的走法，使得局面发展到了结点B 。那么下一步，你的对手的选择就会使得棋局发展成为分值为-2的那个结点所表示的局面。
再来分析结点A 的第二个子结点C ，结点C 与结点B 同属一层，它依然是轮到你的对手作选择。依次查看结点C 的各个子结点的分值，其第一个子结点返回了2„„。
采用 “裁剪”方法。不必再继续考察结点C 的剩余子结点了，因为结点C 已经够糟糕的了，不管结点C 的剩余子结点有怎样的分值，它最多只能传回-8（有可能其剩余子结点中还有分值更小的结点，因而结点C 还有可能传回更小的值）。而与前面已经分析过的结点B 所传回-2相比较，作为“最大一方”的你显然更不愿意看到2的局面。所以，你当然不会选择相应的着法使得局面发展
成为结点C 。因为那样的话，下一步你的对手就会带给你一个分值不高于2的局面。
由此，在不影响搜索质量的前提下避免了搜索“无价值的”结点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;
}
3.1.2 着法排序
Alpha-Beta 搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时
“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的Alpha-Beta 搜索已和“最小-最大”搜索别无二致了）。因而，要想保证Alpha-Beta 搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。
可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer 所提出的“历史启发”（History Heuristic ）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta 搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。
对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。
3.1.3 局面评估
前文已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助“历史启发”）， 在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。
首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点：
1、子力总和
子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值10的话，那可能马值6，卒值2等等。所以在评估局面时，首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。
2、棋子位置
棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位
置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。
3、棋子的机动性
棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认为其机动性为零）。
4、棋子的相互关系
这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击着对方的车。
在程序中，估值函数最后返回的是每一方的总分的差值，而各方的总分就是上面所提到的四个因素的打分的总和。
对于子力打分和控制区域打分，只要遍历棋盘，当遇到棋子时简单地去查事先定义好的“子力价值表”和“控制区域价值表”，取出相对应的值进行累加即可。
对于机动性打分，需要求出各个子总共有多少种走法，然后根据各个子所不同的机动性价值每多一种走法就加一次相应的分数。
对棋子间相互关系的打分，要用到以下几个数据：
int m_BaseValue[15];
int m_FlexValue[15]; //存放棋子基本价值 //存放棋子灵活性分值
short m_AttackPos[10][9]; //存放每一位置被威胁的信息
BYTE m_GuardPos[10][9]; //存放每一位置被保护的信息
BYTE m_FlexibilityPos[10][9];//存放每一位置上棋子的灵活性分值
int m_chessValue[10][9]; //存放每一位置上棋子的总价值
其中计算机会进行所有棋子值的判断，AttackPos 和GuardPos 分别记录该棋子受到的威胁和被保护的值。
当遍历一遍棋盘之后，子力打分、控制区域打分和机动性打分都可以完成，而关系表也可以填完。之后，再根据关系表来具体考察棋子的相互关系，进行关系打分。
分析关系时，首先，对王的攻击保护应分离出来单独考虑，因为对王的保护
没有任何意义，一旦王被吃掉整个游戏就结束了。
其次，对一个普通子，当它既受到攻击又受到保护的时候要注意如下几个问题：
1、攻击者子力小于被攻击者子力，攻击方将愿意换子。比如，一个车正遭受一个炮的攻击，那么任何对车的保护都将失去意义——对方肯定乐意用一个炮来换一个车。
2、多攻击/单保护的情况，并且攻击者最小子力小于被攻击者子力与保护者子力之和，则攻击方可能以一子换两子。
3、三攻击/两保护的情况，并且攻击者子力较小的二者之和小于被攻击者子力与保护者子力之和，则攻击方可能以两子换三子。
4、攻击方与保护方数量相同，并且攻击者子力小于被攻击者子力与保护者子力之和再减去保护者中最大子力，则攻击方可能以n 子换n 子。
当然，上述四条只是覆盖了最常见的几种情况，覆盖并不全面。而且，在程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况（之所以说没有“直接地重新考虑”，是因为搜索继续展开结点后仍会考虑这些因素，只是目前不知这样效果是否受影响——考察这两种方法在效果上的差异需要一定数量的试验数据的支持）。所以，如果今后要对引擎进行改进，提高程序的下棋水平的话，还应当在此进行研究。
3.2 悔棋和还原功能的实现
悔棋和还原是棋类软件中较为基本的功能。要实现悔棋和还原功能，首先要明确哪些信息应当被保存以供悔棋和还原所使用。
在程序中保存了如下信息：
棋局表示中所定义的棋盘数组；
各棋子的贴图位置；
这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后当悔棋的时候，需要撤销着法；还原的时候，需要执行着法。然而，在编写自己的程序时一来考虑到程序的可读性和不易出错性，二来考虑到对当今的计算机的配置来说这点开销基本上不会对程序的效率产生什么影响。因此保存了全部棋子的信息。
根据所要保存的数据定义了如下基本结构类型：
typedef struct
{
CHESSMOVE cmChessMove; short nChessID;//被吃掉的棋子
}UNDOMOVE;
在对弈过程中，每一回合都将棋局信息（这里指前面所说的需要保存的信息）保存至走法队列，以供悔棋所用。还原功能是与悔棋功能相对应的，只有当产生了悔棋功能之后，还原功能才会被激活。一个回合的结束意味着前一次操作没有悔棋功能的产生，因此还原队列也应被清空。
在悔棋中主要完成了以下任务：
1、下棋回合数减一；
2、将当前局面信息保存至走法队列，以供还原所用；
3、从走法队列中取出上一回合的棋局信息，恢复到当前局面，然后将其从 队列中剔除掉；
4、将显示着法名称的列表框中的本回合的着法名称保存到一个着法名称队 列，以供还原所用。然后从列表框中删除它。
而在还原中所做的刚好和悔棋相反：
1、下棋回合数加一；
2、将当前局面信息保存至队列，以供悔棋所用；
3、从队列中取出最近一次悔棋前的棋局信息，恢复到当前局面，然后将其从队列中剔除；
4、从走法队列中取出最近一次存入的着法名称（两项，因为每回合会产生两步着法），将其重新显示到列表框中。然后将其从中剔除。
以上便是悔棋和还原功能所完成的具体操作，其代码分别写入悔棋和还原按钮（Button ）的事件处理函数中。
3.3 着法名称显示功能的实现
每当下棋者（用户或是计算机）走一步棋，在棋盘旁边的一个列表框控件（List Box ）中按照中国象棋关于着法描述的规范要求显示出该着法的名称。如：炮八
进四、马二进三此类。为了获得该着法名称，我们编写了一个函数，其功能就是将被移动的棋子类型以及走法的起点坐标、终点坐标这些信息转换成中国象棋所规范的着法名称。实现此功能代码如下：
void CGradientProgressCtrl::OnPaint()
{
CPaintDC dc(this); // device context for painting // TODO: Add your message handler code here if(m_nCurrentPosition=m_nUpper) { CRect rect; GetClientRect(rect); CBrush brush; brush.CreateSolidBrush(::GetSysColor(COLOR_3DFACE)); dc.FillRect(&rect,&brush); VERIFY(brush.DeleteObject()); return; } CRect rectClient; GetClientRect(rectClient); float
maxWidth((float)m_nCurrentPosition/(float)m_nUpper*(float)rectClient.right);
//绘制 DrawGradient(&dc,rectClient,(int)maxWidth); //显示进程条进度文字 if(m_bShowPercent) { CString percent;
percent.Format("%d%%",(int)(100*(float)m_nCurrentPosition/m_nUpper));
dc.SetTextColor(m_clrText);
dc.SetBkMode(TRANSPARENT); dc.DrawText(percent,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
} //显示其他文字 if(m_bIsShowText) { dc.SetTextColor(m_clrText); dc.SetBkMode(TRANSPARENT);
dc.DrawText(m_strShow,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
} // Do not call CProgressCtrl::OnPaint() for painting messages
}
int CGradientProgressCtrl::SetPos(int nPos)
{
//Set the Position of the Progress m_nCurrentPosition=nPos; return (CProgressCtrl::SetPos(nPos));
}
int CGradientProgressCtrl::StepIt()
{
m_nCurrentPosition+=m_nStep; return CProgressCtrl::StepIt();
}
以下介绍如何对列表框控件（List Box）进行操作，以显示或删除着法名称。
首先，在ChessDlg 下定义以下函数：
this->GetMoveStr(nFromX,nFromY,nToX,nToY ,nSourceID);
//用来获得刚下的一步棋的走法；
void CChessDlg::AddChessRecord(int nFromX,int nFromY ,int nToX,int nToY ,int nUserChessColor,int nSourceID)
//将走法添加进下棋记录；
然后，显示在Listbox 中。
当列表框中的项的数目超过列表框的显示范围时，列表框会自动添加垂直滚动条（前提是其VerticalScrollbar 属性要为True ——该属性默认即为True ）。但是显示的内容依然是最早加进来的项。在控件属性里选择Vertical Scroll ，使得列表框可垂直滚动以显示最新的着法名称。
想要从列表框中删除项时，可以使用
m_lstChessRecord.DeleteString(m_lstChessRecord.GetCount()-1);减一之后正好是最后一项的行号。
3.4 胜败判定
胜负判定只要一方将另一方的将或帅吃掉就是胜者。
主要代码如下：
int CSearchEngine::IsGameOver(BYTE position[][9], int nDepth)
{
int i,j; BOOL RedLive=FALSE,BlackLive=FALSE; //检查红方九宫是否有帅 for(i=7;i
//检查黑方九宫是否有将 for(i=0;i
i=(m_nMaxDepth-nDepth+1)%2;//取当前奇偶标志，奇数层为电脑方，偶数层为用户方。
} //红方不在 if(!RedLive) if(i) return 19990+nDepth; //奇数层返回极大值 else return -19990-nDepth;//偶数层返回极小值 //黑方不在 if(!BlackLive) if(i) return -19990-nDepth;//奇数层返回极小值 else return 19990+nDepth; //偶数层返回极大值 return 0;//将帅都在，返回0
4 界面设计和系统实现
4.1 界面设计
关于棋盘和棋子，建了一个基于对话框的MFC 应用程序。主要工作都在对话框类的两个文件CChessDlg.h 和CChessDlg.cpp 下展开。
毕 业 设 计
中国象棋游戏的设计与实现
中国象棋发展至今已有数千年的历史了，它是中华民族智慧的结晶。在我国，中国象棋的普及程度是其它棋类无法比拟的，大至国际、国内比赛，小至社区街道。如今，仅中国就有2亿人会下中国象棋，且中国象棋的发展趋势日益国际化。本文首先研究了中国象棋在计算机中的表示问题，讨论如何产生着法等一系列相关内容，其次研究了博弈树的搜索技术及在此基础上发展起来的相关剪枝算法。系统使用MFC 文档视图体系结构和Visual C++开发工具，实现了一个具有一定棋力的中国象棋人机对弈程序。此博弈程序实现了人机博弈，悔棋，电脑难度设置，着法名称生成等功能。
关键词：中国象棋 人工智能 博弈树 Alpha-Beta 搜索
1 前言 .................................................................... 1
1.1 中国象棋游戏设计背景和研究意义 . ........................................ 1
1.2 国内外象棋软件发展概况 . ................................................ 1
1.3 中国象棋游戏设计研究方法 . .............................................. 1
1.4 本文的主要工作 . ........................................................ 2
2 棋局表示和着法生成 . ...................................................... 2
2.1 棋盘和棋子的表示 . ...................................................... 2
2.2 着法生成 . .............................................................. 4
3 走棋和博弈程序的实现 . .................................................... 5
3.1 博弈程序的实现 . ........................................................ 5
3.1.1 搜索算法 . ............................................................ 5
3.1.2 着法排序 . ............................................................ 9
3.1.3 局面评估 . ........................................................... 10
3.2 悔棋和还原功能的实现 . ................................................. 12
3.3 着法名称显示功能的实现 . ............................................... 13
3.4 胜败判定 . ............................................................. 16
4 界面设计和系统实现 . ..................................................... 17
4.1 界面设计 . ............................................................. 17
4.2 系统实现 . ............................................................. 19
5 总结 . ................................................................... 23
参 考 文 献 ........................................................... 25
ABSTRACT ................................................................. 26 致 谢 ................................................. 错误！未定义书签。 仲恺农业工程学院毕业论文(设计) 成绩评定表 ................. 错误！未定义书签。
1 前言
1.1 中国象棋游戏设计背景和研究意义
中国象棋游戏流传至今已经有数千年的历史了，是一种古老的文化，它集文化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人的思维，培养人的毅力，增强人的竞争意识。自从计算机发明，向各个领域发展，到成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐步渗入我们每个人的娱乐活动中。在计算机已经普及的今天，对于可以用计算机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想，中国象棋历史悠久不仅源远流长，而且基础广泛，作为一项智力运动更成为我们游戏开发的首选对象。
中国象棋是一项智力游戏，以往都是人和人下棋，现在有了计算机我们可以和计算机竞技，人可以与计算机进行对弈。控制计算机的是人类，而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。
1.2 国内外象棋软件发展概况
最早的象棋软件是一副可以外出携带的电子棋盘，后来升级到电视游戏机。开始出现的一些容量很小的象棋软件如：DOS 界面《将族》、WIN31程序的《中国象棋》等等，与其说人类下不过电脑，倒不如说是没有耐性等待电脑程序慢吞吞的搜索算法，有时甚至怀疑软件是否在搜索中死掉了。后来，网络上先后出现了真正的WINDOWS 窗口界面的象棋专业高级软件《棋隐》、《象棋世家》、《象棋参谋》、《象棋奇兵》等。总而言之，各类象棋软件既有自身的优点，也存在共通性的缺陷，如：中局审势不够智能化，走不出弃子取势的人性化佳构，残局时智力明显低于人脑，难以走出残局例胜的必然着法等。放眼未来，象棋软件已经走完了一波持续上涨的行情，有可能出现逐步降温的滑坡趋势。
1.3 中国象棋游戏设计研究方法
本系统主要用 Visual C++ 进行开发，里面的MFC 类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。
该象棋人机博弈系统实现的功能主要包括：
1、选手选择（人或电脑）；
2、人机对弈（人与电脑竞技）；
3、电脑棋力难度选择（电脑下棋能力难度选择，共有4级：按电脑配置选择难度）；
4、悔棋、还原；
5、着法名称显示（象棋走棋规范名称）。
1.4 本文的主要工作
第一部分主要介绍了中国象棋游戏开发的背景及意义、国内外象棋软件的发展概况和象棋游戏的设计研究方法；
第二部分介绍了棋局表示方法和着法生成；
第三部分介绍了走棋和博弈程序的实现；
第四部分介绍了界面设计和系统的实现。
2 棋局表示和着法生成
2.1 棋盘和棋子的表示
对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”。即用一个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
};
给所有棋子定义一个值：
#define R_BEGIN R_KING
#define R_END R_PAWN
#define B_BEGIN B_KING
#define B_END B_PAWN
#define 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 && x
#define IsRed(x) (x>=R_BEGIN && x
对于着法的表示，直接借用棋盘数组的下标来记录着法的起点和目标点。至于是什么棋子在走，以及是否吃子、吃的是什么子，在着法结构中并不记录。这些信息由外部读取棋盘上起点、终点的数据获得。着法结构定义如下，其中还包含了对着法的历史得分的记录项，以供后面要讲到的“历史启发”所用。 typedef struct
{
short nChessID; //表明是什么棋子 CHESSMANPOS From;//起始位置 CHESSMANPOS To; //走到什么位置 int Score; //走法的分数
}CHESSMOVE;
有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：
生成所有合法着法；
执行着法、撤销着法；
针对某一局面进行评估。
因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建立在其基础上。
2.2 着法生成
在着法生成器中，采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。
这里谈到的“合法着法”包括以下几点：
1、各棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九宫内斜行等等（这里需要特别注意的是卒（兵）的行子规则会随其所在位置的不同而发生变化——过河后可以左右平移）。
2、行子不能越出棋盘的界限。当然所有棋子都不能走到棋盘的外面，同时某些特定的棋子还有自己的行棋界限，如将、士不能出九宫，象不能过河。
3、行子的半路上不能有其它子阻拦（除了炮需要隔一个子才能打子之外）以及行子的目的点不能有本方的棋子（当然不能自己吃自己了）。
4、将帅不能碰面（本程序中只在生成计算机的着法时认为将帅碰面是非法的，而对用户所走的导致将帅碰面的着法并不认为其非法，而只是产生败局罢了）。
产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来我往好几步，这样才有利于对局面进行评估以尽可能避免“目光短浅”），所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。
因此可以将着法队列定义为二维数组m_MoveList[8][70]，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。
关于搜索层数，设定为4，实际使用的是1到3（在界面中将其限定为1—3）。搜索层数的增加会显著提高电脑的下棋水平（当然计算机的棋力在很大程度上也依赖于局面评估）。在配置为1.5G ，512M 内存的计算机上最多只能搜索3层，再多将导致搜索时间达到令人无法容忍的地步（这里还需要特别说明的是，搜索的速度也和着法生成的效率以及局面评估的复杂度有关，因为每分析一个结点都要执行这两种操作）。
对于每一层的着法数，也就是当前下棋方针对当前局面的所有可选的合法着法，据有关数据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数组下标为70，应当可以保证十分的安全。
3 走棋和博弈程序的实现
3.1 博弈程序的实现
3.1.1 搜索算法
搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta 搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta 算法的派生、变种算法）。我们在程序中直接借鉴了Alpha-Beta 搜索算法并辅以历史启发。本节先介绍Alpha-Beta 搜索算法：在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是吃掉对方的将或帅，或者避免自己的将或帅被吃。
图1 博弈树
又此，可以用一棵“博弈树”（图1）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断进行下去直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的模型大概如下图所示，可以把其中连接结点的线段看作是着法，不同的着法自然产生不同的局面。
该树包含三种类型的结点：
1、奇数层的中间结点（以及根结点），表示轮到红方走棋；
2、偶数层的中间结点，表示轮到黑方走棋；
3、叶子结点，表示棋局结束。
现在让计算机来下中国象棋，它应当选择一步对它最有利的着法（最终导致它取胜的着法）。获得最佳着法的方法就是“试走”每一种可能的着法，比较它们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的着法。
结合上面所讲的博弈树，若给每个结点都打一个分值来评价其对应的局面（这一任务由后面所讲的局面评估来完成），那么可以通过比较该分值的大小来判断局面的优劣。假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果
假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上会挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上会选择分值最小的结点。这是“最小-最大”（Minimax ）的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O(bn)。其中b 是分枝因子，即针对各种局面的合法着法的数目的平均值，n 是搜索的深度。对于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！
Alpha-Beta 搜索能在不影响搜索精度的前提下大幅减少工作量。
因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向（假定下棋双方对棋局有着同样的认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟。这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。
下面用图来进一步说明“树的裁剪”。为了简便起见，将博弈树进行了简化——每个结点只有三个分支，实际情况中，刚才讲过在盘中应有大约40个分支。
假定棋盘上的局面发展到了结点A （图2），现在轮到你走棋了，你是“最大的一方”——即你希望棋局的分值尽可能的高。用搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。
图中表示该结点要取子结点中的最大值；表示该结点要取子结点中的
最小值。
图2 树的裁剪
首先，考察结点A 的子结点B 。结点B 所属的这一层是轮到你的对手——“最小者”来走棋了，目的是使得棋局的分值尽可能的小。依次考察结点B 的各个子结点，查看它们的分值（因为事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点B 的第一个子结点（从左到右算起）返回-8，第二个子结点返回了-2，第三个子结点返回了2。由于结点B 这层是你的对手来做选择，假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为-2的那个结点。-2最终也就成了从结点B 传递回的值，即倘若你（现在位于结点A ）选择了产生结点B 的走法，使得局面发展到了结点B 。那么下一步，你的对手的选择就会使得棋局发展成为分值为-2的那个结点所表示的局面。
再来分析结点A 的第二个子结点C ，结点C 与结点B 同属一层，它依然是轮到你的对手作选择。依次查看结点C 的各个子结点的分值，其第一个子结点返回了2„„。
采用 “裁剪”方法。不必再继续考察结点C 的剩余子结点了，因为结点C 已经够糟糕的了，不管结点C 的剩余子结点有怎样的分值，它最多只能传回-8（有可能其剩余子结点中还有分值更小的结点，因而结点C 还有可能传回更小的值）。而与前面已经分析过的结点B 所传回-2相比较，作为“最大一方”的你显然更不愿意看到2的局面。所以，你当然不会选择相应的着法使得局面发展
成为结点C 。因为那样的话，下一步你的对手就会带给你一个分值不高于2的局面。
由此，在不影响搜索质量的前提下避免了搜索“无价值的”结点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;
}
3.1.2 着法排序
Alpha-Beta 搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时
“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的Alpha-Beta 搜索已和“最小-最大”搜索别无二致了）。因而，要想保证Alpha-Beta 搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。
可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer 所提出的“历史启发”（History Heuristic ）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta 搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。
对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。
3.1.3 局面评估
前文已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助“历史启发”）， 在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。
首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点：
1、子力总和
子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值10的话，那可能马值6，卒值2等等。所以在评估局面时，首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。
2、棋子位置
棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位
置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。
3、棋子的机动性
棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认为其机动性为零）。
4、棋子的相互关系
这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击着对方的车。
在程序中，估值函数最后返回的是每一方的总分的差值，而各方的总分就是上面所提到的四个因素的打分的总和。
对于子力打分和控制区域打分，只要遍历棋盘，当遇到棋子时简单地去查事先定义好的“子力价值表”和“控制区域价值表”，取出相对应的值进行累加即可。
对于机动性打分，需要求出各个子总共有多少种走法，然后根据各个子所不同的机动性价值每多一种走法就加一次相应的分数。
对棋子间相互关系的打分，要用到以下几个数据：
int m_BaseValue[15];
int m_FlexValue[15]; //存放棋子基本价值 //存放棋子灵活性分值
short m_AttackPos[10][9]; //存放每一位置被威胁的信息
BYTE m_GuardPos[10][9]; //存放每一位置被保护的信息
BYTE m_FlexibilityPos[10][9];//存放每一位置上棋子的灵活性分值
int m_chessValue[10][9]; //存放每一位置上棋子的总价值
其中计算机会进行所有棋子值的判断，AttackPos 和GuardPos 分别记录该棋子受到的威胁和被保护的值。
当遍历一遍棋盘之后，子力打分、控制区域打分和机动性打分都可以完成，而关系表也可以填完。之后，再根据关系表来具体考察棋子的相互关系，进行关系打分。
分析关系时，首先，对王的攻击保护应分离出来单独考虑，因为对王的保护
没有任何意义，一旦王被吃掉整个游戏就结束了。
其次，对一个普通子，当它既受到攻击又受到保护的时候要注意如下几个问题：
1、攻击者子力小于被攻击者子力，攻击方将愿意换子。比如，一个车正遭受一个炮的攻击，那么任何对车的保护都将失去意义——对方肯定乐意用一个炮来换一个车。
2、多攻击/单保护的情况，并且攻击者最小子力小于被攻击者子力与保护者子力之和，则攻击方可能以一子换两子。
3、三攻击/两保护的情况，并且攻击者子力较小的二者之和小于被攻击者子力与保护者子力之和，则攻击方可能以两子换三子。
4、攻击方与保护方数量相同，并且攻击者子力小于被攻击者子力与保护者子力之和再减去保护者中最大子力，则攻击方可能以n 子换n 子。
当然，上述四条只是覆盖了最常见的几种情况，覆盖并不全面。而且，在程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况（之所以说没有“直接地重新考虑”，是因为搜索继续展开结点后仍会考虑这些因素，只是目前不知这样效果是否受影响——考察这两种方法在效果上的差异需要一定数量的试验数据的支持）。所以，如果今后要对引擎进行改进，提高程序的下棋水平的话，还应当在此进行研究。
3.2 悔棋和还原功能的实现
悔棋和还原是棋类软件中较为基本的功能。要实现悔棋和还原功能，首先要明确哪些信息应当被保存以供悔棋和还原所使用。
在程序中保存了如下信息：
棋局表示中所定义的棋盘数组；
各棋子的贴图位置；
这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后当悔棋的时候，需要撤销着法；还原的时候，需要执行着法。然而，在编写自己的程序时一来考虑到程序的可读性和不易出错性，二来考虑到对当今的计算机的配置来说这点开销基本上不会对程序的效率产生什么影响。因此保存了全部棋子的信息。
根据所要保存的数据定义了如下基本结构类型：
typedef struct
{
CHESSMOVE cmChessMove; short nChessID;//被吃掉的棋子
}UNDOMOVE;
在对弈过程中，每一回合都将棋局信息（这里指前面所说的需要保存的信息）保存至走法队列，以供悔棋所用。还原功能是与悔棋功能相对应的，只有当产生了悔棋功能之后，还原功能才会被激活。一个回合的结束意味着前一次操作没有悔棋功能的产生，因此还原队列也应被清空。
在悔棋中主要完成了以下任务：
1、下棋回合数减一；
2、将当前局面信息保存至走法队列，以供还原所用；
3、从走法队列中取出上一回合的棋局信息，恢复到当前局面，然后将其从 队列中剔除掉；
4、将显示着法名称的列表框中的本回合的着法名称保存到一个着法名称队 列，以供还原所用。然后从列表框中删除它。
而在还原中所做的刚好和悔棋相反：
1、下棋回合数加一；
2、将当前局面信息保存至队列，以供悔棋所用；
3、从队列中取出最近一次悔棋前的棋局信息，恢复到当前局面，然后将其从队列中剔除；
4、从走法队列中取出最近一次存入的着法名称（两项，因为每回合会产生两步着法），将其重新显示到列表框中。然后将其从中剔除。
以上便是悔棋和还原功能所完成的具体操作，其代码分别写入悔棋和还原按钮（Button ）的事件处理函数中。
3.3 着法名称显示功能的实现
每当下棋者（用户或是计算机）走一步棋，在棋盘旁边的一个列表框控件（List Box ）中按照中国象棋关于着法描述的规范要求显示出该着法的名称。如：炮八
进四、马二进三此类。为了获得该着法名称，我们编写了一个函数，其功能就是将被移动的棋子类型以及走法的起点坐标、终点坐标这些信息转换成中国象棋所规范的着法名称。实现此功能代码如下：
void CGradientProgressCtrl::OnPaint()
{
CPaintDC dc(this); // device context for painting // TODO: Add your message handler code here if(m_nCurrentPosition=m_nUpper) { CRect rect; GetClientRect(rect); CBrush brush; brush.CreateSolidBrush(::GetSysColor(COLOR_3DFACE)); dc.FillRect(&rect,&brush); VERIFY(brush.DeleteObject()); return; } CRect rectClient; GetClientRect(rectClient); float
maxWidth((float)m_nCurrentPosition/(float)m_nUpper*(float)rectClient.right);
//绘制 DrawGradient(&dc,rectClient,(int)maxWidth); //显示进程条进度文字 if(m_bShowPercent) { CString percent;
percent.Format("%d%%",(int)(100*(float)m_nCurrentPosition/m_nUpper));
dc.SetTextColor(m_clrText);
dc.SetBkMode(TRANSPARENT); dc.DrawText(percent,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
} //显示其他文字 if(m_bIsShowText) { dc.SetTextColor(m_clrText); dc.SetBkMode(TRANSPARENT);
dc.DrawText(m_strShow,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
} // Do not call CProgressCtrl::OnPaint() for painting messages
}
int CGradientProgressCtrl::SetPos(int nPos)
{
//Set the Position of the Progress m_nCurrentPosition=nPos; return (CProgressCtrl::SetPos(nPos));
}
int CGradientProgressCtrl::StepIt()
{
m_nCurrentPosition+=m_nStep; return CProgressCtrl::StepIt();
}
以下介绍如何对列表框控件（List Box）进行操作，以显示或删除着法名称。
首先，在ChessDlg 下定义以下函数：
this->GetMoveStr(nFromX,nFromY,nToX,nToY ,nSourceID);
//用来获得刚下的一步棋的走法；
void CChessDlg::AddChessRecord(int nFromX,int nFromY ,int nToX,int nToY ,int nUserChessColor,int nSourceID)
//将走法添加进下棋记录；
然后，显示在Listbox 中。
当列表框中的项的数目超过列表框的显示范围时，列表框会自动添加垂直滚动条（前提是其VerticalScrollbar 属性要为True ——该属性默认即为True ）。但是显示的内容依然是最早加进来的项。在控件属性里选择Vertical Scroll ，使得列表框可垂直滚动以显示最新的着法名称。
想要从列表框中删除项时，可以使用
m_lstChessRecord.DeleteString(m_lstChessRecord.GetCount()-1);减一之后正好是最后一项的行号。
3.4 胜败判定
胜负判定只要一方将另一方的将或帅吃掉就是胜者。
主要代码如下：
int CSearchEngine::IsGameOver(BYTE position[][9], int nDepth)
{
int i,j; BOOL RedLive=FALSE,BlackLive=FALSE; //检查红方九宫是否有帅 for(i=7;i
//检查黑方九宫是否有将 for(i=0;i
i=(m_nMaxDepth-nDepth+1)%2;//取当前奇偶标志，奇数层为电脑方，偶数层为用户方。
} //红方不在 if(!RedLive) if(i) return 19990+nDepth; //奇数层返回极大值 else return -19990-nDepth;//偶数层返回极小值 //黑方不在 if(!BlackLive) if(i) return -19990-nDepth;//奇数层返回极小值 else return 19990+nDepth; //偶数层返回极大值 return 0;//将帅都在，返回0
4 界面设计和系统实现
4.1 界面设计
关于棋盘和棋子，建了一个基于对话框的MFC 应用程序。主要工作都在对话框类的两个文件CChessDlg.h 和CChessDlg.cpp 下展开。