Expectimax

Expectimax is a decision-making algorithm used for sequential problems that involve randomness in the environment. It is a variant of minimax designed to handle stochastic outcomes by replacing adversarial choices with expected values.

In an expectimax search tree, there are two kinds of nodes. Max nodes represent the decision points of the agent, where the agent selects the action that maximizes expected value. Chance nodes represent random events with a known probability distribution over outcomes, such as dice rolls or shuffled cards. The value of a chance node is the probability-weighted average (expectation) of its children. Leaf nodes are evaluated with a heuristic utility function, and the search is typically depth-limited because of the exponential growth of the tree.

Expectimax is especially applicable to games and problems with uncertainty but no competitive adversary, or where the environment’s randomness dominates the decision-making. Examples include certain dice games, probabilistic planning tasks, and other stochastic environments where the objective is to maximize expected utility rather than guarantee a worst-case outcome. In two-player stochastic games that include an adversary, the related expectiminimax framework extends expectimax by incorporating min nodes to model the opponent’s optimal moves alongside chance nodes for randomness.

Computationally, expectimax shares the exponential complexity of classical search algorithms and often requires pruning or heuristics to be tractable at practical depths. Because chance nodes disrupt straightforward minimax pruning, specialized strategies are used to manage search efficiency. Overall, expectimax provides a principled way to plan under uncertainty by valuing actions according to their expected consequences.