论文无忧网提供:计算机毕业论文范文|计算机毕业设计|计算机毕业论文
栏目导航 ASP Java Web .NET VB6.0 JAVA VC VF DELPHI PB 计算机网络 计算机科学与技术 PHP 安卓APP 其他 C# 代写论文
当前位置: > 计算机 > VC >

A450vc中国象棋软件(程序+源码+论文)

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

内容来自www.paper51.com

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

幸运的是,Alpha-Beta搜索使得我们能在不影响搜索精度的前提下大幅减少工作量。

内容来自论文无忧网 www.paper51.com

因为,如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向(我们假定下棋双方对棋局有着同样的认知,即你认为对你很糟糕的局面,在你的对手看来则是对他很有利的局面),那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时(确切地说这里的“很糟糕”是与之前分析的情况相比较而言的),你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了,如果你选择了它,那么你必将得到那个很糟糕的局面,甚至可能更糟……这样一来便可以在很大程度上减少搜索的工作量,提高搜索效率,这称为“树的裁剪”。 http://www.paper51.com

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

http://www.paper51.com

我们假定棋盘上的局面发展到了结点A(见下图),现在轮到你走棋了,你是“最大的一方”——即你希望棋局的分值尽可能的高。让我们试着搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。 paper51.com

内容来自论文无忧网 www.paper51.com

图中表示该结点要取子结点中的最大值;表示该结点要取子结点中的最小值。

paper51.com

首先,我们考察结点A的子结点B。结点B所属的这一层是轮到你的对手——“最小者”来走棋了,他的目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点,查看它们的分值(因为我们事先约定好了搜索两层,现在已达到搜索深度的要求了,所以就停下来调用局面评估函数来给它打分)。结点B的第一个子结点(从左到右算起)返回10,第二个子结点返回了-5,第三个子结点返回了2。由于结点B这层是你的对手来做选择,我们假设他一定会做出明智的选择(你不能寄希望于你的对手会走出一步“昏招”),那么他会选择返回值为-5的那个结点。-5最终也就成了从结点B传递回的值,即倘若你(现在位于结点A)选择了产生结点B的走法,使得局面发展到了结点B。那么下一步,你的对手的选择就会使得棋局发展成为分值为-5的那个结点所表示的局面。

内容来自论文无忧网 www.paper51.com

我们再来分析结点A的第二个子结点C,结点C与结点B同属一层,它依然是轮到你的对手作选择。依次查看结点C的各个子结点的分值,其第一个子结点返回了-8……

copyright paper51.com

好了,该是“裁剪”登场的时候了。你已经不必再继续考察结点C的剩余子结点了,因为结点C已经够糟糕的了,不管结点C的剩余子结点有怎样的分值,它最多只能传回-8(有可能其剩余子结点中还有分值更小的结点,因而结点C还有可能传回更小的值)。而与前面已经分析过的结点B所传回-5相比较,作为“最大一方”的你显然更不愿意看到-8的局面。所以,你当然不会选择相应的着法使得局面发展成为结点C。因为那样的话,下一步你的对手就会带给你一个分值不高于-8的局面。

copyright paper51.com

由此,我们就在不影响搜索质量的前提下避免了搜索“无价值的”结点C的剩余子结点的大量工作,从而节省了宝贵时间,为在同样机器配置下搜索更多的层数提供了可能。 http://www.paper51.com

“最小-最大”的思想再加上“对树的裁剪”,这就是Alpha-Beta搜索算法的核心。最基本的Alpha-Beta算法的代码如下: copyright paper51.com

int AlphaBeta(int depth, int alpha, int beta)

内容来自www.paper51.com

{

copyright paper51.com

  if (depth == 0)         //如果是叶子节点(到达搜索深度要求) paper51.com

      return Evaluate();  //则由局面评估函数返回估值

内容来自www.paper51.com

  GenerateLegalMoves();   //产生所有合法着法 paper51.com

  while (MovesLeft())     //遍历所有着法

paper51.com

  { paper51.com

      MakeNextMove();     //执行着法

copyright paper51.com

      int val = -AlphaBeta(depth - 1, -beta, -alpha); //递归调用          UnmakeMove();       //撤销着法

copyright paper51.com

     

paper51.com

      if (val >= beta)        //裁剪

http://www.paper51.com

          return beta;

内容来自论文无忧网 www.paper51.com

      if (val > alpha)        //保留最大值

paper51.com

          alpha= val;

内容来自论文无忧网 www.paper51.com

  } http://www.paper51.com

  return alpha; 内容来自论文无忧网 www.paper51.com

}

内容来自论文无忧网 www.paper51.com

5、历史启发及着法排序(搜索辅助) copyright paper51.com

既然Alpha-Beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率,那么它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行“裁剪”了,那么需要分析的工作量将大大减少,效率自然也就大大提高;而如果直至分析了所有的可能性之后才能做出“裁剪”操作,那此时“裁剪”也已经失去了它原有的价值(因为你已经分析了所有情况,这时的Alpha-Beta搜索已和“最小-最大”搜索别无二致了)。因而,要想保证Alpha-Beta搜索算法的效率就需要调整树的结构,即调整待搜索的结点的顺序,使得“裁剪”可以尽可能早地发生。 http://www.paper51.com

