The Expectiminimax algorithm is an extension of the Minimax algorithm used in game theory and AI for decision-making in games. It handles games with chance elements — where outcomes can be probabilistic, not just deterministic.
In games with both adversarial players and chance events (e.g., dice rolls, card draws).
Examples:
Backgammon (dice rolls)
Monopoly (dice rolls, chance cards)
Some variants of Poker or other games with randomness
Minimax is for perfect-information deterministic games — where players alternate turns and outcomes are fixed.
Expectiminimax incorporates chance nodes in addition to min (opponent) and max (player) nodes.
It computes the expected utility over chance nodes instead of simply min or max values.
The game tree now has three types of nodes:
Max nodes — AI's turn, it chooses the move that maximizes its expected utility.
Min nodes — Opponent's turn, assumed to choose moves that minimize AI's utility.
Chance nodes — Represent probabilistic outcomes (like dice rolls). The value here is the expected value (weighted average) of all possible outcomes.
Max nodes:
Choose the child node with the maximum expectiminimax value.
Min nodes:
Choose the child node with the minimum expectiminimax value.
Chance nodes:
Calculate the expected value by summing the values of all child nodes weighted by their probabilities.
def expectiminimax(node):
if node is a terminal node:
return utility(node)
if node is a max node:
return max(expectiminimax(child) for child in node.children)
elif node is a min node:
return min(expectiminimax(child) for child in node.children)
elif node is a chance node:
expected_value = 0
for child, prob in node.children_with_probabilities:
expected_value += prob * expectiminimax(child)
return expected_value
Consider a dice roll after your move that determines the opponent’s possible responses. The chance node models the dice roll:
Suppose dice roll 1 happens with probability 1/6 → leads to child node A with value 3.
Dice roll 2 → child node B with value 5.
Dice roll 3 → child node C with value 2.
...
The chance node value = (1/6)*3 + (1/6)*5 + (1/6)*2 + ... and so on.
Aspect | Minimax | Expectiminimax |
---|---|---|
Types of nodes | Max and Min only | Max, Min, and Chance |
Game type | Deterministic, perfect info | Stochastic with chance/probability |
Value at chance nodes | N/A | Expected value over probabilistic outcomes |