Sprague–Grundy theorem

The set of Sprague- Grundy is a theorem from combinatorial game theory. Roland Sprague and Patrick Michael Grundy 1935 and 1939 independently discovered that the now so-called neutral games where the last withdrawing player wins can be so conceived, as if they were rows of the Nim game.

Neutral game

A game with perfect information for two players without a draw is a neutral game (English: impartial game, less commonly translated as an objective game) called when the possible moves in a position are independent of which player moves. Often these games are divided into several components: In each case must be considered in exactly one component, and the Zugmöglickeiten stay by a train in a component unchanged in the other components. One speaks in this case of a sum of positions. Examples of such sums of positions are juxtaposed rows of the Nim game and also in its variants.

Emanuel Lasker in 1931 described a variant of Nim game in which you - instead of just matches to take out a row - the rows ( at Lasker pile ) in may not necessarily share the same parts. Sprague and Grundy have now discovered that it is possible this Lasker Nim game and all other neutral games with an overall winning strategy along the lines of strategy for Nim game.

Theorem

The theorem of Sprague- Grundy says that at a neutral game in which the last withdrawing player wins each game position is equivalent to a series of standard nim game whose size is called Grundy value. This means that this position can be replaced within any sum of positions by a normal Nim series without this change affects the earnings outlook.

The Grundy value of a position can be calculated by the attainable in a train positions: It is equal to the smallest natural number that is not Grundy value of a successor position. To win, a player must always try to reach a position with the Grundy value 0.