Impartial game

An impartial game is a game in which both players have the same legal moves from any given position. Under the normal-play convention, a player with no legal move loses. For finite games without draws, Grundy numbers encode positions for the Sprague-Grundy theorem.

An impartial game played under the normal-play convention.

Sprague-Grundy theory studies finite acyclic impartial games under the normal-play convention by assigning each position a Grundy number. The assignment recursively takes the minimum excludant of the values of all legal followers. The Sprague-Grundy theorem then reduces a disjunctive sum of games to the bitwise exclusive or of its component values. This framework explains both why a zero value is losing and how independently understood games can be combined without exploring the entire product of their state spaces.

Every finite acyclic impartial game under the normal-play convention has a Grundy number. The Grundy number of a sum of independent games is the bitwise exclusive or of their individual Grundy numbers, so the sum is losing exactly when that value is zero.

A subtraction game has a heap of nonnegative integer size. A legal move subtracts an allowed positive amount without making the size negative; normal play declares an empty move set losing.

In a disjunctive sum of games, each move changes exactly one component game. Under normal play, a player loses when no component has a legal move.

Fibonacci Nim is a normal play impartial game on one heap. Start with $N\ge 2$ counters. The first move removes between $1$ and $N-1$ counters; thereafter a move removes at least one and at most twice the number just removed by the opponent, without exceeding the remaining heap. Taking the last counter wins.

For a position with $n>0$ counters and permitted maximum $r$, let $z(n)$ be the smallest Fibonacci number appearing in the Zeckendorf representation of $n$, using the sequence $1,2,3,5,8,\dots$. The position is losing exactly when $r<z(n)$. If $r\ge z(n)$, removing $z(n)$ is a winning move. When this does not empty the heap, the next smallest summand exceeds $2z(n)$, so the opponent's new limit is too small. Conversely, the Zeckendorf subtraction lemma gives $z(n-t)\le 2t$ whenever $0<t<z(n)$, so every legal move from a losing position leaves a winning one.^[ref]

Initially $r=N-1$, so the losing initial heap sizes are precisely the Fibonacci numbers. For example, $10=8+2$: take $2$, leaving the opponent $8$ counters and a limit of $4$, a losing position. The move limit is part of the state; heap size alone does not determine later positions.

A Euclid game is an impartial game based on subtraction steps of the Euclidean algorithm.^[ref] Here use the following normal-play convention: a position is an ordered pair $0\le a\le b$; if $a>0$, remove a positive multiple $ka\le b$ from $b$ and reorder. A position with $a=0$ has no legal move and is losing. Thus moving to a zero coordinate wins; variants that instead stop at equal positive coordinates require a different endpoint convention.

The sum of the coordinates strictly decreases, so every play terminates. If $a$ divides $b$, subtract $b$ and win immediately. If $a<b<2a$, there is only one move, to $(b-a,a)$, so the position has the opposite winning status from that successor.

If $b=qa+r$ with $q\ge 2$ and $0<r<a$, two legal choices leave $(r,a)$ or $(a,a+r)$. The latter has exactly one move, to the former, so exactly one of these two successors is losing. Choose it. For example, $(2,3)$ is losing because its only move reaches $(1,2)$, where the opponent takes the whole larger coordinate. From $(2,5)$, subtract $2$ to leave that losing position. These cases give a recursive strategy without exploring every subtraction amount.

The value $g(P)=\mathrm{mex}\{g(Q):P\to Q\}$ of a game position, where mex is the smallest nonnegative integer missing from the values of its legal successors. Terminal positions have value zero. The Sprague-Grundy theorem explains why these values combine by exclusive or.

For finite nimbers, multiplication is recursively defined from smaller arguments bywhere $\oplus$ is Nim-sum and mex selects the smallest missing nonnegative integer. Thus zero times anything is zero and one times $b$ is $b$. For $a=b=2$, the displayed set is $\{0,2,3\}$, so $2\otimes 2=1$.

Together with Nim-sum, this is field arithmetic on finite nimbers, rather than ordinary integer multiplication. In particular $2\otimes 2=1$ cannot be computed by a usual integer product or bitwise exclusive or.^[ref]

An impartial game played with heaps of counters: a move removes a positive number of counters from exactly one heap. Under the normal-play convention, a position is losing exactly when the bitwise exclusive or of its heap sizes is zero.

A Nim heap of size $n$ contains $n$ counters and permits removing any positive number, leaving a heap of any size $0\le k<n$. Under the normal-play convention, its Grundy number is $n$: the reachable values are exactly $0,\dots ,n-1$, whose mex is $n$.

For several heaps, a turn changes exactly one heap. Their combined value is the Nim-sum of the heap sizes, so heaps of sizes three and three form a losing position even though either heap alone is winning. The ability to remove arbitrarily many counters is part of the rule; a bounded-removal subtraction game has different values.

The bitwise exclusive or of a list of nonnegative integers. For heap sizes in ordinary Nim, a zero nim-sum characterizes a losing position under the normal-play convention.

In a finite impartial game with the normal-play convention and no draws, a losing position is one from which the player whose turn it is cannot force a win against best play. It is also called a P-position, since the previous player wins.

A terminal position is losing. Recursively, a position is winning if it has at least one move to a losing position, and losing if every legal move goes to a winning position. Induction on the finite remaining game tree proves this classification. For a single Nim heap, only the empty heap is losing. Infinite plays and misère play need separate conventions and can change the base case.