Minimax值与Expectimax值对比：A是否始终小于等于E？

结论很明确：是的，A总是小于等于E。下面我来拆解背后的逻辑：

核心差异：Min节点 vs 机会节点的决策逻辑 #

首先得明确两种节点的行为差异：

• 在Minimax树的Min节点中，作为对手的Min方会主动选择对Max最不利的结果，也就是取所有子节点值中的最小值。
• 在Expectimax树的机会节点中，结果是子节点值的加权期望（所有概率非负且总和为1）——相当于“随机选择”后的平均结果，不会刻意偏向最不利的情况。

从单个节点看：Min节点的值 ≤ 机会节点的值 #

假设某个原Min节点有子节点值集合{v1, v2, ..., vn}，对应的概率为{p1, p2, ..., pn}（sum(pi)=1，pi≥0）：

• Min节点的输出是 min(v1, v2, ..., vn)
• 机会节点的输出是 p1*v1 + p2*v2 + ... + pn*vn

根据数学上的均值性质：一组数的加权平均值不会小于这组数的最小值（也不会大于最大值）。所以对单个节点来说，机会节点的输出必然≥原Min节点的输出。

向上传递到根节点 #

游戏树的计算是从叶子节点向上递归的：

1. 对于所有底层的原Min节点替换成机会节点后，它们的值都≥原来的Min节点值；
2. 上层的Max节点会选择子节点中的最大值，由于子节点的候选值都变大了（或不变），Max节点的输出自然也不会变小；
3. 这个逻辑逐层向上传递，最终根节点（Max节点）的Expectimax值E必然≥Minimax值A。

极端情况验证 #

即使出现极端概率分布（比如某个子节点的概率为1，其他为0）：

• 如果概率1对应的是子节点中的最小值，那么机会节点的输出等于Min节点的输出，此时E=A；
• 如果概率1对应的是更大的子节点值，那么机会节点的输出大于Min节点的输出，此时E>A。

无论哪种情况，A≤E的结论都成立。

内容的提问来源于stack exchange，提问作者Vincy