Adversarial Search & Games

A game tree is the complete, explicit unrolling of every possible sequence of moves in a two-player game. Each node represents a game state — the full configuration of the board plus whose turn it is. Each edge represents a legal move. The root is the current state; leaves are terminal states where the game is over.

Formally, a two-player zero-sum game is a tuple (S, A, T, U, s₀, TERMINAL) where:

• S is the set of all states
• A(s) is the set of legal actions in state s
• T(s, a) is the deterministic transition (next state after action a in state s)
• U(s) is the utility (score) for the MAX player at terminal state s
• s₀ is the initial state
• TERMINAL(s) returns true if s is a terminal state

Zero-sum means one player's gain is exactly the other's loss: if MAX wins +1, MIN wins -1. This is the key structural assumption that makes minimax correct.

Analogy: Imagine you are arguing with an opponent, and you draw a complete tree of every possible exchange — every response you could give, every counter they could make. That tree IS the game tree. It captures all of time's branching possibilities from the current moment.

The depth of the game tree is the number of moves until the game ends. The branching factor b is the average number of legal moves per state. The number of leaf nodes is roughly b^d. This is the core difficulty: even modest games have astronomical trees. Chess has b ≈ 35, d ≈ 80, giving 35^80 ≈ 10^124 leaves — more than atoms in the observable universe. We cannot enumerate the whole tree; we must search it intelligently.

from dataclasses import dataclass
from typing import Optional

@dataclass
class GameState:
    board: tuple        # immutable board representation
    to_move: str        # 'MAX' or 'MIN'
    
def actions(state: GameState) -> list:
    """Return legal actions in this state."""
    ...

def result(state: GameState, action) -> GameState:
    """Apply action, return new state."""
    ...

def is_terminal(state: GameState) -> bool:
    """Is this a terminal state?"""
    ...

def utility(state: GameState) -> float:
    """Terminal utility for MAX player. Only valid if is_terminal."""
    ...

Minimax is the foundational algorithm for zero-sum two-player games. The key insight is a recursive definition of the minimax value of a state: the utility MAX can guarantee against an optimal MIN player.

Recurrence:

V(s) = utility(s)                         if TERMINAL(s)
V(s) = max over a in A(s) of V(T(s,a))   if MAX's turn
V(s) = min over a in A(s) of V(T(s,a))   if MIN's turn

The algorithm is a depth-first search over the game tree that exactly computes this recurrence. MAX always picks the child with the highest value; MIN always picks the child with the lowest.

Why this is correct: By induction. At terminal states, the value is exactly utility(s). Suppose the value is correctly computed for all states at depth d+1. At depth d, if it is MAX's turn, MAX will pick the action that leads to the highest-value child — and since those child values are correct by induction, MAX's computed value is correct. The argument for MIN is symmetric. QED.

Analogy: Imagine the game as a mountain range seen from the side. MAX is a hiker who always climbs; MIN is a hiker who always descends. Minimax asks: if both hikers make their best choice at every step, what altitude do they end up at?

Complexity:

• Time: O(b^d) — we visit every node once
• Space: O(bd) — we only keep one path in memory at a time (DFS)

For tic-tac-toe (b ≈ 5, d ≈ 9), this is completely tractable. For chess, it is hopeless without pruning and evaluation functions.

def minimax(state, is_max_turn):
    if is_terminal(state):
        return utility(state), None

    best_action = None
    if is_max_turn:
        best_val = float('-inf')
        for a in actions(state):
            val, _ = minimax(result(state, a), False)
            if val > best_val:
                best_val, best_action = val, a
    else:
        best_val = float('inf')
        for a in actions(state):
            val, _ = minimax(result(state, a), True)
            if val < best_val:
                best_val, best_action = val, a

    return best_val, best_action

# Usage: value, action = minimax(initial_state, is_max_turn=True)

Alpha-beta pruning is the key optimization that makes minimax practical. The central insight: we can prune entire subtrees of the game tree without affecting the minimax value, because MIN will never allow MAX to reach a state that is better than something MAX has already found, and vice versa.

We maintain two bounds during search:

• α (alpha): the best value MAX can guarantee on the current path (initialized to -∞)
• β (beta): the best value MIN can guarantee on the current path (initialized to +∞)

The pruning rules:

