expectiminimax

Expectiminimax is a decision-making algorithm used in game-playing artificial intelligence to determine optimal moves in games that combine adversarial competition with random events. It extends the minimax framework by incorporating chance nodes to model stochastic elements such as dice rolls, shuffled decks, or other probabilistic outcomes.

In an expectiminimax game tree, there are three types of nodes: max nodes represent the choosing player's turn and seek to maximize the value; min nodes represent the opponent's turn and seek to minimize the value; and chance nodes represent stochastic events with a known probability distribution over their outcomes. The value at a max node is the maximum of the values of its children, the value at a min node is the minimum, and the value at a chance node is the expected value, computed as the probability-weighted average of its children’s values.

The algorithm proceeds by recursively evaluating nodes down to terminal states or until a depth limit is reached, applying these update rules at each node type to propagate values back up to the root, where the best move is selected based on the root’s value.

Expectiminimax is commonly applied to two-player zero-sum games that involve randomness, such as backgammon or other dice-based games, where uncertainty arises from elements outside both players’ control. It is more general than expectimax, which omits adversarial min nodes and is used for single-agent planning with stochastic outcomes.

Because of the triple-node structure, expectiminimax has exponential complexity in depth, and while alpha-beta pruning can be adapted, its benefits are more limited compared to pure minimax due to the presence of chance nodes.