Sprague–Grundy theorem

The theorem assigns each position in a finite impartial normal-play game a nim heap of equal strategic value, with disjoint game sums represented by bitwise XOR of their Grundy numbers.

Grundy number: A nonnegative integer assigned to an impartial game position, equal to the minimum excluded value among its options’ Grundy numbers. It is the nim-heap size that the theorem assigns to each position.
Impartial game: A two-player game in which both players have the same legal moves from every position. The theorem applies to games whose available moves do not depend on player identity.
Subtraction game: A heap game in which a move removes a permitted number of objects from one heap. Its positions provide a direct setting for computing Grundy numbers by mex.
Misère play: A play convention in which the player making the last legal move loses. Changing who wins at termination breaks the theorem’s direct nim-value interpretation.
Minimum excluded value: The smallest nonnegative integer absent from a specified set of integers, often abbreviated mex. The mex of the option values defines a position’s Grundy number.
Normal-play convention: A rule convention under which the player who makes the last legal move wins. This convention makes positions with no moves losing, anchoring the Grundy recursion.
Kayles: A bowling-pin game in which a move knocks down one pin or two adjacent pins from a row. Its row positions have Grundy values that reveal nontrivial impartial-game structure.
Partizan game: A game in which the two players have different sets of legal moves. Player-dependent options fall outside the impartial games covered by the theorem.
Nim-sum: The bitwise XOR of two or more nonnegative integers, used to combine nim heaps. The theorem represents a disjoint sum by the nim-sum of component values.
Finite game: A game whose play always terminates after finitely many moves. Termination allows Grundy numbers to be defined recursively from terminal positions.

Linked from 4 pages