---
title: Games of Chance and Imperfect Information
module: Search
moduleNumber: 2
lessonNumber: 8
order: 208
summary: >
  Minimax and alpha–beta assume a deterministic game both players can see in full.
  Drop either assumption and search must change. This lesson adds chance nodes and
  the expectiminimax value for games with dice, then belief-state reasoning for
  partially observable games — Kriegspiel and card games — where averaging over
  clairvoyance both helps and misleads. It closes with the line from Deep Blue's
  alpha–beta to AlphaGo's learned evaluation and Monte Carlo tree search, and the
  provable-pruning and self-play research around each end of that story.
topics: [Search]
sources:
  - book: AIMA
    ref: "Ch. 5 — Adversarial Search; §5.5 Stochastic Games; §5.6 Partially Observable Games"
  - book: AIMA
    ref: "§5.7 State-of-the-Art Game Programs"
---

The companion lesson,
[Adversarial Search and Games](/artificial-intelligence/search/adversarial-search),
built the theory of games that are **deterministic** and of **perfect
information**: the minimax value, the MINIMAX algorithm, alpha–beta pruning, and a
heuristic evaluation function with a cutoff test for real-time play. Two
assumptions held throughout — no chance intervened, and both players saw
the whole board. This lesson drops each in turn. First a random roll forces the
minimax value to become an _expectation_; then hidden information forces the search
to reason over the _sets of states_ the agent cannot distinguish. It closes with
the state of the art, where scaled-up alpha–beta beat humans at chess and a
different idea — learned evaluation plus Monte Carlo sampling — beat them at Go.

## Stochastic games: expectiminimax

Backgammon and other games with **dice** add a random element between the players'
choices. The player about to move knows their own legal moves but not the
opponent's, because those depend on a future roll. The game tree therefore needs a
third kind of node — a **chance node** — between MAX and MIN, one branch per
possible roll, each labeled with the roll's probability. With two dice there are
$36$ equally likely outcomes but only $21$ distinct rolls: a double like $1$–$1$
has probability $\tfrac{1}{36}$, and each of the other $15$ distinct rolls
(such as $6$–$5$, which equals $5$–$6$) has probability $\tfrac{1}{18}$.

Positions no longer have a definite minimax value, only an **expected value**
averaged over the chance outcomes — a position's value is defined only on average,
over all the ways the dice could fall. This generalizes the minimax value to the
**expectiminimax value**: MAX and MIN nodes work as before, and a chance node
takes the probability-weighted average of its children.

