Adversarial search is planning when someone else moves too. In a two-player, zero-sum, perfect-information game (chess, Go, tic-tac-toe, Connect Four) your best move depends on the opponent's best reply, which depends on your best reply to that, and so on. The classic answer is minimax with alpha-beta pruning; the modern answer for huge branching factors is Monte Carlo Tree Search (MCTS), usually paired with a learned policy/value network as in AlphaZero.
This page is part of Search & Planning. See also Constraint Satisfaction and Reinforcement Learning.
A game is defined by an initial state s0, a function PLAYER(s) saying whose turn it is, ACTIONS(s), a transition RESULT(s, a), a TERMINAL(s) test, and a UTILITY(s, p) for terminal states. Zero-sum means one player's gain is the other's loss, so a single number scored from MAX's point of view is enough: MAX wants it high, MIN wants it low.
The size of the game tree is roughly bd for branching factor b and depth d. Tic-tac-toe is small enough to solve exhaustively; chess (b around 35) and Go (b around 250) are not, which is why depth limits, evaluation functions, pruning and sampling exist.
Minimax computes the value of every state assuming both players play optimally:
MINIMAX(s) = UTILITY(s) if terminal; maxa MINIMAX(RESULT(s,a)) if MAX moves; mina MINIMAX(RESULT(s,a)) if MIN moves.
It is a depth-first traversal, so memory is O(bd) but time is O(bd). For real games you cut off at a fixed depth and replace UTILITY with a heuristic evaluation function (material count, mobility, a neural value head). The negamax formulation exploits zero-sum symmetry: value(s) = maxa -value(RESULT(s,a)), which removes the MAX/MIN branches from the code.
Alpha-beta returns exactly the minimax value while skipping subtrees that cannot influence the decision. It carries two bounds down the recursion: α, the best value MAX can already guarantee on the path, and β, the best value MIN can guarantee. Whenever α ≥ β at a node, the remaining children are cut.
Effectiveness depends entirely on move ordering. With perfect ordering the effective branching factor drops to about √b, so you can search roughly twice as deep in the same time; with worst-case ordering you prune nothing. Practical engines add iterative deepening (search depth 1, 2, 3... and reuse the best move to order the next iteration), transposition tables (hash positions reached by different move orders), killer-move and history heuristics, and quiescence search to avoid stopping in the middle of a capture sequence.
MCTS needs no evaluation function. It grows an asymmetric tree by repeated sampling: each iteration walks down using the UCT rule (UCB1 applied to trees), adds one node, plays a fast rollout to a terminal state, and propagates the result back up. Over many iterations visit counts concentrate on the strongest lines, and the final move is usually the root child with the most visits (more robust than the highest mean).
The exploration constant c (often around √2 for rewards in [0,1]) balances exploitation of good moves against exploring uncertain ones. AlphaGo Zero and AlphaZero replace random rollouts with a neural value estimate and bias selection with a policy prior (the PUCT rule), which is what made MCTS dominant in Go and strong in chess and shogi.
import math, random
WINS = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
def winner(b):
for i, j, k in WINS:
if b[i] != "." and b[i] == b[j] == b[k]:
return b[i]
return "draw" if "." not in b else None
def moves(b):
return [i for i, c in enumerate(b) if c == "."]
def play(b, i, p):
return b[:i] + p + b[i+1:]
other = {"X": "O", "O": "X"}
# ---- Negamax with alpha-beta ----
def negamax(b, p, alpha=-2, beta=2):
w = winner(b)
if w == "draw": return 0, None
if w: return (1 if w == p else -1), None
best, best_move = -2, None
for m in moves(b):
score = -negamax(play(b, m, p), other[p], -beta, -alpha)[0]
if score > best:
best, best_move = score, m
alpha = max(alpha, score)
if alpha >= beta:
break # cutoff
return best, best_move
# ---- MCTS with UCT ----
class Node:
def __init__(self, b, p, parent=None, move=None):
self.b, self.p, self.parent, self.move = b, p, parent, move
self.children, self.untried = [], moves(b) if winner(b) is None else []
self.N, self.W = 0, 0.0 # W from the view of the player who moved INTO this node
def uct(self, c=1.41):
return self.W / self.N + c * math.sqrt(math.log(self.parent.N) / self.N)
def mcts(b, p, iters=3000):
root = Node(b, p)
for _ in range(iters):
node = root
while not node.untried and node.children: # 1. selection
node = max(node.children, key=Node.uct)
if node.untried: # 2. expansion
m = node.untried.pop(random.randrange(len(node.untried)))
child = Node(play(node.b, m, node.p), other[node.p], node, m)
node.children.append(child)
node = child
sb, sp = node.b, node.p # 3. simulation
while winner(sb) is None:
sb = play(sb, random.choice(moves(sb)), sp); sp = other[sp]
w = winner(sb)
while node: # 4. backprop
mover = other[node.p]
node.N += 1
node.W += 1.0 if w == mover else (0.5 if w == "draw" else 0.0)
node = node.parent
return max(root.children, key=lambda n: n.N).move
board = "X.O" "..." "..."
print("negamax:", negamax(board, "X")) # (value, move)
print("mcts :", mcts(board, "X"))
Both agents should choose a strong move; negamax is exact here because the tree is tiny, while MCTS converges toward the same choice as the iteration count grows.
| Situation | Good fit | Why |
|---|---|---|
| Small/medium branching factor, good hand-written evaluation | Alpha-beta + iterative deepening | Exact within the horizon; mature enhancements (classic chess engines) |
| Huge branching factor, no reliable evaluation | MCTS (UCT) | Anytime, asymmetric growth, only needs a simulator |
| Learned policy and value available | MCTS with PUCT (AlphaZero style) | Network supplies priors and leaf values; search sharpens them |
| Chance nodes (dice, card draws) | Expectiminimax or MCTS | Average over outcomes at chance nodes |
| Imperfect information (poker) | Counterfactual regret minimization, information-set MCTS | Plain minimax assumes you see the full state |
This is the standard textbook tree. MAX moves at the root; each of three MIN nodes has three leaf children, searched left to right.
α = 3: MAX is guaranteed at least 3.α = 3. Its first leaf is 2, so C's value is at most 2. Since 2 ≤ α, MAX will never choose C, and leaves 4 and 6 are skipped.max(3, ≤2, 2) = 3, identical to full minimax, after examining 7 of 9 leaves.The savings compound with depth. With good ordering, alpha-beta examines on the order of bd/2 nodes instead of bd (Knuth and Moore, 1975), which is why engines spend so much effort on move ordering: captures and the previous iteration's best move first, then killer and history moves.
Below the search horizon, an evaluation function stands in for the true game value. It must be fast (it runs at every leaf) and must rank positions in the same order as their real outcomes.
Evaluations should only be applied to quiet positions; that is the job of quiescence search, which keeps extending capture sequences until the position settles. A strong static evaluation called in the middle of an exchange is still wrong.
d from known positions) catch move-generator bugs; comparing alpha-beta with plain minimax on random small trees catches pruning bugs.