Stochastic Games and Expectiminimax
What you'll learn: How to extend minimax to handle games with random elements like dice rolls or hidden card draws.
The Core Challenge
Classic minimax assumes perfect information and deterministic outcomes—every move leads to exactly one known state. But many real games include randomness: backgammon has dice, poker has card shuffles, and many video games use random number generators. These are stochastic games, where chance affects outcomes.
Enter Expectiminimax
Expectiminimax extends minimax by adding a third type of node to your game tree:
- MAX nodes – your player maximizes utility (unchanged)
- MIN nodes – opponent minimizes utility (unchanged)
- CHANCE nodes – represent random events with probabilistic outcomes
How It Works
At a chance node, instead of taking the max or min of child values, you compute the expected value (weighted average) based on each outcome's probability.
Example: Rolling a die before a move:
- Each die face has probability 1/6
- If rolling 1-3 leads to state A (value 10) and 4-6 leads to state B (value 4)
- Expected value = (3/6 × 10) + (3/6 × 4) = 5 + 2 = 7
You propagate this expected value upward, just like minimax propagates min/max values.
Practical Impact
Expectiminimax helps AI evaluate risky vs. safe strategies. A move that might be brilliant or terrible often has lower expected value than a consistently decent move. The algorithm naturally models risk-averse or risk-seeking behavior depending on your utility function design.
Key Takeaway: Expectiminimax extends minimax with chance nodes that compute expected values based on probabilistic outcomes, enabling AI to reason about games involving randomness.