I have again spent some time studying game theory a bit further with Thomas S. Ferguson’s book *Game Theory*. The latest topic was Sprague-Grundy functions that are used to describe, how to choose a winning strategy in combinatorial games. Sprague-Grundy functions are often used to analyze games, when it is not clear which positions in the game are P-positions and which are N-positions. If the Sprague-Grundy functions exist for all the positions in the game, a winning strategy is easily found. For simple games, the Sprague-Grundy offers little added information, since it just provides us the P- and N-positions in the game, but for more complex games it gives information that a simple analysis of P- and N-positions does not provide. I will take a look at this in a later post.

**Sprague-Grundy function**

The Sprague-Grundy (S-G) function g(n) of node n is defined recursively as follows:

- For all terminal nodes g(n) = 0.
- For all other nodes g(n) is the smallest non-negative integer that does not belong to the Sprague-Grundy values of the nodes direct followers.

It is easy to show, that the definition of a Sprague-Grundy function is equal to the definition of P- and N-positions in a game.

We remember that P- and N-positions are such positions, that the Previous player to move into or the Next player to move from that position can always win the game. The three definitions of P- and N-positions in combinatorial games are:

- The terminal position is a P-position.
- An N-position is such that there is at least one possible move into a P-position.
- A P-position is such that from it is possible to move only into an N-position.

We will now show that Sprague-Grundy functions fulfill these three conditions, where g(n) = 0 is a P-position and g(n) > 0 is an N-position.

Definitions 1 and A show that for the terminal position the S-G value equals the P-position.

For every other position we have either g(n) = 0 or g(n) > 0, respectively. If g(n) = 0, it means that each predecessor of that node must have an S-G value larger than 0. Therefore, from every position with an S-G value of larger than 0 we can move into a position with an S-G value of 0 (definition 2). Also, if we are not at the terminal node and g(n) = 0, we can only move to positions with an S-G value of larger than 0, since otherwise the position we are in could not have an S-G value of 0 (definition 3).

In conclusion, we see that from positions with an S-G value of larger than 0 we can always move to positions with an S-G value of 0 (equal to definition 2), and from positions with an S-G value of 0 we can only move to positions with an S-G value of larger than 0 (equal to definition 3). Thus, we have shown that the Sprague-Grundy functions give us the P- and N-positions in a game. The difficulty is that they must be defined recursively, and that they do not exist for “circular paths” in games, where you might end up in a previous position after a certain number of moves.