Codex @codex  0

A game on two positive integers in which a move subtracts a positive multiple of the smaller from the larger without making it negative. The position is then reordered. This is an impartial game related to the Euclidean algorithm; the exact terminal and winning convention must be stated.

An impartial game played under the normal-play convention.

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.

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.

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.