How does expectiminimax differ from minimax?

It adds probability-weighted backups for chance nodes.

Does it predict the exact result of a random game?

No. It evaluates expected utilities under the modeled choices and probabilities.

Is a depth-limited result exact?

Not generally. If nonterminal leaves use heuristic evaluations, the result inherits their approximation error.

AI Glossary / Graphs and symbolic AI / Intermediate

Expectiminimax

Definition

Expectiminimax is a game-tree search method that extends minimax to include random events. It evaluates a maximizing player's choices, a minimizing opponent's choices, and chance outcomes using different rules. Decision nodes take a maximum or minimum, while chance nodes use a probability-weighted average of their successors' values.

What it means

Minimax models an opponent who chooses actions to reduce the maximizing player's outcome. Random events, such as a die roll, do not make strategic choices. Treating them as a hostile opponent would answer a different question.

Expectiminimax combines the two sources of uncertainty within one tree. It is classically used for finite, fully specified, two-player zero-sum games with chance and appropriate information assumptions. The maximizing player seeks the best expected utility against an opponent who minimizes that same utility.

The method is not a general solution to every game involving randomness. Hidden information, simultaneous choices, unknown probabilities, or non-zero-sum preferences require additional modeling and can call for different solution methods.

How it works

Construct a tree whose nodes identify whether MAX, MIN, or chance determines the next transition. Terminal nodes have utilities measured from MAX's perspective.

Evaluate the tree from the leaves upward. At a MAX node, retain the largest successor value. At a MIN node, retain the smallest. At a chance node, multiply each successor value by its transition probability and sum the results. Probabilities must describe mutually exclusive outcomes and sum to one at that node.

At the root, choose an action that attains the appropriate best value. If the search reaches all terminal outcomes in the finite modeled game, the result reflects those exact utilities and probabilities.

Large trees often require cutoffs and heuristic evaluations. Then the returned values are estimates rather than exact solved-game values. The evaluation scale matters because chance-node averaging uses numerical magnitudes, not merely the ranking of leaf positions.

Three practical examples

1. A board-game agent evaluates moves that will be followed by a random roll and then an opponent's response.

2. A game-design simulation compares strategies under explicit random-event probabilities while assuming adversarial choices at opponent turns.

3. An AI lesson uses a small tree to distinguish an opponent selecting a damaging response from nature producing an unfavorable outcome by chance.

Think of it this way

Think of three different people passing scores upward through a tournament diagram. One keeps the largest score, one keeps the smallest, and the third calculates a weighted average according to a random draw.

The analogy has limits: chance is not a person, and the tree must represent who can observe what before choosing. Changing that timing changes the game even if the same numerical outcomes appear at its leaves.

Worked example

Suppose MAX chooses between A and B. After A, a random event has two possible outcomes. The first occurs with probability 0.25 and leads to a MIN node with terminal payoffs 8 and 2. MIN selects 2. The second occurs with probability 0.75 and leads to payoffs 6 and 4. MIN selects 4.

Thus A has value 0.25 × 2 + 0.75 × 4 = 3.5. The opponent is assumed to observe which chance outcome occurred before choosing its response.

After B, MIN chooses between terminal payoffs 3 and 5, giving B a value of 3. MAX therefore chooses A because 3.5 exceeds 3.

If the chance node after A were incorrectly treated as a MIN node, A would receive value 2 and MAX would choose B. That would be a worst-case treatment of nature, not the expected-utility calculation specified here.

Choosing A does not guarantee a realized payoff of 3.5. Under the modeled opponent response, the actual payoff is 2 or 4. The value 3.5 summarizes their probability-weighted combination.

Illustrative case study

Fictional case: Willow Games tests an agent for a small dice-based game. Its first implementation applies a minimum operation at every node not controlled by the agent, including dice outcomes.

The developer separates chance nodes from opponent nodes and verifies a small hand-calculated tree before using deeper search. The team also checks that its representation reveals the roll to the opponent at the correct point. The case illustrates that node type and information timing are essential parts of the game model, not implementation details that can be interchanged freely.

Common misconceptions and mistakes

Do not average opponent moves unless the model deliberately assigns a probability distribution to that opponent's behavior. Classical MIN assumes adversarial choice.

Do not take an unweighted average when chance outcomes have unequal probabilities.

Avoid assuming ordinary alpha-beta cutoffs apply unchanged to arbitrary chance nodes. Bounds and probability contributions must be handled correctly for valid pruning.

Do not use an arbitrary nonlinear transformation of evaluation scores and expect decisions to remain unchanged. A transformation can preserve leaf rankings while altering the weighted averages that drive earlier choices.

Business use

Expectiminimax is useful for game AI and controlled adversarial simulations where random events and strategic responses are explicitly modeled. It also teaches a transferable distinction between uncertainty caused by another decision-maker and uncertainty caused by a stochastic process.

Before applying it to a business simulation, verify whether the zero-sum opponent assumption is justified. Partners or customers may not behave like a player minimizing the organization's utility. Evaluate the resulting policy against the assumptions actually used rather than calling it universally optimal.

Check your understanding

Why does MIN choose 2 rather than averaging 8 and 2 in the first branch of A?

Answer: That node represents an opponent's deliberate minimizing choice. The weighted average belongs at the preceding chance node, whose outcome is random.

Related terms

Learn next

Study minimax first, then add a chance node with unequal probabilities. Calculate the tree by hand and label every backup operation. Next, change the observation timing and check whether the same decision tree still represents the intended game.

Sources

Primary source: Russell and Norvig, Game Playing, sections on nondeterministic games and expectiminimax: https://aima.cs.berkeley.edu/slides-pdf/chapter06.pdf

The worked tree and fictional case are original. Scope is the classical MAX/MIN/chance model; complete-search claims are distinguished from cutoff-based approximations.

Previous: Expected value Next: Expectiminimax value