电子科技大学成都学院计算机系

 

课程结题报告

课 程  名 称：软件体系架构和设计模式

设 计  题 目：______________     _ 

上 课  教 师：______________     _ 

学生学号姓名：______________     _ 

计算机系制

20##年6月

目  录

第1章 引言.................................................................................................................... 3

1.1中国象棋游戏设计背景和研究意义.................................................................. 3

1.2国内外象棋软件发展状况………………………………….…………………..3

1.3中国象棋游戏设计研究方法………………………………….………………..4

第2章总体设计………………………………………………………………………..5

2.1棋盘和棋子的表示……………………………………………………………...6

2.2着法生成………………………………………………………………………...7

第3章详细设计……………………………………………………………………….8

3.1博弈程序的实现…………………………………………………….…………..8

3.1.1搜索算法……………………………………………………….…………..8

3.1.2启发方式……………………………………………………………….…..9

3.1.3局面评估………………………………………………………………….10

3.2胜败判定……………………………………………………………………….11

第4章界面设计和系统实现…………………………………………………………12

4.1界面设计……………………………………………………………………….12

4.2系统实现……………………………………………………………………….14

    第1章   引言

1.1中国象棋游戏设计背景和研究意义

中国象棋游戏流传至今已经有数千年的历史了，是一种古老的文化，它集文化、科学、艺术、竞技于一体，有利于开发人的智慧，锻炼人的思维，培养人的毅力，增强人的竞争意识。自从计算机发明，向各个领域发展，到成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐步渗入我们每个人的娱乐活动中。在计算机已经普及的今天，对于可以用计算机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想，中国象棋历史悠久不仅源远流长，而且基础广泛，作为一项智力运动更成为我们游戏开发的首选对象。中国象棋是一项智力游戏，以往都是人和人下棋，现在有了计算机我们可以和计算机竞技，人可以与计算机进行对弈。控制计算机的是人类，而人工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。因此，对游戏开发过程中的人工智能技术的研究自然也就成了业界的一个热门研究方向。

1.2国内外象棋软件发展概况

最早的象棋软件是一副可以外出携带的电子棋盘，后来升级到电视游戏机。开始出现的一些容量很小的象棋软件如：DOS界面《将族》WIN31程序的《中国象棋》等等，与其说人类下不过电脑，倒不如说是没有耐性等待电脑程序慢吞吞的搜索算法，有时甚至怀疑软件是否在搜索中死掉了。后来，网络上先后出现了真正的WINDOWS窗口界面的象棋专业高级软件《棋隐》《象棋世家》《象棋参谋》《象棋奇兵》等。总而言之，各类象棋软件既有自身的优点，也存在共通性的缺陷，如：中局审势不够智能化，走不出弃子取势的人性化佳构，残局时智力明显低于人脑，难以走出残局例胜的必然着法等。放眼未来，象棋软件已经走完了一波持续上涨的行情，有可能出现逐步降温的滑坡趋势。

1.3中国象棋游戏设计研究方法

本系统主要用Visual C++ 进行开发，里面的MFC类库，使游戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从而完善整个游戏的功能。该象棋人机博弈系统实现的功能主要包括：

（1）、选手选择（人或电脑）；

（2）、人机对弈（人与电脑竞技）；

（3）、重新开局。

第2章   总体设计

2.1棋盘和棋子的表示

对于中国象棋棋盘局面的表示可采用传统而简单的“棋盘数组”即用一个9*10的数组来存储棋盘上的信息，数组的每个元素存储棋盘上是否有棋子。这种表示方法简单易行。按此方法棋盘的初始情形如下所示：

Static  const  BYTE  iStartup[256] = {

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 20, 19, 18, 17, 16, 17, 18, 19, 20, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0,

  0, 0, 0, 22, 0, 22, 0, 22, 0, 22, 0, 22, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 0, 0, 0,

  0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 12, 11, 10, 9, 8, 9, 10, 11, 12, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

};

给棋子定义一个编号：

const int PIECE_KING = 0; //帅

