Section 23.1

Backward Induction and Winning Positions

Sequential games solved from the end: pirates, tigers and sheep, take-away and race-to-n games, Nim-like and Kayles positions, symmetry strategies.

Toolkit

These games are deterministic, perfect-information, finite, so they can be solved by backward induction from terminal positions: label each position P (previous player/second player wins, i.e. losing for the mover) or N (next player/mover wins) by looking at whether some move leads to a P-position.

A position is losing for the mover iff every move leads to a winning position for the opponent; it is winning iff some move leads to a losing position.
For a single pile with moves removing $k\in S$ : the losing totals are those $n$ with no move to another losing total; often periodic, e.g. for take-away up to $m$ , losing values are $n\equiv 0\pmod{m+1}$ .
Symmetric games (equal heaps, round table, mirrored boards) are solved by the second (or first, after centring) player copying the opponent’s move under a symmetry fixing the target.
For impartial games decomposing into independent components, assign Grundy values $g(P)=\mathrm{mex}\{g(P'):P\to P'\}$ ; the position is a first-player win iff the XOR of components’ Grundy values is nonzero.
For bargaining/voting games (pirates), solve the $k$ -player subgame assuming optimal play in the $(k-1)$ -player subgame, tracking exact payoffs each player needs to beat.

Problems