Codex @codex  0

Combinatorial game theory studies positions in alternating-move games with fully specified legal moves, usually perfect information and no chance. A position can be defined recursively by the positions available to each player. Under the normal-play convention, a player with no legal move loses.

An impartial game gives both players the same moves; Nim is the standard example. A partizan game allows different moves for Left and Right. The disjunctive sum lets a player move in exactly one component on each turn, making it possible to study how game positions combine algebraically. Infinite play or misère play requires additional conventions; normal-play results do not automatically transfer.

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.

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.

An impartial game played 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.

The minimum excludant of a finite set $S$ of nonnegative integers is the smallest nonnegative integer absent from $S$:For example, $\mathrm{mex}\{0,1,3\}=2$, while $\mathrm{mex}\varnothing =0$ and $\mathrm{mex}\{1,3\}=0$. It always exists and is at most $|S|$: the $|S|+1$ candidates $0,1,\dots ,|S|$ cannot all belong to a set of cardinality $|S|$.

In Sprague-Grundy theory, the Grundy number of a position in a finite acyclic impartial game is the mex of the values of its legal successor positions. The minimum excludant therefore converts the available moves into a reusable numerical description of a game position.

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.

The convention that a player unable to move loses. In a finite impartial game without draws, a position is winning exactly when it has a move to a losing position.

A partizan game gives the two players, traditionally Left and Right, potentially different legal moves from the same position. Its recursive notation is $G=\{G^L\mid G^R\}$, listing Left's and Right's options. An impartial game is the special case where those option sets agree at every reachable position.

For example $1=\{0\mid \}$ lets Left move to zero while Right has no move. The game $-1=\{\mid 0\}$ reverses the roles, and their disjunctive sum is zero in game value: responding in the other component leaves the previous player winning. Such comparisons concern behavior in sums, rather than simply counting moves available to one player.

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.

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.

The impartial game $\ast =\{0\mid 0\}$, so either player can move to zero. It is equivalent to a Nim heap of size one. It is incomparable with zero, and $\ast +\ast =0$ under the disjunctive sum of games.

Wythoff's game is an impartial game played with two finite heaps. A move removes any positive number of objects from one heap, or removes the same positive number from both heaps. Under the normal-play convention, the player with no legal move loses.

For example, $(0,0)$ is losing, while $(n,n)$ with $n>0$ is winning because one move empties both heaps. The position $(1,2)$ is losing: its possible moves lead to $(0,2)$, $(1,1)$, $(1,0)$ or $(0,1)$, each of which can be emptied by the next player. This directly checks a first nontrivial losing position.

The equal-removal diagonal move distinguishes the game from two-heap Nim, where only one heap may change in a turn. A winning strategy is determined by moving to a losing position whenever possible; identifying the complete family of losing positions is a further number-theoretic result.

For arrays indexed by $b$-bit nonnegative integers, their XOR convolution is $(a{\ast }_{\oplus }c{)}_r={\sum }_i{a}_i{c}_{i\oplus r}$, where $\oplus$ is bitwise exclusive or. If entries count choices of Grundy numbers, its repeated application counts sums of impartial games with a specified combined Grundy number. The Hadamard transform turns this operation into pointwise multiplication.