• At a MIN node: if the current value falls at or below α, stop — MAX has a better option earlier on the path and will never reach this MIN node.
• At a MAX node: if the current value rises at or above β, stop — MIN has a better option earlier on the path and will never reach this MAX node.

Correctness argument: Consider a MIN node n with value v ≤ α. The ancestor MAX node that established α already has a guaranteed value of α. No matter what MIN does at n, the value propagated up will be at most v ≤ α. MAX will never choose the path through n. So we can prune n without affecting the root's minimax value.

Complexity with perfect move ordering:

• Best case (always pick the best move first): O(b^(d/2)) — the same depth can be searched with the square root of the nodes!
• Random move ordering: O(b^(3d/4))
• Worst case (always pick the worst move first): O(b^d) — no pruning at all

This is remarkable. With good move ordering, alpha-beta lets you search twice as deep as plain minimax in the same time. For chess, this is the difference between looking 4 moves ahead and 8 moves ahead — the latter plays at a much stronger level. Move ordering heuristics (killer moves, history heuristic, transposition tables) are specifically designed to trigger alpha-beta pruning as much as possible.

def alpha_beta(state, alpha, beta, is_max_turn):
    """
    alpha: best guaranteed value for MAX so far (lower bound)
    beta:  best guaranteed value for MIN so far (upper bound)
    """
    if is_terminal(state):
        return utility(state), None

    best_action = None
    if is_max_turn:
        value = float('-inf')
        for a in actions(state):
            child_val, _ = alpha_beta(result(state, a), alpha, beta, False)
            if child_val > value:
                value, best_action = child_val, a
            alpha = max(alpha, value)
            if value >= beta:       # MIN won't allow this path (beta cutoff)
                break
        return value, best_action
    else:
        value = float('inf')
        for a in actions(state):
            child_val, _ = alpha_beta(result(state, a), alpha, beta, True)
            if child_val < value:
                value, best_action = child_val, a
            beta = min(beta, value)
            if value <= alpha:      # MAX won't allow this path (alpha cutoff)
                break
        return value, best_action

# Usage: value, action = alpha_beta(state, float('-inf'), float('inf'), True)

For real games like chess and Go, the game tree is too deep to search to terminal states. The practical solution is depth-limited minimax: stop the search at depth d and evaluate the state with a heuristic evaluation function e(s), which estimates how good state s is for MAX.

Designing a good evaluation function is more art than science, but good ones share properties:

1. They agree with the terminal utility at terminal states: e(s) = utility(s) if TERMINAL(s).
2. They are fast to compute. Each evaluation replaces a potentially huge subtree.
3. They capture game-relevant features. For chess: material count (queen=9, rook=5, bishop/knight=3, pawn=1), piece mobility, king safety, pawn structure.

Classic chess evaluation: e(s) = Σ (material_MAX) - Σ (material_MIN) + mobility_bonus + positional_bonus

The horizon effect: A critical weakness. The search might stop just before a major exchange, giving a misleadingly high evaluation to a state where MAX is about to lose a queen. The evaluation function cannot "see" this disaster because it is beyond the search horizon. Solutions include quiescence search (continue searching past captures and checks until the position is stable) and singular extensions (extend promising lines deeper).

Iterative deepening (ID-alpha-beta): In practice, engines don't pick a fixed depth. Instead, they search to depth 1, then depth 2, then depth 3, and so on, using the time budget. This seems wasteful, but because b^d dominates b^(d-1) + b^(d-2) + ..., the overhead is only O(1/b) extra work. The huge benefit: the shallow search gives you a good move order for the deeper search, dramatically improving alpha-beta pruning. Essentially every real chess engine uses iterative deepening.

def depth_limited_minimax(state, depth, is_max_turn):
    if is_terminal(state):
        return utility(state), None
    if depth == 0:
        return evaluate(state), None   # <-- heuristic evaluation

    best_action = None
    if is_max_turn:
        best_val = float('-inf')
        for a in actions(state):
            val, _ = depth_limited_minimax(result(state, a), depth - 1, False)
            if val > best_val:
                best_val, best_action = val, a
    else:
        best_val = float('inf')
        for a in actions(state):
            val, _ = depth_limited_minimax(result(state, a), depth - 1, True)
            if val < best_val:
                best_val, best_action = val, a

    return best_val, best_action

