布奇乐乐园官网-
毕业论文声明
本人郑重声明：
1
．此毕业论文是本人在 指导教师指导下独立进行研究取得的成果。除
了特别加以标注地方外，
本文不包含他人或其它机 构已经发表或撰写过的研
究成果。对本文研究做出重要贡献的个人与集体均已在文中作了明确标明。本人完全意识到本声明的法律结果由本人承担。
2
．本人完全了解学校、学院有 关保留、使用学位论文的规定，同意学
校与学院保留并向国家有关部门或机构送交此论文的复印件和电子 版，
允许
此文被查阅和借阅。
本人授权大学学院可以将此文的全部或部分内容编入有< br>关数据库进行检索，
可以采用影印、
缩印或扫描等复制手段保存和汇编本文。
3
．若在大学学院毕业论文审查小组复审中，发现本文有抄袭，一切后
果均由本人承担 ，与毕业论文指导老师无关。
4.
本人所呈交的毕业论文，
是在指导老师的 指导下独立进行研究所取得
的成果。论文中凡引用他人已经发布或未发表的成果、数据、观点等，均已< br>明确注明出处。论文中已经注明引用的内容外，不包含任何其他个人或集体
已经发表或撰写过的研 究成果。
对本文的研究成果做出重要贡献的个人和集
体，均已在论文中已明确的方式标明。
学位论文作者（签名）
：
年
月
中国象棋游戏的设计与实现
关于毕业论文使用授权的声明
本人在 指导老师的指导下所完成的论文及相关的资料（包括图纸、实验
记录、原始数据、实物照片、图片、录音 带、设计手稿等）
，知识产权归属
华北电力大学。本人完全了解大学有关保存，使用毕业论文的 规定。同意学
校保存或向国家有关部门或机构送交论文的纸质版或电子版，
允许论文被查
阅或借阅。
本人授权大学可以将本毕业论文的全部或部分内容编入有关数据
库进行检索，可以 采用任何复制手段保存或编汇本毕业论文。如果发表相关
成果，一定征得指导教师同意，且第一署名单位 为大学。本人毕业后使用毕
业论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为大学。本人完全了解大学关于收集、保存、使用学位论文的规定，同意如下各
项内容：
按照学校要求提交学位论文的印刷本和电子版本；
学校有权保存学位论
文的印刷本和电子版 ，并采用影印、缩印、扫描、数字化或其它手段保存或
汇编本学位论文；
学校有权提供目录检索 以及提供本学位论文全文或者部分
的阅览服务；
学校有权按有关规定向国家有关部门或者机构送 交论文的复印
件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全
部或部 分内容编入学校有关数据库和收录到《中国学位论文全文数据库》进
行信息服务。在不以赢利为目的的前 提下，学校可以适当复制论文的部分或
全部内容用于学术活动。
论文作者签名：
日期：
指导教师签名：
日期：
毕
业
设
计
中国象棋游戏的设计与实现
中国象棋游戏的设计与实现
中国象棋游戏的设计与实现
摘
要
中国象棋发展 至今已有数千年的历史了，它是中华民族智慧的结晶。在我国，中国
象棋的普及程度是其它棋类无法比拟 的，大至国际、国内比赛，小至社区街道。如今，
仅中国就有
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
致
谢
....................... ...........................
错误
!
未定义书签。
仲恺农业工程学院毕业论文
(
设计
)
成绩评定表
..................
错误
!
未定义书签。
I
1
前言
1.1
中国象棋游戏设计背景和研究意义
中国象棋游戏流传至今已经有数千年的历史了，< br>是一种古老的文化，
它集文
化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人 的思维，培养人的
毅力，增强人的竞争意识。自从计算机发明，向各个领域发展，到成为我们现在
每天工作和生活必不可少的一部分的这个过程中，
电子游戏也逐步渗入我们每个
人的娱乐活动 中。
在计算机已经普及的今天，
对于可以用计算机进行程序编辑的
人来说，
开 发属于自己的游戏，
已经不再是梦想，
中国象棋历史悠久不仅源远流
长，而且基础广泛 ，作为一项智力运动更成为我们游戏开发的首选对象。
中国象棋是一项智力游戏，
以 往都是人和人下棋，
现在有了计算机我们可以
和计算机竞技，人可以与计算机进行对弈。
控制计算机的是人类，
而人工智能是
综合性很强的一门边缘学科，
它的中心任务是研 究如何使计算机去做那些过去只
能靠人的智力才能做的工作。
因此，
对游戏开发过程中 的人工智能技术的研究自
然也就成了业界的一个热门研究方向。
1.2
国内外象棋软件发展概况
最早的象棋软件是一 副可以外出携带的电子棋盘，后来升级到电视游戏机。
开始出现的一些容量很小的象棋软件如：
DOS
界面《将族》
、
WIN31
程序的《中
国象棋》
等等 ，与其说人类下不过电脑，倒不如说是没有耐性等待电脑程序慢吞
吞的搜索算法，
有时甚至怀疑 软件是否在搜索中死掉了。后来，
网络上先后出现
了真正的
WINDOWS
窗 口界面的象棋专业高级软件《棋隐》
、
《象棋世家》
、
《象
棋参谋》
、
《象棋奇兵》等。总而言之，各类象棋软件既有自身的优点，也存在共
通性的缺陷， 如：中局审势不够智能化，走不出弃子取势的人性化佳构，残局时
智力明显低于人脑，难以走出残局例胜 的必然着法等。放眼未来，
象棋软件已经
走完了一波持续上涨的行情，有可能出现逐步降温的滑 坡趋势。
1.3
中国象棋游戏设计研究方法
本系统主要用
Visual C++
进行开发，里面的
MFC< br>类库，使游戏开发更加方
便，
并利用人工智能相关搜索算法实现人工智能的着法生成，< br>从而完善整个游戏
的功能。
该象棋人机博弈系统实现的功能主要包括：
1
、选手选择（人或电脑）
；
2
、人机对弈（人与电脑竞技）
；
3
、电脑棋力难度选择 （电脑下棋能力难度选择，共有
4
级：按电脑配置选
择难度）
；
4
、悔棋、还原；
5
、着法名称显示（象棋走棋规范名称）
。
1.4
本文的主要工作
第一部分主要介绍了中国象棋游戏开发的背景及意义、< br>国内外象棋软件的发
展概况和象棋游戏的设计研究方法；
第二部分介绍了棋局表示方法和着法生成；
第三部分介绍了走棋和博弈程序的实现；
第四部分介绍了界面设计和系统的实现。
2
棋局表示和着法生成
2.1
棋盘和棋子的表示
对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”< br>。即用一个
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<=B_END)//
判断某个棋子是不是黑
色
#define
IsRed(x)
(x>=R_BEGIN
&&
x<=R_END)//
判断某个棋子是不是红
色
对于着法的表示 ，
直接借用棋盘数组的下标来记录着法的起点和目标点。
至
于是什么棋子在走，以及是 否吃子、吃的是什么子，在着法结构中并不记录。这
些信息由外部读取棋盘上起点、终点的数据获得。着 法结构定义如下，
其中还包
含了对着法的历史得分的记录项，以供后面要讲到的“历史启发”所 用。
typedef struct
{
short nChessID;
//
表明是什么棋子
CHESSMANPOS From;//
起始位置
CHESSMANPOS To;
//
走到什么位置
int Score;
//
走法的分数
}CHESSMOVE;
有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：
生成所有合法着法；
执行着法、撤销着法；
针对某一局面进行评估。
因而，棋局表 示好比是整个程序（计算机下棋引擎部分）的地基，之后所有
的操作都将建立在其基础上。
2.2
着法生成
在着法生成器中，
采用的基 本思想就是遍历整个棋盘
（一个接一个地查看棋
盘上的每个位置点）
，
当发现 有当前下棋方的棋子时先判断它是何种类型的棋子，
然后根据其棋子类型而相应地找出其所有合法着法并 存入着法队列。
这里谈到的“合法着法”包括以下几点：
1
、各 棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九
宫内斜行等等（这里需要特别注意的 是卒
（兵）
的行子规则会随其所在位置的不
同而发生变化
——
过河后 可以左右平移）。
2
、行子不能越出棋盘的界限。当然所有棋子都不能走到棋盘的外 面，同时
某些特定的棋子还有自己的行棋界限，如将、士不能出九宫，象不能过河。
3
、行子的半路上不能有其它子阻拦（除了炮需要隔一个子才能打子之外）
以及行子的目的点不 能有本方的棋子（当然不能自己吃自己了）。
4
、将帅不能碰面（本程序中只在生成 计算机的着法时认为将帅碰面是非法
的，而对用户所走的导致将帅碰面的着法并不认为其非法，而只是产 生败局罢
了）。
产生了着法后要将其存入着法队列以供搜索之用，
由于搜索 会搜索多层
（即
考虑双方你来我往好几步，
这样才有利于对局面进行评估以尽可能避免
“目光短
浅”
）
，
所以在把着法存入着法队列的时候还要同时存储该 着法所属的搜索层数。
因此可以将着法队列定义为二维数组
m_Move List[8][70]
，其中第一个数组下标
为层数，第二个数组下标为每一层的全部着法数 。
关于搜索层数，
设定为
4
，
实际使用的是
1< br>到
3
（
在界面中将其限定为
1
—
3
）
。
搜索层数的增加会显著提高电脑的下棋水平
（当然计算机的棋力在很大程度上也
依 赖于局面评估）。在配置为
1.5G
，
512M
内存的计算机上最多只能搜索
3
层，
再多将导致搜索时间达到令人无法容忍的地步
（这里还需要特别说明的 是，
搜索
的速度也和着法生成的效率以及局面评估的复杂度有关，
因为每分析一个结点 都
要执行这两种操作）。
对于每一层的着法数，
也就是当前下棋方针对当前 局面的所有可选的合法着
法，
据有关数据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数
组下标为
70
，应当可以保证十分的安全。
3
走棋和博弈程序的实现
3.1
博弈程序的实现
3.1.1
搜索算法
搜索算法对于整个下棋引擎来说都是至关重要的。
它如同程序的心脏，
驱动
着整个 程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，
它影
响着计算机的下棋水平 。因为，
计算机必须在有限的时间内完成思考，
搜索速度
快意味着在相同的时间内程序 可以“看”得更远，
“想”的更多）
。关于棋类对弈
程序中的搜索算法，
已有 成熟的
Alpha- Beta
搜索算法以及其它一些辅助增强算法
（还有众多基于
Alpha- Beta
算法的派生、变种算法）
。我们在程序中直接借鉴了
Alpha- Beta
搜索算法并辅以历史启发。
本节先介绍
Alpha-Beta
搜索算 法：
在中国
象棋里，
双方棋手获得相同的棋盘信息。
他们轮流走棋，
目的就是吃掉对方的将
或帅，或者避免自己的将或帅被吃。
……
……
表示红方走棋
……
图
1
博弈树
表示黑方走棋
< br>又此，可以用一棵“博弈树”
（图
1
）来表示下棋的过程
——
树中每一个结
点代表棋盘上的一个局面，对每一个局面
（结点）
根据不同的走法又产生 不同的
局面（生出新的结点）
，如此不断进行下去直到再无可选择的走法，即到达叶子
结点（棋局结束）
。中国象棋的博弈树的模型大概如下图所示，可以把其中连接
结点的线段看作 是着法，不同的着法自然产生不同的局面。
该树包含三种类型的结点：
1
、奇数层的中间结点（以及根结点）
，表示轮到红方走棋；
2
、偶数层的中间结点，表示轮到黑方走棋；
3
、叶子结点，表示棋局结束。
现在让计算机来下中国象棋，
它应 当选择一步对它最有利的着法
（最终导致
它取胜的着法）
。获得最佳着法的方法就是“ 试走”每一种可能的着法，比较它
们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的着 法。
结合上面所讲的博弈树，若给每个结点都打一个分值来评价其对应的局面
（这一 任务由后面所讲的局面评估来完成）
，
那么可以通过比较该分值的大小来
判断局面的优 劣。假定甲乙两方下棋，
甲胜的局面是一个极大值
（一个很大的正
数），那么乙胜的局 面就是一个极小值（极大值的负值），和棋的局面则是零值
（或是接近零的值）。如此，当轮到甲走棋时 他会尽可能地让局面上的分值大，
相反轮到乙走棋时他会选尽可能地让局面上的分值小。
反映到 博弈树上，
即如果
假设奇数层表示轮到甲方走棋，
偶数层表示轮 到乙方走棋。
那么由于甲方希望棋
盘上的分值尽可能大，
则在偶数层上会挑选分值最大 的结点
——
偶数层的结点是
甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要 求。同样道理，
由于
乙方希望棋盘上的分值尽可能小，
那么在奇数层上会选择分值最小 的结点。
这是
“最小
-
最大”
（
Minimax
） 的基本思想。这样搜索函数在估值函数的协助下可以
通过在奇数层选择分值最大（最小）的结点，在偶数 层选择分值最小（最大）的
结点的方式来搜索以当前局面为根结点、
限定搜索层数以内的整棵树 来获得一个
最佳的着法。
然而不幸的是，
博弈树相当庞大
（它会成指数增长）
，
因而搜索
（限
定层数以内的）整棵树是一件相当费时的工作
——< br>其时间复杂度为
O(bn)
。其中
b
是分枝因子，即针对各种局面的合 法着法的数目的平均值，
n
是搜索的深度。
对于中国象棋而言，在中盘时平均着法数目 大约是
40
种左右，那么搜索
4
层需
要检查
250
万条路线，搜索
5
层需要检查
1
亿条路线，搜索
6
层需要检 查
40
亿
条路线！
Alpha- Beta
搜索能在不影响搜索精度的前提下大幅减少工作量。
因为，
如果考 虑到下棋是一个你来我往的交替进行并且相互
“较劲”
的过程。
由于每一方都会尽可能 将局面导向对自己有利而对对方不利的方向
（假定下棋双
方对棋局有着同样的认知，
即 你认为对你很糟糕的局面，
在你的对手看来则是对
他很有利的局面）
，
那么某 些局面由于能够产生出很糟糕的局面因而根本没有再
继续考虑的价值。
所以当你看到某个局面有 可能产生很糟糕的局面时
（确切地说
这里的“很糟糕”是与之前分析的情况相比较而言的），你 应当立刻停止对其剩
余子结点的分析
——
不要对它再抱任何幻想了，
如果你选 择了它，
那么你必将得
到那个很糟糕的局面，
甚至可能更糟。
这样一来便可以 在很大程度上减少搜索的
工作量，提高搜索效率，这称为“树的裁剪”。
下面用图来 进一步说明“树的裁剪”。为了简便起见，将博弈树进行了简化
——
每个结点只有三个分支，< br>实际情况中，
刚才讲过在盘中应有大约
40
个分支。
假定棋 盘上的局面发展到了结点
A
（图
2
），现在轮到你走棋了，你是“最
大的一方”
——
即你希望棋局的分值尽可能的高。用搜索两层来看一看“树的裁
剪”对 提高搜索效率的帮助。
图中
表示该结点要取子结点中的最大值；
表示该结点要取子结点中的
最小值。
A
B
C
D
-8
-2
10
2
-8
?
…
…
…
图
2
树的裁剪
首先，
考察结点
A
的子结点
B
。
结点< br>B
所属的这一层是轮到你的对手
——“
最
小者
”
来走 棋了，目的是使得棋局的分值尽可能的小。依次考察结点
B
的各个子
结点，查看它们的 分值
（因为事先约定好了搜索两层，
现在已达到搜索深度的要
求了，所以就停下来调用 局面评估函数来给它打分）。结点
B
的第一个子结点
（从左到右算起）返回
- 8
，第二个子结点返回了
-2
，第三个子结点返回了
2
。由
于结点
B
这层是你的对手来做选择，假设他一定会做出明智的选择（你不能寄
希望于你 的对手会走出一步“昏招”），那么他会选择返回值为
-2
的那个结点。
-2
最终也就成了从结点
B
传递回的值，即倘若你（现在位于结点
A
）选择了产< br>生结点
B
的走法，
使得局面发展到了结点
B
。
那么下 一步，
你的对手的选择就会
使得棋局发展成为分值为
-2
的那个结点所表示的 局面。
再来分析结点
A
的第二个子结点
C
，结点
C
与结点
B
同属一层，它依然是
轮到你的对手作选择。依次查看结点
C
的各个子结点的分值，其第一个子结点
返回了
2
……。
采用
“裁剪”方法。不必再继续考察结点
C
的剩余子结点了，因为 结点
C
已经够糟糕的了，不管结点
C
的剩余子结点有怎样的分值，它最多只能 传回
-8
（有可能其剩余子结点中还有分值更小的结点，因而结点
C
还有可能 传回更小
的值）。而与前面已经分析过的结点
B
所传回
-2
相比较， 作为“最大一方”的
你显然更不愿意看到
2
的局面。
所以，
你当然不 会选择相应的着法使得局面发展
成为结点
C
。
因为那样 的话，
下一步你的对手就会带给你一个分值不高于
2
的局
面。
由此，在不影响搜索质量的前提下避免了搜索“无价值的”结点
C
的剩余
子结点的 大量工作，
从而节省了宝贵时间，
为在同样机器配置下搜索更多的层数
提供了可能。< br>
“最小
-
最大”的思想再加上“对树的裁剪”，这就是
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-Bet a
搜索已和
“最小
-
最大”
搜索别无二致了）
。
因 而，
要想保证
Alpha-Beta
搜索算法的效率就需要调整树的结构，
即 调整待搜索的结点的顺序，
使得
“裁剪”
可以尽可能早地发生。
可 以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。
因为，
通常
当一个局面经 过搜索被认为较好时，
其子结点中往往有一些与它相似的局面
（如
个别无关紧要的棋子 位置有所不同）也是较好的。由
fer
所提出的“历史
启发”
（
Hi story
Heuristic
）就是建立在这样一种观点之上的。在搜索的过程中，
每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”
，一个
多次被搜索并 认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，
按照“历史得分”的高低对它们进行排 序，保证较好的走法（
“历史得分”高的
走法）排在前面，这样
Alpha- Beta
搜索就可以尽可能早地进行“裁剪”
，从而保
证了搜索的效率。
< br>对于着法的排序可以使用各种排序算法，
在程序中采用了归并排序。
归并排
序的 空间复杂度为
O(n)
，时间复杂度为
O(nlog2n)
，具有较高的效率 。
3.1.3
局面评估
前文已经讲过了棋局表示、< br>着法生成、
搜索算法
（包括搜索辅助
“历史启发”
）
，
在象棋程序中如果说搜索算法是心脏，
那么局面评估就是大脑。
搜索算法负责驱< br>动整个程序，
而局面评估则负责对搜索的内容进行判断和评价。
因而搜索与局面
评估是整个下棋引擎的核心。
首先，
先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑
的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点 ：
1
、子力总和
子力是指某一棋子本身所具有的价值。通俗地讲 就是一个棋子它值个什么
价。例如，车值
10
的话，那可能马值
6
， 卒值
2
等等。所以在评估局面时，首
先要考虑双方的子力总和的对比。
比如红 方拥有士象全加车马炮，
而黑方只有残
士象加双马，则红方明显占优。
2
、棋子位置
棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位
置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心
马、将离开底线等则属 较差的棋子位置状态。
3
、棋子的机动性
棋子的机动性指棋子的 灵活度（可移动性）
。例如，起始位置的车机动性较
差，所以下棋讲究早出车。
同样四 面被憋马腿的死马机动性也较差
（对于一步也
不能走的棋子，可以认为其机动性为零）
。
4
、棋子的相互关系
这一点的分析较为复杂，
因为一 个棋子与其它子之间往往存在多重关系。
如：
一个马可能在对方的炮的攻击之下同时它又攻击着 对方的车。
在程序中，
估值函数最后返回的是每一方的总分的差值，
而各方 的总分就是
上面所提到的四个因素的打分的总和。
对于子力打分和控制区域打分，< br>只要遍历棋盘，
当遇到棋子时简单地去查事
先定义好的“子力价值表”和“控制区域价值 表”
，取出相对应的值进行累加即
可。
对于机动性打分，
需要求出 各个子总共有多少种走法，
然后根据各个子所不
同的机动性价值每多一种走法就加一次相应的分 数。
对棋子间相互关系的打分，要用到以下几个数据：
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];
//
存放每一位置上棋子的总价值
其中计算机会进行所有棋子值的判断，< br>AttackPos
和
GuardPos
分别记录该棋
子受到的威胁和 被保护的值。
当遍历一遍棋盘之后，子力打分、控制区域打分和机动性打分都可以完成，而关系表也可以填完。之后，
再根据关系表来具体考察棋子的相互关系，
进行关
系 打分。
分析关系时，
首先，对王的攻击保护应分离出来单独考虑，因为对王的保护
没有任何意义，一旦王被吃掉整个游戏就结束了。
其次，
对一个普通子，< br>当它既受到攻击又受到保护的时候要注意如下几个问
题：
1
、攻击者 子力小于被攻击者子力，攻击方将愿意换子。比如，一个车正遭
受一个炮的攻击，
那么任何对车 的保护都将失去意义
——
对方肯定乐意用一个炮
来换一个车。
2< br>、多攻击
/
单保护的情况，并且攻击者最小子力小于被攻击者子力与保护者
子力 之和，则攻击方可能以一子换两子。
3
、三攻击
/
两保护的情况， 并且攻击者子力较小的二者之和小于被攻击者子
力与保护者子力之和，则攻击方可能以两子换三子。
4
、攻击方与保护方数量相同，并且攻击者子力小于被攻击者子力与保护者
子力 之和再减去保护者中最大子力，则攻击方可能以
n
子换
n
子。
当然，上述四条只是覆盖了最常见的几种情况，覆盖并不全面。而且，在程
序中并没有直接地重新考 虑双方兑子之后的控制区域及机动性变化情况
（之所以
说没有“直接地重新考虑”
，是 因为搜索继续展开结点后仍会考虑这些因素，只
是目前不知这样效果是否受影响
——
考 察这两种方法在效果上的差异需要一定
数量的试验数据的支持）
。所以，如果今后要对引擎进行 改进，提高程序的下棋
水平的话，还应当在此进行研究。
3.2
悔棋和还原功能的实现
悔棋和还原是棋类软件中较为基本的功能。
要实现悔 棋和还原功能，
首先要
明确哪些信息应当被保存以供悔棋和还原所使用。
在程序中保存了如下信息：
棋局表示中所定义的棋盘数组；
各棋子的贴图位置；
这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保 存所有棋
子的信息，
而只是保存之前一步的走棋信息。
此后当悔棋的时候，
需 要撤销着法；
还原的时候，需要执行着法。
然而，
在编写自己的程序时一来考虑到程序 的可读
性和不易出错性，
二来考虑到对当今的计算机的配置来说这点开销基本上不会对
程序的效率产生什么影响。因此保存了全部棋子的信息。
根据所要保存的数据定义了如下基本结构类型：
typedef struct
{
CHESSMOVE cmChessMove;
short nChessID;//
被吃掉的棋子
}UNDOMOVE;
在对弈过程 中，
每一回合都将棋局信息
（这里指前面所说的需要保存的信息）
保存至走法队列，< br>以供悔棋所用。还原功能是与悔棋功能相对应的，只有当产生
了悔棋功能之后，
还原功能 才会被激活。
一个回合的结束意味着前一次操作没有
悔棋功能的产生，因此还原队列也应被清空 。
在悔棋中主要完成了以下任务：
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_nLower || m_nCurrentPosition>=m_nUpper)
{
CRect rect;
GetClientRect(rect);
CBrush brush;
SolidBrush(::GetSysColor(COLOR_3DFACE));
ct(&rect,&brush);
VERIFY(Object());
return;
}
CRect rectClient;
GetClientRect(rectClient);
float
maxWidth((float)m_nCurrent Position/(float)m_nUpper*(float));
//
绘制
DrawGradient(&dc,rectClient,(int)maxWidth);
//
显示进程条进度文字
if(m_bShowPercent)
{
CString percent;
(
tColor(m_clrText);
ode(TRANSPARENT);
xt(p ercent,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGLEL I
NE);
}
//
显示其他文字
if(m_bIsShowText)
{
tColor(m_clrText);
ode(TRANSPARENT);
xt(m _strShow,&rectClient,DT_VCENTER|DT_CENTER|DT_SINGL ELI
NE);
}
// 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
,n ToX,nToY
,nSourceID);
//
用来获得刚下的一步棋的走法；
void
CChessDlg::AddChessRecord(int
nFromX,int
nFromY
,int
nToX,int
nToY
,int
nUserChessColor,int nSourceID)
//
将走法添加进下棋记录；
然后，显示在
Listbox
中。
当列表框中的项的数目超过列表 框的显示范围时，
列表框会自动添加垂直滚
动条
（前提是其
Vertical Scrollbar
属性要为
True
——
该属性默认即为
True
）
。
但是
显示的内容依然是最早加进来的项。在控件属性里选择
Ve rtical
Scroll
，使得列
表框可垂直滚动以显示最新的着法名称。
想要从列表框中删除项时，可以使用
m _String(m_nt()-1);
减
一
之
后
正
好是最 后一项的行号。
3.4
胜败判定
胜负判定只要一方将另一方的将或帅吃掉就是胜者。
主要代码如下：
int CSearchEngine::IsGameOver(BYTE position[][9], int nDepth)
{
int i,j;
BOOL RedLive=FALSE,BlackLive=FALSE;
//
检查红方九宫是否有帅
for(i=7;i<10;i++)
for(j=3;j<6;j++)
{
if(position[i][j]==B_KING)
BlackLive=TRUE;
if(position[i][j]==R_KING)
RedLive=TRUE;
}
//
检查黑方九宫是否有将
for(i=0;i<3;i++)
for(j=3;j<6;j++)
{
if(position[i][j]==B_KING)
BlackLive=TRUE;
if(position[i][j]==R_KING)
RedLive=TRUE;
}
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
和
下展开。
代码主要分布于以下三大部分：
1
、初始化部分
BOOL CCChessUIDlg::OnInitDialog()
{
}
OnInitDialog()
负责的是对话框的初始化。
可以把有关中国象棋的棋局 初始化
情况也放在了这里面。初始化的内容包括：
对引擎部分所用到的变量的初始化 。包括对棋盘上的棋子位置进行初始化
（棋盘数组的初始化）
，对搜索深度、当前走棋方标志、 棋局是否结束标志等的
初始化；
对棋盘、
棋子的贴图位置
（即棋盘 、
棋子在程序中实际显示位置）
的初始化；
对程序辅助部分所用到的一些变 量的初始化。
包括对悔棋、
还原队列的清空，
棋盘、棋子样式的默认形式，
下 棋模式的默认选择，
以及着法名称列表的初始化
等。
2
、绘图部分
void CCChessUIDlg::OnPaint()
{
……
}
OnPaint()
函数负责的是程序界面的绘图。因此，在这里将要完成棋盘、 棋子
的显示走棋起始位置和目标位置的提示框的显示。
由于棋盘、棋子等都是以位图 的形式给出的。所以在
OnPaint()
函数里做的
工作主要都是在贴位图。
需要注意的是由于位图文件不能像
GIF
文件那样有透明的背景并且棋子是
圆形的而位图文件只能是矩形的，
所以如果直接贴图的话会在棋盘上留下一块白
色的边框——
棋子的背景。因此，要想让棋子文件的背景“隐藏”需要通过一些
“与”和“异或”操 作来屏蔽掉棋子的背景。
3
、走棋部分（用户动作响应部分）
为
WM_LBUTTONDOWN
消息添加消息响应事件，可得到如下函数：
void CCChessUIDlg::OnLButtonDown(UINT nFlags, CPoint point)
{
……
}
当用户在窗口客户区按下鼠标左键时，
程序就会调用
OnLButton Down(UINT
nFlags,
CPoint
point)
函数来进行响应。其中第二个参数
CPoint
point< br>是在本程序
中所要用到的，它给出了当鼠标左键被按下时，
鼠标指针的位置坐标。
可以通过
这一信息来得知用户的走法。
在
OnLButtonDown
函数里处理如下两种操作：
1、如果用户点击鼠标的位置落在己方的棋子上，表示用户选中了该棋子，
下一步将移动该子进行走棋
（也可能用户下一步将会选择己方另外的棋子，
总之
这一操作会记录下用户所选的将要 走的棋子）
。
2
、如果之前用户已经选过了棋子，那么这一次的点击（如果 不是另选本方
的其它棋子的话）表达了用户的一次走棋过程。在收到用户传达的走棋信息后，
可 先判断该着法是否合法（是否符合中国象棋的游戏规则）
，如果合法，则执行
之。
紧接 着调用引擎的搜索函数计算出计算机对用户着法的应着，
然后执行该应
着。
如此，在
OnLButtonDown
函数里，实现了人与机器的对弈（当然每走一步
棋，也还需要绘图函数来显示棋盘局面的更新）
。
以上三部分并非界面程序的全部，
而仅仅是与程序密切相关的部分。
此外还
有其它部分对程序同样必不可少，但这些部分 主要由
MFC
自动生成，无需人为
改动，故在此不多做介绍。
4.2
系统实现
现在已具备了实现一款中国象棋对弈 程序引擎部分的所有要素，将上述模块
分别写作
.h
头文件。如下：
ChessDlg.h
——
象棋相关定义。包括棋盘局面和着法的表示。
BaseClasses.h
——
着法生成器。就当前局面生成某一方所有合法着法。
MoveList.h
——
搜索部分。使用搜索求出最佳着法。
Thinkdef.h
——
历史启发。
Alpha- Beta
搜索之补充，以提高搜索效率。
Thinker.h
——
着法排序。对着法按其历史得分进行降序排序，以提高搜索效率。
ThinkOptionDlg.h
——
局面评估。为某一特定局面进行评分。
当实现了引擎部分的各要素时， 可先建立一个
Win32
控制台项目，之后只
要再添加一个
.cpp
文件负责接受用户的输入、调用搜索函数、显示搜索结果，便
可简单的测试引擎了
（采用输入着 法的起点坐标和终点坐标的方式来传送用户走
棋的信息。同样，程序显示计算机走棋的起点坐标和终点坐 标来做出回应）
。
此后，等到界面部分初步完成，
引擎的上述各模块无需作 任何改动，
仍以
.h
头文
件的形式加入界面工程，
只要由界面中的某 个
.cpp
文件调用搜索函数即可。
这种
连接方式实现起来非常简单。
首先，执行该软件，系统并不需要很高的配置，
CPU
在
1.5G
以上，内存在
512M
以上就可以很流畅地执行。下面简单介绍一下象棋相关规则：
对局时，由执红棋的一方先走，双方轮流各走一着，直至分出胜、负、和，
对局即终了。轮到走 棋的一方，
将某个棋子从一个交叉点走到另一个交叉点，
或
者吃掉对方的棋子而占领其 交叉点，
都算走一着。
双方各走一着，
称为一个回合。
如果有一方的主帅被对 方吃了，就算那一方输。
各种棋子的走法：
帅（将）
：帅和将是 棋中的首脑，是双方竭力争夺的目标。它只能在“九宫”
之内活动，可上可下，可左可右，每次走动只能 按竖线或横线走动一格。帅与将
不能在同一直线上直接对面，否则走方判负。
仕（士 ）
：仕（士）是帅（将）的贴身保镖，它也只能在九宫内走动。它的
行棋路径只能是九宫内的斜 线。
相（象）
：相（象）的主要作用是防守，保护自己的帅（将）
。它的走 法是每
次循对角线走两格，俗称“象走田”
。相（象）的活动范围限于“河界”以内的
本方阵地，不能过河，且如果它走的“田”字中央有一个棋子，就不能走，俗称
“塞象眼”
。
车：车在象棋中 威力最大，无论横线、竖线均可行走，只要无子阻拦，步
数不受限制。因此，一车可以控制十七个点，故 有“一车十子寒”之称。
炮：炮在不吃子的时候，走动与车完全相同。
马 ：
马走动的方法是一直一斜，即先横着或直着走一格，然后再斜着走一个
对角线，
俗称
“马走日”
。
马一次可走的选择点可以达到四周的八个点，
故有
“八
面威风”之说。如果在要去的方向有别的棋子挡住，马就无法走过去，俗称“蹩
马腿”
。
兵（卒）
：兵（卒）在未过河前，只能向前一步步走，过河以后，除不能后
退外，允许左右移动，但也只能一次一步。
在懂的以上规则之后并可进行游戏，
执 行该软件后，并可进入游戏界面。棋
盘界面（图
3
）所示：
图
3
棋盘界面
从界面上方的菜单栏中可以进行相关设置
参数设置界面（图
4
）如下：
图
4
参数设置界面
等你将参数设置完毕之后，既可进入游戏。走法记录界面（图
5
）如下：
图
5
走法记录界面
其他辅助功能界面（图
6
）如下：
图
6
其他辅助功能界面
你可以通过上面四个辅助功能对棋局进行研究，从而提高你的下棋水平。
例如，您是红方，第一步走的是兵七进一或兵三进一，电脑则会炮
2
进
4
或炮
8
进
4
（图
7
）
：
图
7
程序运行界面
以上是系统实现的所有界面及功能测试。
5
总结
2009
年
2
月，我开始了我的毕业论文工作，时至今日，论文基本完成。从最初的茫然，到慢慢的进入状态，
再到对思路逐渐的清晰，
整个写作过程难以用
语 言来表达。历经了几个月的奋战，紧张而又充实的毕业设计终于落下了帷幕。
回想这段日子的经历和感受 ，我感慨万千，
在这次毕业设计的过程中，
我拥有了
无数难忘的回忆和收获。
脚踏实地，认真严谨，实事求是的学习态度，不怕困难、坚持不懈、吃苦耐
劳的精神是我在这次 设计中最大的收益。
我想这是一次意志的磨练，
是对我实际
能力的一次提升，也会对我 未来的学习和工作有很大的帮助。
在这次毕业设计中也使我们的同学关 系更进一步了，
同学之间互相帮助，
有什么
不懂的大家在一起商量，
听听不同 的看法对我们更好的理解知识，
所以在这里非
常感谢帮助我的同学。
在此更 要感谢我的导师和专业老师，
是你们的细心指导和关怀，
使我能够顺
利的完成毕业论文 。
在我的学业和论文的研究工作中无不倾注着老师们辛勤的汗
水和心血。老师的严谨治学态度、 渊博的知识、无私的奉献精神使我深受启迪。
从尊敬的导师身上，
我不仅学到了扎实、
宽广的专业知识，
也学到了做人的道理。
在此我要向我的导师致以最衷心的感谢和深深的敬意。
本论文对计算机博弈技术进行了研究，
在深入研究了机器下中国象棋方法理
论基础上，实现了一个具有一定棋力的人机对弈中国象棋程序。然而，
由于时间
关系，程序也存 在着几点不足：
第一：
没对计算机下棋引擎部分作更深一步的挖掘和研究。
对于诸如位棋盘
（
BitBoard
）
、迭代加深（
Iterati ve Deepening
）
、机器学习（
Machine Learning
）等
当今棋类对弈程序中所采用的先进技术和思想，
在程序中并未涉及。
这在一定程
度上影响了程序中下棋引擎的工作效率。
第二：
由于对人工智能算法的不熟悉，
在
Alpha- Beta
搜索算法上花了大量的
时间和精力来了解，导致程序进度的缓慢。
尽管，这些问题最终都得以解决，但却影响了程序开发的进程。
第三、
程序 仍在局面检测和贴图刷新上存在着随机性的出错可能
（出错几率
很小）
。
参
考
文
献
[1]
王小春
.PC
游戏编程（人机博弈）
[M].
重庆：重庆大学出版社，
2002.
[2]
网冠科技
.Visual
C++.NET
小游戏开发时尚编程百例
[M]
.
西安：
机械工业出版社，
2004.
[3]
陈建春
.Visual
C++
高级编程技术——开发实例剖析
[ M].
西安：
电子工业出版社，
1999.
[4]
涂光平等
.Visual C++.NET
基础教程与上机指导
[M].北京：清华大学出版社，
2005.
[5]
伍红兵
.Visual C++
编程深入引导
[M].
长春：中国水利水电出版社，
2002.
[6] Frederic Friedel.
电脑国际象棋简史
[EB/OL]./
~auntyellow/computer/
，
2007-3-7
。
[7] Fran?ois Dominic Laramée.国际象棋程序设计
(一
)
：引言
[EB/OL].http://homepage.
/~ auntyellow/computer/basic_
，
2007-3-5
。
[8] Fran?ois Dominic Laramée.国际象棋程序设计
(< br>三
/OL)
：着法的产生
[EB].http://
/~aunty ellow/computer/basic_
，
2007-3-5
。
[9] Fran?ois Dominic Laramée.国际象棋程序设计
(
四
/OL)
：基本搜索方法
[EB].http://
/~auntyel low/computer/basic_
，
2007-3-5
。
[10] Fran?ois Dominic Laramée.国际象棋程序设计
(
六
/OL)
：局面评估函数
[EB].http://
/~auntye llow/computer/basic_
，
2007-3-5
。
ABSTRACT
Chess Game Design and Implementation
Yao Renjie
(College of Computer Science and Engineering, Zhongkai University of
Agriculture and Technology, Guangzhou 510225,China)
Abstract:
As the quintessence of a country for China, it has passed thousands of
years
since
Chinese
Chess
developed.
Other
chess
couldn’t
be
compared
with
it’s
popularization in China, from large- international or national competition to smaller
pieces community street .It is the distillate of Chinese people’s wisdom. Now, there
are 200 million people can play Chinese Chess only in China. And Chinese Chess is
developing
in
the
way
of
internationalization.
The
display
of
step
list
makes
player
know the process of chess distinctly, and let player make a better choice. This paper
firstly
studies
how
to
represent
a
chess
board
in
computer,
then
discusses
how
to
generate legal moves. Secondly, this paper studies the mini-max searching procedure
of
Game
Tree,
and
the
Alpha-Beta
pruning
algorithm.
A
Chess-playing
system
is
designed
and
developed,
which
is
built
on
the
integrated
computer
MFC
SDI
document view architecture by using Visual C++.
Key
words:
Chinese
chess;artificial
intelligence;game
tree;Alpha-Beta
searching;name of the law
毕业设计（论文）原创性声明和使用授权说明
原创性声明
本人郑重承诺：所呈交的毕业设计（论文）
，是我个人在指导教
师的指导下进行的研究工作及取得的成果。
尽我所知，
除文中特别加
以标注和 致谢的地方外，
不包含其他人或组织已经发表或公布过的研
究成果，
也不包含我为获得
及其它教育机构的学位或学历
而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体 ，
均已在文中作了明确的说明并表示了谢意。
作
者
签
名：
日
期：
指导教师签名：
日
期：
使用授权说明
本人完全了解
大学关于收集、保存、使用毕业设计（论
文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电
子版本；学校有权保存毕业设计（ 论文）的印刷本和电子版，并提供
目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制< br>手段保存论文；
在不以赢利为目的前提下，
学校可以公布论文的部分
或全部内容 。
布奇乐乐园官网-
布奇乐乐园官网-
布奇乐乐园官网-
布奇乐乐园官网-
布奇乐乐园官网-
布奇乐乐园官网-
布奇乐乐园官网-
布奇乐乐园官网-
本文更新与2021-01-27 06:24，由作者提供，不代表本网站立场，转载请注明出处：http://www.xapfxb.com/yuer/429919.html
-
上一篇：基于JAVA的五子棋游戏系统设计与实现(互联网+)
下一篇：象棋游戏课程设计