Home/Game AI/Expectimax
Search algorithmsCTRL K

Expectimax

· minimax with chance nodes
/gameai/expectimax
VISITED
1/ 40
nodes entered
LEAVES
0/ 27
positions scored
VALUE
—
at the current node
CHANCE NODES
0
averaged so far
PROBABILITY
1 / 3
of each outcome
currentevaluatedbest expectationunvisited
b = 3 · depth 3 · seed 7 · 93 steps
step 0 / 92
Depth3
expectimax.ts
1
function expectimax(node: Node, depth: number, chance: boolean): number {
2
  if (depth === 0 || node.isLeaf) return node.value;
3
  if (chance) {
4
    let expected = 0;
5
    for (const child of node.children) expected += child.probability * expectimax(child, depth - 1, false);
6
    return expected;
7
  }
8
  let best = -Infinity;
9
  for (const child of node.children) best = Math.max(best, expectimax(child, depth - 1, true));
10
  return best;
11
}
CURRENT STEP
line 8

MAX node at ply 0: pick the child with the highest expected value.

// how it works

Understanding Expectimax

expectimax · when the opponent is a die, average instead of fearing the worst
01

The idea

Minimax assumes the opponent always picks the move that hurts you most. When the 'opponent' is a die roll, a shuffled deck or a player known to move at random, that is too pessimistic: the right value of a chance node is the expected value, each outcome's value weighted by its probability.

Expectimax keeps MAX nodes as they are and replaces MIN nodes by chance nodes that average. The best line can differ from minimax's: a move with a great average but one bad outcome is chosen by expectimax and refused by minimax. The price is that alpha-beta pruning no longer applies in full, since an average can always be pulled up by an unseen child.

02

The four stages

1
descendvisit the first child until a leaf
2
scoreleaf returns its outcome
3
averagea chance node sums value × probability
4
maximiseMAX keeps the highest expectation
03

Complexity

best
O(bᵈ)every leaf is needed for an exact average
average
O(bᵈ)the same
worst
O(bᵈ)*-minimax prunes only with bounded values
space
O(d)depth-first
04

Versus its siblings

LEAVES SCORED · b = 3, d = 4
minimax
81
expectimax
81
alpha-beta
44
*-minimax (bounded)
60
same tree · expectimax cannot prune unless leaf values are bounded
05

Pseudocode

EXPECTIMAX(node, depth, chance)
  if depth = 0 or node is a leaf: return value(node)
  if chance: return Σ probability(child) × EXPECTIMAX(child, depth − 1, false)
  else: return max over children of EXPECTIMAX(child, depth − 1, true)
06

When to use

Games of chance: backgammon, 2048, card games, dice; and any planning problem with a stochastic environment.
Modelling an imperfect opponent: a random or weighted policy instead of a perfect adversary.
07

Pitfalls

The evaluation scale matters: averaging makes the magnitude of scores meaningful, where minimax only needed their order.
Branching explodes: a chance node adds a factor per outcome, so depth is limited; sample outcomes when there are many.
A rare catastrophic outcome is averaged away; if it must be avoided, minimax over the dangerous branch.
08

History

Donald Michie described expectimax in 1966 while studying game learning; Bruce Ballard's *-minimax of 1983 brought partial pruning back by bounding the evaluation. Gerald Tesauro's TD-Gammon paired a two-ply expectimax with a learned evaluation to reach world-class backgammon in 1992.

Back to Game AI