Adversarial Search — Minimax, Alpha–Beta Pruning and Expectimax

Games as search problems (deterministic, zero-sum, perfect information), game trees and the minimax algorithm, alpha–beta pruning traced step by step with the effect of move ordering, depth-limited search with evaluation functions, expectimax for games of chance, and a glimpse of Monte Carlo tree search.

Games as search

Classical game playing considers two-player, turn-taking, deterministic, perfect-information, zero-sum games (chess, checkers, Go, tic-tac-toe). A game is a search problem with:

initial state, $\text{PLAYER}(s)$ (whose move), $\text{ACTIONS}(s)$ , $\text{RESULT}(s, a)$ ;
a terminal test and a utility for terminal states (e.g. $+1$ win, $0$ draw, $-1$ loss for MAX).

MAX tries to maximise the utility; MIN tries to minimise it. Unlike ordinary search, the agent needs a strategy — a move for every possible reply.

Minimax

\text{MINIMAX}(s) = \begin{cases}\text{UTILITY}(s) & \text{terminal}\\ \max_a\text{MINIMAX}(\text{RESULT}(s, a)) & \text{MAX to move}\\ \min_a\text{MINIMAX}(\text{RESULT}(s, a)) & \text{MIN to move}\end{cases}

Python

def minimax(state, maximizing):
    if is_terminal(state):
        return utility(state)
    values = [minimax(child, not maximizing) for child in successors(state)]
    return max(values) if maximizing else min(values)

A complete depth-first exploration: time $O(b^m)$ , space $O(bm)$ . Optimal against an optimal opponent (and never worse against a weaker one, in terms of the guaranteed value).

Minimax value 3; alpha–beta skips two leaves of C.

Alpha–beta pruning

Keep two bounds along the current path:

$\alpha$ — the best (highest) value MAX can already guarantee;
$\beta$ — the best (lowest) value MIN can already guarantee.

Prune a node's remaining children as soon as $\alpha \ge \beta$ : at a MIN node when its value drops to $\le \alpha$ ; at a MAX node when its value rises to $\ge \beta$ .

Python

import math

def alphabeta(state, maximizing, alpha=-math.inf, beta=math.inf):
    if is_terminal(state):
        return utility(state)
    if maximizing:
        v = -math.inf
        for child in successors(state):
            v = max(v, alphabeta(child, False, alpha, beta))
            alpha = max(alpha, v)
            if alpha >= beta:
                break                     # beta cut-off
        return v
    v = math.inf
    for child in successors(state):
        v = min(v, alphabeta(child, True, alpha, beta))
        beta = min(beta, v)
        if alpha >= beta:
            break                         # alpha cut-off
    return v

Move ordering	Leaves examined
worst (weakest moves first)	$O(b^m)$ — no savings
random	about $O(b^{3m/4})$
perfect (best moves first)	$O(b^{m/2})$ — doubles the reachable depth

Good ordering heuristics: try captures and threats first, killer moves, iterative deepening (use the previous iteration's best move first), and transposition tables for repeated positions.

Imperfect real-time decisions

Real games are too deep to search to the end. Depth-limited search replaces the terminal test with a cut-off test and the utility with a heuristic evaluation function $\text{EVAL}(s)$ , e.g. a weighted sum of features (material balance, mobility, king safety). Problems: the horizon effect (pushing an unavoidable loss beyond the depth limit) — mitigated by quiescence search (extend search in volatile positions).

Games of chance: expectimax

Add chance nodes whose value is the expected value of their children:

\text{EXPECTIMAX}(s) = \sum_r P(r)\,\text{EXPECTIMAX}(\text{RESULT}(s, r)) \quad\text{at chance nodes}.

Because values are averaged, the evaluation function's actual magnitudes matter (only its order matters in minimax). Pruning is harder, since bounds on averages need bounds on the utilities.

Beyond minimax

Monte Carlo tree search (used by AlphaGo) estimates move values by random playouts, balancing exploration and exploitation with the UCB1 rule; it works without a hand-made evaluation function and suits games with huge branching factors such as Go.