const int PIECE_ADVISOR = 1;//象

const int PIECE_BISHOP = 2; //士

const int PIECE_KNIGHT = 3;//马

const int PIECE_ROOK = 4;//车

const int PIECE_CANNON = 5;// 炮

const int PIECE_PAWN = 6;//兵

对于着法的表示，直接借用棋盘数组的下标来记录着法的起点和目标点。至于是什么棋子在走，以及是否吃子、吃的是什么子，在着法结构中并不记录。这些信息由外部读取棋盘上起点、终点的数据获得。着法结构定义如下，其中还包含了对着法的历史得分的记录项，以供后面要讲到的“历史启发”所用。

struct MoveStruct {

WORD wmv; 

BYTE ucpcCaptured, ucbCheck;

DWORD dwKey;

void Set(int mv, int pcCaptured, BOOL bCheck, DWORD dwKey_) {

wmv = mv;

ucpcCaptured = pcCaptured;

ucbCheck = bCheck;

dwKey = dwKey_;

}

}; // mvs

有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：生成所有合法着法；执行着法、撤销着法针对某一局面进行评估。因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建立在其基础上。

2.2着法生成

在着法生成器中，采用的基本思想就是遍历整个棋盘（一个接一个地查看棋盘上的每个位置点），当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。这里谈到的“合法着法”包括以下几点：

（1）、各棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九宫内斜行等等（这里需要特别注意的是卒（兵）的行子规则会随其所在位置的不同而发生变化——过河后可以左右平移）。

（2）、行子不能越出棋盘的界限。当然所有棋子都不能走到棋盘的外面，同时某些特定的棋子还有自己的行棋界限，如将、士不能出九宫，象不能过河。

（3）、行子的半路上不能有其它子阻拦（除了炮需要隔一个子才能打子之外）以及行子的目的点不能有本方的棋子（当然不能自己吃自己了）。

（4）、将帅不能碰面（本程序中只在生成计算机的着法时认为将帅碰面是非法的，而对用户所走的导致将帅碰面的着法并不认为其非法，而只是产生败局罢了）。生成所有着法后还需要评估走法。

第3章    详细设计

3.1博弈程序的实现

3.1.1搜索算法

搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变种算法）。我们的程序采用了静态搜索方法。当Alpha-Beta用尽深度后，通过调用静态搜索来代替调用“Evaluate()”。这个函数也对局面作评价，只是避免了在明显有对策的情况下看错局势。简而言之，静态搜索就是应对可能的动态局面的搜索。走子一方可以选择是吃子还是不吃子。这就好比打扑克牌时可以只用手中的牌而不去抓牌。代码如下：

int Quies(int alpha, int beta)

 {

val = Evaluate();

if (val >= beta)

{

return beta;

}

if (val > alpha)

 {

alpha = val;

}

GenerateGoodCaptures();

while (CapturesLeft())

{

MakeNextCapture();

val = -Quies(-beta, -alpha);

UnmakeMove();

if (val >= beta)

{

return beta;

}

if (val > alpha) {

alpha = val;

} }

return alpha;

}

这看上去和“Alpha-Beta”非常相似，但是区别是很明显的。这个函数调用静态评价，如果评价好得足以截断而不需要试图吃子时，就马上截断(返回Beta)。如果评价不足以产生截断，但是比Alpha好，那么就更新Alpha来反映静态评价。 然后尝试吃子着法，如果其中任何一个产生截断，搜索就中止。可能它们没有一个是好的，这也没问题。这个函数有几个可能的结果：可能评价函数会返回足够高的数值，使得函数通过Beta截断马上返回；也可能某个吃子产生Beta截断；可能静态评价比较坏，而任何吃子着法也不会更好；或者可能任何吃子都不好，但是静态评价只比Alpha高一点点。 注意这里静态搜索中没有传递“深度”这个参数。正因为如此，如果找到好的吃子，或者有一系列连续的强制性吃子的着法，那么搜索可能会非常深。

3.1.2启发方式

