---
title: Adversarial Search and Games
module: Search
moduleNumber: 2
lessonNumber: 7
order: 207
summary: >
  When another agent plans against you, search becomes a game. We formalize
  two-player, zero-sum, perfect-information games as search problems, define the
  minimax value that optimal play backs up through the game tree, and give the
  MINIMAX algorithm that computes it. Alpha–beta pruning then cuts the cost of
  that search roughly in half in the exponent without changing the answer, and a
  heuristic evaluation function plus a cutoff test turns the exact algorithm into
  a real-time player that copes with the horizon effect.
topics: [Search]
sources:
  - book: AIMA
    ref: "Ch. 5 — Adversarial Search; §5.1 Games; §5.2 Optimal Decisions in Games"
  - book: AIMA
    ref: "§5.3 Alpha–Beta Pruning; §5.4 Imperfect Real-Time Decisions"
---

The [search](/artificial-intelligence/search/uninformed-search) problems of the
last lessons had one agent moving through a passive world: the map does not
rearrange itself to keep you from Bucharest. A **game** breaks that assumption. A
second agent takes turns with you, sees the same board, and chooses its moves to
make yours turn out badly. Its goals are in direct conflict with yours, and that
conflict is what makes the setting **adversarial**. Planning ahead now requires
anticipating an opponent who is also planning ahead.[^aima-games]

This lesson treats the cleanest version of that problem: **deterministic,
turn-taking, two-player, zero-sum games of perfect information** — chess,
checkers, Go, tic-tac-toe. Both players see the whole board (perfect
information), no dice intervene (deterministic), and one player's gain is exactly
the other's loss (zero-sum). We call the two players **MAX** and **MIN**: MAX
moves first and wants to maximize a final numeric outcome, MIN wants to minimize
it. The messier cases — dice, hidden cards, fog of war — are the subject
of the companion lesson,
[Games of Chance and Imperfect Information](/artificial-intelligence/search/games-of-chance-and-imperfect-information).

## A game as a search problem

A game is a search problem with a few extra pieces. The state space and the
transition model carry over unchanged from ordinary search; what is new is that
two players alternate control, and terminal states carry a numeric payoff rather
than a plain goal flag.[^aima-defn]

| Component | Meaning |
| --- | --- |
| $S_0$ | the **initial state**: the board as it is set up at the start |
| $\text{Player}(s)$ | which player has the move in state $s$ |
| $\text{Actions}(s)$ | the set of legal moves in $s$ |
| $\text{Result}(s, a)$ | the **transition model**: the state reached by taking move $a$ in $s$ |
| $\text{Terminal-Test}(s)$ | true when the game is over ($s$ is a **terminal state**) |
| $\text{Utility}(s, p)$ | the **utility function**: the final numeric payoff to player $p$ in terminal state $s$ |

The utility function is the whole point of contact between the game's rules and
the search. In chess the outcome is a win, loss, or draw, worth $+1$, $0$, or
$\tfrac{1}{2}$; backgammon payoffs range from $0$ to $+192$. A game is
**zero-sum** when the total payoff to all players is the same constant for every
terminal state — chess is zero-sum because every game pays out $0 + 1$, $1 + 0$,
or $\tfrac{1}{2} + \tfrac{1}{2}$. ("Constant-sum" would be the more honest name,
but zero-sum is traditional.) In a two-player zero-sum game one number suffices:
MAX's utility, with MIN's being its negation, so a single value $U$ at each
terminal state describes the outcome for both.

$S_0$, $\text{Actions}$, and $\text{Result}$ together define the **game tree**: a
tree whose nodes are game states and whose edges are moves, with the two players'
moves alternating level by level.

