nimber

Nimber is a concept in combinatorial game theory used to analyze impartial games under normal play. Each position in such a game is assigned a nimber, also called a Grundy number, defined as the mex (minimum excluded value) of the set of nimbers of its options. The nimber of a terminal position is 0. The Sprague-Grundy theorem states that every impartial game is equivalent, under disjunctive sum, to a nimber, so the outcome of any sum of games is determined by the nimber of each component.

Arithmetic with nimbers involves two basic operations. Nim-addition, or nim-sum, corresponds to bitwise exclusive OR (XOR) of the binary representations of nimbers. The nimber of the sum of two independent positions is the nim-sum of their nimbers. A position is losing (a P-position) if and only if its nimber is 0. Nim-multiplication is a separate, more complex operation defined recursively so that the set of nimbers forms a commutative semiring; its full computation is nontrivial.

Finite nimbers align with ordinary natural numbers: in the classic Nim game, a heap of size n has nimber n, and the disjunctive sum of heaps has nimber equal to their nim-sum. Beyond finite cases, nimbers can extend to transfinite values (ordinals) in more general impartial games, a topic treated in advanced combinatorial game theory.

Historically, nimbers emerged from the work of Sprague and Grundy and were developed further by John Conway. They provide a unifying framework for solving impartial games and for understanding the algebraic structure of game sums.