Sprague–Grundy theorem

related topics
{game, team, player}
{math, number, function}

In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to. In the case of a game whose positions (or summands of positions) are indexed by the natural numbers (for example the possible heap sizes in nim-like games), the sequence of nimbers for successive heap sizes is called the nim-sequence of the game.

The theorem was discovered independently by R. P. Sprague (1935) and P. M. Grundy (1939).

Contents

Definitions

For the purposes of the Sprague–Grundy theorem, a game is a two-player game of perfect information satisfying the ending condition (all games come to an end: there are no infinite lines of play) and the normal play condition (a player who cannot move loses).

An impartial game is one such as nim, in which each player has the same available moves in every position. Impartial games fall into two outcome classes: either the next player wins (an N-position) or the previous player wins (a P-position).

An impartial game can be identified with the set of positions that can be reached in one move (these are called the options of the game). Thus the game with options A, B, or C is the set {A, B, C}.

The normal play convention is where the last player to move wins. Alternatively, the player who first does not have any valid move loses. The opposite - the misere convention is where the last person to have a valid move or makes the last move loses.

A nimber is a special game denoted *n for some ordinal n. We define *0 = {} (the empty set), then *1 = {*0}, *2 = {*0, *1}, and *(n+1) = *n ∪ {*n}. When n is an integer, the nimber *n = {*0, *1, ..., *(n−1)}. This corresponds to a heap of n counters in the game of nim, hence the name.

Two games G and H can be added to make a new game G+H in which a player can choose either to move in G or in H. In set notation, G+H means {G+h for h in H} ∪ {g+H for g in G}, and thus game addition is commutative and associative.

Two games G and G' are equivalent if for every game H, the game G+H is in the same outcome class as G'+H. We write GG'.

A game can refer to two things. It can define a set of possible positions and their moves through its rules, for example, chess, or nim. It can also refer to a certain position, for example, the game *5. Generally, it is clear from the context the meaning that is to be taken.

Lemma

For impartial games, GG' if and only if G+G' is a P-position.

Firstly, we note that ≈ is an equivalence relation since equality of outcome classes is an equivalence relation.

Full article ▸

related documents
Simple squeeze
Balderdash
Calcutta auction
Laura Serrano
Yuba-Sutter Gold Sox
Sporting de Gijón
Yomiuri Giants
Sparta Rotterdam
Ada Velez
Jim Hines
Gordie Howe
Ian Ure
Florida State League
Norfolk Tides
Johann Olav Koss
Andoni Goikoetxea Olaskoaga
Richmond Braves
Nashua Pride
Greg Louganis
1934 FIFA World Cup
Camden Riversharks
Beggar-My-Neighbour
1968 Summer Olympics
Lansquenet
Auction bridge
Byoyomi
Gulf Coast League
Matt Stairs
Pedro Morales
Angel Manfredy