Games of Chance and Imperfect Information

The companion lesson, Adversarial Search and Games, 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 $\frac{1}{36}$, and each of the other $15$ distinct rolls (such as $6$–$5$, which equals $5$–$6$) has probability $\frac{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.

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

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.¹ 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.

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-ϵ$: White must expose a bishop for one move, and can shrink $ϵ$ 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)$:

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

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.

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. 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.² 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.

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.