The idea: the opponent is not always perfect
Minimax assumes the opponent always picks the reply that is worst for us. That is right for chess against a strong player. It is too gloomy when the opponent plays at random, or when the next step is a dice roll: a move that is bad only in one unlikely case gets thrown away.
Expectimax keeps the MAX nodes and replaces the MIN nodes with chance nodes. A chance node does not choose. Its value is the expected value of its children: each child's value times its probability, added up.
Pick a tree, then press Minimax or Expectimax, or run a demo. Green numbers on the edges are the probabilities.
Chance nodes add up p × v
The search is the same depth-first walk as minimax. A chance node starts at 0. Each time a child returns a value v, the node adds p × v, where p is the probability on that edge. When all children are back, the sum is the node's value.
expectimax(node):
if node is a leaf: return score(node)
if MAX to move: return max(expectimax(c) for c in children)
if MIN to move: return min(expectimax(c) for c in children)
if chance node: return sum(p(c) * expectimax(c) for c in children)Same tree, different move
On the random-opponent tree the three moves lead to these leaves:
| move | leaves | minimax (min) | expectimax (average) |
|---|---|---|---|
| A | 3, 12, 9 | 3 | 8 |
| B | 5, 6, 4 | 4 ✓ | 5 |
| C | 1, 20, 15 | 1 | 12 ✓ |
Minimax picks B: it can be sure of 4 (Demo 1). Expectimax picks C: against a random opponent it gets 12 on average, but one time in three it gets only 1 (Demo 2). Which one is right depends on how the opponent really plays. If the model is wrong, expectimax can walk into a trap that minimax would avoid.
Dice: expectiminimax
In backgammon both players choose, and a die is rolled between their moves. The tree then has three kinds of node: MAX, chance and MIN. This is called expectiminimax. The probabilities need not be equal: in the dice game a roll of 1–2 has probability 1/3 and a roll of 3–6 has 2/3.
Plain minimax treats the die as a hostile player and sees both moves as worth 3. Expectiminimax sees that the good roll for B is the likely one (Demo 5).
Scores are amounts now
Minimax only compares scores, so any change that keeps their order (1 < 3 < 4 …) keeps its move. Expectimax adds scores up, so their size matters. The rescaled tree passes every score through such an order-keeping map:
| tree | minimax | expectimax |
|---|---|---|
| random opponent | B (4) | C (12) |
| rescaled scores | B (7) | A (9) |
Minimax still picks B (Demo 4), but expectimax now picks A (Demo 3). So for expectimax the evaluation function must measure how good a position is, for example a win probability or expected points, not just rank positions.
No easy pruning
Alpha-beta cuts a branch once one child proves it is bad enough. A chance node's value depends on every child, so one bad child proves nothing: the next child could be huge. Expectimax therefore visits every node, as the stats panel shows. With a known upper bound on the scores some pruning is possible again (the *-minimax family), but it cuts far less than alpha-beta.
A chance node is the game-tree form of an expectation over next states, the same sum that appears in the Bellman update of Value Iteration and of Q-Learning. Monte Carlo Tree Search estimates such averages by sampling play-outs instead of summing every branch.
What the page leaves out
Depth limits and evaluation functions in detail; pruning for chance nodes (Star1, Star2); sampling a few dice outcomes instead of all of them; opponent models that are neither perfect nor uniform; games with hidden information such as poker; and more than two players.