1. 简介
在本文中，我们将介绍 Expectimax（期望最大化）搜索算法，它适用于解决非确定性游戏中的对抗性问题。
我们主要关注的是包含随机元素的双人博弈，比如掷骰子等。由于 Expectimax 是 Minimax 的变种，因此我们也会先介绍 Minimax，它是用于确定性游戏的经典算法。
2. 对抗性搜索
在经典搜索中，AI 智能体通过寻找一系列最优动作来达成目标。在这个过程中，只有智能体自己可以对环境施加影响。
而在对抗性搜索中，环境中有至少一个其他智能体参与博弈，双方目标冲突，因此需要考虑对手的行为。智能体不仅要建模自己的状态，还要建模对手的状态。
典型的对抗性搜索应用场景包括象棋、扑克等双人或多人游戏。
3. 游戏定义
在 AI 博弈中，游戏的状态通常被称为“位置”，动作被称为“移动”。一个游戏的定义包括以下几个核心组件：
S₀：初始状态turn(s)：返回在状态s中轮到谁行动moves(s)：返回状态s中合法的移动集合result(s, a)：返回在状态s中执行动作a后的新状态terminal(s)：判断状态s是否为终止状态utility(s, p)：返回玩家p在终止状态s中的效用值（得分）
我们关注的是零和博弈（zero-sum games），即所有玩家在终止状态下的效用值总和为 0。这意味着一方最大化自己的效用就等于另一方的损失。
4. 确定性游戏
在确定性游戏中，环境、动作选择和状态转移都是完全确定的。例如井字棋（Tic-Tac-Toe）就是一个典型例子。
对于这类游戏，我们使用经典的 Minimax 算法 来寻找最优策略。
4.1. Minimax 算法原理
Minimax 算法中包含两个角色：
- MAX：我们的 AI 智能体，试图最大化自己的效用
- MIN：对手，试图最小化 MAX 的效用
算法通过递归构建一个博弈树，从当前状态出发，模拟所有可能的移动路径，计算每个节点的 Minimax 值：
minimax(u) = {
utility(u, MAX), 如果 u 是终止节点
max{minimax(result(u, a))}, 如果当前是 MAX 的回合
min{minimax(result(u, a))}, 如果当前是 MIN 的回合
}
最终，MAX 会选择能使结果值最大的动作。
4.2. 伪代码实现
algorithm Minimax(game_description, u, player):
(move, value) <- MAXVALUE(u, player)
return move
function MAXVALUE(u, player):
if terminal(u):
return (null, utility(u, player))
(best_move, max_value) <- (null, -infinity)
for move in moves(u):
(min_move, value) <- MINVALUE(result(u, move), player)
if value > max_value:
best_move, max_value = move, value
return (best_move, max_value)
function MINVALUE(u, player):
if terminal(u):
return (null, utility(u, player))
(best_move, min_value) <- (null, +infinity)
for move in moves(u):
(max_move, value) <- MAXVALUE(result(u, move), player)
if value < min_value:
best_move, min_value = move, value
return (best_move, min_value)
在实际应用中，我们通常会对搜索树进行剪枝（如 Alpha-Beta 剪枝）或限制搜索深度，以提高效率。
5. Expectimax 算法
5.1. 与 Minimax 的区别
与确定性游戏不同，随机性游戏（stochastic games） 包含概率因素。例如：
- 某些动作可能产生多个结果，每个结果对应一个概率
- 某些动作的选择依赖于随机事件（如掷骰子）
在这种情况下，Minimax 不再适用，我们需要引入 Expectimax 算法。
5.2. 引入 Chance 节点
Expectimax 在博弈树中引入了 Chance 节点（机会节点），表示在该节点上，动作的选择依赖于概率分布。
Expectimax 值的计算公式如下：
expectimax(u) = {
utility(u, MAX), 如果 u 是终止节点
max{expectimax(result(u, a))}, 如果当前是 MAX 的回合
min{expectimax(result(u, a))}, 如果当前是 MIN 的回合
sum{P(r) * expectimax(result(u, r))}, 如果当前是 Chance 节点
}
其中 r 是随机事件的结果，P(r) 是其发生的概率。
5.3. 伪代码实现
algorithm Expectimax(u, player):
(move, value) <- EXPECTIMAX_VALUE(u, player)
return move
function EXPECTIMAX_VALUE(u, player):
if u is a chance node:
expected = 0
for r in moves(u):
(move, value) <- EXPECTIMAX_VALUE(result(u, r), player)
expected += P(r) * value
return (null, expected)
else if turn(u) == player:
return MAX_VALUE(u, player)
else:
return MIN_VALUE(u, player)
注意：与 Minimax 不同，Expectimax 中的 MAX 和 MIN 节点不再直接调用对方，而是统一调用 EXPECTIMAX_VALUE。
5.4. 剪枝与评估函数
在 Expectimax 中，剪枝技术（如 Alpha-Beta）也可以应用，但需要对评估函数进行上下界约束，才能在未完全展开节点的情况下进行剪枝。
此外，评估函数的设计尤为重要：
- Minimax 只需保持动作顺序正确即可
- Expectimax 要求评估函数是效用值的线性正相关函数
这意味着，即使是小的评估值变化，也可能导致智能体选择不同的动作。
如果评估函数设计困难，可以考虑使用 蒙特卡洛树搜索（MCTS） 来辅助评估。
6. 小结 ✅
- Minimax 适用于确定性游戏，通过模拟对手行为寻找最优策略
- Expectimax 是其扩展，适用于包含随机因素的博弈问题
- Expectimax 引入了 Chance 节点，并使用期望值代替最大/最小值
- 实际应用中通常需要限制搜索深度、使用评估函数或剪枝优化
- 评估函数的设计对 Expectimax 的表现影响更大
总结一句话：
Expectimax 是 Minimax 的概率扩展，适用于包含随机元素的博弈问题，但对评估函数和剪枝策略提出了更高要求。