# Example evaluation for Tic-Tac-Toe (simplified)
def evaluate(state):
    # Returns a heuristic: +10 if MAX is winning position,
    # -10 if MIN is winning, 0 otherwise
    if check_win(state, 'MAX'): return +10
    if check_win(state, 'MIN'): return -10
    return 0  # real evals are far more nuanced

A crucial optimization in real game engines: transposition tables (a form of memoization). In many games, the same board position can be reached via different move sequences — a transposition. Without caching, minimax re-explores these positions from scratch each time. A transposition table is a hash map from game states to their previously computed minimax values (and bounds).

What to store per entry:

• The Zobrist hash of the state (a fast, collision-resistant hash)
• The computed value
• The node type: EXACT (the exact minimax value), LOWER_BOUND (a beta cutoff occurred — actual value is at least this), UPPER_BOUND (an alpha cutoff occurred — actual value is at most this)
• The depth to which the position was searched
• The best move found (for move ordering)

Zobrist hashing is a standard technique: assign a random 64-bit number to each (piece, square) pair. XOR them all together for the full position. Updating after a move is O(1): XOR out the old piece, XOR in the new one.

Using the table in alpha-beta:

• Before searching a node, look it up. If it was searched to at least the required depth:
  • EXACT: return the stored value directly
  • LOWER_BOUND: update α
  • UPPER_BOUND: update β
  • If α ≥ β after the update, prune immediately
• After searching, store the result with the appropriate type

Transposition tables provide enormous speedups in practice because games often have highly transposition-prone structures (especially in chess endgames). Modern engines allocate hundreds of megabytes to transposition tables and carefully manage replacement strategies (depth-preferred, always-replace, two-tier).

# Simplified transposition table integration
from enum import Enum

class NodeType(Enum):
    EXACT = 0
    LOWER = 1   # alpha cutoff: value >= stored
    UPPER = 2   # beta cutoff:  value <= stored

transposition_table = {}  # zobrist_hash -> (value, node_type, depth, best_move)

def alpha_beta_tt(state, depth, alpha, beta, is_max):
    key = zobrist_hash(state)
    if key in transposition_table:
        val, ntype, stored_depth, best_move = transposition_table[key]
        if stored_depth >= depth:
            if ntype == NodeType.EXACT:  return val, best_move
            if ntype == NodeType.LOWER:  alpha = max(alpha, val)
            if ntype == NodeType.UPPER:  beta  = min(beta, val)
            if alpha >= beta:            return val, best_move

    if is_terminal(state) or depth == 0:
        v = utility(state) if is_terminal(state) else evaluate(state)
        transposition_table[key] = (v, NodeType.EXACT, depth, None)
        return v, None

    orig_alpha = alpha
    best_action = None
    value = float('-inf') if is_max else float('inf')
    for a in actions(state):
        child_val, _ = alpha_beta_tt(result(state,a), depth-1, alpha, beta, not is_max)
        if is_max:
            if child_val > value: value, best_action = child_val, a
            alpha = max(alpha, value)
        else:
            if child_val < value: value, best_action = child_val, a
            beta = min(beta, value)
        if alpha >= beta: break

    # Determine node type and store
    if value <= orig_alpha:      ntype = NodeType.UPPER
    elif value >= beta:          ntype = NodeType.LOWER
    else:                        ntype = NodeType.EXACT
    transposition_table[key] = (value, ntype, depth, best_action)
    return value, best_action

Minimax assumes a perfect adversary. But many real games — backgammon, poker, Minesweeper, Pac-Man with randomized ghosts — involve chance nodes: outcomes determined by dice, shuffled cards, or random events. Expectimax generalizes minimax to handle these stochastic elements.

Expectimax adds a third type of node alongside MAX and MIN:

• CHANCE node: takes the probability-weighted average (expected value) of its children's values

Value function:

V(s) = utility(s)                                      if TERMINAL(s)
V(s) = max over a in A(s) of V(T(s,a))               if MAX node
V(s) = min over a in A(s) of V(T(s,a))               if MIN node (adversary)
V(s) = Σ_{a} P(a|s) * V(T(s,a))                      if CHANCE node

Critical difference from minimax: Under minimax, only the ordering of leaf values matters — you can apply any monotone transformation to utilities without changing the best action. Under expectimax, the actual magnitudes matter because we're computing weighted averages. Doubling all utilities doubles the expected value but doesn't change the optimal action; but shifting utilities (adding a constant) does change the relative preference between risky and safe options.

