Adversarial Search & Games — Reading Notes

1.Game Terminology & Problem Formulation

In classical single-agent search (Topics 01 and 02), an agent plans a complete sequence of actions to reach a static goal in a predictable environment. The environment does not actively conspire against the agent, nor does it respond with counter-strategies. In an adversarial environment, however, two or more competitive agents with diametrically opposed goals make alternating decisions. The agent cannot simply find a single fixed path to victory; it must compute a contingency strategy specifying what move to make for every possible countermove the opponent could choose.

1.1Adversarial Environments

An adversarial environment is a multi-agent setting where the goals of the agents are in direct conflict. In the classical two-player competitive setting, one player is conventionally named MAX (the agent seeking to maximize the terminal outcome) and the other is named MIN (the opponent seeking to minimize MAX's outcome, which is equivalent to maximizing their own outcome).

The defining feature of adversarial search is the assumption of rationality on the part of the opponent: MAX assumes that MIN will always select the move that is worst for MAX. Planning under this assumption provides a worst-case theoretical guarantee.

1.2Formal Game Definition

Following Russell & Norvig (AIMA Chapter 5), a deterministic, two-player, turn-taking game is formally defined as a 6-tuple ⟨S₀, PLAYER, ACTIONS, RESULT, TERMINAL-TEST, UTILITY⟩:

Initial State (S₀)

Specifies the starting configuration of the board and identifies which player moves first (e.g., an empty 3×3 Tic-Tac-Toe grid with MAX to move).

PLAYER(s)

A function that returns which player (MAX or MIN) has the turn to move in state s.

ACTIONS(s)

Returns the set of legal moves available to the player whose turn it is in state s.

RESULT(s, a)

The transition model: returns the new state s′ resulting from taking legal action a in state s.

TERMINAL-TEST(s)

A boolean predicate returning true if the game has ended (by checkmate, three-in-a-row, stalemate, or exhaustion of moves) and false otherwise. States where TERMINAL-TEST(s) = true are called terminal states.

UTILITY(s, p)

A utility function (also called an objective function or payoff function) that assigns a definitive numeric score to player p when the game terminates in state s. In zero-sum games, utility is usually written from MAX's perspective: win = +1 (or +∞), draw = 0, loss = −1 (or −∞).

Notice the direct correspondence to single-agent problem formulation (Topic 01):

• GOAL-TEST(s) is replaced by TERMINAL-TEST(s) — search does not stop when MAX reaches a desired state, but only when the game officially terminates for both players.
• PATH-COST(c) is replaced by UTILITY(s, p) — step costs along intermediate moves are irrelevant in chess or tic-tac-toe; only the final terminal outcome matters.

1.3Game Trees & Plies

The state space of a game is structured as a game tree: a rooted tree where the root node represents S0, directed edges represent legal moves produced by ACTIONS(s), internal nodes represent intermediate game states labeled with the player to move (MAX or MIN), and leaves represent terminal states labeled with their numeric utility values.

Because games involve alternating turns, AI literature makes a strict distinction between a move and a ply:

• A ply (or half-move) represents one turn taken by a single player. In a game tree, each horizontal layer of edges corresponds to exactly 1 ply.
• A full move consists of two plies: one move by MAX followed by one reply by MIN.
• The branching factor b is the number of legal actions available at a given state. In chess, b ≈ 35; in Go, b ≈ 250.
• The maximum depth m is the maximum number of plies in a game. In chess, m ≈ 80 plies (40 full moves); in Go, m ≈ 150 plies.

1.4Zero-Sum vs. General-Sum Games

Games are classified by how the players' utility functions relate to one another:

• Zero-Sum Games (Constant-Sum): The sum of all players' payoffs is constant across every possible terminal state. For two players, UMAX(s) + UMIN(s) = 0 ⇒ UMIN(s) = −UMAX(s). Pure competition: any gain for MAX is an equal, direct loss for MIN. There is no possibility of cooperation, mutual benefit, or compromise. Chess, Checkers, Go, and Tic-Tac-Toe are zero-sum games.
• General-Sum Games: Payoffs are independent vectors (U1, U2) where outcomes can be win-win (cooperative trade), lose-lose (nuclear war / mutual defect in Prisoner's Dilemma), or asymmetric. General-sum games require Nash equilibrium analysis rather than minimax search.

1.5Perfect vs. Imperfect Information

Game environments differ fundamentally based on whether the state is fully observable:

• Perfect Information: All players have full, unobstructed visibility of the entire game state at all times. There are no hidden variables, concealed cards, or private state. Chess, Checkers, Go, and Tic-Tac-Toe are perfect information games.
• Imperfect Information: Critical elements of the game state are concealed from players (e.g., facedown cards in Poker, hidden ship coordinates in Battleship, or fog-of-war in real-time strategy games). Players must reason over information sets — collections of possible states consistent with their current observations.

1.6Deterministic vs. Stochastic Games

Games also differ based on how transitions are governed:

• Deterministic Games: The execution of legal action a in state s deterministically produces state s′ = RESULT(s, a). There is no randomness or luck.
• Stochastic Games: Actions involve elements of chance (dice rolls, card shuffling, tile draws). The transition model is probabilistic: P(s′ | s, a). In game trees, this introduces chance nodes alongside MAX and MIN nodes. Backgammon, Monopoly, and Yahtzee are stochastic games.

2.Minimax & Alpha-Beta Pruning

When two rational players compete in a zero-sum, perfect-information, deterministic game, what constitutes an optimal move? The classic answer was formulated by John von Neumann in the Minimax Theorem (1928) and adapted to artificial intelligence search trees by Shannon (1950) and McCarthy (1956).

2.1The Minimax Value

The minimax value of a state s, written MINIMAX(s), represents the best achievable utility for MAX from state s, under the fundamental assumption that both players play with perfect rationality from s until game termination.

The logic is symmetric: MAX chooses whichever legal move leads to the successor state with the highest minimax value; MIN chooses whichever legal move leads to the successor state with the lowest minimax value (which minimizes MAX's score and maximizes MIN's score).

2.2The Minimax Algorithm & Value Trace

The Minimax algorithm performs a complete depth-first search (DFS) traversal of the entire game tree. It recurses down to the terminal leaves, evaluates their true utility using UTILITY(s, MAX), and then backs up (propagates) these values bottom-up through the tree:

function MINIMAX-DECISION(state) returns an action
    return argmaxa ∈ ACTIONS(state) MIN-VALUE(RESULT(state, a))

function MAX-VALUE(state) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state, MAX)
    v ← −∞
    for each a in ACTIONS(state) do
        v ← max(v, MIN-VALUE(RESULT(state, a)))
    return v

function MIN-VALUE(state) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state, MAX)
    v ← +∞
    for each a in ACTIONS(state) do
        v ← min(v, MAX-VALUE(RESULT(state, a)))
    return v

