Adversarial Search

From search to adversarial search

Ordinary search asks: "Which sequence of my actions reaches the goal?" Adversarial search asks: "Which action is best after accounting for the opponent's best response?" The opponent is part of the model, not noise added later.

Games are classified as deterministic vs stochastic (dice), two-player vs multi-player, zero-sum (one's gain is the other's loss) vs general-sum, and perfect vs imperfect information (poker hides cards). We start with deterministic, two-player, zero-sum, perfect-information games such as tic-tac-toe, chess and Go.

A game as a formal problem

• S₀: initial state. PLAYER(s): whose turn it is (MAX or MIN).
• ACTIONS(s): legal moves. RESULT(s, a): transition model.
• TERMINAL-TEST(s): is the game over? UTILITY(s): final score for MAX (+1 win / 0 draw / −1 loss).

MAX wants a high utility and MIN wants a low one, on the same scale. Tic-tac-toe already has 9 first moves, 8 replies, 7 answers… The full tree is finite but has 255,168 possible games.

The minimax principle

Assume both players are rational. MAX picks the move with the highest guaranteed value, and MIN picks what is worst for MAX. Values are backed up from the leaves to the root:

Worked example (lecture tree)

1. Left MIN node: min(3, 12, 8) = 3.
2. Middle MIN node: min(2, 4, 6) = 2.
3. Right MIN node: min(14, 5, 2) = 2.
4. Root MAX: max(3, 2, 2) = 3, so MAX plays the left move.

Minimax is optimal against an optimal opponent, but it is expensive: with branching factor b and depth m it explores O(b^m) states. Chess has b ≈ 35 and games of ~80 plies (half-moves), far too many.

Alpha–beta pruning

Many branches can't change the decision. Alpha–beta pruning skips them and returns exactly the same root value as minimax.

• α = the best value MAX can guarantee so far on the current path (starts at −∞).
• β = the best value MIN can guarantee so far on the current path (starts at +∞).
• At a MAX node: α ← max(α, v); stop if v ≥ β. At a MIN node: β ← min(β, v); stop if v ≤ α.
• Prune when α ≥ β: the remaining siblings can't affect the decision.

On our tree: after the left subtree, α = 3. In the middle subtree the first leaf is 2, so that MIN node is worth at most 2. MAX already has 3, so the leaves 4 and 6 don't matter: pruned. In the right subtree MIN sees 14 (β=14), 5 (β=5), then 2 (β=2 ≤ α). That was the last leaf anyway. Visited leaves: 3, 12, 8, 2, 14, 5, 2, which is 7 of 9.

def alphabeta(state, alpha, beta, maximizing):
    if terminal(state): return utility(state)
    if maximizing:
        v = float("-inf")
        for child in successors(state):
            v = max(v, alphabeta(child, alpha, beta, False))
            alpha = max(alpha, v)
            if alpha >= beta: break        # β-cutoff
        return v
    else:
        v = float("inf")
        for child in successors(state):
            v = min(v, alphabeta(child, alpha, beta, True))
            beta = min(beta, v)
            if alpha >= beta: break        # α-cutoff
        return v

Move ordering matters. If the best moves are tried first, bounds tighten early and pruning is strongest. With perfect ordering alpha–beta examines about O(b^m/2) nodes, so it can search twice as deep in the same time.

Real games: depth limits & evaluation functions

Real games can't be searched to the end. We stop at a depth limit d and replace the true utility with an evaluation function that estimates how good a position is, usually a weighted sum of features:

Compare: an A* heuristic estimates remaining path cost; a game evaluation estimates the strategic quality of a state. Both inject domain knowledge into search.

Horizon effect: a disaster just beyond the depth limit stays invisible, so a position may look great while a loss is one move away. Deeper search and quiescence search (extending tactically unstable positions until quiet positions are reached) help but don't fully remove it.

Practical 4 warm-up: a delivery price war (MAX = our company)

Payoffs are invented profit (million KZT) in a simplified zero-sum model. Minimax: MIN answers each strategy with its smallest payoff (4, 3, 1), and MAX takes the largest of those, so it plays A with a guaranteed value of 4. C has the tempting 9, but a rational competitor would never allow it.

When the opponent is chance: expectimax

Minimax assumes the uncontrolled choice is adversarial. Dice, slipping wheels or a random ghost aren't trying to beat you, so worst-case thinking is too pessimistic. Expectimax replaces MIN nodes with chance nodes that compute an expected value:

The rule of thumb: use minimax against strategic opponents and expectimax when a probability model describes the uncertainty better. Treating an adversary as random is dangerously optimistic. Treating randomness as an adversary is needlessly pessimistic.