单机游戏开发报告
1、 实验目的
中国象棋是一项智力游戏，以往都是人和人下棋，现在有了计算机我们可以和计算机竞技，人可以与计算机进行对弈。控制计算机的是人类，而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。
2、 实验步骤
本系统主要用 Visual C++ 进行开发，里面的MFC类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。
该象棋人机博弈系统实现的功能主要包括：
1、选手选择（人或电脑）；
2、人机对弈（人与电脑竞技）；
3、电脑棋力难度选择（电脑下棋能力难度选择，共有4级：按电脑配置选择难度）；
4、悔棋、还原；
5、着法名称显示（象棋走棋规范名称）。
对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”。即用一个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;
搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变种算法）。我们在程序中直接借鉴了Alpha-Beta搜索算法并辅以历史启发。本节先介绍Alpha-Beta搜索算法：在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是吃掉对方的将或帅，或者避免自己的将或帅被吃。
图1 博弈树
又此，可以用一棵“博弈树”（图1）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断进行下去直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的模型大概如下图所示，可以把其中连接结点的线段看作是着法，不同的着法自然产生不同的局面。
。
图2 树的裁剪
首先，考察结点A的子结点B。结点B所属的这一层是轮到你的对手——“最小者”来走棋了，目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点，查看它们的分值（因为事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点B的第一个子结点（从左到右算起）返回-8，第二个子结点返回了-2，第三个子结点返回了2。由于结点B这层是你的对手来做选择，假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为-2的那个结点。-2最终也就成了从结点B传递回的值，即倘若你（现在位于结点A）选择了产生结点B的走法，使得局面发展到了结点B。那么下一步，你的对手的选择就会使得棋局发展成为分值为-2的那个结点所表示的局面。
再来分析结点A的第二个子结点C，结点C与结点B同属一层，它依然是轮到你的对手作选择。依次查看结点C的各个子结点的分值，其第一个子结点返回了2……。
“最小-最大”的思想再加上“对树的裁剪”，这就是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;
}
：
2、棋子的相互关系
对棋子间相互关系的打分，要用到以下几个数据：
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分别记录该棋子受到的威胁和被保护的值。
当遍历一遍棋盘之后，子力打分、控制区域打分和机动性打分都可以完成，而关系表也可以填完。之后，再根据关系表来具体考察棋子的相互关系，进行关系打分。
分析关系时，首先，对王的攻击保护应分离出来单独考虑，因为对王的保护没有任何意义，一旦王被吃掉整个游戏就结束了。
其次，对一个普通子，当它既受到攻击又受到保护的时候要注意如下几个问题：
这里需要特别说明的是通常象棋程序处于程序效率的考虑并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后当悔棋的时候，需要撤销着法；还原的时候，需要执行着法。然而，在编写自己的程序时一来考虑到程序的可读性和不易出错性，二来考虑到对当今的计算机的配置来说这点开销基本上不会对程序的效率产生什么影响。因此保存了全部棋子的信息。
根据所要保存的数据定义了如下基本结构类型：
typedef struct
{
CHESSMOVE cmChessMove;
short nChessID;//被吃掉的棋子
}UNDOMOVE;
在对弈过程中，每一回合都将棋局信息（这里指前面所说的需要保存的信息）保存至走法队列，以供悔棋所用。还原功能是与悔棋功能相对应的，只有当产生了悔棋功能之后，还原功能才会被激活。一个回合的结束意味着前一次操作没有悔棋功能的产生，因此还原队列也应被清空。
每当下棋者（用户或是计算机）走一步棋，在棋盘旁边的一个列表框控件（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;
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);减一之后正好是最后一项的行号。
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
}
关于棋盘和棋子，建了一个基于对话框的MFC应用程序。主要工作都在对话框类的两个文件CChessDlg.h和CChessDlg.cpp下展开。
代码主要分布于以下三大部分：
1、初始化部分
BOOL CCChessUIDlg::OnInitDialog()
{
}
OnInitDialog()负责的是对话框的初始化。可以把有关中国象棋的棋局初始化情况也放在了这里面。初始化的内容包括：
对引擎部分所用到的变量的初始化。包括对棋盘上的棋子位置进行初始化（棋盘数组的初始化），对搜索深度、当前走棋方标志、棋局是否结束标志等的初始化；
对棋盘、棋子的贴图位置（即棋盘、棋子在程序中实际显示位置）的初始化；
对程序辅助部分所用到的一些变量的初始化。包括对悔棋、还原队列的清空，棋盘、棋子样式的默认形式，下棋模式的默认选择，以及着法名称列表的初始化等。
2、绘图部分
void CCChessUIDlg::OnPaint()
{
……
}
OnPaint()函数负责的是程序界面的绘图。因此，在这里将要完成棋盘、棋子的显示走棋起始位置和目标位置的提示框的显示。
由于棋盘、棋子等都是以位图的形式给出的。所以在OnPaint()函数里做的工作主要都是在贴位图。
需要注意的是由于位图文件不能像GIF文件那样有透明的背景并且棋子是圆形的而位图文件只能是矩形的，所以如果直接贴图的话会在棋盘上留下一块白色的边框——棋子的背景。因此，要想让棋子文件的背景“隐藏”需要通过一些“与”和“异或”操作来屏蔽掉棋子的背景。
3、走棋部分（用户动作响应部分）
为WM_LBUTTONDOWN消息添加消息响应事件，可得到如下函数：
void CCChessUIDlg::OnLButtonDown(UINT nFlags, CPoint point)
{
……
}
当用户在窗口客户区按下鼠标左键时，程序就会调用OnLButtonDown(UINT nFlags, CPoint point)函数来进行响应。其中第二个参数CPoint point是在本程序中所要用到的，它给出了当鼠标左键被按下时，鼠标指针的位置坐标。可以通过这一信息来得知用户的走法。
现在已具备了实现一款中国象棋对弈程序引擎部分的所有要素，将上述模块分别写作.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 程序运行界面
从最初的茫然，到慢慢的进入状态，再到对思路逐渐的清晰，整个写作过程难以用语言来表达。脚踏实地，认真严谨，实事求是的学习态度，不怕困难、坚持不懈、吃苦耐劳的精神是我在这次设计中最大的收益。我想这是一次意志的磨练，是对我实际能力的一次提升，也会对我未来的学习和工作有很大的帮助。
在老师的严谨治学态度、渊博的知识、无私的奉献精神使我深受启迪。从尊敬的导师身上，我不仅学到了扎实、宽广的专业知识，也学到了做人的道理。在此我要向我的导师致以最衷心的感谢和深深的敬意。
