J2ME的蓝牙联网游戏中国象棋游戏的设计与实现 第6页

J2ME的蓝牙联网游戏中国象棋游戏的设计与实现 第6页
然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O(bn)。其中b是分枝因子，即针对各种局面的合法走法的数目的平均值，n是搜索的深度。对于中国象棋而言，在中盘时平均走法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线!
幸运的是，Alpha-Beta搜索能在不影响搜索精度的前提下大幅减少搜索量。因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向，那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当看到某个局面有可能产生很糟糕的局面时，应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果选择了它，那么必将得到那个很糟糕的局面。这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。
下面用图3-4来进一步说明“树的裁剪”。为了简便起见，假设博弈树的每个结点只有三个分支。
 
图3-4 简化的博弈树
现在假定棋盘上的局面发展到了结点A，现在轮到“最大者”走棋了——即“最大者”希望棋局的分值尽可能的高。可以试着搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。
首先，考察结点A的子结点B。结点B所属的这一层是轮到对方——“最小者”走棋，“最小者”的目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点，查看它们的分值（因为事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点Ｂ的第一个子结点（从左到右算起）返回10，第二个子结点返回了-5，第三个子结点返回了２。由于结点Ｂ这层是“最小者”来做选择，假设“最小者”一定会做出明智的选择，那么“最小者”会选择返回值为-5的那个结点。
我们再来分析结点A的第二个子结毕业论文http://www.751com.cn点C，结点C与结点B同属一层，它依然是轮到“最小者”作选择。依次查看结点C的各个子结点的分值，其第一个子结点返回了-8。好了，该是“裁剪”的时候了。不必再继续考察结点C的剩余子结本文来自辣文论文网发展成为结点C。因为如果那样的话，下一步“最小者”就会带给“最大者”一个分值不高于-8的局面。
由此，在不影响搜索质量的前提下避免了搜索“无价值的”结点C的剩余子结点，从而节省了宝贵时间，为在同样机器配置下搜索更多的层数提供了可能。
“最小-最大”的思想再加上“对树的裁剪”，这就是Alpha-Beta搜索算法的核心。最基本的Alpha-Beta算法的代码如下：
int AlphaBeta(int depth, int alpha, int beta){
 if (depth == 0)   //如果是叶子节点（到达搜索深度要求）
  return Eveluate (); //则由局面评估函数返回估值
 CreatePossibleMove (); //产生所有合法走法 
 while (MovesLeft()){  //遍历所有走法
  MakeMove ();//执行走法
  int val = -AlphaBeta(depth - 1, -beta, -alpha); //递归调用    UnMakeMove ();//撤销走法
  if (val >= beta) //裁剪
   return beta;
  if (val > alpha)  //保留最大值
   alpha = val;
 } 
 return alpha;
}

3.5历史启发及走法排序（搜索辅助）
Alpha-Beta搜索算法在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，它的效率在很大程度上取决于树的结构——如果搜索了没多久就发现可以“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能“裁剪”,那此时“裁剪”也已经失去了它原有的价值。因而，要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。
根据部分已经搜索的结果来调整将要进行搜索的节点顺序是一个可行的方向。通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面也是较好的。由J.Schaeffer所提出的“历史启发”（History Heuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。
对于走法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。
3.6 局面评估
局面评估是评估一个局面优劣的过程。如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。
在中国象棋中所要考虑的最基本的几个因素包括如下三点：
(1)棋子的价值评估
棋子的价值评估，简单的说就是评估双方都有哪些棋子在棋盘上。例如，可以让一个车价值为500，一个马价值为300，一个兵价本文来自辣文论文网值为100，“将”的价值为无限大（通常用一个远大于其他棋子的数）等等。一方的毕业论文http://www.751com.cn棋子总值就是棋盘上存活的该方棋子乘以棋子价值的和。用一个式子表达：
SideValue=Sum(PieceNumber*PieceValue)
其中PieceNumber是某种棋子的数量，PieceValue是该种棋子的价值，Sum 是对各种棋子的总价值求和。如果红色的棋子价值总和大于黑色的棋子价值总和，通常意味着红方的局势优于黑方。红黑双方的SideValue之差越大，优势也就越大。
(2)棋子的灵活性与棋盘控制
棋子的灵活性是指棋子的活动范围，通常是越大越好。一匹不能动的马很难在棋局中发挥重要作用；同样，一个蹲在角落里的车也是价值不高的。评估棋子的灵活性较为简单，将一个棋子的所有合法走法罗列出来，乘上该种棋子每一可走步的价值就行了。也可用一个式子表达：
Mobility=Sum(MoveNumber*MoveValue)
其中，MoveNumber是某种棋子的合法走法数量，MoveValue是该种棋子每一走法的价值，Sum是对所有棋子的灵活性价值求和。Mobility就是所有棋子的灵活性分数。
还可以评估博弈双方对棋盘上位置的控制能力。在象棋中，如果某一位置落在某方棋子的合法走步上，就可以认为被该方控制。如果某一位置同时落在双方的合法走步上，我们可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。
(3)棋子关系的评估
棋子间的关系也是估值的重要内容之一，我们可以将某个棋子被对方棋子威胁看成是一个不利的因素。例如红车的位置在黑马的合法走步当中，此时我们可以把红车的价值减去一个值。而如果红马在黑车的合法走步之中，红马同时也在红卒的合法走步之中，我们可以认为红马置于红卒的保护之下，没有受到威胁，价值不变。
棋子关系的评估应考虑到该谁走棋的问题。如果某个红马落在黑炮的合法走步之内，但此时轮到红方走棋，应认为红马受到的威胁较轻。而如果此时轮到黑方走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。如果“将”被对方威胁，且轮到对方走棋，那么无论有何种棋子可以走到“将”位都没有意义，将等于失去了。此时应结束估值返回失败的估值（通常是极大或极小值）。

上一页  [1] [2] [3] [4] [5] [6] [7] 下一页

J2ME的蓝牙联网游戏中国象棋游戏的设计与实现 第6页下载如图片无法显示或论文不完整，请联系qq752018766