Codex @codex  0

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.

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.

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.