$$
% caption: A game tree with chance nodes (circles) for a dice game. MAX and MIN
% nodes back up max and min as before; each chance node backs up the expected
% value, the sum of its children weighted by the roll probabilities $P(r)$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  chance/.style={circle, draw, minimum size=6mm, inner sep=0pt, fill=black!5},
  lvl/.style={anchor=east, font=\footnotesize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  % MAX root
  \coordinate (root) at (0,3.2);
  \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[lvl] at (-3.7,3.1) {MAX};
  % chance nodes
  \node[chance] (c1) at (-2.2,1.6) {};
  \node[chance] (c2) at (2.2,1.6)  {};
  \node[lvl] at (-3.7,1.6) {CHANCE};
  \draw[black] (root) -- (c1) node[midway, above left=-2pt, text=black] {a1};
  \draw[black] (root) -- (c2) node[midway, above right=-2pt, text=black] {a2};
  % MIN nodes under c1
  \foreach \i/\x/\v in {1/-3.1/2, 2/-1.3/3} {
    \coordinate (m\i) at (\x,0.0);
    \fill[black] (m\i) ++(-0.24,0.36) -- ++(0.48,0) -- ++(-0.24,-0.36) -- cycle;
    \draw[black] (m\i) ++(-0.24,0.36) -- ++(0.48,0) -- ++(-0.24,-0.36) -- cycle;
    \node[anchor=north, text=acc, font=\scriptsize] at (\x,-0.44) {\v};
  }
  \foreach \i/\x/\v in {3/1.3/1, 4/3.1/4} {
    \coordinate (m\i) at (\x,0.0);
    \fill[black] (m\i) ++(-0.24,0.36) -- ++(0.48,0) -- ++(-0.24,-0.36) -- cycle;
    \draw[black] (m\i) ++(-0.24,0.36) -- ++(0.48,0) -- ++(-0.24,-0.36) -- cycle;
    \node[anchor=north, text=acc, font=\scriptsize] at (\x,-0.44) {\v};
  }
  \node[lvl] at (-3.7,0.0) {MIN};
  \draw[black] (c1) -- (m1) node[midway, left=1pt, font=\scriptsize, text=black] {.9};
  \draw[black] (c1) -- (m2) node[midway, right=1pt, font=\scriptsize, text=black] {.1};
  \draw[black] (c2) -- (m3) node[midway, left=1pt, font=\scriptsize, text=black] {.9};
  \draw[black] (c2) -- (m4) node[midway, right=1pt, font=\scriptsize, text=black] {.1};
  % chance node backed-up expected values
  \node[anchor=south, text=acc, font=\scriptsize] at (-2.2,1.95) {2.1};
  \node[anchor=south, text=acc, font=\scriptsize] at (2.2,1.95)  {1.3};
\end{tikzpicture}
$$

The recurrence adds one case for the chance player, summing over rolls $r$ with
probability $P(r)$:

$$
\textsc{Expectiminimax}(s) =
\begin{cases}
\text{Utility}(s) & \text{Terminal-Test}(s) \\[2pt]
\max_{a} \textsc{Expectiminimax}(\text{Result}(s, a)) & \text{Player}(s) = \text{MAX} \\[2pt]
\min_{a} \textsc{Expectiminimax}(\text{Result}(s, a)) & \text{Player}(s) = \text{MIN} \\[2pt]
\sum_{r} P(r)\, \textsc{Expectiminimax}(\text{Result}(s, r)) & \text{Player}(s) = \text{CHANCE}.
\end{cases}
$$

Run the numbers on the figure above. MAX has two moves. Move $a_1$ leads to a
chance node whose two outcomes have probabilities $0.9$ and $0.1$ and back-up
values $2$ and $3$ from the MIN nodes below, so its expected value is
$0.9 \times 2 + 0.1 \times 3 = 1.8 + 0.3 = 2.1$. Move $a_2$ leads to a chance node
with the same probabilities over values $1$ and $4$, giving
$0.9 \times 1 + 0.1 \times 4 = 0.9 + 0.4 = 1.3$. MAX takes the maximum of the two
chance values, $\max(2.1, 1.3) = 2.1$, and plays $a_1$. Now scale every leaf by an
order-preserving map that is _not_ linear — say raise each to the power of the
rank, sending $1, 2, 3, 4$ to $1, 4, 9, 16$. The first chance node becomes
$0.9 \times 4 + 0.1 \times 9 = 4.5$ and the second $0.9 \times 1 + 0.1 \times 16 =
2.5$: $a_1$ still wins here, but a differently shaped monotone map can reverse the
two averages even though it never reorders a single leaf. That is the concrete
sense in which an expectiminimax evaluation must be calibrated to probabilities,
not merely rank-correct — a caution that does not arise in deterministic minimax.

Chance nodes change the picture in two ways. First, cost: expectiminimax runs in
$O(b^m n^m)$ for $n$ distinct rolls, so even three plies is often all that is
tractable — in backgammon $n = 21$ and $b$ can reach the thousands on doubles.
Second, and more subtly, the evaluation function must now be a _positive linear
transformation_ of the probability of winning. With deterministic minimax any
order-preserving rescaling of leaf values leaves the best move unchanged, because
only comparisons matter. Under an expectation the actual magnitudes matter: stretch
one branch's values and the average shifts, so an order-preserving change of scale
can flip the chosen move. The evaluation must mean something, not merely rank
correctly. One robust workaround is Monte Carlo **rollout** — from a position, play
many random games to the end and average the outcomes, an idea that returns
below.

## Partially observable games

Chess is sometimes called war in miniature, but real war has a feature chess
lacks: **partial observability**. In the fog of war the location of enemy units is
unknown until direct contact reveals it, which is why armies use scouts and spies
to gather information and concealment and bluff to deny it. Games with hidden
information share these traits and are qualitatively unlike the perfect-information
games above, where both players see the whole board.[^aima-po] Two kinds of
hidden information arise: an opponent's _choices_ may be hidden (deterministic
partial observability), or information may be _dealt at random_ and kept private
(stochastic partial observability).