Consider the classic AIMA Figure 5.2 two-ply game tree: Root A (MAX) has children B, C, D (all MIN nodes). Node B has leaves with utilities (3, 12, 8); Node C has leaves (2, 4, 6); Node D has leaves (14, 5, 2).

• MIN-VALUE(B) = min(3, 12, 8) = 3
• MIN-VALUE(C) = min(2, 4, 6) = 2
• MIN-VALUE(D) = min(14, 5, 2) = 2
• MAX-VALUE(A) = max(3, 2, 2) = 3, achieved by selecting action a = Move(B).

Even though Node D has a leaf with utility +14, MAX cannot reach it because MIN, acting rationally, would choose the reply yielding 2. The minimax decision at the root correctly selects branch B to guarantee a utility of at least 3.

Time Complexity

O(bm) — Minimax must visit every node in the game tree.

Space Complexity

O(bm) — depth-first recursion stack storing active sibling nodes down to depth m.

Completeness

Yes, if the tree is finite.

Optimality

Yes, against an optimal opponent. Against a suboptimal opponent who makes mistakes, Minimax guarantees at least the minimax payoff, but does not take speculative risks to exploit blunders.

2.3Alpha (α) & Beta (β) Bounds

The exponential time complexity O(bm) renders exhaustive minimax search completely impractical for nontrivial games (e.g., chess has ≈ 10⁴⁰ nodes even at depth 10). However, it is possible to compute the exact same minimax value without evaluating every node in the tree.

Alpha-Beta Pruning maintains two scalar bounds along the search path from the root to the current node:

• α (Alpha): The value of the best (highest-value) choice found so far at any choice point along the path for MAX. Initialized to α = −∞ at the root.
• β (Beta): The value of the best (lowest-value) choice found so far at any choice point along the path for MIN. Initialized to β = +∞ at the root.

The interval [α, β] represents the search window — the range of viable game values. If at any point the algorithm discovers that a child node's value falls outside this window, the remaining sibling branches cannot possibly affect the root's decision and can be pruned immediately.

2.4Alpha-Beta Pruning Algorithm

Pruning occurs whenever α ≥ β:

• At a MAX node: MAX seeks values greater than α. If MAX evaluates a child with value v ≥ β, MAX immediately returns v without evaluating remaining children. Reason: MIN above this node already has a guaranteed option of value β; MIN will never allow play to reach a state that awards MAX v ≥ β.
• At a MIN node: MIN seeks values less than β. If MIN evaluates a child with value v ≤ α, MIN immediately returns v without evaluating remaining children. Reason: MAX above this node already has a guaranteed option of value α; MAX will never choose the branch that enters this MIN node.

function ALPHA-BETA-SEARCH(state) returns an action
    v ← MAX-VALUE(state, −∞, +∞)
    return the action in ACTIONS(state) with outcome value v

function MAX-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state, MAX)
    v ← −∞
    for each a in ACTIONS(state) do
        v ← max(v, MIN-VALUE(RESULT(state, a), α, β))
        if v ≥ β then return v   // β-cutoff (prune remaining MIN branches)
        α ← max(α, v)
    return v

function MIN-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state, MAX)
    v ← +∞
    for each a in ACTIONS(state) do
        v ← min(v, MAX-VALUE(RESULT(state, a), α, β))
        if v ≤ α then return v   // α-cutoff (prune remaining MAX branches)
        β ← min(β, v)
    return v

2.5The Impact of Move Ordering

Alpha-Beta pruning never changes the final returned move or minimax value — it is mathematically exact. However, the number of nodes examined depends entirely on the order in which child moves are evaluated:

• Worst-Case Ordering: If children are ordered from worst to best, no pruning occurs at all. The algorithm visits all O(bm) nodes, identical to standard Minimax.
• Random Ordering: With random move ordering, Alpha-Beta evaluates approximately O(b3m/4) nodes.
• Optimal Move Ordering: If the best move is always examined first, Alpha-Beta evaluates only O(bm/2) = O((\sqrt{b})m) nodes.

This is a profound result: with optimal move ordering, the effective branching factor drops from b to √b. In chess (b ≈ 35), the effective branching factor drops to √35 ≈ 6. This means Alpha-Beta can search twice as deep as Minimax in the same amount of computation time.

Practical game engines employ domain-independent heuristics to achieve near-optimal move ordering:

• Principal Variation / Iterative Deepening: Use the best move discovered in the previous shallow iteration (depth d−1) as the first move examined at depth d.
• Killer Moves: Moves that caused a β-cutoff in a sibling position at the same depth are tried early.
• Captures & Tactical Moves (MVV-LVA): Most Valuable Victim – Least Valuable Attacker (e.g., Pawn taking Queen is evaluated before Queen taking Pawn).
• History Heuristic: Maintain a table counting how often each action caused a cutoff across all search positions.

3.Heuristic Evaluation & Resource Limits

Even with Alpha-Beta pruning, searching to the true terminal leaves of games like Chess (10⁴⁰ nodes) or Go (10³⁶⁰ states) is computationally impossible. Real-time game engines must make a decision within seconds or minutes. In 1950, Claude Shannon proposed replacing the exhaustive search with a heuristic depth cutoff.

3.1Depth Cutoffs & Real-Time Limits

A resource-limited game search replaces the exact TERMINAL-TEST(state) with a CUTOFF-TEST(state, depth):

When CUTOFF-TEST evaluates to true on a non-terminal state at depth d (the search horizon), the search does not continue downward. Instead, it calls a heuristic evaluation function EVAL(s) that estimates the expected utility of state s.

3.2Evaluation Functions (EVAL)

An evaluation function EVAL(s) maps a non-terminal board configuration to a real number estimating the winning chances of MAX. A valid evaluation function must satisfy three fundamental properties:

1. Agreement with Terminal Utilities: EVAL(s) must order terminal states identically to UTILITY(s) (e.g., a checkmate win must score higher than any non-terminal advantage).
2. Fast Computation: EVAL(s) is called millions of times per second; computing it must be computationally lightweight.
3. Strong Correlation with True Winning Chances: For non-terminal states, higher values must reliably correspond to higher probabilities of winning.

Evaluation functions are traditionally formulated as a weighted linear combination of board features:

In chess, classic features fi(s) include:

• Material Balance: f1 = (QMAX − QMIN), with standard piece weights wPawn = 1, wKnight = 3, wBishop = 3.25, wRook = 5, wQueen = 9.
• Piece-Square Tables: Positional bonuses rewarding Knights in the center and Pawns on advanced squares.
• Mobility: Number of legal moves available (restricting opponent mobility is advantageous).
• King Safety: Castling status, pawn shield integrity, and enemy open attacking files.
• Pawn Structure: Penalties for isolated, doubled, or backward pawns; bonuses for passed pawns.

3.3Quiescence Search

Evaluating an arbitrary board state strictly when depth = d causes disastrous blunders if the position is in the middle of an unresolved tactical trade. For example, if MAX captures MIN's Queen on ply d, a raw cutoff evaluates MAX as having a massive +9 material advantage — completely unaware that MIN recaptures MAX's Queen on ply d+1.

Positions with active captures, checks, or threats are called turbulent (non-quiescent). A robust engine applies Quiescence Search:

• At depth d, test QUIESCENT(s). If the state is quiet (no pending captures or forced tactical moves), return EVAL(s).
• If the state is non-quiescent, extend search deeper along capture and check moves only, until tactical equilibrium is restored.

3.4The Horizon Effect

The horizon effect occurs when an inevitable, damaging move by the opponent is delayed beyond the search horizon d by playing useless stalling moves or sacrificial checks.

Example: MAX's Bishop is trapped and unavoidably lost. But MAX has several meaningless checks with other pieces. By playing check on move 1, check on move 2, etc., MAX pushes the capture of the Bishop past depth d. At the search horizon, the Bishop appears safe, but MAX has ruined its position by sacrificing pawns and pieces purely to postpone the inevitable.

3.5Transposition Tables & Zobrist Hashing

Game state spaces are directed acyclic graphs (DAGs), not trees. Different move orders (e.g., 1. e4 e5 2. Nf3 vs. 1. Nf3 e5 2. e4) reach the exact same board configuration — called a transposition.

A Transposition Table is a high-speed hash table caching previously evaluated states:

• Zobrist Hashing: Each board square and piece type is assigned an independent 64-bit random number. The hash of a board position is computed in O(1) time via XOR operations on piece moves: hash′ = hash ⊕ table[piece, from] ⊕ table[piece, to].
• Cache Hits: If a state is encountered at equal or greater depth, its stored value and bounds are returned immediately, eliminating entire subtrees of redundant search.

4.Chance & Monte Carlo Tree Search

Classical Minimax assumes deterministic outcomes. Many real-world games incorporate random chance (Backgammon, Monopoly, Pig, Poker). Furthermore, games with massive branching factors like Go (b ≈ 250) defied heuristic evaluation functions for decades until the invention of Monte Carlo Tree Search (MCTS).

4.1Expectiminimax & Chance Nodes

To model games with dice rolls, card shuffling, or coin flips, the game tree introduces chance nodes (traditionally drawn as circles ◯) alongside MAX nodes (▵) and MIN nodes (∇).

While MAX and MIN nodes compute extreme values (max and min), chance nodes compute the mathematical expectation (weighted average) over all possible random outcomes weighted by their transition probabilities P(s′ | s).

Complexity: If there are n distinct chance outcomes per chance node, the time complexity scales to O(bm · nm) = O((bn)m). Standard Alpha-Beta pruning cannot easily prune chance nodes without strict mathematical bounds on leaf utilities.

4.2Utility Scale & Transformations

In deterministic Minimax, any monotonic (order-preserving) transformation f(u) where u1 > u2 ⇒ f(u1) > f(u2) produces the exact same moves, because max(f(x), f(y)) = f(max(x, y)).

