|
判断局面的优劣。假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果我们假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上我们会挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上我们会选择分值最小的结点。这就是“最小-最大”（Minimax）[2]的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O(bn)。其中b是分枝因子，即针对各种局面的合法着法的数目的平均值，n是搜索的深度。对于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！！！ http://www.paper51.com 幸运的是，Alpha-Beta搜索使得我们能在不影响搜索精度的前提下大幅减少工作量。 paper51.com 因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向（我们假定下棋双方对棋局有着同样的认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟……这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。 内容来自论文无忧网 www.paper51.com 下面用图来进一步说明“树的裁剪”。为了简便起见，我将博弈树进行了简化——每个结点只有三个分支，实际情况中，刚才讲过在中盘应有大约40个分支。 内容来自www.paper51.com 我们假定棋盘上的局面发展到了结点A（见下图），现在轮到你走棋了，你是“最大的一方”——即你希望棋局的分值尽可能的高。让我们试着搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。 http://www.paper51.com
内容来自论文无忧网 www.paper51.com
图中表示该结点要取子结点中的最大值；表示该结点要取子结点中的最小值。 内容来自www.paper51.com
首先，我们考察结点A的子结点B。结点B所属的这一层是轮到你的对手——“最小者”来走棋了，他的目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点，查看它们的分值（因为我们事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点Ｂ的第一个子结点（从左到右算起）返回10，第二个子结点返回了-5，第三个子结点返回了２。由于结点Ｂ这层是你的对手来做选择，我们假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为-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的剩余子结点的大量工作，从而节省了宝贵时间，为在同样机器配置下搜索更多的层数提供了可能。 内容来自论文无忧网 www.paper51.com “最小-最大”的思想再加上“对树的裁剪”，这就是Alpha-Beta搜索算法的核心。最基本的Alpha-Beta算法的代码如下： 内容来自www.paper51.com
int AlphaBeta(int depth, int alpha, int beta) 内容来自论文无忧网 www.paper51.com { 内容来自www.paper51.com if (depth == 0) //如果是叶子节点（到达搜索深度要求） 内容来自论文无忧网 www.paper51.com
return Evaluate(); //则由局面评估函数返回估值 paper51.com
GenerateLegalMoves(); //产生所有合法着法 内容来自论文无忧网 www.paper51.com
while (MovesLeft()) //遍历所有着法 paper51.com
{ copyright paper51.com MakeNextMove(); //执行着法 http://www.paper51.com 内容来自www.paper51.com |