### Kriegspiel: belief states over positions

**Kriegspiel** is chess made partially observable. Each player sees a board
holding only their own pieces; a referee sees everything and makes public
announcements. On your turn you propose a move that would be legal if the board
held no enemy pieces; the referee says "illegal" (and you try again, learning
something) or accepts it and announces any capture, any check and its direction,
and checkmate or stalemate. All uncertainty comes from not knowing the opponent's
past choices — there is no dice, so this is _deterministic_ partial observability,
the same class as Battleship (hidden static positions) and Stratego (hidden piece
identities).

The tool for reasoning here is the **belief state**: the set of all board
positions consistent with the complete history of percepts so far. Initially
White's belief state is a single position, since Black has not moved. After White
moves and Black replies, White's belief state holds up to $20$ positions, one per
Black reply, because White cannot see which reply Black chose. Maintaining the
belief state across the game reprises the **state-estimation** update from
partially observable, nondeterministic search: treat the opponent as the source of
nondeterminism, so that the result of White's move is White's own (predictable)
effect composed with Black's unpredictable reply.

$$
% caption: A belief state in the KRK (king-and-rook versus king) Kriegspiel
% endgame, shown on a reduced board. White sees its own king (WK) and rook (WR)
% but not Black's king, which could be on any of three squares (marked bk?). A
% probing move that draws a referee announcement prunes the belief state toward a
% single position.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  sq/.style={draw, minimum size=8mm, inner sep=0pt},
  bk/.style={draw, minimum size=8mm, inner sep=0pt, fill=acc!14}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \c in {0,1,2,3} \foreach \r in {0,1,2,3}
    \node[sq] (s\c\r) at (\c*0.85, \r*0.85) {};
  % file/rank labels
  \foreach \c/\l in {0/a,1/b,2/c,3/d} \node[font=\scriptsize, anchor=north] at (\c*0.85,-0.5) {\l};
  \foreach \r/\l in {0/1,1/2,2/3,3/4} \node[font=\scriptsize, anchor=east] at (-0.5,\r*0.85) {\l};
  % white pieces
  \node at (s01) {WK};
  \node at (s21) {WR};
  % candidate black-king squares
  \node[bk] at (s03) {bk?};
  \node[bk] at (s13) {bk?};
  \node[bk] at (s33) {bk?};
  \node[acc, anchor=west, font=\scriptsize, align=left] at (3.9,2.55) {belief state:\\3 possible\\black-king\\positions};
\end{tikzpicture}
$$

Given a belief state, White may ask "can I force a win?" A **strategy** in a
partially observable game is no longer a move per opponent move; it is a move for
every **percept sequence** the referee might produce. A **guaranteed checkmate**
is a strategy that, for each percept sequence, delivers checkmate in _every_ board
state of the current belief state, whatever the opponent does. This definition
makes the opponent's own belief state irrelevant — the strategy must work even if
the opponent sees all the pieces — which simplifies the computation to an
**AND–OR search** over the belief-state space, exactly the machinery of
nondeterministic planning. The incremental belief-state version finds midgame
checkmates to depth $9$, past most human ability.

### Probabilistic and accidental checkmate

Partial observability introduces a concept impossible in a fully observable game:
the **probabilistic checkmate**, one guaranteed to work in every board state of
the belief state but only with probability approaching $1$ over the winning
player's own randomization. To find a lone black king with only the white king,
move the white king at random; it will eventually bump into the black king, since
Black cannot keep guessing the right evasion forever, and detection occurs with
probability $1$. The KBNK endgame (king, bishop, knight) is won this way — White
offers Black an infinite random sequence of choices, one of which Black gets
wrong. KBBK is won with probability $1 - \epsilon$: White must expose a bishop for
one move, and can shrink $\epsilon$ toward zero by choosing the risky moment
randomly deep in a long sequence, but never to zero.