In Expectiminimax, however, this property breaks down! Expected values are sensitive to nonlinear scaling:

Example: Consider two chance actions. Action A gives 1.0 with certainty (Expected = 1.0). Action B gives 0 with probability 0.5 and 3.0 with probability 0.5 (Expected = 1.5). Under original utilities, Action B is preferred (1.5 > 1.0). If we apply monotonic transform f(u) = √u, Action A yields √1 = 1.0, while Action B yields 0.5(0) + 0.5(√3) ≈ 0.866. The preference flips to Action A! Utilities in stochastic games must be genuine cardinal values, not arbitrary ordinal rankings.

4.3Monte Carlo Tree Search Overview

In games like Go, chess evaluation functions fail because subtle stone liberties and territory boundaries cannot be captured by linear feature sums. Monte Carlo Tree Search (MCTS), developed by Coulom (2006) and Kocsis & Szepesvári (2006), solves this without requiring any evaluation function.

Instead of computing static heuristics, MCTS evaluates a board position by playing out thousands of fast, random simulated games (rollouts) to the very end and recording the win/loss frequency.

4.4The 4-Phase MCTS Cycle

MCTS builds a search tree incrementally through four iterative steps:

Phase 1: Selection & UCB1

Starting at the root, the algorithm traverses the existing search tree by selecting child nodes that maximize the Upper Confidence Bound for Trees (UCB1) formula:

• Exploitation Term (U(n)/N(n)): The average win rate / utility of node n. Encourages choosing moves that have proven successful.
• Exploration Term (C · √(ln Nparent / Nn)): Gives a statistical bonus to moves with low visit counts N(n). As parent visits grow, rarely explored branches become increasingly attractive.
• Exploration Constant (C): Balances exploration vs. exploitation. Theoretically C = √2 ≈ 1.414 for rewards in [0, 1].

Phase 2: Expansion

When the selection step reaches a node that has unvisited legal actions (or a leaf node that is non-terminal), one or more new child nodes are added to the search tree.

Phase 3: Simulation (Rollout)

From the newly added node, a simulation is played out to the end of the game using a fast rollout policy (e.g., choosing legal actions uniformly at random, or with lightweight heuristic preferences). No tree nodes are stored during simulation — it executes rapidly to produce a single terminal payoff v ∈ {+1, 0, −1}.

Phase 4: Backpropagation & Final Decision

The outcome v is propagated back up the search path from the newly expanded node to the root. For every ancestor node n along the path:

Move Selection at the Root: After thousands of MCTS iterations (when time expires), the agent chooses the action corresponding to the most-visited child node (argmaxa N(childa)), not the child with the highest single win rate. Visit count is far more stable and resistant to statistical variance.

4.5Asymmetric Tree Growth

Traditional Minimax builds a uniform, symmetric search tree exploring every branch to depth d. In contrast, MCTS exhibits asymmetric tree growth: the UCB1 formula naturally directs computation down heavily contested, high-promise variations (growing trees to depth 50+ along critical lines) while abandoning poor moves after just 2 or 3 simulations.

5.Evaluating Game Search Algorithms

This section synthesizes the theoretical properties, computational bounds, and real-world applicability of all game search strategies.

5.1Game Complexity Parameters

The complexity of game search algorithms is parameterized by four core quantities:

• b: Branching factor (number of legal actions per state).
• m: Maximum depth of the game tree (number of plies to terminal states).
• d: Search cutoff depth (the search horizon).
• N: Total number of MCTS simulation rollouts.
• n: Number of distinct random outcomes per chance node in stochastic games.

5.2Time & Space Complexity

Because Minimax and Alpha-Beta are depth-first search algorithms, their space complexity is strictly linear in depth: O(bm) or O(bd). They only need to hold the active search path and unexplored siblings in memory.

MCTS, however, stores every expanded node in memory. Its space complexity is proportional to the tree size: O(N) for N iterations.

5.3Completeness & Optimality Guarantees

