# Sprague-Grundy theorem

Given a 2 player impartial game, decide for a given configuration if there is a possibility for the first player to win assuming the second player plays perfectly.

## Summary

See the corresponding wikipedia page for more details.

The theory says the following. Suppose you have a directed acyclic graph, with a pebble on a cell. Two players move in turns the pebble along an outgoing arc to a successor vertex. The first player who cannot move the pebble anymore looses.

Which are the winning and which are the loosing configurations? Well this can be determined recursively. Vertices with zero outdegree are loosing vertices. Vertices that lead to a loosing vertex are winning vertices. Vertices that lead only to loosing vertices are loosing vertices.

Now we can augment this binary information by replacing it by a non-negative integer, called the *Grundy number* or *nimber*. Vertices with zero outdegree get the number 0. In general the number assigned to a vertex is the smallest non-negative integer which does not belong to one of the reachable vertices. Clearly a vertex is winning iff its nimber is positive.

These number became interesting when combining two games, and this is the purpose of the Sprague-Grundy theorem. Suppose you combine two DAGs into one game. Now there is a pebble in each graph, hence a game configuration is a pair of vertices, one from each graph. A valid move is to move one of the pebbles to a successor, and to leave the other pebble untouched. This is a game that could be decribed by a much bigger and single DAG. The Sprague-Grundy theorem says that the nimber of configuration (u,v) is simply the bitwise exclusive OR of the nimbers of u and of v.

## Example

See this page for an excellent and more detailed explanation of a solution to the following problem.

You are given a row of cells, some of which are marked. Two players in turn each marks a cell. The first player who reaches a configuration with 3 adjacent marked cells wins. The goal is to list all cells such that if the first player marks one of those, then he can always win the game.

```
intial configuration: .....X.
player 1: ..X..X.
player 2: ..X.XX.
player 1 wins: ..X.XXX
```

Basically you first need to detect patterns where the first player can immediately win, namely .XX, X.X or XX. Then by adding X.. to the left and ..X to the right we end up with a string of the form X..?X..?X etc, where every sequence of points has some length at least 2. These sequences form sub-games, where the 2 first and 2 last points are forbidden cells, since the opponent can then immediately win. The trick is then to compute the nimber for configurations of the form X.{k}X for every k up to 200. Then you can combine these numbers with XOR in order to decide whether some configuration is loosing or not.

The following code solves this problem in time \(O(n^2)\).