When the game has explicit randomness (dice, drawn cards), insert "chance" nodes between min and max nodes. Compute the expected value at chance nodes instead of min or max.
Algorithm
``` function expectiminimax(state, depth): if state is terminal or depth == 0: return utility(state) if state is MAX_TURN: return max over actions of expectiminimax(result(state, action), depth-1) if state is MIN_TURN: return min over actions of expectiminimax(result(state, action), depth-1) if state is CHANCE: return sum over outcomes of P(outcome) * expectiminimax(result, depth-1) ```
Backgammon as the canonical example
A turn: player rolls dice (chance node), then chooses a move (max or min node), then opponent's turn starts. The search tree alternates max → chance → min → chance → ...
Branching factor at chance nodes can be huge — 21 distinct dice rolls per turn, each with non-trivial probability. Pure expectiminimax to deep depths is infeasible.
Pruning is harder
Alpha-beta works because comparing two known utilities at a min/max node lets you bound the parent immediately. At a chance node, you'd need to bound expected value — but you can't bound that until you've explored most outcomes. Some pruning is possible (probabilistic alpha-beta) but it's significantly less effective.
TD-Gammon and the modern story
Tesauro's TD-Gammon (1992) used a neural network evaluation function trained by temporal-difference learning from self-play. Combined with shallow expectiminimax, it played at world-class level. The first major success of neural-network-based game AI — predating AlphaGo by 24 years.
For backgammon and many stochastic games, the value comes mostly from a strong learned evaluation function plus shallow search, not from deep search.
Where chance nodes show up in modern AI
- Game tree search for randomized games (Catan, Risk's combat).
- Monte Carlo tree search uses random rollouts — a different but related way to handle uncertainty.
- Real-world planning under stochastic dynamics — usually modeled as MDPs (covered later).