alphabetic alphabetical,AlphaBeta

　　Bruce Moreland/最小值-最大值问题Alpha-Beta和“最小值-最大值”很像，其实只是多了一个语句。在最小运行时，检查整个游戏树，然后尽可能选择最佳路线。这个很好理解，但是效率很低。每次深入搜索，树的大小都会呈指数级增长。通常一个棋局大概有35个合理的走法，所以如果用min-max搜索一层的深度，有35个情况要查，用这个函数搜索两层，有352个情况要查。已经几千了。看起来不多，但是数量增长非常快。比如六楼搜索接近20亿，十楼搜索超过2万亿。如果您想要检查搜索树的第一层并在叶节点上使用启发式评估，尽可能进行深度搜索是很重要的。Min-max搜索不能做深度搜索，因为有效分支因子太大。幸运的是，我们有一个降低分支因子的方法，非常可靠。其实绝对无害，纯有益。这个方法是基于一个想法。如果你已经有了一个不算太差的选择，那么当你想再做一个选择，并且知道不会更好的时候，你就不需要知道它到底有多差了。有了最好的选择，任何不比它好的选择都已经够糟糕了，完全不了解就可以放在一边。只要你能证明它不比最佳选择更好，你就可以完全抛弃它。你可能还不明白，我举个例子吧。比如你的死敌面前有很多口袋。他跟你打赌输了，所以他得给你点东西。不过挑选规则很奇怪：每个口袋里都有几件物品，你可以拿其中一件。你可以挑这个物品所在的口袋，他会挑这个口袋里的物品。你得掏出口袋赶紧离开，因为你不想一直翻口袋，让你的死敌盯着你。假设你一次只能找到一个口袋，一次只能从口袋里摸出一样东西。很明显，在你掏口袋的时候，你的死敌会把口袋里最差的物品给你，所以你的目标就是把“众多最差物品中的极品”掏出来。你可以很容易地把最小-最大原则应用到这个问题上。你是最大的玩家，你会挑出最好的口袋。而你的死敌是最小的玩家，他会在最好的口袋里挑出最差的物品。运用最小-最大原则，你需要做的就是挑选一个口袋，里面有“最好和最差”的物品。假设你能估算出口袋里每样东西的确切价值，最小最大原则就能做出正确的选择。在我们的讨论题目中，准确的评价并不重要，因为这与min-max或Alpha-Beta的工作原理无关。现在让我们假设你能正确地评估项目。最小值-最大值原理刚刚讨论过，它的问题是效率太低。你必须查看每个口袋里的所有东西，这需要很多时间。那么如何才能做到比min-max更高效呢？我们从第一个口袋开始，查看每个项目并评估口袋。比如口袋里有一个花生酱三明治和一辆新车的钥匙。你知道三明治更糟糕，所以如果你选择这个口袋，你将得到一个三明治。其实只要我们假设对手会和我们一样正确的评价商品，口袋里的车钥匙就无关紧要了。现在你开始翻第二个口袋，这次你的计划和最小最大计划不一样。你一次看一样东西，然后和你能得到的最好的(三明治)比较。只要商品比三明治好，那么你就可以按照min-max计划找到最差的。也许最坏的也比三明治好。那你可以选这个口袋，比那个装三明治的好。例如，这个口袋里的第一件东西是一张20美元的钞票，这比一个三明治要好。

　　如果包里没有别的东西比这个差，那么你选择这个口袋，就是对手必须给你的物品，这个口袋就成了你的选择。这个口袋里的下一件东西是一张六包的流行唱片。如果你觉得比三明治好，但比20美元差，你还是可以选择这个口袋。下一项是一条烂鱼，这次比三明治还难吃。所以你说“不，谢谢”，把你的口袋放回去，不要再想它了。不管你口袋里有什么，也许是另一辆车的钥匙，都没用，因为你会得到那条烂鱼。也许还有比烂鱼更惨的东西(那就随你的便吧)。反正烂鱼已经够惨了，你也知道挑三明治口袋会更好。算法Alpha-Beta就是这样工作的，只能通过递归实现。后面再说最小方的策略。我希望这一点会更清楚。这个想法是在搜索中传递两个值。第一个值是Alpha，这是搜索到的最佳值。任何比它小的值都没用，因为策略就是知道Alpha的值，任何小于等于Alpha的值都不会提高。第二个值是，对对手来说是最差的值。这是对手能承受的最坏的情况，因为我们知道，在对手看来，他总会找到一个不比差的对策。如果在搜索过程中返回或者比更好的值，就足够好了，下棋的人就没有机会使用这个策略了。当搜索一个咒语时，每个被搜索的咒语返回一个与Alpha和Beta相关的值。它们之间的关系非常重要，这可能意味着搜索可以停止并返回。如果一个方法的结果小于或等于Alpha，那么它就是一个差的方法，所以可以丢弃。因为我前面说了，在这个策略中，情况是由为棋手评估的。如果某个方法的结果大于等于，那么整个节点都是无效的，因为对手不想走到这种情况，它有其他方法可以避免。所以，如果我们找到的评价大于等于，就证明这个节点不会发生，就不需要再去搜索剩下的合理方法了。如果某个方法的结果大于但小于，那么这个方法可以被棋手考虑，除非以后有变化。所以会不断增加以反映新的情况。有时候合理的方法不超过，这在实战中经常发生。此时不考虑这种情况。因此，为了避免这种情况，我们必须在博弈树的上层选择另一种方法。在第二个口袋里找到烂鱼，相当于超越了Beta。如果口袋里没有烂鱼，那就考虑六盒pop唱片的口袋会比三明治的口袋好，相当于超过了Alpha(上一层)。算法如下，引人注目的部分是在min-max算法上改的：int alpha beta (int depth，int alpha，int beta){ if(depth==0){ return evaluate()；} GenerateLegalMoves()；while(moves left()){ MakeNextMove()；val=-AlphaBeta(深度- 1，-beta，-alpha)；unmake move()；if(val=beta){ return beta；} if(val alpha){ alpha=val；} }返回alpha}去掉吸引眼球的部分，剩下的就是min-max函数了。可以看出现在的算法变化不大。这个函数需要传递的参数有：要搜索的深度，负无穷大是Alpha，正无穷大是beta: val=alpha beta (5，-infinity，infinity)；这样，5级搜索就完成了。当我写Min-Max函数时，我使用了一个技巧来避免使用“Min”函数和“Max”函数。在那个算法中，当我从递归中返回时，我简单地取一个负数作为返回值。这样，函数值在每次递归中改变评估的角度，以反映双方玩家的交替，他们的目标是相反的。我们在-函数中做了同样的事情。唯一让算法变得复杂的是和可以不断互换。

　　当函数递归时，Alpha和Beta不仅取负数而且交换位置，这使得情况比口袋示例更复杂，但可以证明它只是比min-max算法好。最终在搜索树的很多地方，Beta很容易被超越，所以省略了很多工作。这个算法可能的弱点很大程度上取决于该方法的搜索顺序。如果总是先搜索最差解，那么截断就不会发生，所以这个算法就跟min-max一样，效率很低。该算法最终将搜索整个博弈树，就像最小-最大算法一样。如果程序总是能先选择最佳方法进行搜索，那么数学上的有效分支因子就接近实际分支因子的平方根。这是Alpha-Beta算法所能达到的最好结果。因为象棋的分支因子约为35，这意味着Alpha-Beta算法可以使象棋搜索树的分支因子变为6。这是一个很大的进步。在搜索节点数量不变的情况下，你的搜索深度可以翻倍。这就是为什么用Alpha-Beta搜索的时候，拼写的顺序很重要。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。