α-β搜索

2.6　α-β搜索

极小极大搜索在搜索过程中需要检查一定深度的整棵博弈树，然后尽可能选择最好的路线上的节点序列。这种考虑非常全面，对所有搜索分支不会有所遗漏，但是同时也造成了效率的低下。每次搜索更深一层时，树的节点数目就呈指数式增长。对于9×9围棋来说，我们可以做一个保守的假设，如果平均每个盘面都有40个可能的选择，如果搜索两层，就有大约40×39个盘面要搜索，属于10³这个数量级，并不算很大，但是其盘面树和搜索深度D的关系为40！/（40-D）！，对于D＝5，其要搜索的盘面数为10⁷数量级，当D＝10时，则上升到10¹⁵数量级，如果想将博弈树完全展开，树的规模可想而知，对于当前计算机的计算性能来说，无论是时间上还是空间上都不可能实现。

α-β搜索算法是于1958年由卡耐基-梅隆大学的3位学者（Newell、Shaw和Simon）最先提出的。该算法的提出，使得计算机在解决选择性问题上有了一个突破。这个算法有着坚实的数学基础，并不局限于某一类具体问题。α-β剪枝基于这样一种思想：如果已经有一个还不错的选择A，而对于其他的选择B、C、D、…，如果不会比这个选择更好，那么就没有必要知道它们究竟不好到一个什么程度；当有了一个好的选择，其他任何一个不比它好的选择我们都可以看做已经足够坏了，因此完全可以不必深究它们究竟坏到什么程度就可以直接放弃掉这些选择了。

为了帮助理解，我们可以举个形象些的例子；仍然是两个人A和B，有一些袋子，每个袋子里各有几个乒乓球，每个乒乓球上都随机写着1～100这一百个数字中的任意一个数字。规则如下：A首先挑选一个袋子，B从这个袋子里随机挑出一个球给A，其中A和B都可以翻看袋子里的球，A要尽可能地保证B最后递给A的球上的数字尽可能的大，B则会在袋子里挑选出一个数字尽可能小的球出来。

如果将极小极大搜索运用到这个问题上，A是“极大”的一方，要挑出最好的口袋，B则是“极小”的一方，要挑出数字尽可能小的球。对于极小极大搜索来说，A必须查看每个袋子中的每个小球，如果袋子很多，这将会浪费掉大量时间。

为了节省A查看袋子的时间，A采用另一种更加高效的策略。A打开第1个口袋，里面有3个球，发现上面分别写着17、25、33，现在A去打开第2个口袋，现在A采用另一个策略，每拿出一个球之后，就和第1个袋子里最小的数字17做比较，如果每个球上的数字都比17要大，那么则放弃第一个袋子，以第2个袋子中球上的最小数字作为基准来查看第3个袋子；否则，如果在第2个袋子里碰到球上的数字比17还小的时候，就立即放弃第2个袋子，继续以17为基准去查看第3个袋子。

例如，第2个袋子里的第1个球上写着37，它比17要大，那么接着看其他的球，分别为42和29，那么A则暂时把第二个袋子作为最佳候选；如果第二个袋子里的第二个球上写的不是42，而是4，小于17，A则还继续将第一个袋子作为暂时的最佳选择。据此，依次地翻看接下来的每个袋子。

这也就是α-β剪枝策略，对于当有了一个还不错的选择，对于其他任何一个不比它好的选择我们都可以看作已经足够坏了，也就是说当看到4时我们已经可以确定第二个袋子已经没有第一个袋子好了，袋子里还没被查看过的球究竟是写着1还是100已经不重要了，也就是完全可以不必深究它们究竟不好到了一个什么样的程度就可以直接放弃掉这些选择了。

α-β搜索算法的伪代码如算法2.5所示。其中参数β表示前面对手的最佳选择，如果α比最佳选择差，则放弃本节点的搜索。在该算法对子节点的递归调用中，根据对称关系，-β成为进一步剪枝搜索中的α，-α成为进一步剪枝搜索中的β。该算法在第7行实行β剪枝。

算法2.5　α-β算法的伪代码

在α-β搜索算法中，［α，β］从本质上定义了搜索结果所存在的窗口。这个搜索窗口在α-β搜索算法中的初始值是（-∞，∞）。在α-β搜索算法的执行过程中，这个搜索窗口逐渐缩小，直至缩小到搜索窗口的大小为零，即一个点，该点即是最终的搜索结果。

搜索窗口的大小与α-β搜索算法的剪枝能力是有直接关系的，搜索窗口越小，条件就越苛刻，满足条件的节点就越少，因此剪枝能力就越高。虽然α-β搜索算法在初始阶段剪枝能力较弱，但该算法的优点是通过保守的剪枝来保证总能正确返回最终的结果。

为了提高α-β搜索算法的剪枝能力，我们可以把其搜索窗口的初始值设置得比较小，这中改进方法就是渴望搜索（Aspiration Search）。在极端的情况下，我们可以把α和β设为相同，这种技术叫做零窗口搜索，或空窗口搜索，或侦查搜索。

渴望搜索的效率在很大程度上取决于其初始搜索窗口的选定。如果初始搜索窗口选择准确，即所要搜索的最终结果就在这个窗口内，渴望搜索便可以进行大量剪枝，并快速返回最终结果，也有可能搜索的最终结果不在这个窗口内。如果渴望搜索的返回结果大于β，那么最终结果是在搜索窗口［β，∞）内；如果渴望搜索的返回结果小于α，那么最终结果将落在搜索窗口（-∞，α］内。对于以上两种情况，就需要在新窗口内重新搜索。因此，如果初始搜索窗口选择准确，渴望搜索就可以大大缩短搜索时间；如果不准确选择，渴望搜索的剪枝优势就不明显了。

渴望搜索可以被视为一种基本的搜索方法，它与迭代加深搜索算法结合使用的时候，就可以利用前面深度较浅的搜索结果来较准确地估计当前深度的搜索窗口。