采用了MVV/LVA启发。MVV/LVA 意思是”最有价值的受害者/最没价值的攻击者”(Most Valuable Victim/Least Valuable Attacker)。这是一个应用上非常简单的着法排序技巧，从而最先搜索最好的吃子着法。这个技术假设最好的吃子是吃到最大的子。如果不止一个棋子能吃到最大的子，那么假设用最小的子去吃是最好的。这就意味者PxQ(兵吃后)首先考虑(假设王的将军另外处理)。接下来是NxQ或BxQ，然后是RxQ、QxQ、KxQ。接下来是PxR、B/NxR、RxR、QxR、KxR，等等。这个工作总比不做要好，但是很明显有很严重的问题。即使车被保护着，RxR仍旧排在PxB的前面。MVV/LVA 可以解决静态搜索膨胀的问题，但是它仍然留给你比较庞大的静态搜索树。MVV/LVA 的优势在于它实现起来非常方便，而且可以达到很高NPS值(每秒搜索的结点数)。它的缺点是搜索效率低——你花大量的时间来评估吃亏的吃子，所以你的搜索不会很深。

3.1.3局面评估

在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素

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

1、子力总和

子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值10的话，那可能马值6，卒值2等等。所以在评估局面时，首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。

2、棋子位置

棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。

3、棋子的机动性

棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，

可以认为其机动性为零）

4、棋子的相互关系

这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击着对方的车。在程序中，估值函数最后返回的是每一方的总分的差值，而各方的总分就是上面所提到的四个因素的打分的总和。对于子力打分和控制区域打分，只要遍历棋盘，当遇到棋子时简单地去查事先定义好的“子力价值表”和“控制区域价值表”，取出相对应的值进行累加即可。对于机动性打分，需要求出各个子总共有多少种走法，然后根据各个子所不同的机动性价值每多一种走法就加一次相应的分数。当遍历一遍棋盘之后，子力打分、控制区域打分和机动性打分都可以完成，而关系表也可以填完。之后，再根据关系表来具体考察棋子的相互关系，进行关系打分。分析关系时，首先，对王的攻击保护应分离出来单独考虑，因为对王的保护没有任何意义，一旦王被吃掉整个游戏就结束了。其次，对一个普通子，当它既受到攻击又受到保护的时候要注意如下几个问题：

1、攻击者子力小于被攻击者子力，攻击方将愿意换子。比如，一个车正遭受一个炮的攻击，那么任何对车的保护都将失去意义——对方肯定乐意用一个炮来换一个车。

2、多攻击单保护的情况，并且攻击者最小子力小于被攻击者子力与保护者子力之和，则攻击方可能以一子换两子。

3、三攻击两保护的情况，并且攻击者子力较小的二者之和小于被攻击者子力与保护者子力之和，则攻击方可能以两子换三子。

4、攻击方与保护方数量相同，并且攻击者子力小于被攻击者子力与保护者子力之和

再减去保护者中最大子力，则攻击方可能以n子换n子。当然，上述四条只是覆盖了最常见的几种情况，覆盖并不全面。而且，在程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况

3.2胜败判定

胜负判定只要一方将另一方的将或帅吃掉就是胜者

 主要代码如下：

BOOL PositionStruct::IsMate(void)

 {

int i, nGenMoveNum, pcCaptured;

int mvs[MAX_GEN_MOVES];

nGenMoveNum = GenerateMoves(mvs);

for (i = 0; i < nGenMoveNum; i ++)

   {

pcCaptured = MovePiece(mvs[i]);

if (!Checked())

 {

         UndoMovePiece(mvs[i], pcCaptured);

Return  FALSE;

 }

else

      {

      UndoMovePiece(mvs[i], pcCaptured);

 }

 }

return TRUE;

}

第4章界面设计和系统实现

4.1界面设计

关于棋盘和棋子，均采用API函数编写。代码主要分布于以下三大部分：

1、绘图部分

主要会制棋盘，并装载图片。代码如下：