Implication: Evaluation functions for expectimax must be calibrated. Returning +100 for a slightly good position and +1000 for a great one will make the agent appear to be a risk-seeker compared to returning +1 and +10.

When adversary is sub-optimal: If your opponent doesn't play perfectly, minimax is pessimistic — it assumes worst-case play. Expectimax with a model of the opponent's actual policy (e.g., random moves) can outperform minimax against weak opponents, because it doesn't sacrifice value to guard against adversarial moves that will never occur. The tradeoff: if your opponent model is wrong, expectimax can perform catastrophically.

def expectimax(state, agent_idx, num_agents):
    """
    agent_idx: 0 = MAX (our agent), 1..n-1 = other agents
    In Pac-Man: agent 0 is Pac-Man (MAX), agents 1..n are ghosts (CHANCE)
    """
    if is_terminal(state):
        return utility(state), None

    next_agent = (agent_idx + 1) % num_agents
    best_action = None

    if agent_idx == 0:          # MAX node
        best_val = float('-inf')
        for a in actions(state):
            val, _ = expectimax(result(state, a), next_agent, num_agents)
            if val > best_val:
                best_val, best_action = val, a
        return best_val, best_action

    else:                       # CHANCE node (opponent modeled as random)
        acts = actions(state)
        total = 0.0
        prob = 1.0 / len(acts)  # uniform random; replace with real model
        for a in acts:
            val, _ = expectimax(result(state, a), next_agent, num_agents)
            total += prob * val
        return total, None       # no best_action for chance nodes

In games like Go (branching factor ≈ 250, typical game length ≈ 150), designing a strong evaluation function is notoriously hard — the game position is too complex for handcrafted features. Monte Carlo Tree Search (MCTS) sidesteps this by replacing the evaluation function with random playouts (rollouts): play random moves from the current state until the game ends, and use the win/loss result as the value estimate.

MCTS builds the game tree incrementally through four repeated phases:

1. Selection: Starting from the root, use a tree policy (usually UCB1) to navigate the already-built tree, choosing children that balance exploitation (go to high-win-rate nodes) and exploration (go to under-visited nodes).

2. Expansion: At the frontier of the built tree, add one or more new child nodes representing unexplored moves.

3. Simulation (Rollout): From the new node, play to terminal using a default policy (random moves, or a fast shallow policy). Record the outcome.

4. Backpropagation: Walk back up the tree, updating each node's visit count N(s) and accumulated value W(s).

UCB1 (Upper Confidence Bound) formula — the canonical tree policy:

UCB1(child) = W(child)/N(child)  +  c * sqrt(ln(N(parent)) / N(child))

The first term is the exploitation term (average win rate of this child). The second is the exploration term (visit under-explored nodes). c ≈ √2 is a tuning constant.

Why it works: With enough rollouts, the win-rate estimates converge to the true minimax values (under certain conditions). More importantly, MCTS naturally focuses its computational budget on the most promising parts of the tree — no hand-crafted features needed.

AlphaGo and AlphaZero replaced random rollouts with a learned value network and guided selection with a policy network. This made MCTS exponentially more efficient: the policy network narrows the branching factor (only consider likely moves) and the value network replaces costly rollouts with a fast neural estimate.

import math, random
from collections import defaultdict

class MCTSNode:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []       # list of MCTSNode
        self.N = 0               # visit count
        self.W = 0.0             # total value (wins)
        self.untried = list(actions(state))  # unexplored moves

def ucb1(node, c=1.414):
    if node.N == 0: return float('inf')
    return (node.W / node.N) + c * math.sqrt(math.log(node.parent.N) / node.N)

def mcts(root_state, n_simulations):
    root = MCTSNode(root_state)
    for _ in range(n_simulations):
        # 1. Selection
        node = root
        while not node.untried and node.children:
            node = max(node.children, key=ucb1)
        # 2. Expansion
        if node.untried:
            move = random.choice(node.untried)
            node.untried.remove(move)
            child_state = result(node.state, move)
            child = MCTSNode(child_state, parent=node)
            node.children.append(child)
            node = child
        # 3. Simulation (random rollout)
        sim_state = node.state
        while not is_terminal(sim_state):
            sim_state = result(sim_state, random.choice(actions(sim_state)))
        reward = utility(sim_state)   # +1 win, 0 draw, -1 loss for MAX
        # 4. Backpropagation
        while node:
            node.N += 1
            node.W += reward
            node = node.parent
    # Best action: most-visited child of root
    best = max(root.children, key=lambda n: n.N)
    return [a for a in actions(root_state)
            if result(root_state, a) == best.state][0]

