《算法技术手册》分析

图7-17是一字棋游戏中，玩家O采取Minimax搜索时的追寻深度为2的轨迹。交替的MAX和MIN层级告诉玩家，要避免被秒杀，那么在左上角画一个O是唯一走法。注意这里会扩展出所有可能的棋面状态，即使确定玩家X可以稳赢。

博弈树的深度是固定的，我们可以根据追寻长度的走法序列，得到一系列可能的局面状态。当每个局面状态都有固定的b个走法时，追寻深度d的Minimax算法需要搜索的局面状态的总数大约是O(bd)，很明显是指数级增长。

我们看看图7-17的结果，肯定有办法能够消除掉无用的局面状态。玩家MAX试着最大化局面状态的得分，因为每一步都会被评价，玩家MAX计算出他能够保证的最大值maxValue。因为我们假设对手不会犯错，一旦指向一棵MIN子树的走法得到的结果比maxValue要小，那么就不会搜索这棵子树。同样地，玩家MIN尝试着最小化局面状态的得分，并且计算出他能够保证的最小值minValue，一旦指向一棵MAX子树的走法得到的结果比minValue要大，那么就不会搜索这棵子树。我们不会试着处理这两种情况（MAX或者MIN），我们首先讨论一种评价博弈树的替代方案，这个替代方案将会对局面状态使用同样的评论方法，而不是根据博弈树的层级。