$$
% caption: Part of the game tree for tic-tac-toe. From the initial empty board,
% MAX (X) has nine moves; play alternates between MAX and MIN (O) until a terminal
% state, whose utility (here $-1$, $0$, $+1$) is read from MAX's point of view.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  lvl/.style={anchor=east, font=\footnotesize, text=black},
  nd/.style={draw, minimum size=5mm, inner sep=0pt, fill=black!3}]
  \definecolor{acc}{HTML}{2348F2}
  % level labels
  \node[lvl] at (-5.4,3.0)  {MAX (X)};
  \node[lvl] at (-5.4,1.5)  {MIN (O)};
  \node[lvl] at (-5.4,0.0)  {MAX (X)};
  \node[lvl] at (-5.4,-2.0) {TERMINAL};
  % root
  \node[nd] (r) at (0,3.0) {};
  % MIN level
  \node[nd] (m1) at (-3.6,1.5) {};
  \node[nd] (m2) at (-1.2,1.5) {};
  \node[nd] (m3) at (1.2,1.5)  {};
  \node[nd] (m4) at (3.6,1.5)  {};
  \node[font=\small] at (4.9,1.5) {...};
  \draw[black] (r) -- (m1); \draw[black] (r) -- (m2);
  \draw[black] (r) -- (m3); \draw[black] (r) -- (m4);
  % MAX level under m2
  \node[nd] (a1) at (-2.1,0.0) {};
  \node[nd] (a2) at (-0.3,0.0) {};
  \node[font=\small] at (0.9,0.0) {...};
  \draw[black] (m2) -- (a1); \draw[black] (m2) -- (a2);
  % terminal leaves
  \node[nd] (t1) at (-2.7,-2.0) {};
  \node[nd] (t2) at (-1.5,-2.0) {};
  \node[nd] (t3) at (-0.3,-2.0) {};
  \draw[black] (a1) -- (t1); \draw[black] (a1) -- (t2); \draw[black] (a2) -- (t3);
  \node[anchor=north, text=acc] at (-2.7,-2.35) {-1};
  \node[anchor=north, text=acc] at (-1.5,-2.35) {0};
  \node[anchor=north, text=acc] at (-0.3,-2.35) {+1};
\end{tikzpicture}
$$

For tic-tac-toe the tree has fewer than $9! = 362{,}880$ terminal nodes, small
enough to draw. Chess has over $10^{40}$ nodes — a construct we can reason about
but never build. Either way, it is MAX's job to search enough of the tree to
decide what to do; the part actually examined is a **search tree** superimposed on
the full game tree.

## Optimal decisions: the minimax value

In an ordinary search problem the solution is a sequence of actions to a goal. In
a game MIN gets a say between every pair of MAX's moves, so MAX cannot commit to a
fixed sequence. MAX needs a **strategy**: a move for the initial state, then a
move for each state that could result from every MIN reply, and so on down. The
strategy that is optimal against an opponent who also plays optimally is captured
by a single quantity per node, the **minimax value**.

> **Definition (Minimax value).** The minimax value of a node $n$, written
> $\textsc{Minimax}(n)$, is the utility (to MAX) of the terminal state reached
> from $n$ when **both players play optimally** from there to the end of the game.
> A terminal node's minimax value is just its utility. MAX, having the move,
> picks the successor of maximum value; MIN picks the successor of minimum value.

Read the definition as a simple pessimistic rule: assume your opponent will always
make your best move as bad as possible, then pick the move that leaves you best off
under that assumption. Writing that as a recurrence, the minimax value is the
utility at a leaf, a max over successors at a MAX node, and a min over successors
at a MIN node:

$$
\textsc{Minimax}(s) =
\begin{cases}
\text{Utility}(s) & \text{if } \text{Terminal-Test}(s) \\[2pt]
\max_{a \in \text{Actions}(s)} \textsc{Minimax}(\text{Result}(s, a)) & \text{if } \text{Player}(s) = \text{MAX} \\[2pt]
\min_{a \in \text{Actions}(s)} \textsc{Minimax}(\text{Result}(s, a)) & \text{if } \text{Player}(s) = \text{MIN}.
\end{cases}
$$

The values are computed bottom-up: leaves get their utilities, and the min/max
choices are **backed up** the tree as the recursion unwinds. Consider a two-ply
tree — one move by MAX, one reply by MIN, so two half-moves, or two **plies**.
The three MIN nodes each take the minimum of their three leaves; the root MAX node
then takes the maximum of those three backed-up values.

