Expectimax

The idea

Expectimax is a game-playing search that works like minimax but adds CHANCE nodes to handle randomness (dice rolls, card shuffles, coin flips). At MAX nodes you pick the best move, at MIN nodes the opponent picks their best move, and at CHANCE nodes you take the probability-weighted average of the possible random outcomes. This gives a score that reflects what you'd expect to happen on average, rather than assuming the dice always turn against you.

How it works

1. Build (or explore) a game tree where each node is a game state. Label each layer by whose 'turn' it is: MAX (you), MIN (opponent, if the game has one), or CHANCE (a random event like a dice roll).
2. Recurse downward until you hit a terminal state (game over) or a depth limit, then score that leaf using the game's outcome or an evaluation function.
3. At a MAX node, compute the value of every child and keep the MAXIMUM — you'll choose the move that helps you most.
4. At a MIN node, compute the value of every child and keep the MINIMUM — assume the opponent chooses the move that hurts you most.
5. At a CHANCE node, compute the value of every child and take the EXPECTED VALUE: multiply each outcome's value by its probability and sum them (a weighted average).
6. Pass each computed value back up to the parent, combining them according to that parent's node type.
7. At the very top (a MAX node = your turn), pick the child move with the highest backed-up value and play it.

OPEN, CLOSED & the data structures

A game tree with three node types: MAX, MIN (optional), and CHANCE. Each CHANCE node also needs a probability distribution over its children (e.g. each die face = 1/6). The algorithm is usually a single recursive function that carries the current state, the node type (or whose turn it is), and a remaining depth. It returns a numeric value up the tree; the top-level call also remembers which move produced the best value.

Pseudocode

function expectimax(state, depth):
    if state is terminal or depth == 0:
        return evaluate(state)

    if node_type(state) == MAX:
        best = -infinity
        for each action a in actions(state):
            best = max(best, expectimax(result(state, a), depth - 1))
        return best

    if node_type(state) == MIN:            # optional layer
        worst = +infinity
        for each action a in actions(state):
            worst = min(worst, expectimax(result(state, a), depth - 1))
        return worst

    if node_type(state) == CHANCE:
        total = 0
        for each outcome o in outcomes(state):
            total = total + probability(o) * expectimax(result(state, o), depth - 1)
        return total          # expected (average) value

At a glance