More common than either is the **accidental checkmate** — a strategy that mates in
_some_ board states of the belief state but not others, which happens to succeed
because the opponent's pieces were in the right places. Most human checkmates in
Kriegspiel are of this kind, and their existence forces the question of how
_likely_ a given strategy is to win, which in turn asks how likely each board
state in the belief state is to be the true one.

Those probabilities cannot simply be uniform over the belief state. After Black's
first move, an optimal Black should have played a good move, so board states from
bad moves deserve low probability. But there is a subtler point: each player wants
not only to place pieces well but to _minimize the information_ its play leaks.
Any predictable "optimal" policy hands the opponent information, so optimal play in
a partially observable game demands a willingness to act **randomly** — the same
reason a hygiene inspector visits at random. The probabilities over board states
and the optimal randomized strategy are thus mutually defining, a circle that only
the game-theoretic notion of an **equilibrium** breaks; computing one is
prohibitively expensive, so practical Kriegspiel programs do bounded-depth
lookahead in their own belief-state space, with an evaluation function that rewards
a _smaller_ belief state.

### Card games: averaging over clairvoyance

Card games such as bridge, whist, hearts, and poker are _stochastic_ partial
observability: the hidden information — who holds which cards — is dealt at random
at the start. It is tempting to treat this like a dice game where all the dice were
rolled up front, and that intuition suggests an algorithm even though the analogy
is not quite right. Consider every possible deal $s$ of the hidden cards, solve
each as a fully observable game, and pick the move that scores best _averaged over
the deals_, weighting each by its probability $P(s)$:

$$
\arg\max_{a} \sum_{s} P(s)\, \textsc{Minimax}(\text{Result}(s, a)).
$$

The number of deals is usually enormous — in bridge each player sees $2$ of the $4$
hands, leaving $\binom{26}{13} \approx 10{,}400{,}600$ deals — so we sample: draw
$N$ random deals in proportion to $P(s)$ and average $\textsc{Minimax}$ over the
sample.

