Impartial Games and how to Solve Them Part 2

Abstract: In this post we introduce two more fundamental ideas to to the study of impartial games. The Sprague-Grundy function, and the Sprague-Grundy Theorem. With these new tools, we are able begin to solve more complicated impartial games, specifically games that are the disjoint sum of other games. Finally, we introduce the game of Nim and present its solution, as well as a very basic AI that utilizes the solution.

In the last post we introduced a very basic game, in which players take turns removing chips, until no more chips can be removed. We showed that, assuming optimal play, the first player will be able to force a win by ending their turn with a multiple of four chips left in the pile. However, what if we wanted to try and find a solution for a more general case of these games? One could, in theory, use backwards induction to solve any of these games, but what if we wanted more general theorem that could be used to solve all such games? One way to find such a solution would be using the Sprague-Grundy function/theorem.

However, before introducing the Sprague-Grundy theorem, we should first formally define our generalization of the earlier game. Let be a set a of positive integers. We define our general version of the subtraction game as follows. Starting with chips, two players talk alternative turns substracting from the chips, where . The player who takes the last chip wins. As mentioned above, the game in are previous post is one of these “subtraction” games, where is 23, and .

The final thing we need to formally define before discussing the Sprague-Grundy function is another function. This function maps a state in an impartial game to all possible states that are one turn away. We define this function to be , where is any state in an our impartial game. As an example, take the subtraction game described earlier, where and . We will represent states of these games by the amount of chips, so starting from the first turn, . Then, we can say that . Finally, it is important to note that if is empty, than x is a terminal state. (As a second note, the literature often represents games as a graph for this analysis, but I have not done so in an attempt to make it more readable\concise for non technical backgrounds.)

With both of those definitions done, we can now move on to the Sprague-Grundy function which is defined as g(x) where:

In words, is the smallest non negative integer that is not found in the possible states after a move has been made. Note that this formula is defined recursively, meaning that in order to find the “g-value” of a given state, we need to find the g-value of all states that could be reached from this state.

For terminal states, or states where the game is over, we can see that the g-value will be 0, as by definition, terminal states are end states and where is a terminal state. For states that can only move to a terminal state, their g-value is 1 and so on. When analyzing some games, one can find an equation for the g-value of any given state inductively, although some games require more subtitle methods, and certain games are (at this time) unknown to have a pattern to analyze.

Now, lets look at our earlier subtraction game. Our terminal state has a g-value of 0. With only 1 chip left in the pile, we can only subtract 1, so the only possible state from 1 chip is 0. As such, . With 2 chips, we can either go to 1 or 0, so the g-value for 2 is 2. With 3, we can either go to 0, 1, or 2, chips. This means that . However with 4 chips, we can only go 1, 2, or 3 chips, none of which have a g-value of 0. Because of this, the state with 4 chips, gets a g-value of 0 (). This pattern continues, with , , etc… From this we can say that the g-value for any given state in our subtraction game is .

Now that we have g(x) defined for our game, we can use this formula to find out if any given state is a P-position or a N-position, using the following rule. If for any given state its g-value () is 0, then that state is a P-position. If not, than the position is a N-position. Of course this doesn’t mean every impartial game is instantly solved as finding the g-function for a given game can be tricky. One also might be thinking that the Sprague-Grundy function gives us more information that we need for P/N-positions, and they would be right. However, that information will be used in the next topic, the Sprague-Grundy theorem.

Suppose that we wanted to make our base subtraction game a bit more difficult or more complex. One way we could would be to add a second instance of the game, and players choose which instance of the game they wished to move in. The winner would then be the player who acts last out of both instances, (or the player who ends their turn with all games being a terminal state). We call this new game, the disjunctive sum of two other games. But, how do we analyze such a game?

As it turns out, their is a specific theorem that can help us out here, referred to as the Sprague-Grundy theorem, that states that if we can find the g-value of both individual games, we can find the entire states g-value with relative ease. To do so, we find the bitwise exclusive or\xor, often written as of both of their g-values. The process can be somewhat easily summarized like so: First find the binary representation of the individual g-values, then apply the XOR operator to the individual bits. An example is shown below with ^ being used as the XOR operation, as it is in python.

So, in order to find our g-value for our two game game, we simply find the g-value of both subgames and bitwise xor them together.

Now that we have discussed how to find the g-value of the disjunctive sum of a games, we can move on to analyzing one of the most important impartial games, Nim. Essentially, Nim is multiple subtraction games all played at once, where . This means that players can take any positive number of chips from a single pile as their move. A starting example of Nim, with the items being matches, instead of chips is shown below to the right. In this instance we have four piles, with object sizes being 1, 3, 5, 7.

In order to find the g-value of this state, we must first find the g-value of the individual piles, which is surprisingly quite easy. Because we are able to take any number of items from a pile, any states g-value will just be the number of items in that pile. For example, take the second pile, which has three items. From here, one could either take 1, 2, or 3 items away, leaving 0, 1, or 2 items left. Since 0 items is a terminal state, its g-value must also be 0 (). With 1 item, we can only move to 0, so its g-value must be 1. With 2 items, we can either go to 0 or 1, meaning our g-value must be 2. The same can be said for 3, 4, 5, etc. As such we can define our g-function for these individual subtraction games to be: .

Now that we have done this, finding the g-value for the entire board is quite easy, we only need to the individual g-values together. Doing so gives us the following result: Which means, as per our earlier definition, this state is a P-position, so assuming optimal play, the first player will always lose this game.

We can also use this idea to write an algorithm for finding the optimal move in a game of Nim (assuming on exists, as if we are passed a p-position, assuming optimal play, our moves don’t matter). In normal play, the winning move is one in which the g-value of the state is 0. To reach that from any state that does not have a g-value of 0, we do the following. Find a pile where the xor of the full games g-value and pile’s size is less than the pile’s size. Then reduce that pile to value found from xoring the full games g-value and the pile’s size. This works as we are “removing” the extra pieces in that pile that are not cancelled out by the xor operation, thus setting the total g-value of the state to be 0. Basic python code for finding this is shown below.

def AITurn(heaps):
    # Calculate the g-value
    nimber = 0
    for i in range(len(heaps)):
        nimber ^= heaps[i]
    # Checks for which heap to reduce and reduces it so the g-value is 0
    for i in range(len(heaps)):
        if nimber ^ heaps[i] < heaps[i]:
            heaps[i] = nimber ^ heaps[i]
            return
    else:
        for i in range(len(heaps)):
            if heaps[i] != 0:
                heaps[i] -= 1
                return

Do note that if no optimal move is found, this code finds the first non zero pile and subtracts on from it, as that would give a human player the most time to possible make a mistake. A full and very simply implementation of the game can be found on the GitHub repo linked below.

Final Thoughts and Conclusions: With this we have shown the solution, and how to play optimally for the game of Nim, using the Sprague-Grundy theorem. Obviously, some important details have been left out, mainly a proof of the Sprague-Grundy theorem, but proving the theorem is a bit beyond the scope of this post. Another important detail could be a full proof of the winning strategy, however, again this is slightly out of the scope of this post, and more likely to brought in a future post.

With this information completed, we can now move on the analyzing more complicated impartial games, which should be the final post in the series.

Also, here is the link to the very basic code for playing Nim. Currently, the game is set for the player to start with an N-position, allowing for the player to win if they can find the optimal plays.

[1] – By Uncopy – Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=18360836