Minimax / Expectiminimax Demo

A demonstration of two game-tree search algorithms: Minimax and Expectiminimax. Both compute the utility of the root of a game tree by recursively evaluating each node according to its type.

MAX nodes choose the child with the highest value. MIN nodes (an adversarial opponent) choose the child with the lowest value. CHANCE nodes model a random event and take the probability-weighted average — the expectation — over their children's values. TERMINAL nodes simply hold a fixed utility.

A tree containing only MAX and MIN nodes is evaluated by plain Minimax. A tree that also contains CHANCE nodes is evaluated by Expectiminimax instead — and in that setting the MIN player doesn't have to appear at all: a purely stochastic game built from MAX and CHANCE nodes only is just as valid a tree.

function MINIMAX-DECISION(state) returns an action
    value ← MINIMAX-VALUE(ROOT(state))
    return the action leading to that value

function MINIMAX-VALUE(node) returns a utility value
    if node.TYPE = TERMINAL then return node.value
    if node.TYPE = MAX then
        return max( MINIMAX-VALUE(c) for each child c of node )
    if node.TYPE = MIN then
        return min( MINIMAX-VALUE(c) for each child c of node )

function EXPECTIMINIMAX-DECISION(state) returns an action
    value ← EXPECTIMINIMAX-VALUE(ROOT(state))
    return the action leading to that value

function EXPECTIMINIMAX-VALUE(node) returns a utility value
    if node.TYPE = TERMINAL then return node.value
    if node.TYPE = MAX then
        return max( EXPECTIMINIMAX-VALUE(c) for each child c of node )
    if node.TYPE = MIN then
        return min( EXPECTIMINIMAX-VALUE(c) for each child c of node )
    if node.TYPE = CHANCE then
        return Σ P(node → c) · EXPECTIMINIMAX-VALUE(c) over each child c

Step through the algorithm below. Each step reveals exactly what the search does at that point — entering a node, examining a terminal, updating the running best (or expected) value after a child returns — and the message line explains it in words.