中国象棋游戏的设计与实现-毕业设计(2)

因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建立在其基础上。 2.2 着法生成

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

这里谈到的“合法着法”包括以下几点：

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

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

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

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

产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来我往好几步，这样才有利于对局面进行评估以尽可能避免“目光短浅”），所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。因此可以将着法队列定义为二维数组m_MoveList[8][70]，其中第一个数组下标为层数，第二个数组下标为每一层的全部着法数。

关于搜索层数，设定为4，实际使用的是1到3（在界面中将其限定为1—3）。搜索层数的增加会显著提高电脑的下棋水平（当然计算机的棋力在很大程度上也依赖于局面评估）。在配置为1.5G，512M内存的计算机上最多只能搜索3层，再多将导致搜索时间达到令人无法容忍的地步（这里还需要特别说明的是，搜索的速度也和着法生成的效率以及局面评估的复杂度有关，因为每分析一个结点都要执行这两种操作）。

对于每一层的着法数，也就是当前下棋方针对当前局面的所有可选的合法着法，据有关数据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数组下标为70，应当可以保证十分的安全。

4

3 走棋和博弈程序的实现

3.1 博弈程序的实现 3.1.1 搜索算法

搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，已有成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变种算法）。我们在程序中直接借鉴了Alpha-Beta搜索算法并辅以历史启发。本节先介绍Alpha-Beta搜索算法：在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是吃掉对方的将或帅，或者避免自己的将或帅被吃。

?? ?? 表示红方走棋 ?? 图1 博弈树

表示黑方走棋

又此，可以用一棵“博弈树”（图1）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断进行下去直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的模型大概如下图所示，可以把其中连接结点的线段看作是着法，不同的着法自然产生不同的局面。

该树包含三种类型的结点：

1、奇数层的中间结点（以及根结点），表示轮到红方走棋；

5

2、偶数层的中间结点，表示轮到黑方走棋； 3、叶子结点，表示棋局结束。

现在让计算机来下中国象棋，它应当选择一步对它最有利的着法（最终导致它取胜的着法）。获得最佳着法的方法就是“试走”每一种可能的着法，比较它们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的着法。

结合上面所讲的博弈树，若给每个结点都打一个分值来评价其对应的局面（这一任务由后面所讲的局面评估来完成），那么可以通过比较该分值的大小来判断局面的优劣。假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上会挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上会选择分值最小的结点。这是“最小-最大”（Minimax）的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O(bn)。其中b是分枝因子，即针对各种局面的合法着法的数目的平均值，n是搜索的深度。对于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！

Alpha-Beta搜索能在不影响搜索精度的前提下大幅减少工作量。

因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向（假定下棋双方对棋局有着同样的认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟。这样一来

6

便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。

下面用图来进一步说明“树的裁剪”。为了简便起见，将博弈树进行了简化——每个结点只有三个分支，实际情况中，刚才讲过在盘中应有大约40个分支。

假定棋盘上的局面发展到了结点A（图2），现在轮到你走棋了，你是“最大的一方”——即你希望棋局的分值尽可能的高。用搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。

图中

表示该结点要取子结点中的最大值；

A 表示该结点要取子结点中的最小值。

B C D -8 -2 10 2 -8 ? … … …

图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（有可能其剩余

7

子结点中还有分值更小的结点，因而结点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搜索已和“最小-最大”搜索别

8

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库中国象棋游戏的设计与实现-毕业设计(2)在线全文阅读。