在计算机科学和人工智能的世界里，特别是在博弈论的领域，我们经常需要编写能够做出“聪明”决策的程序。最经典的例子莫过于国际象棋、跳棋或围棋等双人零和博弈游戏。对于这些游戏，我们通常会想到使用 Minimax 算法（极小化极大算法）。然而，现实世界并非总是非黑即白的，我们的对手也并不总是像机器一样毫无破绽。有时候，我们需要面对的是一个充满不确定性的环境，或者是一个会犯错的对手。
这就是我们今天要探讨的主角——Expectimax 算法（期望最大化算法）大显身手的时候。在这篇文章中，我们将深入探讨 Expectimax 算法的原理、它与 Minimax 的区别、核心代码实现，以及它在实际开发中的应用和优化技巧。让我们系好安全带，开始这场概率与决策的探索之旅。
为什么我们需要 Expectimax？
在深入算法之前，让我们先回顾一下老朋友——Minimax 算法。Minimax 的核心思想非常简单且“悲观”：它假设我们的对手（最小化者）是绝对理性的，并且总是采取对我们最不利的策略。为了获胜，我们必须在对手的完美应对下寻找最优解。
但是，你有没有想过这样一个场景：如果你玩的不是棋类游戏，而是像大富翁、扑克牌，或者包含掷骰子机制的电子游戏呢？在这些情况下，对手的行动（或者随机事件）并不是完全针对你的，它们往往遵循某种概率分布。或者，即使是对手，他也可能是一个会失误的人类，而不是一台完美的 Minimax 机器。
如果我们依然使用 Minimax，在这个充满随机性的世界里，我们可能会因为过于保守而错失良机。Expectimax 算法正是为了解决这一问题而诞生的。它不再假设对手会做出最坏的选择，而是考虑所有可能结果的数学期望。
Minimax vs Expectimax：直观对比
让我们通过一个简单的可视化思维模型来看看两者的区别。
#### 1. Minimax 的世界（确定性）
在 Minimax 算法中，树的结构通常是这样的：
- 最大化节点：轮到我们行动，我们会选择得分最高的路径。
- 最小化节点：轮到对手行动，我们假设对手会选择得分最低（对我们最不利）的路径。
假设我们有一棵简单的博弈树，根节点是我们。左边分支对手给我们的分数是 10，右边分支对手给我们的分数是 100。在 Minimax 看来，既然是对手行动，对手肯定会选择让我们得 10 分的那一边（左边），而不是让我们得 100 分的那一边。因此，根节点的值被评估为 10。这就导致了 Minimax 的“保守”。
#### 2. Expectimax 的世界（概率性）
在 Expectimax 算法中，我们引入了一个新的节点类型：机会节点，通常用圆圈表示。这代表了不可控的因素——无论是掷骰子的随机性，还是一个非最优对手的某种行为模式。
让我们看一个具体的例子。假设同样的树结构，现在“对手”变成了一个“随机事件”或“普通水平的对手”：
- 左子树：包含两个结果，值分别为 10 和 10。平均值为 (10+10)/2 = 10。
- 右子树：包含两个结果，值分别为 100 和 9。平均值为 (100+9)/2 = 54.5。
现在，作为最大化者，我们在根节点面临选择：
- 选左边：确定能得到 10。
- 选右边：期望值是 54.5。
即使右边存在得到 9 分的风险，但从数学期望的角度看，54.5 远大于 10。因此，Expectimax 算法会大胆地选择右边。这就是 Minimax 和 Expectimax 最大的区别：一个追求最小风险下的保底，一个追求平均收益的最大化。
Expectimax 算法详解
在 Expectimax 算法中，我们的博弈树主要由两种节点组成：
- 最大化节点：这与 Minimax 相同。我们需要计算所有子节点的值，并返回其中的最大值。
- 机会节点：这是新的角色。我们不取最大也不取最小，而是计算所有子节点的加权平均值。
#### 数学公式
对于一个机会节点，如果它有 $n$ 个子节点，每个子节点发生的概率为 $Pi$，对应的效用值为 $Vi$，那么该机会节点的期望效用 $E$ 计算如下：
$$E = \sum{i=1}^{n} (Pi \times V_i)$$
如果没有任何先验知识，我们通常假设所有结果发生的概率相等（均匀分布），即 $P_i = 1/n$。此时公式简化为简单的算术平均值。
深入代码实现
光说不练假把式。让我们看看如何用代码来实现这个算法。为了方便理解，我们定义一个简单的二叉树结构。
#### 1. 数据结构定义
首先，我们需要定义树的节点。在 C++ 中，我们可以这样写：
// 定义树节点结构
struct Node {
int value; // 节点的值（对于叶子节点）
Node *left, *right; // 左右子节点指针
};
// 创建新节点的辅助函数
Node* newNode(int v) {
Node* temp = new Node;
temp->value = v;
temp->left = NULL;
temp->right = NULL;
return temp;
}
#### 2. Expectimax 核心递归逻辑
这是算法的灵魂所在。我们编写一个递归函数 INLINECODE6c9a7ff4，它接收当前节点和一个布尔标志 INLINECODE94a2f510 来告诉我们当前是“最大化者”还是“机会节点”。
#include
#include // 用于 max 函数
using namespace std;
// Expectimax 算法核心函数
// node: 当前节点
// is_max: 如果是 true，代表最大化节点；如果是 false，代表机会节点
float expectimax(Node* node, bool is_max) {
// 基本情况：如果是叶子节点，直接返回其值
if (node->left == NULL && node->right == NULL) {
return node->value;
}
// 情况 1: 这是一个最大化节点（轮到我们决策）
if (is_max) {
// 我们递归计算左右子树的值，并选择较大的那个
// 注意：这里传递 false 是假设下一层是对手层或随机层
return max(
expectimax(node->left, false),
expectimax(node->right, false)
);
}
// 情况 2: 这是一个机会节点（随机事件或非最优对手）
else {
// 我们递归计算左右子树的值，并返回它们的平均值（期望值）
// 注意：这里传递 true 是假设再下一层又轮到我们决策了
return (
expectimax(node->left, true) +
expectimax(node->right, true)
) / 2.0;
}
}
#### 3. 运行一个完整的实例
让我们构建前面提到的那个树：左边稳健（10, 10），右边高风险高回报（100, 9）。让我们看看算法会选择哪边。
int main() {
/*
构建如下结构的树：
10 100
*/
// 初始化非叶子节点（值可以是任意，因为算法不看它们的 value，只看叶子）
Node* root = newNode(0);
root->left = newNode(0);
root->right = newNode(0);
// 设置叶子节点的值
root->left->left = newNode(10);
root->left->right = newNode(10);
root->right->left = newNode(100);
root->right->right = newNode(9);
// 从根节点开始计算，假设根节点是最大化者
float result = expectimax(root, true);
cout << "计算得到的 Expectimax 值是: " << result << endl;
return 0;
}
输出结果分析：
当你运行这段代码时，输出将是 54.5。这证实了我们的分析：算法无视了左边稳妥的 10 分，果断选择了期望值更高的右边。
实战扩展：不同概率的机会节点
在实际开发中，随机事件往往不是 50/50 的。比如在一个 RPG 游戏中，你的攻击有 80% 的概率命中，20% 的概率Miss。我们需要修改代码来支持这种加权平均。
// 加权版本的 Expectimax
// p_left: 左子节点发生的概率 (0.0 - 1.0)
float weighted_expectimax(Node* node, bool is_max, float p_left) {
if (node->left == NULL && node->right == NULL) {
return node->value;
}
if (is_max) {
// 最大化逻辑不变
return max(
weighted_expectimax(node->left, false, p_left),
weighted_expectimax(node->right, false, p_left)
);
}
else {
// 概率逻辑：左子树概率 * 左值 + (1 - 左子树概率) * 右值
float left_val = weighted_expectimax(node->left, true, p_left);
float right_val = weighted_expectimax(node->right, true, p_left);
return (p_left * left_val) + ((1.0 - p_left) * right_val);
}
}
评估函数的重要性：一个关键陷阱
在使用 Expectimax 时，有一个你必须非常注意的点：评估函数的尺度至关重要。
- 在 Minimax 中：评估函数只需要保持“序数”性质。只要状态 A 优于状态 B，具体的数值差多少并不重要（f(A) > f(B) 即可）。我们可以用 {0, 1, 2} 也可以用 {0, 100, 200}，决策结果是一样的。
- 在 Expectimax 中：评估函数必须保持“基数”性质，也就是数值本身的大小和距离必须是有意义的。
为什么会这样？ 因为我们在做平均计算。如果你有三个叶子节点：[Win(10), Tie(5), Lose(0)]。
如果我们将 INLINECODE7ebdd1d4 改为 INLINECODE4e789704（表示极度厌恶失败），在 Minimax 中，这通常不会改变策略，因为只要能避开 -1000，选什么都一样。但在 Expectimax 中，这巨大的负值会极大地拉低平均值，导致算法为了避险而彻底改变策略。
因此，在设计游戏 AI 时，如果你的评估函数是基于概率的，你必须非常精确地校准这些数值，确保它们真实反映了你对“好坏”程度的量化认知。
优缺点与最佳实践
在决定是否使用 Expectimax 时，我们需要权衡它的优缺点。
优点：
- 更真实的模拟：在涉及骰子、抽卡或非完美对手的游戏中，它的表现远优于 Minimax。
- 利用对手弱点：如果对手容易犯错，Expectimax 可以计算出比 Minimax 更激进的、收益更高的策略。
缺点与挑战：
- 剪枝极其困难：这是最大的痛点。Minimax 中常用的 Alpha-Beta 剪枝依赖于“如果这一步已经比某一步差，就不用算了”的逻辑。但在 Expectimax 中，一个极低的概率值（比如 0.001 * 100000）可能会极大地影响平均值。因此，我们几乎无法进行有效的剪枝，这导致搜索深度通常受限，计算量巨大。
- 非最优性：它是基于概率的。如果那个 1% 概率的坏运气真的发生了，你会输得很惨。
性能优化建议
既然剪枝很难，我们该怎么办？
- 限制搜索深度：这是最直接的方法。结合强有力的启发式评估函数。
- 蒙特卡洛树搜索 (MCTS)：对于复杂游戏，现代 AI 更倾向于使用 MCTS。虽然 MCTS 也基于模拟，但它通过随机采样来估算期望值，比遍历整棵树更高效。
总结
我们通过这篇文章，从理论到代码，全面剖析了 Expectimax 算法。它是连接确定性与随机性世界的桥梁。当你下次需要为游戏设计一个包含“运气”成分的 AI，或者想要模拟人类般的非完全理性对手时，不妨试试 Expectimax。记住，评估函数的精确校准是它成功的关键，而计算复杂度则是你需要权衡的代价。希望你在实际编码中能灵活运用这一强大的工具！