分析

因为AlphaBeta返回的结果和Minimax以及NegMax计算出来的几乎相同,那么唯一能够看出AlphaBeta好处的地方就是检查生成的博弈树的规模。这个任务是非常复杂的,因为如果对手的最优走法首先被评价,AlphaBeta能够节省大量的时间。当每个局面状态有b个可行走法时,追寻深度为d的AlphaBeta算法可能搜索的状态数目大约为bd。如果走法是按照某种顺序降序排列,那么我们仍然需要评价所有的b个子节点(因为我们要选择最优的走法),但是,最好情况下我们只需要评价对手的第一种走法。在图7-21中,由于走法有序,在评价了一些走法之后,就能够进行剪枝,所以在这棵博弈树下,走法排序并不是最优的。

最好情况下,AlphaBeta在每一级为玩家评价b个局面状态,但是只评价对手的一个局面状态。所以,在博弈树的第d级,AlphaBeta只需要评价b*1*b*……*b*1个局面状态,而不是扩展出b*b*b*……*b*b个局面状态。所以局面状态的总数是bd/2,节省了巨大的开销。AlphaBeta并不会试图简单地最小化状态的数目,AlphaBeta扩展的数目有可能和Minimax一样多,但是这种情况下,AlphaBeta扩展的深度是Minimax的两倍。

从经验上来比较Minimax和AlphaBeta,我们构建了一个一字棋初始棋面状态的集合,这些棋面状态至少能够走k步。然后定义追寻深度为d=9-k,保证所有可能的走法都会探测到,然后对比Minimax和AlphaBeta。结果见表7-5。我们看到AlphaBeta算法剪除掉了大量的状态。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

阅读 ‧ 电子书库

每个比较都说明了AlphaBeta的巨大改进。而且有些情况能够解释为什么AlphaBeta如此优秀,例如这个局面状态:

阅读 ‧ 电子书库

AlphaBeta只需扩展47的局面状态(Minimax需要扩展8232个,节省了99.4%)来告知玩家X应该选择中间的方块。但是,能够得到这样大的性能改进的前提是可行走法有序,并且最优走法排在最前面。因为我们的一字棋的解不会排序走法,可能会得到一些异常结果。例如,将上面的棋面旋转180°:

阅读 ‧ 电子书库

那么AlphaBeta只需要探测960个局面状态(节省了88.3%)。