期望极小极大值的复杂度

如果程序能够提前知道游戏后面出现的所有掷骰子结果，那么解决这样的有骰子的游戏和没有骰子的游戏就是一样的了，用极小极大值算法要花费的时间为 O(bm)。因为期望极小极大值还要考虑所有可能的掷骰子序列，它需要花费的时间为O(bmnm)，其中n是不同掷骰子结果的数目。

尽管搜索深度被限制在某个比较小的深度 d，但是和极小极大值搜索相比额外的代价使得在大多数包含几率的游戏中向前考虑得很远是不现实的。在双陆棋中，n是21，而b通常大约为20，但是在某些情况下当掷出相同骰子数的组合时，b可能高达4000。所以我们实际可能考虑的只有3层。

考虑这个问题的另一种方式是：α -β剪枝的优势在于采取最佳招数的情况下它忽略了一些未来不会发生的进展。这样，它集中于可能发生的情况。而在有骰子的游戏中，因为招数的生效必须以掷骰子的结果使之成为合法的招数作为前提，所以没有比较可能的行棋序列。每当不确定性进入画面时，这就是一个普遍的问题：可能性急剧增多，制定一个详细的行动计划几乎是无意义的，因为世界很可能不配合。

毫无疑问读者会想到对有几率节点的博弈树使用类似α -β剪枝的技术。确实可以。对于 MAX 和MIN节点的分析不变，不过我们可以剪掉一些几率节点，用一点灵活性。考虑图6.11中的几率节点C在我们检查和评价它的子节点时它的值会发生什么变化。是否有可能在我们观察它的全部子节点前就发现C的值的上界呢？（回想一下，这是在α -β剪枝中剪掉一个节点和它的子树所需要的条件。）乍一看这好像是不可能的，因为C的值是它的子节点值的平均。直到我们看到所有掷骰子的结果之前，由于未检查的子节点可能有任意值，所以平均值也可能是任意值。但是如果我们限制效用函数的可能值的范围，我们就可以得到平均值的界限了。例如，我们限制所有的效用值在−3 到+3 之间，那么叶节点的值是有界的，也就是说我们不用看几率节点的子节点就可以设置几率节点的值的上界。