↑ arvau

Wikipedia / Sprague–Grundy theorem

In combinatorial game theory, the SpragueGrundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.

The Grundy value or nim-value of any impartial game is the unique nimber that the game is equivalent to. In the case of a game whose positions are indexed by the natural numbers (like nim itself, which is indexed by its heap sizes), the sequence of nimbers for successive positions of the game is called the nim-sequence of the game.

The Sprague–Grundy theorem and its proof encapsulate the main results of a theory discovered independently by R. P. Sprague (1936) and P. M. Grundy (1939).

Definitions

For the purposes of the SpragueGrundy theorem, a game is a two-player sequential 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).

At any given point in the game, a player's position is the set of moves they are allowed to make. As an example, we can define the zero game, since the set of moves each player can make is empty.

An impartial game is one in which at any given point in the game, each player is allowed exactly the same set of moves. Normal-play nim is an example of an impartial game. In nim, there are one or more heaps of objects, and two players (we'll call them Alice and Bob), take turns choosing a heap and removing 1 or more objects from it. The winner is the player who removes the final object from the final heap. The game is impartial because for any given configuration of pile sizes, the moves Alice can make on her turn are exactly the same moves Bob would be allowed to make if it were his turn. In contrast, a game such as checkers is not impartial because, supposing Alice were playing red and Bob were playing black, for any given arrangement of pieces on the board, if it were Alice's turn, she would only be allowed to move the red pieces, and if it were Bob's turn, he would only be allowed to move the black pieces.

Note that any configuration of an impartial game can therefore be written as a single position, because the moves will be the same no matter whose turn it is. For example, the position of the zero game, because if it's Alice's turn, she has no moves to make, and if it's Bob's turn, he has no moves to make either. A move can be associated with the position it leaves the next player in.

Doing so allows positions to be defined recursively. For example, consider the following game of Nim played by Alice and Bob.

Example Nim Game

  • .

  • At step 5, Alice had exactly one option: to remove one object from heap C, leaving Bob with no moves. Since her move, her position.

  • .

  • , as described in step 4. However, removing 1 from B would leave Bob with two objects in a single pile. His, so her.

Nimbers

referenced in our example game are called nimbers.

While the word nimber comes from the game nim, nimbers can be used to describe the positions of any finite, impartial game, and in fact, the SpragueGrundy theorem states that every instance of a finite, impartial game can be associated with a single nimber.

Combining Games

Two games can be combined by adding.

Example Game 2

We can combine it with our first example:

Combined Game

To differentiate between the two games, for the first example game

For the second example game

To compute the starting position of the combined game

, which means that addition is both commutative and associative.

Equivalence

Positions in impartial games fall into two outcome classes- position- position-position.

are equivalent.

To use our running examples, notice that in both the first and second-positions. (Notice that in the combined game, Bob.)

First Lemma

.

-position.

.

As these are the only two cases, the lemma holds.

Second Lemma

-position.

by commutativity, the previous player can respond with the same move in the other copy, and so always make the last move.

. By associativity is an equivalence relation because equality is an equivalence relation on outcome classes. Via the transitivity.

Proof of the Sprague–Grundy theorem

We prove that all positions are equivalent to a nimber by structural induction. The more specific result, that the given game's initial position must be equivalent to a nimber, shows that the game is itself equivalent to a nimber.

. By the induction hypothesis is the mex (minimum exclusion).

.

. We do so by giving an explicit strategy for the previous player.

-position.

was the minimum-position.

.)

, as desired.

Development

is called its Grundy value, or Grundy number, and the function that assigns this value to each such position is called the Sprague–Grundy function. R. L. Sprague and P. M. Grundy independently gave an explicit definition of this function, not based on any concept of equivalence to nim positions, and showed that it had the following properties:

  • ;

  • -position) if and only if its Grundy value is zero; and

  • The Grundy value of the sum of a finite set of positions is just the nim-sum of the Grundy values of its summands.

. Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it follows directly from their results and is credited to them. These results have subsequently been developed into the field of combinatorial game theory, notably by Richard Guy, Elwyn Berlekamp, John Horton Conway and others, where they are now encapsulated in the Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.

See also

References