我们可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为,通常当一个局面经过搜索被认为较好时,其子结点中往往有一些与它相似的局面(如个别无关紧要的棋子位置有所不同)也是较好的。由J.Schaeffer所提出的“历史启发”(History Heuristic)就是建立在这样一种观点之上的。在搜索的过程中,每当发现一个好的走法,我们就给该走法累加一个增量以记录其“历史得分”,一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点,按照“历史得分”的高低对它们进行排序,保证较好的走法(“历史得分”高的走法)排在前面,这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”,从而保证了搜索的效率。 内容来自www.paper51.com

对于着法的排序可以使用各种排序算法,在我们的程序中采用了归并排序。归并排序的空间复杂度为O(n),时间复杂度为O(nlog2n),具有较高的效率。 copyright paper51.com

6、局面评估 copyright paper51.com

前面已经讲过了棋局表示、着法生成、搜索算法(包括搜索辅助), 在象棋程序中如果说搜索算法是心脏,那么局面评估就是大脑。搜索算法负责驱动整个程序,而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。 内容来自www.paper51.com

首先,先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点:

paper51.com

1、子力总和

http://www.paper51.com

子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如,车值500的话,那可能马值300,卒值80等等。所以在评估局面时,我们首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮,而黑方只有残士象加双马,则红方明显占优。 内容来自论文无忧网 www.paper51.com

2、棋子位置(控制区域) 内容来自www.paper51.com

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

copyright paper51.com

3、棋子的机动性

paper51.com

棋子的机动性指棋子的灵活度(可移动性)。例如,起始位置的车机动性较差,所以我们下棋讲究早出车。同样四面被憋马腿的死马机动性也较差(对于一步也不能走的棋子,可以认为其机动性为零)。

http://www.paper51.com

4、棋子的相互关系(包括攻击关系和保护关系) copyright paper51.com

这一点的分析较为复杂,因为一个棋子与其它子之间往往存在多重关系。如:一个马可能在对方的炮的攻击之下同时它又攻击着对方的车。

paper51.com

在我的程序中,估值函数最后返回的是每一方的总分的差值,而各方的总分就是上面所提到的四个因素的打分的总和。 paper51.com

对于子力打分和控制区域打分,只要遍历棋盘,当遇到棋子时简单地去查事先定义好的“子力价值表”和“控制区域价值表”,取出相对应的值进行累加即可(这些值的具体设定参考了前人的程序并作了适当的调整,今后仍应根据电脑下棋所反映出的实际问题对这些值作适当修改)。 内容来自论文无忧网 www.paper51.com

对于机动性打分,需要求出各个子总共有多少种走法,然后根据各个子所不同的机动性价值每多一种走法就加一次相应的分数。

内容来自www.paper51.com

对棋子间相互关系的打分,我先定义了一个关系表的结构类型 http://www.paper51.com

typedef struct _relationtable{

内容来自论文无忧网 www.paper51.com

    BYTEnCChessID ;

http://www.paper51.com

    int nUAttackCount ; http://www.paper51.com

    int nUGuardCount ; http://www.paper51.com

    BYTEUnderAttack[5]; 内容来自论文无忧网 www.paper51.com

    BYTEUnderGurad[5];

http://www.paper51.com

} RelationTable;

http://www.paper51.com

RelationTable RelationOfMan[9][10]; // 关系表 内容来自论文无忧网 www.paper51.com

其中nCChessID给出棋子的类型,nUAttackCount和nUGuardCount分别记录正攻击该子的棋子数量和正保护该子的棋子数量,UnderAttack[5]和UnderGuard[5]则存放攻击该子和保护该子的具体棋子(的类型)。因为考虑到实战中几乎不可能出现同时有超过五个棋子攻击/保护一个子的情况,故数组下标设定为5。

内容来自www.paper51.com

当遍历一遍棋盘之后,子力打分、控制区域打分和机动性打分都可以完成,而关系表也可以填完。之后,再根据关系表来具体考察棋子的相互关系,进行关系打分。

内容来自论文无忧网 www.paper51.com

分析关系时,首先,对王的攻击保护应分离出来单独考虑,因为对王的保护没有任何意义,一旦王被吃掉整个游戏就结束了。 http://www.paper51.com

其次,对一个普通子,当它既受到攻击又受到保护的时候要注意如下几个问题: copyright paper51.com

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

内容来自论文无忧网 www.paper51.com

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

http://www.paper51.com

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

copyright paper51.com

4、攻击方与保护方数量相同,并且攻击者子力小于被攻击者子力与保护者子力之和再减去保护者中最大子力,则攻击方可能以n子换n子。

http://www.paper51.com

当然,上述四条只是覆盖了最常见的几种情况,覆盖并不全面。而且,在我们的程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况(之所以说没有“直接地重新考虑”,是因为搜索继续展开结点后仍会考虑这些因素,只是目前我们尚不知这样效果是否受影响——考察这两种方法在效果上的差异需要一定数量的试验数据的支持)。所以,如果今后要对引擎进行改进,提高程序的下棋水平的话,还应当在此多做文章…… copyright paper51.com

------分隔线----------------------------
联系方式