Expectimax, in depth: chance nodes, why evaluation scale suddenly matters, Star1 pruning and a measured 2048 player

From worst case to expected case

Suppose action A yields +10 with probability 0.9 and -5 with probability 0.1, and action B yields 2 for sure. Minimax values A at its worst outcome, -5, and chooses B. Expectimax values A at 0.9*10 + 0.1*(-5) = 8.5 and chooses A. If the branch really is random, A is better on average by 6.5 points every time you face this choice. Minimax pays a large price for insurance against an adversary that does not exist.

The reverse error is just as real. If a hostile agent actually controls the outcome, expectimax will happily walk into the 10% branch every time, because the adversary will make it a 100% branch. The modelling question, "who chooses this outcome?", comes before any algorithm.

The recursion

A game tree for expectimax has max nodes (your choice), chance nodes (nature's draw, with known probabilities) and, in the two-player variant called expectiminimax, min nodes for the opponent. Backgammon is the classic expectiminimax game: each turn is a dice roll followed by a player's choice.

def value(state, depth):
    if depth == 0 or state.is_terminal():
        return evaluate(state)                    # must be on a utility scale
    if state.node_type == MAX:
        return max(value(state.apply(a), depth - 1) for a in state.actions())
    if state.node_type == MIN:                    # expectiminimax only
        return min(value(state.apply(a), depth - 1) for a in state.actions())
    # CHANCE: probability-weighted average of outcomes
    return sum(p * value(state.apply(o), depth - 1) for o, p in state.outcomes())

The probabilities at each chance node must sum to one, and terminal losses must be large finite numbers rather than -inf: a single -inf child turns the whole average into -inf, even if that child has probability one in a million.

Evaluation scale now matters

Minimax only ever compares values, so any strictly increasing transformation of the evaluation function, squaring positive scores or taking logarithms, leaves every decision unchanged. Expectimax adds values together, and averages are not preserved by nonlinear transformations. Only positive affine changes, a*v + b with a greater than 0, are safe.

Concretely: action A gives 0 or 20 with equal probability, action B gives 9 for certain. Expectimax prefers A (10 versus 9). Apply the increasing transformation sqrt: A becomes 0.5*0 + 0.5*4.47 = 2.24 and B becomes 3, so the choice flips to B. Neither scale is wrong, but they encode different attitudes to risk. A concave scale is risk-averse, a convex one risk-seeking.

So the evaluation function for expectimax must approximate the quantity you actually want to maximise in expectation: expected final score, win probability or expected reward. A heuristic that was tuned for minimax by eye usually needs re-tuning, and a learned value function trained on real outcomes is often the better fit.

Case study: a 2048 player

2048 is a clean single-player expectimax problem. You choose one of four slides; then the game places a new tile on a uniformly random empty cell, a 2 with probability 0.9 or a 4 with probability 0.1. A max node has at most 4 children and a chance node has twice as many children as there are empty cells, up to 30.

import math

def slide_row(row):
    """Slide one row left and merge equal neighbours once."""
    tiles = [t for t in row if t]
    out, i = [], 0
    while i < len(tiles):
        if i + 1 < len(tiles) and tiles[i] == tiles[i + 1]:
            out.append(tiles[i] * 2); i += 2
        else:
            out.append(tiles[i]); i += 1
    return tuple(out + [0] * (4 - len(out)))

def move(board, d):
    """board: tuple of 4 row tuples. d: 0 left, 1 right, 2 up, 3 down."""
    rows = board if d < 2 else tuple(zip(*board))
    new = []
    for r in rows:
        r2 = slide_row(r[::-1] if d % 2 else r)
        new.append(r2[::-1] if d % 2 else r2)
    new = tuple(new) if d < 2 else tuple(zip(*new))
    return new if new != board else None          # None: illegal move

def evaluate(board):
    empty = sum(t == 0 for r in board for t in r)
    mono = 0
    for lines in (board, tuple(zip(*board))):
        for r in lines:
            v = [math.log2(t) if t else 0 for t in r]
            up = sum(max(0, b - a) for a, b in zip(v, v[1:]))
            down = sum(max(0, a - b) for a, b in zip(v, v[1:]))
            mono -= min(up, down)                 # penalise zig-zag rows
    return 2.7 * empty + mono + 1.5 * math.log2(max(board[0][0], 1))

def chance(board, depth, cache):
    """Nature drops a 2 (p=0.9) or a 4 (p=0.1) on a uniformly random empty cell."""
    key = (board, depth)
    if key in cache:
        return cache[key]
    empties = [(r, c) for r in range(4) for c in range(4) if board[r][c] == 0]
    if depth == 0 or not empties:
        return evaluate(board)
    total = 0.0
    for r, c in empties:
        for tile, pt in ((2, 0.9), (4, 0.1)):
            child = tuple(tuple(tile if (i, j) == (r, c) else board[i][j]
                                for j in range(4)) for i in range(4))
            total += pt / len(empties) * best_value(child, depth - 1, cache)
    cache[key] = total
    return total

def best_value(board, depth, cache):
    vals = [chance(b, depth, cache) for b in map(lambda d: move(board, d), range(4)) if b]
    return max(vals) if vals else -1e9            # no move: game over, finite loss

def best_move(board, depth=2):
    cache, best = {}, (None, -math.inf)
    for d in range(4):
        b = move(board, d)
        if b and (v := chance(b, depth, cache)) > best[1]:
            best = (d, v)
    return best[0]

The transposition cache is keyed by board and remaining depth, which is exact here because a chance node's value depends on nothing else. Different move orders often reach the same board, so the cache saves real work.

Measured cost

We measured one mid-game position with 7 empty cells, counting evaluation calls. Each extra depth level multiplies the work by roughly 15 to 20, the product of the move and spawn branching after cache hits:

Playing ten seeded games at depth 1 (about 10 ms per move), five reached the 2048 tile, four reached 1024 and one stopped at 512. The evaluation weights are hand-set starting points, not tuned values. Strong 2048 programs represent the board as a 64-bit integer with four bits per tile, precompute row moves in a 65,536-entry table, and search deeper with the same recursion; the speed-up comes from representation, not from a different algorithm.

Pruning chance nodes

Alpha-beta prunes because one child of a max node can prove the node is too good for the opponent to allow. A chance node needs all its children to compute its average, so a single child proves nothing unless you know how large or small the unseen children could be. Ballard's 1983 paper on *-minimax gave the classic answer: if evaluations are bounded in [L, U], then after visiting some children the chance value lies between

lo = seen_sum + remaining_prob * L
hi = seen_sum + remaining_prob * U
if hi <= alpha: return hi      # cannot reach the window: prune (fail low)
if lo >= beta:  return lo      # already above the window: prune (fail high)

That is Star1. Star2 adds a cheap probing pass that searches only the first child of each chance outcome to get tighter bounds before the full search. Both only work when L and U are real, reasonably tight bounds, which is another reason to keep the evaluation on a bounded utility scale. Ballard reported savings from about a quarter up to an order of magnitude depending on move ordering.

Three cheaper techniques are common in practice. A probability cutoff stops expanding branches whose cumulative probability of being reached falls below a threshold and evaluates them statically. Sampling draws a fixed number of chance outcomes instead of enumerating all of them, trading exactness for a bounded branching factor. Iterative deepening searches depth 1, 2, 3 until a time budget runs out and keeps the last complete answer.

Expectimax, MDPs and MCTS

Expectimax is a finite-horizon Bellman backup laid out as a tree: chance nodes are expectations over transitions, max nodes are the maximisation over actions. When states recur often and the state space is small enough to enumerate, the same equations solved over a table, as in probability dynamic programming or value iteration, avoid repeating work that the tree recomputes. When the state space is huge and probabilities are only available through a simulator, Monte Carlo tree search samples chance outcomes and concentrates effort on promising lines instead of expanding everything.

Failure modes

• Wrong opponent model. Treating a real adversary as random makes the agent exploitable; treating a random process as an adversary makes it timid and sub-optimal. In a classic teaching exercise, a minimax Pac-Man trapped near randomly moving ghosts assumes death is certain and rushes into one, while an expectimax agent takes the gamble and often escapes.
• Uncalibrated evaluation. Scores tuned by eye combine features on arbitrary scales, so averages mean nothing. Validate by checking that higher evaluations really predict better outcomes.
• Wrong probabilities. If the real spawn rule or dice model differs from the one you search with, every chance value is biased. Measure the real distribution.
• Cache keys that miss state. If a cached value depends on anything besides the key, such as a probability cutoff threshold or the reach probability, a truncated estimate can be reused where an exact one was needed. Either include it in the key or do not cache truncated nodes.
• Infinities in averages. Use large finite terminal values.
• Branching explosion. Late in a game, with few empties, search is cheap; early on it is expensive. Adapt depth to the number of chance outcomes instead of fixing it.

Operational guidance

Budget by time, not depth. Use iterative deepening with a deadline, and set the depth by the product of the branching factors at the current state. Count evaluations as well as time, so regressions in pruning or caching show up as numbers. Keep the evaluation function fast and pure, because it dominates the profile. Before trusting a deeper search, compare it against a shallow one over many seeded games; with randomness in play, a single game proves nothing, and differences between configurations need dozens of games to separate from noise.

Trade-offs

What to do next

1. Run the 2048 code at depth 1 and 2 over ten seeds each and record the highest tile.
2. Add a probability cutoff, keyed safely in the cache, and measure evaluations saved.
3. Replace the board tuples with a 64-bit integer and a row lookup table; measure speed.
4. Rescale the evaluation with sqrt or v**2 and watch how move choices change; then fit weights to real game outcomes.
5. Implement Star1 with honest bounds for a dice game and compare node counts.
6. Review alpha-beta and the minimax deep dive to see exactly which guarantees the averaging step removes.