static void DrawBoard(HDC hdc)

 {

int x, y, xx, yy, sq, pc;

HDC hdcTmp; // 画棋盘

hdcTmp = CreateCompatibleDC(hdc);

SelectObject(hdcTmp, Qiyun.bmpBoard);

BitBlt(hdc,LEFT UP, BOARD_WIDTH, BOARD_HEIGHT, hdcTmp, 0, 0, SRCCOPY); //摆棋子

for (x = FILE_LEFT; x <= FILE_RIGHT; x ++)

{//for1

for (y = RANK_TOP; y <= RANK_BOTTOM; y ++)

{//for2

xx = LEFT +BOARD_EDGE + (x - FILE_LEFT) * SQUARE_SIZE;//X_mirror(x) 翻转棋盘用这个

yy = UP + BOARD_EDGE + (y - RANK_TOP) * SQUARE_SIZE; //Y_mirror(y)

sq = ObtainPosition_XY(x, y);

pc = pos.ucpcSquares[sq];

if (pc != 0)

{

//xx,yy为目标格子左上角坐标将hdc复制到hdcTmp

DrawTransBmp(hdc, hdcTmp, xx, yy,Qiyun.bmpPieces[pc]);

}

if (sq == Qiyun.sqSelected || sq == SRC(Qiyun.mvLast) || sq == DST(Qiyun.mvLast))

{

DrawTransBmp(hdc, hdcTmp, xx, yy, Qiyun.bmpSelected);

}

}//for2

}//for1

DeleteDC(hdcTmp);

}

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

主要通过消息传递实现响应，主要的按键功能：

ESC-退出程序

F1-重新开局

F2-重新开局，并使电脑先走（默认玩家先走）方向键移动光标

SPACE/ENTER-选中棋子

HOME-使光标移到棋盘最左上方

END-使光标移到棋盘最右下方

4.2系统实现

现在已具备了实现一款中国象棋对弈程序引擎部分的所有要素，将上述模块分别写作.h头文件。如下：

Qiyun.h ——象棋相关定义。包括棋盘局面和着法的表示、生成，还包括搜索与启发。Resourse.h ——象棋相关常量定义。对局时，由执红棋的一方先走，双方轮流各走一着，直至分出胜、负、和，对局即终了。轮到走棋的一方，将某个棋子从一个交叉点走到另一个交叉点，或者吃掉对方的棋子而占领其交叉点，都算走一着。双方各走一着，称为一个回合。如果有一方的主帅被对方吃了，就算那一方输。

各种棋子的走法：

帅（将）：帅和将是棋中的首脑，是双方竭力争夺的目标。它只能在“九宫”之内活动，可上可下，可左可右，每次走动只能按竖线或横线走动一格。帅与将不能在同一直线上直接对面，否则走方判负。

仕（士）：仕（士）是帅（将）的贴身保镖，它也只能在九宫内走动。它的行棋路径只能是九宫内的斜线。

相（象）：相（象）的主要作用是防守，保护自己的帅（将）。它的走法是每次循对角线走两格，俗称“象走田”。相（象）的活动范围限于“河界”以内的本方阵地，不能过河，且如果它走的“田”字中央有一个棋子，就不能走，俗称“塞象眼”。

车：车在象棋中威力最大，无论横线、竖线均可行走，只要无子阻拦，步数不受限制。因此，一车可以控制十七个点，故有“一车十子寒”之称。

炮：炮在不吃子的时候，走动与车完全相同。

马：马走动的方法是一直一斜，即先横着或直着走一格，然后再斜着走一个对角线，俗称“马走日”。马一次可走的选择点可以达到四周的八个点，故有“八面威风”之说。如果在要去的方向有别的棋子挡住，马就无法走过去，俗称“蹩马腿”。

兵（卒）：兵（卒）在未过河前，只能向前一步步走，过河以后，除不能后退外，允许左右移动，但也只能一次一步。在懂的以上规则之后并可进行游戏，执行该软件后，并可进入游戏界面

电子科技大学成都学院

　　     课程成绩评定表