Adversarial Search

Ordinary search assumes that action outcomes follow a fixed transition model. In a game, the next state also depends on another decision maker whose interests may conflict with ours. A move cannot be judged only by what it makes possible; it must be judged by what remains possible after an opponent responds intelligently.

Adversarial search models this strategic dependence. It is useful beyond board games: cybersecurity, negotiation, competitive pricing, robust planning, and resource competition all involve choices made in anticipation of other agents.

Game Types

The classical minimax model assumes a game that is:

• deterministic;
• turn-taking;
• two-player;
• zero-sum;
• fully observable;
• finite.

Chess and tic-tac-toe approximately fit. Dice introduce stochastic transitions. Poker hides information. Team games have more than two players. Negotiation can be general-sum because both parties may benefit.

An algorithm’s guarantees apply only to the game model it assumes.

Game Model

A deterministic game can be described by:

• states S, including an initial state;
• player(s), identifying whose turn it is;
• actions(s), the legal moves;
• result(s, a), the successor state;
• terminal(s), whether play has ended;
• utility(s, p), the final payoff to player p.

A solution is not one path. It is a policy that recommends an action for every state the opponent might force us to encounter.

In a zero-sum game, one player’s utility is the negative of the other’s. We can therefore use one value: MAX tries to increase it and MIN tries to decrease it.

Minimax

For terminal states, value is known from utility. For non-terminal states:

V(s) = max V(result(s,a))   when MAX moves
V(s) = min V(result(s,a))   when MIN moves

Values are backed up from leaves to the root. MAX assumes MIN will choose the most damaging response; MIN assumes MAX will choose the strongest move.

Example

Suppose MAX can choose A or B.

          MAX
        /     \
       A       B
      MIN     MIN
     /  \     /  \
    3    5   2    9

MIN would turn A into value 3 and B into value 2. MAX therefore chooses A, guaranteeing at least 3. Choosing B because it contains a possible 9 would be irrational against an opponent who can force 2.

Implementation

def minimax_tree(tree, maximizing=True):
    if isinstance(tree, int):
        return {"value": tree, "leaves": 1}
    if not tree:
        raise ValueError("an internal node needs children")

    child_results = []
    for child in tree:
        result = minimax_tree(child, not maximizing)
        child_results.append(result)

    values = []
    total_leaves = 0
    for result in child_results:
        values.append(result["value"])
        total_leaves += result["leaves"]

    if maximizing:
        best_value = max(values)
    else:
        best_value = min(values)

    return {"value": best_value, "leaves": total_leaves}

Nested tuples are a transparent compact model: tuples are positions with legal children, integers are terminal utilities, and levels alternate between MAX and MIN. A real game replaces tuple indexing with actions(state) and result(state, action), but the recurrence is unchanged.

With branching factor b and depth m, exhaustive minimax takes O(b^m) time and depth-first space around O(bm). Even modest games become infeasible.

Depth Limits

Real programs stop search before terminal states and evaluate cutoff positions:

Eval(s) ≈ true minimax value of s

For a board game, a linear evaluation may combine features:

Eval(s) = w₁ material + w₂ mobility + w₃ safety + w₄ position

The features and weights express domain knowledge. A deeper search can compensate for a rough evaluation, while an expensive evaluation reduces searchable depth.

Horizon Effect

A cutoff may hide a decisive event just beyond the horizon. A program might postpone an unavoidable loss until after the search limit and mistakenly rate the position well.

Mitigations include:

• iterative deepening;
• extending tactically unstable positions;
• quiescence search;
• stronger evaluation features.

Replanning Failure

Repeatedly planning a short distance ahead does not automatically create long-term intelligence. Suppose an agent receives a reward only after three uninterrupted preparation actions, but replans with a two-step horizon. At every decision point, the delayed reward remains invisible. An immediate small reward therefore looks better forever, and the important task is starved.

A second failure is thrashing. If two actions look equally promising within the horizon, small changes in the state or evaluation can make the agent alternate between them. Each new plan abandons the progress made by the previous one.

Possible remedies include:

• evaluation features that value partial progress;
• commitments that cannot be casually reversed;
• longer or adaptive search horizons;
• remembering abandoned plans and switching costs;
• searching until a stable or tactically quiet state.

Replanning is useful when the world changes, but the evaluation must connect short searches to long-term goals.

Iterative Deepening

Search first to depth 1, then 2, then 3, retaining the best completed result. If interrupted, the agent can still act using the last completed depth.

Repeated upper-level work is offset by:

• most nodes occurring near the deepest level;
• improved move ordering from earlier iterations;
• predictable time control;
• a valid action being available at any interruption.

Alpha-Beta

Alpha-beta pruning avoids branches that cannot affect the minimax decision.

• α is the best value MAX can already guarantee along the current path.
• β is the best value MIN can already guarantee.

At a MAX node, if a child makes the value at least β, MIN would never allow this branch; remaining children can be pruned. At a MIN node, a value at most α allows symmetric pruning.

def alpha_beta_tree(
    tree,
    maximizing=True,
    alpha=float("-inf"),
    beta=float("inf"),
):
    if isinstance(tree, int):
        return {"value": tree, "leaves": 1, "cutoffs": 0}
    if not tree:
        raise ValueError("an internal node needs children")

    value = float("-inf") if maximizing else float("inf")
    leaves = 0
    cutoffs = 0

    for index, child in enumerate(tree):
        result = alpha_beta_tree(
            child, not maximizing, alpha, beta
        )
        leaves += result["leaves"]
        cutoffs += result["cutoffs"]

        if maximizing:
            value = max(value, result["value"])
            alpha = max(alpha, value)
        else:
            value = min(value, result["value"])
            beta = min(beta, value)

        if alpha >= beta:
            cutoffs += len(tree) - index - 1
            break

    return {
        "value": int(value),
        "leaves": leaves,
        "cutoffs": cutoffs,
    }