$$
% caption: Averaging over clairvoyance samples $N$ deals of the hidden cards,
% solves each deal as a fully observable game with minimax, and picks the action
% with the best average value. Each sampled deal fixes every hidden card, turning
% the game observable.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  dealbox/.style={draw, minimum width=17mm, minimum height=9mm, align=center, font=\scriptsize},
  actbox/.style={draw, minimum width=17mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[actbox, draw=acc, text=acc] (a) at (0,1.0) {choose\\action a};
  \node[dealbox] (d1) at (3.6,2.4) {deal s1\\solve: +4};
  \node[dealbox] (d2) at (3.6,1.0) {deal s2\\solve: -2};
  \node[dealbox] (d3) at (3.6,-0.4) {deal s3\\solve: +6};
  \node[actbox, draw=acc, text=acc] (avg) at (7.4,1.0) {average\\= 2.67};
  \draw[->, acc, thick] (a) -- (d1);
  \draw[->, acc, thick] (a) -- (d2);
  \draw[->, acc, thick] (a) -- (d3);
  \draw[->, thick] (d1) -- (avg);
  \draw[->, thick] (d2) -- (avg);
  \draw[->, thick] (d3) -- (avg);
  \node[font=\scriptsize, text=black, anchor=north] at (3.6,-1.1) {each deal solved as if fully observable};
\end{tikzpicture}
$$

The method works well for bridge, but it embodies a subtle error.
**Averaging over clairvoyance** assumes the game becomes observable to both players
_right after the first move_. It therefore never values actions that gather
information, never hides information from an opponent or shares it with a partner,
and never bluffs — because it presumes everyone already knows everything the deal
determined. The classic illustration: three days running, road A gives gold and
road B forks to a bigger heap on one branch and a fatal bus on the other. On days 1
and 2 you know which fork is safe and B is correct; on day 3 you do _not_ know which
fork is safe, yet averaging over clairvoyance still recommends B — because it
imagines that in each hidden world you would somehow know the fork. It ignores the
belief state the agent will actually be in after acting, so it accepts a coin
flip between the gold and the bus as if the outcome were certain.

$$
% caption: Averaging over clairvoyance fails on the road example. On day 3 the
% agent does not know which fork is safe, but averaging treats each hidden world as
% if it were known, so it never accounts for the belief state of total ignorance
% (one branch is certain death) it will actually face after choosing road B.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  nd/.style={draw, circle, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[nd] (start) at (0,0) {};
  \node[nd] (fork) at (2.4,0) {};
  \node[nd, draw=acc] (gA) at (2.4,-1.6) {};
  \node[nd, draw=acc] (gold) at (5.0,0.9) {};
  \node[nd, draw=red] (bus) at (5.0,-0.9) {};
  \draw[->, thick] (start) -- (fork) node[midway, above, font=\scriptsize] {road B};
  \draw[->, thick] (start) -- (gA) node[midway, left=1pt, font=\scriptsize] {road A};
  \draw[->, acc, thick] (fork) -- (gold);
  \draw[->, red, thick] (fork) -- (bus);
  \node[acc, anchor=west, font=\scriptsize] at (5.2,0.9) {bigger gold};
  \node[red, anchor=west, font=\scriptsize] at (5.2,-0.9) {hit by bus};
  \node[acc, anchor=east, font=\scriptsize] at (2.2,-1.6) {gold (safe)};
  \node[font=\scriptsize, text=black, anchor=north] at (3.9,-2.15) {which fork is which is unknown};
\end{tikzpicture}
$$

The right treatment solves the true partially observable problem, where actions can
deliberately gather or conceal information; that is the subject of
[decision networks and game theory](/artificial-intelligence/uncertainty/decision-networks-and-game-theory).
The reason Monte Carlo sampling works for bridge but not Kriegspiel is where the
uncertainty lives: in bridge most of it comes from the random deal, which sampling
handles well, whereas in Kriegspiel it comes from adversarial play, where the value
of information dominates and averaging over clairvoyance throws that value away.

## From Deep Blue to AlphaGo

Everything above is the standard combination: minimax, an evaluation function, and
alpha–beta with move ordering. Scaled up, it beat the best humans at chess. IBM's
**Deep Blue** defeated world champion Garry Kasparov in 1997 running alpha–beta on
a parallel machine with $480$ custom chess processors, searching up to $30$ billion
positions per move and reaching depth $14$ routinely — and, through singular
extensions, depth $40$ on forcing lines. Its evaluation function had over $8000$
features, backed by an opening book of about $4000$ positions and an endgame
database of all five-piece and many six-piece positions.[^aima-sota] Later programs
matched its strength on ordinary hardware, using pruning heuristics — the **null
move** (let the opponent move twice; if the position is still good, prune) and
**futility pruning** — to push the effective search depth still deeper.

**Go** broke this approach. On a $19 \times 19$ board the branching factor starts near
$361$, far too large for alpha–beta, and territory is so fluid that no simple
weighted-linear evaluation function works until the endgame. The response was a
different search entirely: **Monte Carlo tree search** (MCTS), which estimates a
move's value not by an evaluation function but by rollouts — playing many random
games out from a position and averaging the results — while using the UCT rule
(upper confidence bounds on trees) to steer the sampling toward promising moves.
Early programs like MoGo reached strong amateur play this way.

The line runs directly from there to **AlphaGo**, which reached and then surpassed
human champions by fusing the two ideas this pair of lessons has developed: MCTS for
the search, and a _learned_ evaluation (and move-ordering policy) in place of the
hand-built weighted-linear function — deep networks trained by reinforcement
learning to estimate the value of a position and to bias the rollouts. Alpha–beta
was the efficiency idea that made exact deep search possible in chess; learned
evaluation plus MCTS was the efficiency idea that made it possible in Go. We follow
that thread in the reinforcement-learning
[case studies](/reinforcement-learning/deep-rl/case-studies).

## Provable pruning and self-play

AIMA presents alpha–beta and AlphaGo; two lines of public work sharpen each end of
that story past the chapter.

**What alpha–beta's square root really means.** The $O(b^{m/2})$ figure is not a
loose bound — it is exactly optimal. Knuth and Moore's 1975 analysis (_Artificial
Intelligence_ 6(4)) recast alpha–beta as **negamax**, a single recursion in which
each node negates and swaps the incoming bounds so MAX and MIN code become one
routine, and proved that on a tree with perfectly ordered moves alpha–beta visits
$b^{\lceil m/2 \rceil} + b^{\lfloor m/2 \rfloor} - 1$ leaves, the minimum any
algorithm computing the exact minimax value must examine. No pruning scheme can do
asymptotically better while still returning the true value. Their paper also
introduced the analysis of _type-1, type-2, type-3_ nodes that underlies later
refinements. Two of those refinements narrow the window
deliberately. **Principal variation search** (also called NegaScout, Reinefeld
1983) searches the first move with the full $(\alpha, \beta)$ window and every
later move with a **null window** $(\alpha, \alpha+1)$ — a probe that only asks "is
this move better than the best so far?" and, being maximally narrow, prunes fast;
a move that beats the probe is re-searched with the full window. **MTD(f)** (Plaat
et al. 1996) drives the whole search with null-window probes and a running bound,
converging on the minimax value from a sequence of yes/no cutoff tests, and paired
with a transposition table it outran plain alpha–beta on the chess and checkers
programs of the day.

**Self-play removed the hand-built evaluation entirely.** AlphaGo (Silver et al.,
_Nature_ 529, 2016) still learned its value and policy networks partly from a
database of human expert games. Its successor **AlphaGo Zero** (Silver et al.,
_Nature_ 550, 2017) started from random weights and _no human data_: a single
network output both a move policy and a position value, MCTS used that network to
guide its rollouts, and the improved move distribution MCTS produced became the
training target for the network — a loop of search improving the network improving
the search, run purely on games the system played against itself. It surpassed the
earlier human-trained version. **AlphaZero** (Silver et al., _Science_ 362, 2018)
then showed the same algorithm, unchanged, learning chess, shogi, and Go from the
rules alone, reaching superhuman play in each — and it did so searching only about
$80{,}000$ positions per second in chess against Stockfish's $70$ million, meaning
a _learned_ evaluation guiding MCTS beat a hand-tuned alpha–beta engine searching
three orders of magnitude more nodes. **MuZero** (Schrittwieser et al., _Nature_
588, 2020) closed the last gap: it learns the transition model itself, planning
with MCTS over a learned latent dynamics rather than the true rules, and matched
AlphaZero on board games while also mastering Atari. The line from Knuth–Moore to
MuZero traces one question — how few nodes must be examined to choose well — from
a provably optimal pruning of the _given_ tree to a learned model that decides
which tree to search at all.

These methods form a hierarchy of approximations. Minimax defines the ideal but is
unaffordable. Alpha–beta computes the same answer for roughly the square root of
the cost, and is the single most important efficiency idea in the companion lesson.
A cutoff test with an evaluation function trades exactness for real-time play.
Expectiminimax extends the framework to chance. And when the branching factor
defeats even alpha–beta, sampling — rollouts, MCTS, learned evaluators — takes over.
Every strong game player is some point on that curve between exact search and
learned approximation.

[^aima-po]: **AIMA**, §5.6 — Partially Observable Games: Kriegspiel as deterministic partial observability, belief states over board positions and their state-estimation update, guaranteed checkmate via AND–OR search, probabilistic and accidental checkmate, the need for randomized play, and card games (bridge) as stochastic partial observability solved by Monte Carlo averaging over deals — Equations (5.1)–(5.2), the road/bus example, and the failure of averaging over clairvoyance to gather information, hide information, or bluff.
[^aima-sota]: **AIMA**, §5.7 — State-of-the-Art Game Programs: Deep Blue's alpha–beta search, custom hardware, singular extensions, $8000$-feature evaluation, and opening/endgame databases; and the Monte Carlo / UCT rollout approach used for Go where a heuristic evaluation function is hard to write.