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.
An impartial game played under the normal-play convention.
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.
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.
A subtraction game has a heap of nonnegative integer size. A legal move subtracts an allowed positive amount without making the size negative; normal play declares an empty move set losing.
In a disjunctive sum of games, each move changes exactly one component game. Under normal play, a player loses when no component has a legal move.
A heap game in which, after the first move, a player may remove at most twice the number removed on the preceding move. Under the usual first-move restriction of fewer than all counters, Fibonacci numbers and the Zeckendorf representation characterize the winning moves.
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.
The value 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 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 bitwise exclusive or of a list of nonnegative integers. For heap sizes in ordinary Nim, a zero nim-sum characterizes a losing position under the normal-play convention.
Articles by others on the same topic
An impartial game is a type of combinatorial game in which the possible moves available to each player depend only on the current state of the game, and not on which player is currently taking their turn. This means that the options available to both players are the same regardless of who is playing. In impartial games, the rules apply equally to both players, and the game ends when there are no legal moves left.