Expectimax 算法

• 9 min read • 1679 words
Tags: Adversarial Search Games
Categories: Introduction to Artificial Intelligence

Expectimax 算法

1. Expectimax 概念

Minimax算法的核心假设是对手总是做出最优选择，这使其在面对非最优或随机对手时显得过于悲观。例如，在棋牌或骰子游戏中，结果本身具有不确定性，Minimax的“最坏情况”分析不再适用。

Expectimax搜索是Minimax的泛化，专门用于处理这类不确定性。它在博弈树中引入了机会节点（Chance Nodes） 来取代Minimax中的最小化节点（Minimizer Nodes）。

  • 最小化节点：计算其子节点中的最小值（最坏情况）。
  • 机会节点：计算其子节点值的期望值（平均情况）。

通过这种方式，Expectimax能够基于概率对未来的不确定状态进行建模和决策。

2. Expectimax 算法原理

Expectimax对博弈树中不同类型节点的值计算规则进行了调整。

a.a. 状态值递归定义

我们将状态 ss 的值记为 V(s)V(s)，其递归定义如下：

  • MAX 节点（我方）：与Minimax相同，选择能够导向最大子节点值的行动： V(s)=max⁡s′∈successors(s)V(s′)V(s) = \max_{s' \in \text{successors}(s)} V(s')
  • 机会节点（随机事件/对手）：计算所有可能结果的加权平均值，权重为每个结果发生的概率： V(s)=∑s′∈successors(s)p(s′∣s)V(s′)V(s) = \sum_{s' \in \text{successors}(s)} p(s'|s) V(s')
  • 终止状态： V(s)=known valueV(s) = \text{known value}

在这里，p(s′∣s)p(s'|s) 指的是从状态 ss 转移到后继状态 s′s' 的概率。这个概率可以来源于游戏的随机元素（如掷骰子）或对非最优对手行为的建模（如假设对手有50%的概率向左，50%的概率向右）。

b.b. 与Minimax的关系

Minimax可以被视为Expectimax的一个特例。一个最小化节点等价于一个特殊的机会节点，该机会节点将其所有子节点中值最低的那个赋予100%的概率，而其他所有子节点的概率均为0。

c.c. 代码实现

算法结构与Minimax非常相似，只是将min_value函数替换为了expected_value函数。

def expectimax_value(state):
    """
    Returns the expectimax value of a state.
    """
    if state.is_terminal():
        return state.get_utility()

    agent_type = state.get_agent_to_move_type() # MAX or CHANCE

    if agent_type == "MAX":
        # MAX player wants to maximize the value
        return max(expectimax_value(s) for s in state.get_successors())

    elif agent_type == "CHANCE":
        # Chance node computes the expected value
        total_value = 0
        successors = state.get_successors()
        num_successors = len(successors)

        for successor_state, probability in state.get_successor_probabilities():
            # probability is p(s'|s)
            total_value += probability * expectimax_value(successor_state)

        return total_value

def get_expectimax_action(state):
    """
    Returns the optimal action for the MAX player.
    """
    best_action = None
    best_value = -float('inf')

    for action in state.get_legal_actions():
        successor = state.generate_successor(action)
        value = expectimax_value(successor)

        if value > best_value:
            best_value = value
            best_action = action

    return best_action

3. Expectimax 的特性与扩展

a.a. 剪枝

一个重要的结论是：在通用情况下，Alpha-Beta剪枝对机会节点无效：在计算期望值时，必须考虑所有子节点。一个值极大但概率很小的分支，或者一个值极小但概率很小的分支，都可能对最终的期望值产生显著影响。我们无法像在Minimax中那样，仅凭一个子节点的值就断定整个分支的优劣并将其剪掉。只有在能够确定所有可能值的上下界时，才有可能实现某种形式的剪枝。

b.b. 混合层类型

现实中的游戏通常比严格的“我方-敌方”交替更为复杂。Expectimax框架的强大之处在于其灵活性，允许我们构建混合层（Mixed Layer） 的博弈树。以Pacman游戏为例：

  • 多对手合作：在Pacman游戏中，如果有多只鬼，可以在一个MAX层（Pacman）之后连接多个连续的MIN层（Ghosts）。这自然地模拟了鬼之间的合作，因为它们会轮流行动，共同将Pacman的最终得分最小化。
  • 混合最优与随机对手：如果一个游戏中有两只鬼，一只是最优的（Minimax行为），另一只是随机的（Random行为），则博弈树可以是一个MAX -> MIN -> CHANCE的交替结构。

这种灵活性使得我们可以为几乎任何零和博弈构建一个定制的、能够准确反映游戏规则的Minimax/Expectimax混合搜索算法。