Sprague-Grundy values

Hello Math 450,

The purpose of this post is to explore Sprauge-Grundy values. Before dwelling into the topic I would like to remind you of features that pertain to combinatorial games:

Impartial games
An impartial game is a two-player game in which the legal moves are solely based on position and each position has the same payouts between players. The only difference between players in an ideal impartial game is who goes first.

Normal play
Under the normal play rule, the last person to play wins.

P- and N-positions
Positions in the game can be classified accordingly, depending if the current player wins or if the bystanding player wins (granted that both players play optimally). A current player win is an N-position because the next player to play will win. Likewise a P-position is if the bystanding player wins because the previous player to play will win.

Note: All terminal positions are P-positions.
Note: From every N-position there is at least one move to a P-position.

OK.. Enough of that. Onward!

We have a decent understanding of combinatorial games. Now, we want to take that understanding and display it graphically. Impartial games can be represented using directed acyclic graphs. A directed acyclic graph is a finite graph with no directed cycles. These can be displayed on an xy-plane with vertices and edges.

from: http://mathinsight.org/definition/undirected_graph

From graph to game, the vertices correspond to positions and edges represent a legal move from one position to another.

Mathematically speaking: "a directed graph, G, is a pair (X, F) where X is a nonempty set of vertices (positions) and F is a function that gives for each x ∈ X a subset of X, F(x) ⊂ X. For a given x ∈ X, F(x) represents the positions to which a player may move from x (called the followers of x). If F(x) is empty, x is called a terminal position."

A two-person game may be represented using graph G=(X,F) and by following these rules:

(1) Player 1 moves first, starting at a set opening position.
(2) Players alternate moves
(3) At position x, the player whose turn it is to move chooses a position y ∈ F(x).
(4) The player who is confronted with a terminal position at his turn, and thus cannot move, loses.

An impartial game (what we are working with) requires more regulation.

As of now, from the previous definitions, this game could continue for an infinite amount of moves. To fit the rules of the games that we are working with, such as Nim, we need to impose the property that no matter what starting point x is used, there is a number n, such that every path from x has length less than or equal to n. These graphs are considered progressively bounded, this means that there are no cycles.

This image depicts a directed a cyclic graph for a game where you start with 10 pieces and can take away 1,2, or 3 pieces. Notice how there is no repetition of moves. Notice anything else?


source: http://m.blog.csdn.net/article/details?id=21039309



Using the idea of N- and P- positions we can get graphs that look like this:
                                                    
source:http://www.gabrielnivasch.org/fun/combinatorial-games/sprague-grundy

Is it a good time to talk about Sprague-Grundy values?

Two mathematicians in the 1930's, Roland Sprague and Patrick Grundy, are credited with a function that will assign each position in combinatorial games a natural number.  The Sprague-Grundy function of a graph, G=(X, F), is a function, g, defined on X and taking non-negative integer values, such that

g(x) = mex{g(y) : y ∈ F(x)}. 

g(x) is defined recursively, meaning g(x) is defined in terms of g(y) for all followers y of x.

mex is a short way of saying the minimal excludant. The minimal excludant of a non-negative integer set is the smallest non-negative integer in that set.

Ex. Let M be the set {0, 1,3,4}
mex(M)=2

Ex. Let M be the set {0,2,100}
mex(M)= 1

The end-game Grundy value is equal to 0, thus terminal positions are when g(x)=0. Also, p-positions in a game will have a Grundy value of 0.

Example:
Let there be a game where a position consists of a pile of chips, and a legal move is to remove 1, 2 or 3 chips.

Imagine a table where x is the amount of chips and g is the Grundy function:
                x   0   1   2   3   4   5   6   7   8
             g(x) 0   1   2   3   0   1    2   3   0
g(x) outputs the corresponding Grundy value's for x. Notice how there is a Grundy value of 0 for 4 chips left.

That is, g(2) = mex{0, 1} = 2, g(3) = mex{0, 1, 2} = 3, and g(4) = mex{1, 2, 3} = 0.

In this example g(x)= x mod 4.

Another Example:
A game consists of a pile of chips. A legal move from a position with n chips is to remove any positive number of chips strictly smaller than n/2 + 1.

Here are the corresponding Grundy values for x being the number of chips and g(x) being the grundy values.

x       0   1   2   3   4
g(x)  0   1   0   2   1

The Grundy values may be hard to mentally visualize, but it may be easier to comprehend if you write it out. Instead of tables we can apply those graphs we were working on earlier.

source: http://www.gabrielnivasch.org/fun/combinatorial-games/sprague-grundy

So far Grundy values haven't told us much of anything new. We could compute nim-values to find the N- and P-positions.

Fortunately the Sprague-Grundy function lets us analyze Sums of Graph Games. 

Definition: The sum of two combinatorial games G1 and G2 is that game G where, for any move, a player may choose in which of the games G1 and G2 to play. The terminal position in G is (t1,t2), where t is terminal in Gi for i ∈ {1, 2}. We will write G = G1 + G2.

Every progressively bounded combinatorial game, G, in normal play is equivalent to a nim pile.

Need help imagining G1 and G2? Think of those nim piles we love so much.

Suppose we are given G1 and G2. Can we correctly play their sum G1+G2 if we know the N- and P- positions of the seperate games?

Unfortunately the answer is no.

It can be seen through observation that the sum of P-positions is always a P-position.. And the sum of an N-position and a P-position  will be a N-position. But what happens if we add the sums of N-positions? Ambiguity happens :(, not good. The Sprague-Grundy Function takes away this ambiguity.

The Sprague-Grundy function has two important properties:
           -A vertex v is a P-positoin iff g(v)=0
           - if G= G1+G2 and v=v1v2 is a position in G, then g(v) is the bitwise XOR (nimsums) of the binary representations of g(v1) and g(v2): g(v)= g(v₁) ⊕ g(v₂).

These properties imply that v=v1v2 is a P-position iff g(v1)=g(v2), since this is the only way the nim-sum can come out to zero.

The sums of games is a commutative and associative operation, this means we can understand ideal play with any impartial game as long as we know the Grundy function. 


Moving forward we can think about the most efficient path for achieving a win by looking at a graph.

"The most natural application of the Sprague-Grundy theory is for games that naturally decompose into sums of themselves.

Consider the following game: There is a checkerboard of size m × n, and there is an unlimited supply of polyominoes of a certain shape. On each turn, a player places a polyomino on an empty place on the board, and the player who cannot make a move is the loser:

During the course of the game, the board will gradually split into separate regions, for which we can calculate their Grundy values independently:

"

from source 3. 

Any questions or comments would be greatly appreciated.

sources:

1. Ferguson, Thomas S., F. Thomas Bruss, and Le Cam Lucien M. Game theory, optimal stopping, probability and statistics: papers in honor of Thomas S. Ferguson. Beachwood, OH: Institute of Mathematical Statistics, 2000.

2. Peres, Yuvul. "Stat 155 Game theory." http://www.stat.berkeley.edu/~yuvalweb/gath7.pdf.

3. "Sprague-Grundy theory - Gabriel Nivasch." Gabriel Nivasch. Accessed January 30, 2017. http://www.gabrielnivasch.org/fun/combinatorial-games/sprague-grundy.