TREE = (
    (3, 5, 6),
    (9, 1, 2),
    (0, -1, 7),
)

plain = minimax_tree(TREE)
pruned = alpha_beta_tree(TREE)

assert pruned["value"] == plain["value"]
assert pruned["leaves"] <= plain["leaves"]
print("minimax value:", pruned["value"])
print("leaves evaluated:", pruned["leaves"])
print("branches cut:", pruned["cutoffs"])

Alpha-beta returns the same root minimax value as exhaustive search. It changes computation, not the decision rule. The equality assertion is the central correctness check. cutoffs counts sibling branches skipped at their parent; it is a teaching metric, not the exact number of leaf states hidden beneath those branches.

Move Ordering

Pruning effectiveness depends on examining strong moves first. With poor ordering, alpha-beta approaches O(b^m). With ideal ordering, it approaches O(b^(m/2)), effectively doubling searchable depth for the same node budget.

Ordering methods include:

• the best move from the previous iterative-deepening pass;
• captures or forcing actions first;
• domain-specific tactical priorities;
• cached results from previously evaluated positions.

Ordering is metareasoning: computation used to decide which computation is valuable.

Root Actions

Alpha-beta guarantees the correct minimax choice at the root, but not every intermediate number produced during a pruned search is an exact minimax value. Some returned values are only bounds: a cutoff proves that a branch cannot improve the decision, so the algorithm has no reason to finish measuring that branch.

This matters when selecting an action. The root search should update best_action whenever it finds a better child while using the normal alpha-beta window. A fragile implementation instead searches one child, then separately asks for exact-looking values of all other children using narrowed windows and compares those numbers as though every one were exact.

The safe interpretation is:

• the completed root value and chosen root action are exact for the searched tree;
• a fully searched node has an exact value;
• a cutoff node may carry only a lower or upper bound;
• move ordering changes which branches receive exact values, but not the correct root decision.

Transposition tables therefore store whether a cached number is exact, a lower bound, or an upper bound. Treating all cached values as exact can produce a wrong move even when the pruning logic itself is sound.

Game Tree Analysis

Trace a small tree by recording, for each recursive call:

node, player, alpha before, beta before,
child value, updated bound, cutoff?

First compute minimax bottom-up by hand. Then run alpha-beta left-to-right and verify the same root value. Finally reorder root and internal children without changing the utilities. The returned value must remain fixed while evaluated-leaf count changes.

This experiment separates two claims that are often confused:

• alpha-beta is correct regardless of move order;
• alpha-beta is efficient only when good moves are considered early.

For a depth-limited game, replace terminal integers with an evaluation function at the cutoff depth. At that point the result is an estimate, and comparison with full minimax on a small tree becomes a useful evaluation-function test.

Transposition Tables

Different action sequences may reach the same position. A transposition table caches:

• state key;
• searched depth;
• value or value bound;
• best known move.

The cache key must include everything affecting future play: board arrangement, player to move, and rule-specific history. An incomplete key can reuse an invalid result.

Imperfect Opponents

Minimax assumes optimal opposition. It guarantees the best worst-case outcome but can be conservative against a predictable weak opponent.

An exploitative strategy models the opponent’s likely actions and may gain more, but risks doing worse if the model is wrong. Robust systems may combine:

• worst-case protection;
• opponent modelling;
• uncertainty over opponent type;
• online adaptation.

Chance Games

For stochastic games, expectiminimax adds chance nodes:

V(s) = Σ P(outcome | s) × V(outcome)

For hidden-information games, the agent reasons over information sets or beliefs rather than a single fully known state. Strategies may need randomization so an opponent cannot exploit predictable behavior.

These are not minor modifications. They change the state representation and the meaning of a policy.

Applications

• board and video-game agents;
• defensive cybersecurity;
• bidding and auctions;
• competitive resource allocation;
• negotiation;
• robust planning against worst-case disturbances;
• automated testing where one agent seeks failures.

Common Mistakes

• Using minimax for a non-zero-sum setting without modelling separate utilities.
• Returning the largest leaf visible anywhere rather than backing up MIN choices.
• Evaluating positions without including whose turn it is.
• Claiming alpha-beta changes the optimal move.
• Ignoring move order and receiving almost no pruning.
• Treating evaluation scores as true utilities.
• Comparing agents only against one opponent.
• Forgetting that depth measured in plies counts individual player moves.

Exercises

1. Back up minimax values for a three-level game tree and identify the root action.
2. Trace alpha and beta values by hand and mark every pruned branch.
3. Implement tic-tac-toe using minimax and verify that two perfect agents draw.
4. Add depth limits and create two evaluation functions. Find positions where they disagree.
5. Measure alpha-beta node counts under best-first, random, and worst-first move ordering.
6. Extend a small game with a dice outcome and implement chance nodes.
7. Give a real decision problem that is adversarial but not zero-sum. Explain why ordinary minimax is insufficient.
8. Instrument the implementation with a complete alpha-beta trace.
9. Find best- and worst-case child orders for one fixed tree.
10. Compare cutoff evaluations with exact minimax on shallow trees.