我们假定棋盘上的局面发展到了结点A（见下图），现在轮到你走棋了，你是“最大的一方”——即你希望棋局的分值尽可能的高。让我们试着搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。
图中表示该结点要取子结点中的最大值；表示该结点要取子结点中的最小值。
首先，我们考察结点A的子结点B。结点B所属的这一层是轮到你的对手——“最小者”来走棋了，他的目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点，查看它们的分值（因为我们事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点Ｂ的第一个子结点（从左到右算起）返回10，第二个子结点返回了-5，第三个子结点返回了２。由于结点Ｂ这层是你的对手来做选择，我们假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为-5的那个结点。-5最终也就成了从结点B传递回的值，即倘若你（现在位于结点A）选择了产生结点B的走法，使得局面发展到了结点B。那么下一步，你的对手的选择就会使得棋局发展成为分值为-5的那个结点所表示的局面。
我们再来分析结点A的第二个子结点C，结点C与结点B同属一层，它依然是轮到你的对手作选择。依次查看结点C的各个子结点的分值，其第一个子结点返回了-8……
好了，该是“裁剪”登场的时候了。你已经不必再继续考察结点C的剩余子结点了，因为结点C已经够糟糕的了，不管结点C的剩余子结点有怎样的分值，它最多只能传回-8（有可能其剩余子结点中还有分值更小的结点，因而结点C还有可能传回更小的值）。而与前面已经分析过的结点B所传回-5相比较，作为“最大一方”的你显然更不愿意看到-8的局面。所以，你当然不会选择相应的着法使得局面发展成为结点C。因为那样的话，下一步你的对手就会带给你一个分值不高于-8的局面。
由此，我们就在不影响搜索质量的前提下避免了搜索“无价值的”结点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;
}
5、历史启发及着法排序（搜索辅助）
既然Alpha-Beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，那么它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的Alpha-Beta搜索已和“最小-最大”搜索别无二致了）。因而，要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。
我们可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer所提出的“历史启发”（History Heuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，我们就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。
对于着法的排序可以使用各种排序算法，在我们的程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。
6、局面评估
前面已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助）， 在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。
首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点：
1、子力总和
子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值500的话，那可能马值300，卒值80等等。所以在评估局面时，我们首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。
2、棋子位置（控制区域）
棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。
3、棋子的机动性
棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以我们下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认为其机动性为零）。
4、棋子的相互关系（包括攻击关系和保护关系）
这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击着对方的车。
&nb
首页 上一页 1 2 3 4 5 6 7 下一页 尾页 3/7/7
免费vc中国象棋软件(三)由毕业论文网（www.huoyuandh.com）会员上传。
