Expectiminimax

Expectiminimax is a variant of the minimax algorithm designed for zero-sum, two-player games that incorporate elements of chance, such as dice rolls or card draws. Unlike standard minimax which assumes an optimal adversary, expectiminimax introduces chance nodes that compute the mathematical expectation (expected value) of possible outcomes. This formalization accounts for stochastic environments, bridging deterministic adversarial search with probabilistic decision theory.

from dataclasses import dataclass
from enum import Enum
from typing import List, Tuple, Union

class NodeType(Enum):
    MAX = 1
    MIN = 2
    CHANCE = 3

@dataclass(frozen=True)
class GameState:
    board_score: float
    is_terminal: bool
    node_type: NodeType
    probabilities: Tuple[float, ...] = ()

def expectiminimax(state: GameState, depth: int) -> float:
    if depth == 0 or state.is_terminal:
        return state.board_score

    if state.node_type == NodeType.MAX:
        max_eval = float('-inf')
        for child in get_successors(state):
            eval = expectiminimax(child, depth - 1)
            max_eval = max(max_eval, eval)
        return max_eval

    elif state.node_type == NodeType.MIN:
        min_eval = float('inf')
        for child in get_successors(state):
            eval = expectiminimax(child, depth - 1)
            min_eval = min(min_eval, eval)
        return min_eval

    elif state.node_type == NodeType.CHANCE:
        expected_value = 0.0
        successors = get_successors(state)
        for child, prob in zip(successors, state.probabilities):
            expected_value += prob * expectiminimax(child, depth - 1)
        return expected_value

    raise ValueError(f"Unknown node type: {state.node_type}")

def get_successors(state: GameState) -> List[GameState]:
    # Stub for state transition generation
    return []

import pytest

def test_expectiminimax_chance_node():
    # Test expected value calculation: 0.5 * 10 + 0.5 * 20 = 15.0
    child_max = GameState(board_score=10.0, is_terminal=True, node_type=NodeType.MAX)
    child_min = GameState(board_score=20.0, is_terminal=True, node_type=NodeType.MIN)
    
    chance_state = GameState(
        board_score=0.0,
        is_terminal=False,
        node_type=NodeType.CHANCE,
        probabilities=(0.5, 0.5)
    )
    
    # Mock successors resolution
    global get_successors
    get_successors = lambda s: [child_max, child_min]
    
    result = expectiminimax(chance_state, depth=1)
    assert result == 15.0

from functools import lru_cache

@lru_cache(maxsize=65536)
def memoized_expectiminimax(state_hash: bytes, depth: int, node_type_val: int) -> float:
    # Production implementation incorporating transposition tables
    pass

Mathematical Foundation and Recurrence Relations

Expectiminimax formalizes decision-making under uncertainty in deterministic, alternating, zero-sum games with stochastic elements. Let S be the state space, partitioned into maximizing player states S_max, minimizing player states S_min, and chance states S_chance. The value function V(s, d) at depth d is defined recursively as follows: For s in S_max: V(s, d) = max over a in A(s) { V(Transition(s, a), d – 1) }. For s in S_min: V(s, d) = min over a in A(s) { V(Transition(s, a), d – 1) }. For s in S_chance: V(s, d) = sum over i { P(o_i | s) * V(Transition(s, o_i), d – 1) }, where o_i represents distinct stochastic outcomes with respective probabilities P(o_i | s) summing to 1.0.

Complexity Analysis and Branching Explosion

The time complexity of expectiminimax expands catastrophically compared to standard minimax. If the average branching factor of adversarial moves is b and the average branching factor of chance events is c, the worst-case time complexity is O(b^m * c^d), where m is the ply depth of adversarial decisions and d is the ply depth of chance events. This exponential tree growth severely limits search depth. Space complexity remains linear relative to the recursion depth, bounded at O(m + d) for depth-first traversal, or up to O(b^m * c^d) when employing transposition tables for memoization.

Limitations of Alpha-Beta Pruning

In deterministic minimax, alpha-beta pruning significantly reduces the search space by bounding evaluation windows. In expectiminimax, standard alpha-beta pruning is generally inapplicable because chance nodes compute expected values. Multiplying probability weights across nodes can distort static bounds unless specific conditions are met. Pruning algorithms designed for expectiminimax (such as *Expectiminimax Alpha-Beta* or *Refimax*) require strict bounds on utility values (e.g., utility functions bounded within [0, 1]) to safely prune branches where expected values cannot cross established thresholds.