中国象棋游戏的设计与实现.docx
《中国象棋游戏的设计与实现.docx》由会员分享，可在线阅读，更多相关《中国象棋游戏的设计与实现.docx（27页珍藏版）》请在冰点文库上搜索。
中国象棋游戏的设计与实现
中国象棋游戏的设计与实现
摘要
象棋程序的实现可以被分为人工智能和界面程序辅助两大部分。
人工智能部分主要体现计算机的下棋思路，既计算机如何进行思考并以最佳走法完成下一步，先由相应的搜索算法进行搜索，并对各种可能的走法进行估值，从中选择胜利面最大的一步；而界面及程序辅助部分主要便于用户通过以前的下棋步骤，更好地调整下棋思路，着法显示使用户能够清楚地知道下棋过程，更准确地把握整个局面。
本文首先研究了中国象棋在计算机中的表示问题，接着讨论如何产生着法一系列相关内容。
其次研究了博弈树的极小极大搜索技术及在此基础上发展起来的Alpha-Beta剪枝算法，使用MFC文档视图体系结构和VisualC++开发工具，实现了一个具有一定棋力的中国象棋人机对弈程序。
关键词：
中国象棋；人工智能；博弈树；Alpha-Beta搜索
TheDesignandImplementationofChineseChess
Abstract
Theimplementationofachessprogramcanbedecomposedintotwomajorparts:
theartificialintelligenceandtheuserinterfaceandprogramassist.Thepartofartificialintelligenceshowsthewayofcomputerthinking,andwhichstepisthebeststepwouldbedecidedbyit.Firstly,thecomputerusessearchalgorithmstosearch,andthenevaluateseveryimpossiblestep,finallychosesthebestone,theotherpartisusedfortheplayertoadjusthisthoughttothecurrentlyphases.Thedisplayofsteplistmakesplayerknowtheprocessofchessdistinctly,andletplayermakeabetterchoice.
Thispaperfirstlystudieshowtorepresentachessboardincomputer,thendiscusseshowtogeneratelegalmoves.Secondly,thispaperstudiesthemini-maxsearchingprocedureofGameTree,andtheAlpha-Betapruningalgorithm.AChess-playingsystemisdesignedanddeveloped,whichisbuiltontheintegratedcomputerMFCSDIdocumentviewarchitecturebyusingVisualC++.
Keywords:
Chinesechess;ArtificialIntelligence;Gametree;Alpha-Betasearching
目录
1引言1
1.1象棋设计背景和研究意义1
1.2象棋设计研究方法1
2人工智能算法设计2
2.1棋局表示3
2.2着法生成4
2.3搜索算法5
2.4历史启发及着法排序9
2.5局面评估9
2.6程序组装11
3界面及程序辅助设计12
3.1界面基本框架12
3.2多线程13
3.3着法名称显示14
3.4悔棋和还原15
4系统实现16
结论19
参考文献20
致谢21
声明22
1引言
1.1象棋设计背景和研究意义
电脑游戏行业经过二十年的发展，已经成为与影视、音乐等并驾齐驱的全球最重要的娱乐产业之一，其年销售额超过好莱坞的全年收入。
游戏，作为一种娱乐活动。
早期的人类社会由于生产力及科技的制约，只能进行一些户外的游戏。
随着生产力的发展和科技进步，一种新的游戏方式——电子游戏也随之诞生。
当计算机发明以后，电子游戏又多了一个新的载体。
电子游戏在整个计算机产业的带动下不断地创新、发展着。
自从计算机发明，向各个领域发展，到成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐步渗入我们每个人的娱乐活动中。
而计算机已经普及的今天，对于可以用计算机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想。
事实上，个人计算机软件市场的大约80%销售份额是来自游戏软件。
棋牌游戏属于休闲类游戏，相对于角色扮演类游戏和即时战略类游戏等其它游戏，具有上手快、游戏时间短的特点，更利于用户进行放松休闲，为人们所喜爱，特别是棋类游戏，方便、快捷、操作简单，在休闲娱乐中占主要位置。
作为中华民族悠久文化的代表之一，中国象棋不仅源远流长，而且基础广泛，作为一项智力运动，中国象棋开始走向世界。
随着计算机处理速度的飞速提高，人们很早就提出了疑问：
计算机是否会超越人类？
世界国际象棋大师已被计算机打败，计算机已经超过了人类？
而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。
因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。
1.2象棋设计研究方法
对于象棋来说，核心设计主要包括人工智能算法的以及整个游戏中界面及程序辅助部分的实现，主要用VisualC++进行开发，里面的MFC类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。
本文的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈程序。
该程序功能包括：
*人机对弈；
*搜索深度设定；
（电脑棋力选择）
*悔棋、还原；
*着法名称显示；
整个程序的实现可分为两大部分：
一、人工智能算法设计（计算机下棋引擎）
该部分实现了如何让计算机下中国象棋，其中涉及人机对弈的基本理论及思想，是该程序的核心部分，同时也是本项目研究的重点所在。
二、界面及程序辅助设计
光有下棋引擎尚不能满足人机交互的基本要求，因此还需要一个框架（界面）来作为引擎的载体，同时提供一些诸如悔棋，还原之类的附属功能（程序辅助）。
下面分别介绍各部分实现。
由于界面及程序辅助部分涉及内容宽泛而又繁琐，因而本文只介绍其中重点部分。
2人工智能算法设计
程序的基本框架：
从程序的结构上讲，大体上可以将引擎部分划分为四大块：
棋局表示；
着法生成；
搜索算法；
局面评估。
程序的大概的思想是：
首先使用一个数据结构来描述棋局信息，对某一特定的棋局信息由着法生成器生成当前下棋方所有合法的着法并依次存入着法队列。
然后通过搜索算法来逐一读取着法并调用局面评估函数对该着法所产生的后继局面进行评估打分，从中选出一个最有可能导致走棋方取胜的着法。
在搜索的过程中还可以采用一些辅助手段来提高搜索的效率。
其过程如下所示（图1）：
图1程序结构图
下面将分别介绍程序各个部分：
2.1棋局表示
计算机下棋的前提是要让计算机读懂象棋。
所谓读懂，即计算机应该能够清楚地了解到棋盘上的局面（棋盘上棋子的分布情况）以及下棋方所走的每一种着法。
因而首先需要设计一套数据结构来表示棋盘上的局面以及着法。
对于棋盘局面的表示可采用传统而简单的“棋盘数组”。
即用一个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
};
给所有棋子定义一个值：
#defineR_BEGINR_KING
#defineR_ENDR_PAWN
#defineB_BEGINB_KING
#defineB_ENDB_PAWN
#defineNOCHESS0//没有棋子
黑方：
#defineB_KING1//黑帅
#defineB_CAR2//黑车
#defineB_HORSE3//黑马
#defineB_CANON4//黑炮
#defineB_BISHOP5//黑士
#defineB_ELEPHANT6//黑象
#defineB_PAWN7//黑卒
红方：
#defineR_KING8//红将
#defineR_CAR9//红车
#defineR_HORSE10//红马
#defineR_CANON11//红炮
#defineR_BISHOP12//红士
#defineR_ELEPHANT13//红相
#defineR_PAWN14//红兵
判断颜色：
#defineIsBlack（x）（x>=B_BEGIN&&x<=B_END）//判断某个棋子是不
是黑色
#defineIsRed（x）（x>=R_BEGIN&&x<=R_END）//判断某个棋子是不
是红色
对于着法的表示，直接借用棋盘数组的下标来记录着法的起点和目标点。
至于是什么棋子在走，以及是否吃子、吃的是什么子，在着法结构中并不记录。
这些信息由外部读取棋盘上起点、终点的数据获得。
着法结构定义如下，其中还包含了对着法的历史得分的记录项，以供后面要讲到的“历史启发”所用。
typedefstruct
{
shortnChessID;//表明是什么棋子
CHESSMANPOSFrom;//起始位置
CHESSMANPOSTo;//走到什么位置
intScore;//走法的分数
}CHESSMOVE;
有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：
1、生成所有合法着法；
2、执行着法、撤销着法；
3、针对某一局面进行评估。
因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建立在其基础上。
2.2着法生成
程序需要让计算机在轮到它走子的时候能够执行一步它认为对它最有利的着法，那前提就是它要有诸多（也可能是唯一）可供选择的着法，提供所有候选着法的“清单”就是着法生成器所要完成的。
之后用搜索函数来搜索“清单”，并用局面评估函数来逐一打分，最后就可以选择出“最佳着法”并执行了。
在着法生成器中，采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。
这里谈到的“合法着法”包括以下几点：
1、各棋子按其行子规则行子。
诸如马跳“日”字、象走“田”字、士在九宫内斜行等等（这里需要特别注意的是卒（兵）的行子规则会随其所在位置的不同而发生变化——过河后可以左右平移）。
2、行子不能越出棋盘的界限。
当然所有子都不能走到棋盘的外面，同时某些特定的子还有自己的行棋界限，如将、士不能出九宫，象不能过河。
3、行子的半路上不能有其它子阻拦（除了炮需要隔一个子才能打子之外）以及行子的目的点不能有本方的棋子（当然不能自己吃自己了）。
4、将帅不能碰面（本程序中只在生成计算机的着法时认为将帅碰面是非法的，而对用户所走的导致将帅碰面的着法并不认为其非法，而只是产生败局罢了）。
产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来我往好几步，这样才有利于对局面进行评估以尽可能避免“目光短浅”），所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。
因此可以将着法队列定义为二维数组m_MoveList[8][80]，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。
关于搜索层数，设定为8，实际使用的是1到7（在界面中将其限定为1—7）。
搜索层数的增加会显著提高电脑的下棋水平（当然计算机的棋力在很大程度上也依赖于局面评估）。
在配置为1.5G，512M内存的计算机上最多只能搜索4层，再多将导致搜索时间达到令人无法容忍的地步（这里还需要特别说明的是，搜索的速度也和着法生成的效率以及局面评估的复杂度有关，因为每分析一个结点都要执行这两种操作）。
对于每一层的着法数，也就是当前下棋方针对当前局面的所有可选的合法着法，据有关数据统计在象棋实战中一般最多情况下也就五六十种。
定义第二个数组下标为80，应当可以保证十分的安全。
着法生成为搜索部分提供了“原料”，接下来的任务就交给搜索和局面评估了。
2.3搜索算法
搜索算法对于整个下棋引擎来说都是至关重要的。
它如同程序的心脏，驱动着整个程序。
搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。
因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。
关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变种算法）在程序中直接借鉴了Alpha-Beta搜索算法并辅以了历史启发。
本节先介绍Alpha-Beta搜索算法：
在中国象棋里，双方棋手获得相同的棋盘信息。
他们轮流走棋，目的就是将死对方，或者避免被将死。
由此，可以用一棵“博弈树”（图2）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断直到再无可选择的走法，即到达叶子结点（棋局结束）。
中国象棋的博弈树的模型大概如下图所示，可以把其中连接结点的线段看作是着法，不同的着法自然产生不同的局面。
图2博弈树
该树包含三种类型的结点：
1、奇数层的中间结点（以及根结点），表示轮到红方走棋；
2、偶数层的中间结点，表示轮到黑方走棋；
3、叶子结点，表示棋局结束。
现在让计算机来下中国象棋，它应当选择一步对它最有利的着法（最终导致它取胜的着法）。
获得最佳着法的方法就是“试走”每一种可能的着法，比较它们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的着法。
结合上面所讲的博弈树，若给每个结点都打一个分值来评价其对应的局面（这一任务由后面所讲的局面评估来完成），那么可以通过比较该分值的大小来判断局面的优劣。
假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。
如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。
反映到博弈树上，即如果假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。
那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上会挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。
同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上会选择分值最小的结点。
这是“最小-最大”（Minimax）的基本思想。
这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。
然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O（bn）。
其中b是分枝因子，即针对各种局面的合法着法的数目的平均值，n是搜索的深度。
对于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！
Alpha-Beta搜索能在不影响搜索精度的前提下大幅减少工作量。
因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。
由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向（假定下棋双方对棋局有着同样的认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。
所以当你看到某个局面有可能产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟……这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。
下面用图来进一步说明“树的裁剪”。
为了简便起见，将博弈树进行了简化——每个结点只有三个分支，实际情况中，刚才讲过在盘中应有大约40个分支。
假定棋盘上的局面发展到了结点A（图3），现在轮到你走棋了，你是“最大的一方”——即你希望棋局的分值尽可能的高。
用搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。
图中
表示该结点要取子结点中的最大值；
表示该结点要取子结点中的最小值。
图3树的裁剪
首先，考察结点A的子结点B。
结点B所属的这一层是轮到你的对手——“最小者”来走棋了，目的是使得棋局的分值尽可能的小。
依次考察结点B的各个子结点，查看它们的分值（因为事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。
结点B的第一个子结点（从左到右算起）返回10，第二个子结点返回了-5，第三个子结点返回了2。
由于结点B这层是你的对手来做选择，假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为-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;
}
2.4历史启发及着法排序
既然Alpha-Beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，那么它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的Alpha-Beta搜索已和“最小-最大”搜索别无二致了）。
因而，要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。
可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。
因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。
由J.Schaeffer所提出的“历史启发”（HistoryHeuristic）就是建立在这样一种观点之上的。
在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。
对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。
对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。
归并排序的空间复杂度为O（n），时间复杂度为O（nlog2n），具有较高的效率。
2.5局面评估
前文已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助），在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。
搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。
因而搜索与局面评估是整个下棋引擎的核心。
首先，先介绍一下在局面评估中需要考虑的因素。
就不同的棋类可能要考虑的因素略有差异。
在中国象棋中所要考虑的最基本的几个因素包括如下四点：
1、子力总和
子力是指某一棋子本身所具有的价值。
通俗地讲就是一个棋子它值个什么价。
例如，车值500的话，那可能马值300，卒值80等等。
所以在评估局面时，首先要考虑双方的子力总和的对比。
比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。
2、棋子位置
棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位置。
例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。
3、棋子的机动性
棋子的机动性指棋子的灵活度（可移动性）。
例如，起始位置的车机动性较差，所以下棋讲究早出车。
同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认为其机动性为零）。
4、
升级会员 