基本搜索方法——Alpha-Beta搜索.doc.doc

《对弈程序基本技术》专题 Alpha-Beta 搜索 Bruce Moreland /文最小- 最大的问题 Alpha-Beta 同“最小-最大”非常相似,事实上只多了一条额外的语句。最小最大运行时要检查整个博弈树,然后尽可能选择最好的线路。这是非常好理解的,但效率非常低。每次搜索更深一层时,树的大小就呈指数式增长。通常一个国际象棋局面都有 35个左右的合理着法,所以用最小-最大搜索来搜索一层深度,就有 35个局面要检查,如果用这个函数来搜索两层,就有 35 2 个局面要搜索。这就已经上千了,看上去还不怎样,但是数字增长得非常迅速, 例如六层的搜索就接近是二十亿,而十层的搜索就超过两千万亿了。要想通过检查搜索树的前面几层,并且在叶子结点上用启发式的评价,那么做尽可能深的搜索是很重要的。最小-最大搜索无法做到很深的搜索,因为有效的分枝因子实在太大了。口袋的例子幸运的是我们有办法来减小分枝因子,这个办法非常可靠,实际上这样做绝对没有坏处,纯粹是个有益的办法。这个方法是建立在一个思想上的,如果你已经有一个不太坏的选择了,那么当你要作别的选择并知道它不会更好时,你没有必要确切地知道它有多坏。有了最好的选择,任何不比它更好的选择就是足够坏的,因此你可以撇开它而不需要完全了解它。只要你能证明它不比最好的选择更好,你就可以完全抛弃它。你可能仍旧不明白,那么我就举个例子。比如你的死敌面前有很多口袋,他和你打赌赌输了,因此他必须从中给你一样东西,而挑选规则却非常奇怪: 每个口袋里有几件物品,你能取其中的一件,你来挑这件物品所在的口袋, 而他来挑这个口袋里的物品。你要赶紧挑出口袋并离开,因为你不愿意一直做在那里翻口袋而让你的死敌盯着你。假设你一次只能找一只口袋,在找口袋时一次只能从里面摸出一样东西。很显然,当你挑出口袋时,你的死敌会把口袋里最糟糕的物品给你,因此你的目标是挑出“诸多最糟的物品当中是最好的”那个口袋。你很容易把最小-最大原理运用到这个问题上。你是最大一方棋手,你将挑出最好的口袋。而你的死敌是最小一方棋手,他将挑出最好的口袋里尽可能差的物品。运用最小-最大原理,你需要做的就是挑一个有“最好的最差的”物品的口袋。假设你可以估计口袋里每个物品的准确价值的话,最小-最大原理可以让你作出正确的选择。我们讨论的话题中,准确评价并不重要,因为它同最小-最大或 Alpha-Beta 的工作原理没有关系。现在我们假设你可以正确地评价物品。最小-最大原理刚才讨论过,它的问题是效率太低。你必须看每个口袋里的每件物品,这就需要花很多时间。那么怎样才能做得比最小-最大更高效呢? 我们从第一个口袋开始,看每一件物品,并对口袋作出评价。比方说口袋里有一只花生黄油三明治和一辆新汽车的钥匙。你知道三明治更糟,因此如果你挑了这只口袋就会得到三明治。事实上只要我们假设对手也会跟我们一样正确评价物品,那么口袋里的汽车钥匙就是无关紧要的了。现在你开始翻第二个口袋,这次你采取的方案就和最小-最大方案不同了。你每次看一件物品,并跟你能得到的最好的那件物品(三明治)去比较。只要物品比三明治更好,那么你就按照最小-最大方案来办——去找最糟的,或许最糟的要比三明治更好,那么你就可以挑这个口袋,它比装有三明治的那个口袋好。比方这个口袋里的第一件物品是一张 20美元的钞票,它比三明治好。如果包里其他东西都没比这