• Minimax & Alpha-Beta: Guaranteed complete on finite trees and optimal against an optimal opponent. Against a fallible opponent who makes mistakes, Minimax guarantees the game-theoretic value, but does not actively set traps or exploit blunders.
• Expectiminimax: Optimal in the sense of maximizing expected utility against a rational opponent in stochastic settings.
• MCTS: As the number of rollouts N → ∞, UCB1 guarantees that the probability of choosing a suboptimal move converges to zero — MCTS converges asymptotically to the true Minimax value.

5.4Search Strategy Comparison Matrix

6.Practice Exercises

These four worked exercises test your mastery of minimax propagation, alpha-beta pruning derivation, expectiminimax decision making, and MCTS UCB1 calculations.

Value(D) = max(4, 7) = 7
Value(E) = max(2, 8) = 8
Value(F) = max(1, 5) = 5
Value(G) = max(3, 6) = 6

Value(B) = min(Value(D), Value(E)) = min(7, 8) = 7
Value(C) = min(Value(F), Value(G)) = min(5, 6) = 5

Value(A) = max(Value(B), Value(C)) = max(7, 5) = 7
Optimal Move: MAX chooses action A → B (guaranteeing utility ≥ 7).

1. At Root A (MAX): [α = −∞, β = +∞]. Recurse into child B.
2. At Node B (MIN): [α = −∞, β = +∞]. Recurse into child B1.
3. At Node B1 (MAX): [α = −∞, β = +∞].
   - Leaf 3: v = max(−∞, 3) = 3 ⇒ α = max(−∞, 3) = 3.
   - Leaf 5: v = max(3, 5) = 5 ⇒ α = max(3, 5) = 5.
   - Return v = 5 to B.
4. At Node B (MIN): v = min(+∞, 5) = 5 ⇒ β = min(+∞, 5) = 5. Window at B is [−∞, 5].
5. At Node B2 (MAX): Passed [α = −∞, β = 5].
   - Leaf 2: v = max(−∞, 2) = 2 ⇒ α = 2.
   - Leaf 9: v = max(2, 9) = 9. Since v=9 ≥ β=5, β-cutoff triggers! Return 9.
6. At Node B (MIN): v = min(5, 9) = 5. Return v = 5 to Root A.
7. At Root A (MAX): v = max(−∞, 5) = 5 ⇒ α = max(−∞, 5) = 5. Window at A is [α = 5, β = +∞].
8. At Node C (MIN): Passed [α = 5, β = +∞]. Recurse into child C1.
9. At Node C1 (MAX): Passed [α = 5, β = +∞].
   - Leaf 1: v = max(−∞, 1) = 1.
   - Leaf 4: v = max(1, 4) = 4.
   - Return v = 4 to C.
10. At Node C (MIN): v = min(+∞, 4) = 4 ⇒ β = min(+∞, 4) = 4.
    - Check Pruning Condition: α = 5 ≥ β = 4  (α ≥ β).
    - PRUNE! The entire remaining subtree of C (node C2 and leaves 8, 7) is PRUNED!
11. At Root A (MAX): v = max(5, 4) = 5. Minimax decision is action A → B with value 5.

EV(C1) = ∑ P(s′) · Utility(s′)
       = 0.5 × (+10) + 0.5 × (−4)
       = +5.0 − 2.0 = +3.0

EV(C2) = ∑ P(s′) · Utility(s′)
       = 0.25 × (+20) + 0.25 × (−10) + 0.25 × (+4) + 0.25 × (0)
       = +5.0 − 2.5 + 1.0 + 0 = +3.5

Decision = argmax(EV(C1), EV(C2)) = argmax(3.0, 3.5) = a2

Exploitation:  28 / 40 = 0.7000
Exploration:   1.414 × √(4.6052 / 40) = 1.414 × √(0.11513) = 1.414 × 0.33931 = 0.4798
UCB1(A1)     = 0.7000 + 0.4798 = 1.1798

Exploitation:  30 / 50 = 0.6000
Exploration:   1.414 × √(4.6052 / 50) = 1.414 × √(0.09210) = 1.414 × 0.30349 = 0.4291
UCB1(A2)     = 0.6000 + 0.4291 = 1.0291

Exploitation:  8 / 10 = 0.8000
Exploration:   1.414 × √(4.6052 / 10) = 1.414 × √(0.46052) = 1.414 × 0.67862 = 0.9596
UCB1(A3)     = 0.8000 + 0.9596 = 1.7596