Minimax assumes exactly two players with perfectly opposed utilities. Real multi-player games (multiplayer board games, poker, auctions) break this assumption in two ways: there are more than two agents, and utilities need not sum to zero.

Multi-player minimax: Replace the single value with a vector of utilities — one per player. Each player, on their turn, maximizes their own component of the utility vector. There is no longer a simple recursion, and the concept of "optimal play" becomes Nash equilibrium: a strategy profile where no player can unilaterally improve their utility.

Coalition formation: With 3+ players, alliances can form. Even if game rules don't allow alliances, two players might cooperate informally to prevent a third from winning. This means the optimal strategy for an agent depends on predicting not just individual-rational play but also coalition dynamics — a much harder problem.

Non-zero-sum two-player games: If players can both benefit from cooperation (e.g., Prisoner's Dilemma), minimax overestimates the adversarialness and may leave value on the table. The right tool is game theory (Nash equilibria, Pareto optima), not minimax.

Partially observable games: Poker is the canonical example. Players don't know the full state (opponents' cards). The state space becomes a belief state — a probability distribution over possible true states. Optimal play requires reasoning about what the opponent believes, what they believe you believe, and so on (the theory of counterfactual regret minimization, CFR, was developed specifically for this).

The single-player case: With only one agent and no adversary, the game degenerates to a standard search problem (BFS, A*, etc.). Expectimax with only MAX and CHANCE nodes corresponds exactly to a Markov Decision Process (MDP), which is the foundation of reinforcement learning.

# Multi-player minimax: value is a tuple, each player maximizes their component
def multiplayer_minimax(state, current_player, n_players):
    if is_terminal(state):
        return utility_vector(state)  # e.g. (1, 0, -1) for 3 players

    best_action = None
    # each player maximizes their own component
    best_val_for_current = float('-inf')
    best_val_vector = None
    next_player = (current_player + 1) % n_players
    for a in actions(state):
        val_vector = multiplayer_minimax(result(state, a), next_player, n_players)
        # current player cares only about their component
        if val_vector[current_player] > best_val_for_current:
            best_val_for_current = val_vector[current_player]
            best_val_vector = val_vector
            best_action = a
    return best_val_vector, best_action

The theoretical benefit of alpha-beta pruning is only realized when good moves are searched first. In practice, move ordering is one of the most important engineering decisions in a game engine.

Key move ordering heuristics:

1. Transposition table move: If the transposition table has a best move for this position (from a shallower search), try it first. This is almost always good.

2. Killer move heuristic: Keep track of the last two moves at each depth that caused a beta cutoff ("killer moves"). Try these first at the same depth in sibling nodes. Intuition: if a move was refuting at depth 5 in a nearby branch, it might refute here too.

3. History heuristic: Maintain a global table mapping moves to a score based on how often they caused beta cutoffs across the whole search. Order moves by this score.

4. MVV-LVA (Most Valuable Victim - Least Valuable Attacker): In chess, for captures, prioritize capturing the most valuable piece with the least valuable attacker first.

5. Static Exchange Evaluation (SEE): Quickly determine if a capture sequence is winning or losing material overall, before committing to a full subtree search.

Iterative deepening + aspiration windows: Narrow the alpha-beta window around the expected value from the previous iteration. If the search falls outside the window, re-search with a wider window. This reduces the number of nodes searched in the common case.

Null-move pruning: Try passing your turn (making a "null move"). If the opponent still can't beat beta even with a free move, the position is so good for you that you can prune. This is an unsound heuristic but very effective in practice.

Late move reductions (LMR): Moves searched late in the move list (after good moves have been tried) are probably bad. Search them to a reduced depth. If they turn out to be better than expected, re-search at full depth.

These heuristics, layered on top of alpha-beta, are why Stockfish (the strongest classical engine) can search 50+ million positions per second on modern hardware and look 30+ moves ahead effectively.