4、搜索算法

 搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着计算机的下棋水平。因为，计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，经前人的努力已形成了非常成熟的Alpha-Beta搜索算法[ Alpha-beta算法，该算法是由匹兹堡大学的三位科学家Newell, Shaw and Simon于1958年提出的。]以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变种算法）。鉴于目前我们的知识储备、时间、精力等均达不到推陈出新、另开炉灶的要求，再加之前人的算法着实已相当完善，所以我们在自己的程序中直接借鉴了Alpha-Beta搜索算法并辅以了历史启发。本节先介绍Alpha-Beta搜索算法：
 在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是将死对方，或者避免被将死。
 由此，我们可以用一棵“博弈树”（一棵n叉树）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的模型大概如下图所示，我们可以把其中连接结点的线段看作是着法，不同的着法自然产生不同的局面。
 
 该树包含三种类型的结点：
奇数层的中间结点（以及根结点），表示轮到红方走棋；
偶数层的中间结点，表示轮到黑方走棋；
叶子结点，表示棋局结束。
 现在让计算机来下中国象棋，它应当选择一步对它最有利的着法（最终导致它取胜的着法）。获得最佳着法的方法就是“试走”每一种可能的着法，比较它们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的着法。
 结合上面所讲的博弈树，如果我们给每个结点都打一个分值来评价其对应的局面（这一任务由后面所讲的局面评估来完成），那么我们可以通过比较该分值的大小来判断局面的优劣。假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果我们假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上我们会挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上我们会选择分值最小的结点。这就是“最小-最大”（Minimax）[ “最小-最大”（Minimax）最早是由John von Nuoma（1903-1957，美籍匈牙利数学家）在60多年前完整描述的：
　　1、假设有对局面评分的方法，来预测棋手甲（我们称为最大者）会赢，或者对手（最小者）会赢，或者是和棋。评分用数字表示，正数代表最大者领先，负数代表最小者领先，零代表谁也不占便宜；
　　2、最大者的任务是增加棋盘局面的评分（即尽量让评分最大）；
　　3、最小者的任务是减少棋盘局面的评分（即尽量让评分最小）；
 4、假设谁也不会犯错误，即他们都走能让使局面对自己最有利的着法。]的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的着法。然而不幸的是，博弈树相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O(bn)。其中b是分枝因子，即针对各种局面的合法着法的数目的平均值，n是搜索的深度。对于中国象棋而言，在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线！！！
 幸运的是，Alpha-Beta搜索使得我们能在不影响搜索精度的前提下大幅减少工作量。
 因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向（我们假定下棋双方对棋局有着同样的认知，即你认为对你很糟糕的局面，在你的对手看来则是对他很有利的局面），那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时（确切地说这里的“很糟糕”是与之前分析的情况相比较而言的），你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟……这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“树的裁剪”。
 下面用图来进一步说明“树的裁剪”。为了简便起见，我将博弈树进行了简化——每个结点只有三个分支，实际情况中，刚才讲过在中盘应有大约40个分支

首页 上一页 1 2 3 4 5 6 7 下一页 尾页 2/7/7

相关论文