$$
% caption: A two-ply game tree. Triangles pointing up are MAX nodes, down are MIN
% nodes. Each MIN node backs up the minimum of its leaves; the root backs up the
% maximum of the MIN values, giving minimax value $3$. MAX's optimal move is the
% left branch $a_1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  leaf/.style={anchor=north, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % root (MAX)
  \coordinate (root) at (0,3.4);
  \fill[black] (root) ++(-0.28,-0.42) -- ++(0.56,0) -- ++(-0.28,0.42) -- cycle;
  \draw[black] (root) ++(-0.28,-0.42) -- ++(0.56,0) -- ++(-0.28,0.42) -- cycle;
  \node[anchor=south, text=acc] at (0,3.5) {3};
  \node[anchor=east, text=black] at (-4.4,3.2) {MAX};
  % MIN nodes
  \foreach \i/\x/\v in {1/-3.2/3, 2/0/2, 3/3.2/2} {
    \coordinate (b\i) at (\x,1.6);
    \fill[black] (b\i) ++(-0.28,0.42) -- ++(0.56,0) -- ++(-0.28,-0.42) -- cycle;
    \draw[black] (b\i) ++(-0.28,0.42) -- ++(0.56,0) -- ++(-0.28,-0.42) -- cycle;
    \node[anchor=east, text=acc] at (\x-0.34,1.72) {\v};
  }
  \node[anchor=east, text=black] at (-4.4,1.5) {MIN};
  % edges root->MIN (highlight winning a1)
  \draw[acc, very thick] (root) -- (b1) node[midway, above left=-1pt, text=acc] {a1};
  \draw[black] (root) -- (b2) node[midway, right, text=black] {a2};
  \draw[black] (root) -- (b3) node[midway, above right=-1pt, text=black] {a3};
  % leaves
  \foreach \i/\bx in {1/-3.2, 2/0, 3/3.2} {
    \foreach \j/\dx in {1/-0.9, 2/0, 3/0.9} {
      \coordinate (l\i\j) at (\bx+\dx,-0.1);
      \draw[black] (b\i) -- (l\i\j);
    }
  }
  \node[leaf] at (-4.1,-0.1) {3};  \node[leaf] at (-3.2,-0.1) {12}; \node[leaf] at (-2.3,-0.1) {8};
  \node[leaf] at (-0.9,-0.1) {2};  \node[leaf] at (0,-0.1) {4};     \node[leaf] at (0.9,-0.1) {6};
  \node[leaf] at (2.3,-0.1) {14};  \node[leaf] at (3.2,-0.1) {5};   \node[leaf] at (4.1,-0.1) {2};
\end{tikzpicture}
$$

The first MIN node backs up $\min(3, 12, 8) = 3$; the other two back up $2$ and
$2$; the root backs up $\max(3, 2, 2) = 3$. The **minimax decision** at the root
is the move $a_1$ that achieves this value — the move to the highest-valued
successor. Because MAX assumes MIN plays optimally, this choice maximizes the
_worst case_. If MIN ever plays worse than optimally, MAX only does better; a
different strategy might exploit a specific weak opponent, but never at less risk
against a strong one.

### The minimax algorithm

The recurrence turns directly into a recursive, depth-first procedure. MAX-VALUE
and MIN-VALUE call each other, walking all the way down to the leaves and backing
values up; the top-level MINIMAX-DECISION returns the action whose successor has
the best backed-up value.

```algorithm
caption: $\textsc{Minimax-Decision}(state)$ — the optimal move for MAX by full game-tree search
function $\textsc{Minimax-Decision}(state)$ returns an action
  return the action $a \in \text{Actions}(state)$ maximizing $\textsc{Min-Value}(\text{Result}(state, a))$
function $\textsc{Max-Value}(state)$ returns a utility value
  if $\textsc{Terminal-Test}(state)$ then return $\text{Utility}(state)$
  $v \gets -\infty$
  for each $a$ in $\text{Actions}(state)$ do
    $v \gets \max(v,\ \textsc{Min-Value}(\text{Result}(state, a)))$
  return $v$
function $\textsc{Min-Value}(state)$ returns a utility value
  if $\textsc{Terminal-Test}(state)$ then return $\text{Utility}(state)$
  $v \gets +\infty$
  for each $a$ in $\text{Actions}(state)$ do
    $v \gets \min(v,\ \textsc{Max-Value}(\text{Result}(state, a)))$
  return $v$
```

Minimax performs a complete depth-first exploration of the game tree. If the tree
has maximum depth $m$ and there are $b$ legal moves at each point, the time cost is
$O(b^m)$ and the space cost is $O(bm)$ (generating all actions at once) or $O(m)$
(one at a time). For real games $O(b^m)$ is hopeless — chess has $b \approx 35$
and $m \approx 100$ — but this algorithm is the mathematical foundation on which
every practical game player is built. The rest of the lesson is a sequence of ways
to compute the same decision, or a good approximation of it, without paying the
full $b^m$.

## Alpha–beta pruning

The problem with minimax is the exponent, and we cannot remove it — but we can
roughly halve it. Once a refutation to a move is found, there is no need to know
_how_ bad the move is, only that it is worse than something already available;
the minimax value of the root can often be determined **without examining every
leaf**. **Alpha–beta pruning** exploits this: run the same depth-first minimax
search, but stop exploring a branch the moment it is clear that branch cannot
affect the final decision. Applied to minimax it returns exactly the same move; it
skips work that provably does not matter.[^aima-ab]

Return to the two-ply tree. Suppose the search has finished the first MIN node,
learning its value is $3$, so the root is worth _at least_ $3$. Now it begins the
second MIN node and finds its first leaf is $2$. That MIN node takes a minimum, so
its value is _at most_ $2$ — already below the $3$ MAX can guarantee elsewhere.
MAX would never choose this branch, so its remaining leaves are irrelevant and can
be **pruned**, unexamined. Writing the root's value as a formula makes the
independence explicit: with the two unexamined leaves of the second node called
$x$ and $y$,

$$
\begin{aligned}
\textsc{Minimax}(\text{root}) &= \max\big(\min(3, 12, 8),\ \min(2, x, y),\ \min(14, 5, 2)\big) \\
&= \max\big(3,\ \min(2, x, y),\ 2\big) \\
&= \max(3,\ z,\ 2), \qquad z = \min(2, x, y) \le 2 \\
&= 3.
\end{aligned}
$$

The value of the root, and therefore MAX's decision, is _independent_ of $x$ and
$y$. Whatever they are, $z \le 2 < 3$, so that middle branch loses. Those leaves
never needed to be looked at.

$$
% caption: Alpha–beta on the two-ply tree of the previous figure. The dashed
% edges and shaded leaves are pruned: once the middle MIN node's first leaf is $2$
% (at most $2$) and MAX can already guarantee $3$ on the left, the rest of that
% node is never examined.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  leaf/.style={anchor=north, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % root (MAX)
  \coordinate (root) at (0,3.4);
  \fill[black] (root) ++(-0.28,-0.42) -- ++(0.56,0) -- ++(-0.28,0.42) -- cycle;
  \draw[black] (root) ++(-0.28,-0.42) -- ++(0.56,0) -- ++(-0.28,0.42) -- cycle;
  \node[anchor=south, text=acc] at (0,3.5) {3};
  \node[anchor=east, text=black] at (-4.4,3.2) {MAX};
  % MIN nodes
  \foreach \i/\x/\v in {1/-3.2/3, 2/0/{$\le 2$}, 3/3.2/2} {
    \coordinate (b\i) at (\x,1.6);
    \fill[black] (b\i) ++(-0.28,0.42) -- ++(0.56,0) -- ++(-0.28,-0.42) -- cycle;
    \draw[black] (b\i) ++(-0.28,0.42) -- ++(0.56,0) -- ++(-0.28,-0.42) -- cycle;
    \node[anchor=east, text=acc] at (\x-0.34,1.72) {\v};
  }
  \node[anchor=east, text=black] at (-4.4,1.5) {MIN};
  \draw[acc, very thick] (root) -- (b1);
  \draw[black] (root) -- (b2);
  \draw[black] (root) -- (b3);
  % leaves node 1 (all examined)
  \foreach \dx in {-0.9,0,0.9} { \coordinate (p) at (-3.2+\dx,-0.1); \draw[black] (b1) -- (p); }
  \node[leaf] at (-4.1,-0.1) {3};  \node[leaf] at (-3.2,-0.1) {12}; \node[leaf] at (-2.3,-0.1) {8};
  % leaves node 2: first examined (2), other two pruned (dashed, shaded)
  \draw[black] (b2) -- (-0.9,-0.1);
  \draw[red, dashed] (b2) -- (0,-0.1);
  \draw[red, dashed] (b2) -- (0.9,-0.1);
  \node[leaf] at (-0.9,-0.1) {2};
  \node[leaf, text=black] at (0,-0.1) {x}; \node[leaf, text=black] at (0.9,-0.1) {y};
  \node[text=red, anchor=north, font=\scriptsize] at (0.45,-0.55) {pruned};
  % leaves node 3 (examined)
  \foreach \dx in {-0.9,0,0.9} { \coordinate (p) at (3.2+\dx,-0.1); \draw[black] (b3) -- (p); }
  \node[leaf] at (2.3,-0.1) {14};  \node[leaf] at (3.2,-0.1) {5};   \node[leaf] at (4.1,-0.1) {2};
\end{tikzpicture}
$$

The general principle names two bounds carried down each path of the search:

> **Definition (Alpha and beta).** $\alpha$ is the value of the best (highest)
> choice found so far along the path for MAX — a lower bound on what MAX can
> achieve. $\beta$ is the value of the best (lowest) choice found so far for MIN —
> an upper bound on what MIN will allow. As the search descends it tightens
> $\alpha$ and $\beta$; whenever a node's value falls outside the current
> $(\alpha, \beta)$ window, the rest of that node's children are pruned, because a
> better choice already exists higher up the path.

Concretely: at a MAX node, if the running value $v$ ever reaches $\beta$ or above,
MIN (higher up) would never let the game come here, so we stop and return $v$
(a **beta cutoff**). Symmetrically, at a MIN node, if $v$ drops to $\alpha$ or
below, MAX would never come here, so we return $v$ (an **alpha cutoff**). The
algorithm is minimax with exactly those two extra tests plus the bookkeeping to
pass $\alpha$ and $\beta$ down.

```algorithm
caption: $\textsc{Alpha-Beta-Search}(state)$ — minimax value with pruning; returns MAX's optimal move
function $\textsc{Alpha-Beta-Search}(state)$ returns an action
  $v \gets \textsc{Max-Value}(state, -\infty, +\infty)$
  return the action in $\text{Actions}(state)$ with value $v$
function $\textsc{Max-Value}(state, \alpha, \beta)$ returns a utility value
  if $\textsc{Terminal-Test}(state)$ then return $\text{Utility}(state)$
  $v \gets -\infty$
  for each $a$ in $\text{Actions}(state)$ do
    $v \gets \max(v,\ \textsc{Min-Value}(\text{Result}(state, a), \alpha, \beta))$
    if $v \ge \beta$ then return $v$ // beta cutoff: MIN avoids this node
    $\alpha \gets \max(\alpha, v)$
  return $v$
function $\textsc{Min-Value}(state, \alpha, \beta)$ returns a utility value
  if $\textsc{Terminal-Test}(state)$ then return $\text{Utility}(state)$
  $v \gets +\infty$
  for each $a$ in $\text{Actions}(state)$ do
    $v \gets \min(v,\ \textsc{Max-Value}(\text{Result}(state, a), \alpha, \beta))$
    if $v \le \alpha$ then return $v$ // alpha cutoff: MAX avoids this node
    $\beta \gets \min(\beta, v)$
  return $v$
```

Alpha–beta returns the identical value minimax would, so it is a pure efficiency
win: it prunes only branches that cannot change the answer. On any tree it visits
a subset of the nodes minimax would, and often it prunes entire subtrees rather
than a few leaves.

### Move ordering

How much alpha–beta saves depends entirely on the order in which moves are tried.
If MIN's best replies are examined first, cutoffs happen early and whole subtrees
vanish; if the worst are tried first, nothing prunes. In the tree above, the two
leaves under the middle node were pruned only because its low value $2$ appeared
before its higher siblings.

With **perfect ordering** — best moves always examined first — alpha–beta needs to
examine only $O(b^{m/2})$ nodes instead of $O(b^m)$. The effective branching
factor drops from $b$ to $\sqrt{b}$: for chess, from $35$ to about $6$. Put
differently, in the same amount of time alpha–beta searches roughly _twice as
deep_ as plain minimax. With random ordering the count is about $O(b^{3m/4})$ for
moderate $b$. Perfect ordering is of course unattainable (a function that always
knew the best move could just play the game), but cheap heuristics get close: try
captures first, then threats, then forward moves. Dynamic schemes go further —
**killer moves** reorder to try moves that caused cutoffs elsewhere, and a
**transposition table** hashes previously evaluated positions so that different
move orders leading to the same board are not re-searched.

| Move ordering | Nodes examined | Effective branching factor |
| --- | --- | --- |
| none (plain minimax) | $O(b^m)$ | $b$ |
| random | $O(b^{3m/4})$ | $b^{3/4}$ |
| perfect (best-first) | $O(b^{m/2})$ | $\sqrt{b}$ |

### A worked pruning trace

The two-ply picture shows _that_ pruning happens; a slightly larger tree shows how
the $(\alpha, \beta)$ window produces the cutoffs. Take a three-ply tree — MAX at the root,
MIN below, MAX below that, then leaves — with three children everywhere and the
twelve leaves, read left to right, equal to
$3, 12, 8,\; 2, 4, 6,\; 14, 5, 2,\; 11, 7, 9$ grouped into four MIN nodes. (Here
the bottom search level is a MAX level, so each of the four grand-nodes below the
root is a MIN node over three MAX leaves; we take the leaves directly to keep the
arithmetic short.) Walk the depth-first search carrying $(\alpha, \beta)$, opening
at $(-\infty, +\infty)$ at the root.

The **first MIN node** is explored with $(\alpha, \beta) = (-\infty, +\infty)$.
Its leaves $3, 12, 8$ give $v = 3$; no leaf ever drops to $\alpha = -\infty$, so
nothing prunes and it returns $3$. Back at the root, $\alpha \gets \max(-\infty, 3)
= 3$: MAX can already guarantee $3$.

The **second MIN node** inherits $(\alpha, \beta) = (3, +\infty)$. Its first leaf
is $2$, so $v = 2$. The MIN-node test $v \le \alpha$ fires — $2 \le 3$ — an **alpha
cutoff**: MAX would never enter this node, so its remaining leaves $4, 6$ are
pruned. It returns $2$; the root's $\alpha$ stays $3$.

The **third MIN node** inherits $(3, +\infty)$. Leaf $14$ gives $v = 14$; then
$\beta \gets \min(+\infty, 14) = 14$, leaf $5$ gives $v = 5$, $\beta \gets 5$, leaf
$2$ gives $v = 2$. No cutoff ($v$ never fell to $\alpha = 3$ _before_ the last
leaf; the check $2 \le 3$ would fire on the very last child, saving nothing), so it
returns $2$. The root's $\alpha$ stays $3$.

The **fourth MIN node** inherits $(3, +\infty)$. Leaf $11$ gives $v = 11$, $\beta
\gets 11$; leaf $7$ gives $v = 7 > 3$, no cutoff, $\beta \gets 7$; leaf $9$ leaves
$v = 7$. It returns $7$. Root: $\alpha \gets \max(3, 7) = 7$. The root value is
$\max(3, 2, 2, 7) = 7$, and MAX plays toward the fourth node.

Of twelve leaves, two were pruned — the $4$ and $6$ under the second node — because
that node's opening leaf $2$ already fell at or below the guarantee of $3$. Order
matters exactly here: had the second node's leaves arrived as $6, 4, 2$, the value
$2$ would surface only on the third leaf and nothing would prune. The trace also
shows the asymmetry of the bounds. $\alpha$ tightened only at the root (a MAX
node); $\beta$ tightened only inside each MIN node and reset to $+\infty$ on entry,
because the root imposes no upper bound on a first-level MIN node.

$$
% caption: A three-ply alpha-beta trace over twelve leaves. The four MIN nodes back
% up $3, 2, 2, 7$; the root MAX value is $7$. The inherited window at each MIN node
% is shown above it as $\alpha, \beta$. Under the second MIN node the leaves $4$ and $6$ (shaded,
% dashed) are cut by an alpha cutoff, because its first leaf $2$ is at or below the
% $\alpha = 3$ MAX has already secured.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  leaf/.style={anchor=north, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % root (MAX)
  \coordinate (root) at (0,3.6);
  \fill[black] (root) ++(-0.26,-0.4) -- ++(0.52,0) -- ++(-0.26,0.4) -- cycle;
  \draw[black] (root) ++(-0.26,-0.4) -- ++(0.52,0) -- ++(-0.26,0.4) -- cycle;
  \node[anchor=south, text=acc] at (0,3.7) {7};
  \node[anchor=east, text=black] at (-5.6,3.4) {MAX};
  % MIN nodes
  \foreach \i/\x/\v/\win in {1/-4.2/3/{a=-inf b=+inf}, 2/-1.4/2/{a=3 b=+inf}, 3/1.4/2/{a=3 b=+inf}, 4/4.2/7/{a=3 b=+inf}} {
    \coordinate (b\i) at (\x,1.8);
    \fill[black] (b\i) ++(-0.26,0.4) -- ++(0.52,0) -- ++(-0.26,-0.4) -- cycle;
    \draw[black] (b\i) ++(-0.26,0.4) -- ++(0.52,0) -- ++(-0.26,-0.4) -- cycle;
    \node[anchor=south, text=acc, font=\scriptsize] at (\x,1.95) {\v};
    \node[anchor=south, text=black, font=\scriptsize] at (\x,2.28) {\win};
  }
  \node[anchor=east, text=black] at (-5.6,1.8) {MIN};
  \draw[black] (root) -- (b1);
  \draw[black] (root) -- (b2);
  \draw[black] (root) -- (b3);
  \draw[acc, very thick] (root) -- (b4);
  % leaves under each node
  \foreach \i/\bx in {1/-4.2, 3/1.4, 4/4.2} {
    \foreach \dx in {-0.75,0,0.75} { \draw[black] (b\i) -- (\bx+\dx,0.0); }
  }
  % node 2: first leaf examined, other two pruned
  \draw[black] (b2) -- (-2.15,0.0);
  \draw[red, dashed] (b2) -- (-1.4,0.0);
  \draw[red, dashed] (b2) -- (-0.65,0.0);
  % leaf values
  \node[leaf] at (-4.95,0.0) {3};  \node[leaf] at (-4.2,0.0) {12}; \node[leaf] at (-3.45,0.0) {8};
  \node[leaf] at (-2.15,0.0) {2};
  \node[leaf, text=black] at (-1.4,0.0) {4}; \node[leaf, text=black] at (-0.65,0.0) {6};
  \node[leaf] at (0.65,0.0) {14}; \node[leaf] at (1.4,0.0) {5};  \node[leaf] at (2.15,0.0) {2};
  \node[leaf] at (3.45,0.0) {11}; \node[leaf] at (4.2,0.0) {7};  \node[leaf] at (4.95,0.0) {9};
  \node[text=red, anchor=north, font=\scriptsize] at (-1.0,-0.5) {pruned};
\end{tikzpicture}
$$

## Imperfect real-time decisions

Alpha–beta prunes a great deal, but it still searches all the way to terminal
states for at least part of the tree, and for chess that depth is unreachable in
the minutes a move is allowed. Claude Shannon's 1950 proposal was to **cut off**
the search early and apply a heuristic **evaluation function** to nonterminal
positions, treating them as if they were terminal. Two substitutions turn minimax
into a real-time player: replace $\text{Utility}$ with an estimate
$\textsc{Eval}(s)$, and replace $\text{Terminal-Test}$ with a **cutoff test**
$\textsc{Cutoff-Test}(s, d)$ that stops at some depth $d$.[^aima-eval]

$$
\text{H-}\textsc{Minimax}(s, d) =
\begin{cases}
\textsc{Eval}(s) & \text{if } \textsc{Cutoff-Test}(s, d) \\[2pt]
\max_{a} \text{H-}\textsc{Minimax}(\text{Result}(s, a), d{+}1) & \text{if } \text{Player}(s) = \text{MAX} \\[2pt]
\min_{a} \text{H-}\textsc{Minimax}(\text{Result}(s, a), d{+}1) & \text{if } \text{Player}(s) = \text{MIN}.
\end{cases}
$$

In practice the cutoff test is a fixed depth limit combined with **iterative
deepening**: search to depth $1$, then $2$, then $3$, returning the best move from
the deepest search that finished before time ran out. Iterative deepening also
supplies the move ordering that makes alpha–beta efficient, since each pass seeds
the next.

### Evaluation functions

An evaluation function returns an _estimate_ of the expected utility from a
position, exactly as the heuristics of
[informed search](/artificial-intelligence/search/informed-search) estimated
distance to a goal. A good one must (1) order terminal states the same way the
true utility does — wins above draws above losses — (2) compute quickly, and (3)
correlate strongly with the real chance of winning at nonterminal states.

Most evaluation functions are a **weighted linear function** of features $f_i$ of
the position, each weighted by $w_i$:

$$
\textsc{Eval}(s) = w_1 f_1(s) + w_2 f_2(s) + \cdots + w_n f_n(s) = \sum_{i=1}^{n} w_i f_i(s).
$$

For chess the features are things like material — pawn $= 1$, knight or bishop
$= 3$, rook $= 5$, queen $= 9$ — plus pawn structure and king safety. Summing
feature contributions assumes each feature is _independent_ of the others, which
is false (a bishop is worth more in an open endgame), so strong programs use
**nonlinear** combinations. The weights need not come from a human: they can be
learned from data by the machine-learning techniques of a later module, and
learning applied to chess confirms that a bishop is indeed worth about three
pawns.

$$
% caption: A weighted-linear evaluation function maps board features (material,
% mobility, king safety) to a single scalar estimate of MAX's utility, which the
% cutoff search backs up in place of a true terminal value.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  fbox/.style={draw, minimum width=30mm, minimum height=8mm, align=left, font=\scriptsize},
  outbox/.style={draw, thick, minimum width=22mm, minimum height=12mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[fbox] (f1) at (0,1.6)  {material (f1): +2};
  \node[fbox] (f2) at (0,0.6)  {mobility (f2): +5};
  \node[fbox] (f3) at (0,-0.4) {king safety (f3): -1};
  \node[outbox, draw=acc, text=acc] (ev) at (5.6,0.6) {Eval(s)\\= 0.76};
  \draw[->, acc, thick] (f1.east) -- (ev.west) node[midway, above, font=\scriptsize, text=black] {w1};
  \draw[->, acc, thick] (f2.east) -- (ev.west);
  \draw[->, acc, thick] (f3.east) -- (ev.west) node[midway, below, font=\scriptsize, text=black] {w3};
  \node[font=\scriptsize, text=black, anchor=north] at (2.8,-1.4) {weighted sum of features};
\end{tikzpicture}
$$

### The horizon effect

Cutting off search introduces its own error. A crude material-only evaluation may
misjudge a position because the decisive event lies just beyond the depth limit —
the classic case being a piece about to be captured on the very next ply. The fix
for wild swings is to keep searching **non-quiescent** positions (those with a
favorable capture pending) a little deeper until they settle down, a technique
called **quiescence search**.

Harder to remove is the **horizon effect**. It arises when the opponent is about
to inflict serious, unavoidable damage, and the searching player finds a sequence
of pointless delaying moves that pushes that damage past the depth limit — over
the search's horizon. The program sacrifices material to postpone a loss it cannot
prevent, sees only that the loss has vanished from view, and rates the sacrifices
as good moves when they merely made things worse.

$$
% caption: The horizon effect. The losing player interposes forcing checks that
% each push the inevitable capture one ply deeper; at the depth limit the loss has
% dropped past the horizon (dashed line) and the wasteful delaying moves look good.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  nd/.style={circle, draw, minimum size=4mm, inner sep=0pt, fill=black!5}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[nd] (n0) at (0,0)   {};
  \node[nd] (n1) at (1.5,0) {};
  \node[nd] (n2) at (3.0,0) {};
  \node[nd] (n3) at (4.5,0) {};
  \draw[->, black] (n0) -- (n1) node[midway, above, font=\scriptsize] {check};
  \draw[->, black] (n1) -- (n2) node[midway, above, font=\scriptsize] {check};
  \draw[->, black] (n2) -- (n3) node[midway, above, font=\scriptsize] {check};
  \node[anchor=north, font=\scriptsize, text=black] at (0,-0.35)   {delay};
  \node[anchor=north, font=\scriptsize, text=black] at (1.5,-0.35) {delay};
  \node[anchor=north, font=\scriptsize, text=black] at (3.0,-0.35) {delay};
  % horizon line
  \draw[red, dashed, thick] (5.2,-1.1) -- (5.2,1.1);
  \node[text=red, anchor=south, font=\scriptsize] at (5.2,1.1) {horizon (depth limit)};
  % the loss beyond
  \node[nd, draw=red] (loss) at (6.4,0) {};
  \draw[->, red] (n3) -- (loss);
  \node[text=red, anchor=west, font=\scriptsize] at (6.6,0) {piece lost};
\end{tikzpicture}
$$

A **singular extension** mitigates it: a move that is clearly better than all
alternatives is remembered and allowed to extend the search past the normal limit,
deepening only the few lines where it matters. **Forward pruning** goes the other
way, cutting some moves immediately (as **beam search** keeps only the $n$
best-looking moves) — faster but dangerous, since the true best move might be among
those discarded.

Everything so far assumes a deterministic game of perfect information: no dice, and
both players see the whole board. Loosen either assumption — add a random roll, or
hide part of the state — and the minimax value has to be replaced by an
_expectation_, and the search by something that reasons about what the agent
_cannot_ see. This continues in
[Games of Chance and Imperfect Information](/artificial-intelligence/search/games-of-chance-and-imperfect-information),
which develops expectiminimax for stochastic games, belief-state reasoning for
partially observable ones, and the line from Deep Blue's alpha–beta to AlphaGo's
learned evaluation and Monte Carlo tree search.

[^aima-games]: **AIMA**, Ch. 5 — Adversarial Search; §5.1 Games: competitive multiagent environments where agents' goals conflict, giving rise to adversarial search, and the standard restriction to deterministic, turn-taking, two-player, zero-sum games of perfect information.
[^aima-defn]: **AIMA**, §5.1 — a game defined as a search problem with the elements $S_0$, $\text{Player}$, $\text{Actions}$, $\text{Result}$, $\text{Terminal-Test}$, and $\text{Utility}$; the game tree spanned by the initial state, actions, and result; and the zero-sum condition on payoffs.
[^aima-ab]: **AIMA**, §5.3 — Alpha–Beta Pruning: computing the minimax decision without examining every node, the $\alpha$/$\beta$ bounds as the best-so-far values along a path for MAX and MIN, and the $O(b^{m/2})$ best-case node count with perfect move ordering.
[^aima-eval]: **AIMA**, §5.4 — Imperfect Real-Time Decisions: Shannon's cutoff test and heuristic evaluation function, H-MINIMAX, the weighted-linear evaluation function, quiescence search, the horizon effect, and singular extensions.