Sprague-Grundy

The Sprague-Grundy Theorem

“Every progressively bounded, impartial combinatorial game G with starting position x under normal play is equivalent to a single Nim pile of size g(x) ≥ 0, where g(x) is the Sprague-Grundy function evaluated at the starting position x.”

In English, this means that these specific games usually have a function called *drumroll* Sprague-Grundy function, which allows us to find P-positions and N-positions provided we are able to decipher the pattern. It also means that any game with a Sprague-Grundy function can be represented by its function g(x) given a starting position of x. An example that will sound astonishingly familiar is the subtraction game S {1, 2, 3} where two players can take 1, 2 or 3 chips out of a pile per turn until the pile is empty, with the winner being the rock star who empties the pile.  Let’s look at it in a table where x represents the number of chips and g(x) the Sprague-Grundy values:

x	0	1	2	3	4	5	6	7	8
g(x)	0	1	2	3	0	1	2	3	0

In this case, the Sprague-Grundy function would be g(x) = x mod 4. Applying the theorem, we see that any such game starting with x chips would be equivalent to a single Nim pile with x (mod 4) chips. The single part in single Nim pile is of critical importance because this will also apply when we are summing games together (we can add Sprague-Grundy functions together too to create a new function for summed games!), a topic which someone else will have the pleasure to explain to us later on.

Sprague-Grundy in Graph Games

In this post, we will look at Sprague-Grundy values and functions with a focus on Graph Games. Graph Games are combinatorial games played on a directed graph. A directed graph, name it G, is a pair (X, F) where X is a nonempty set of vertices (points of intersection between lines on a graph, those are the positions) and F is a function that give a subset of vertices in X for each x ∈ X . The function represents the positions to which a player can move from x, which are defined as the followers of x.

Graph Types

In order for Graph Games to satisfy the finite game condition, the graph may be progressively bounded or progressively finite. A progressively bounded graph is one where X, or the set of vertices, is finite, thus allowing every path from x_0 (initial position) to have a length lesser or equal to n, where n is the number of vertices.  A path is a sequence of positions x_0, x_1, x_2, x_3…, x_m such that x_i ∈ F(x_i - 1) for all i = 1, 2, …, m, where m is the length of the path. A progressively finite graph is one where every path is finite in length but the length has no upper limit. Additionally, the number of possible paths has no upper limit. It is not progressively bounded because the length of a path from the initial position is not limited. An example of such an instance would be a subtraction game where the initial move is the pick the number of chips to remove. Both these conditions provide the required restriction that there be no cycle. Simply put, a cycle is a path that will never yield a P-position in a graph game (in technical terms it is a path x_0, x_1, x_2, …, x_(m-1)  where m ≥ 3).

Progressively Bounded Graph Game

A two player game played on a progressively bounded graph would see the first player move from x_0, then players would take turns, which means that from a position x a player would move to a position y ∈ F(x) until confronted to a terminal position. A terminal position would be where F(x) is empty, thus making a next move is impossible.

The Sprague-Grundy function of a graph, (X, F), is a function on X taking non-negative integer values. g(x) is the least non-negative integer not present among the Sprague-Grundy values of the followers of x. Where g(x) = z, the Sprague-Grundy value is z. The function can be defined as follows:

g(x) = min{n ≥ 0 ∶ n ≠ g(y)  for y ∈ F(x)}.

Or

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

Here mex is defined as the minimum excludant, or smallest integer absent from the set. Note that in the second function, g(x) is defined in terms of the followers of x, labelled y, in g(y). Terminal vertices x will have a Sprague-Grundy value of 0 (g(x) = 0). For non-terminal positions where the following vertex is terminal, the Sprague-Grundy value will be 1, since the smallest integer not included in the followers {0} is 1. Using the Sprague-Grundy function of a graph game, we see that every position where the Sprague-Grundy value is 0 is a P-position, otherwise it is an N-position. In order to win, a player must select moves putting him in P-positions. At a position x where g(x) = 0, any follower y of x is such that g(y) ≠ 0 and at a position x where g(x) ≠ 0, at least one follower y of x is such that g(y) = 0.

To determine Sprague-Grundy values in a progressively bounded graph, we can start from the terminal values, which are all 0, then work our way up using g(x) = mex{g(y) ∶ y ∈ F(x)}.

Here is an example where I took a shot at one of Ferguson’s Exercise in section 3.5:

P-position logic

There is another item that will be helpful to prove in order to further our understanding of Sprague-Grundy theory. Let's look at the following statement "Let G be a progressively bounded, impartial combinatorial game with normal play rules. A position x in G is a P-position if and only if the Sprague-Grundy value of x is 0."

Given the SG function g(x) = mex{ g(y) : y in F(x)} where g(y) represents all followers y of x, we see that the SG value of a position will be 0 only if it follows positions having SG values other than 0 and if its followers have SG values other than 0. Playing from a position with SG value of 0, you will automatically move to a position with some SG value a (for a > 0). From this position, the player will have at least one opportunity to move to a position with SG value = 0. Terminal positions have a SG value of 0 at all times, because their set of followers is empty. In order to win, you must reach the terminal position, by definition. You cannot win if you move to a position with SG value > 0, because then the next player would have the opportunity to move to a position where SG value = 0, and eventually this position will be the terminal position. Thus, the only way for a player to win is to put himself in a position where the SG value is 0, where the previous player to move would win. Therefore, a position x in a game is a P-position if and only if the SG value of x is 0.

Progressively Finite Graph Game

Sprague-Grundy functions exist in such graphs, but requires allowing transfinite numbers as Sprague-Grundy values, since the number of finite paths from the first position along with the length of these paths have no upper limit. However, all paths must eventually lead to a terminal position. In such games, the starting position would have a Sprague-Grundy value corresponding to the smallest integer greater than all the integers in the paths. This is usually denoted ω (lower case Greek letter omega). Nim positions may also be defined to have transfinite Sprague-Grundy values.

Graph Games with Cycles

Things start to get a little bumpy if graphs are allowed to have cycles. If you recall the quick overview mentioned above, it is easy to understand why: such graphs do not satisfy the ending condition of combinatorial games. Cycles are such that players would follow the same moves over and over without ever winning or losing the game (hence the name cycle). If a player broke the cycle, he would immediately put himself in an N-Position, a losing position, and therefore would never do such a thing (right?).

Here is an example of a cyclic graph:

In this example, a player confronted to position d would never move to position e, because then the next player could win the game by going to the terminal position f, which is the only one with a Sprague-Grundy value of 0. The game would always follow the cycle abcdabcd… without ever reaching the terminal position. In such an instance, the Sprague-Grundy function does not exist.  Some cyclic graph do however have Sprague-Grundy functions, but it may be complicated to find it, and even when it is known and you are able to move to P-positions, you may find yourself back in a previous position many times before things unfold. You think this is interesting? You want to solve the answer to complicated cyclic graph games? I heard we had to do a final project…

Final Thoughts

Sprague-Grundy theory is very useful to establish systematic rules to win combinatorial games. Here we focused on Graph Games, but it can be used for all types of combinatorial jousts. The theorem mentions only progressively bounded games and it would be interesting to see how it fares in instances where the game is only progressively finite, especially when it comes to the property that allows the sum of games and their Sprague-Grundy functions (which, once again, we will discuss later). Furthermore, it is also restricted to normal play. What about misère play? These are questions we can all take interest in and hopefully we will come up with answers!

I leave you with this final challenge, which is an exercise from Thomas S. Ferguson’s Game Theory material: what would be the Sprague-Grundy function of the subtraction game with subtraction set S = {1, 3, 4}?

Cheers,

Sam