Article on NIM and Sprague-Grundy theorem

A friend of yours comes up with a game for both of you to play. There are ’n’ coins in a pile and both of you alternately pick up 1 or 2 coins only from the pile. The last one person who is not able to make a move loses the game. After a lot of games, you try to determine if the winner and the loser can be determined at the start of the game itself.

Assumptions of a game:

1. In this case, games are defined for two people who make their moves alternately.
2. The player starting the game is defined as the “first player” and the player making the second move is called the “second player”.
3. There is no hidden information and each game has a pre-determined winner and loser given both players optimally.
4. Players usually move till they reach a specific condition and depending upon the game rules, the last person to make the move is declared either a winner or a loser.

Let us try to take small values of ’n’ and see if there some pattern of winning and losing depending upon the value of ‘n’.

If n = 0 then the first player loses.

If n = 1 the second player loses (as the first player can take away one stone and n becomes 0)

If n = 2 the second player loses again (as the first player can take away two stones and n becomes 0)

If n = 3 the first player loses (the first player picks up either 1 or 2 stones, leaving behind 2 or 1 stone respectively. The second player takes away all the remaining stones and n becomes 0 for the first player)

If n = 4 the second player loses (the first player can take away 1 stone making n = 3 which is a losing state for the second player or take away 2 stone making n = 2 which is a losing state for the first player. Because he is playing optimally, he will take away one stone and win)

We can find the answers for further values of ’n’ and tabulate our results. We have a Boolean array starting from n = 0 to any arbitrary value of n (say 9 in this case). If at any index, the array has true, it means that it is a winning state i.e., any player who has to make a move at that n will win the game. If it is false, that ’n’ is a losing state i.e., any player who has to make a move at that n will lose the game.

Whenever ’n’ is a multiple of 3 (n%3=0), there is a losing state. This means that if ’n’ is divisible by 3, the first player will always lose and if not, the first player will always win. In this way, we an get our answer in constant time and space.

Let’s assume we can remove 1, 2 or 3 stones; we end up with the following table:

Here, we can see that every value of ’n’ divisible by 4 is a losing state.

In fact, this can be generalized when we can remove any number of stones between ‘a’ and ‘b’.

If (n%(a+b) = 0), the first player loses else the first player wins.

Game of NIM

When we had only one pile of coins, it was quite easy to calculate the outcome. Another variation of this game is instead of having only one pile, we have ’n’ piles of consisting of

[a1, a2, a3 … an-1, an] coins. The task is very similar to the first game. Each player can remove >=1 coins at their turn given that all the coins removed come from the same pile; that is if a player chooses the ith pile, it has ai coins; player can remove anywhere form 1 to ai coins from that pile. The last player to have no coins left in any piles loses the game. This game is popularly known as the game of NIM.

This problem seems quite hard at first glance as there are so many possible moves that can be made by each player but there exists a very popular formula to solve this question. The solution is as stated:

“If the XOR of all the number of coins of each pile comes out to 0, that state is a losing. If the XOR of all number of coins comes out to be non-zero, it is a winning state.”

Intuition behind NIM:

Let us say we only have one pile of coins consisting of ‘k’ coins.

If k>0, the first player can remove all coins from the pile and win. If k=0, then there are no coins for the first player to remove and thus loses.

For each game state “g”, we will assign it some value “G” which will tell us if that state (g) is a winning state or a losing state. Given two game states “a” and “b” with values “A” and “B” respectively, we need a function which can tell the game state of a+b using the values “A” and “B”

i.e., f(A, B)

Some of the properties that function ‘f’ should have are:

1. f(A, B. C) should be equal to f(A, C, B) i.e. order to piles should not matter and the function should be commutative and associative.
2. f(A, 0) = A i.e. existence of an empty pile shouldn’t affect our answer.
3. f(A, A) = 0 i.e. if there are two piles with equal number of coins, the first player should lose (first player removes A coins from the first pile and the second player removes A coins from the other pile leaving 0 piles with non-zero coins for the first player). This essentially is a mirror play.

All these properties are shown by the bitwise XOR operator (^) making it viable in the solution for the game of NIM.

Let us assume we have ’n’ piles of consisting of [a1, a2, a3 … an-1, an] coins.

The NIM sum for this array is given by (a1^a2^a3 … an-1^ an)

From a losing state, we can only move to a winning state:

A losing state is given if we have the NIM sum=0 i.e. (a1^a2^a3 … an-1^ an) = 0

We choose an ith index having ai coins. We remove ‘s’ coins from that pile 1<=s<=ai. After this move the NIM sum becomes ((a1^a2^a3 … an-1^ an)^ai^(ai-s)). We have (a1^a2^a3 … an-1^ an) = 0.

To have a losing state, ai^(ai-s) has to be equal to 0. This is possible only when

ai = (ai — s)

this is possible only when s=0. However, that is not possible only when since 1<=s<=ai. Thus, we have proved that form a losing state we can only move to a winning state.

From a winning state, it is possible to move to at least one losing state:

If the NIM sum (a1^a2^a3 … an-1^ an) != 0 (‘!=’ refers to ‘not equal to’), we can change it to 0 by finding the left most column where the number of 1s is odd, changing one of them to 0 and then by changing 0s or 1s on the right side of it to gain even number of 1s in every column. In this way there is at least one way of going form a winning to a losing state.

1. It is evident by above explanation that the optimal strategy for each player is to make the NIM sum for his opponent zero in each of their turn, which will not be possible if it’s already zero.
2. If the current turn player has a zero state, they have no choice but to ‘disturb’ it into a nonzero state.
3. The next player then, given a nonzero state, always is able to ‘restore’ it back into a zero state.
4. Thus, if the players know what they are doing, the first player is helpless if the NIM-sum is 0. The second player can always ensure that the NIM-sum is 0 if and only if it is the first player’s turn. There are only a finite number of moves in a game of NIM (obvious, but you can prove it by induction, using the fact that pile sizes only get smaller). Eventually, the game ends when the last stone is taken, meaning the NIM-sum is 0. So, we know that it is the first player’s turn when the game ends, thus the second player can ensure that the first player loses.
5. Similarly, if the current turn player has a nonzero state, they can restore it to a zero state and pass the board over to the second player, who by our logic, must be the loser, thus the first player is the winner.

Grundy numbers

Grundy number aka nimbers are number used to define the game state of any impartial games.

It is given by the following rules:

· If it is a losing state for the player starting at that position, nimber = 0

· Else nimber of that position = mex(all the reachable nimber values form that position)

We can try to solve the game we started with using grundy numbers. We have 5 coins and the two players can remove 1 or 2 coins alternately and the first to reach zero coins loses.

We will start from zero coins and go to 5 coins.

When n = 0; G(0)=0

When n =1; G(1) = mex(G(0)) = mex(0) = 1

When n = 2; G(2) = mex(G(0), G(1)) = mex(0, 1) = 2

When n = 3; G(3) = mex(G(1), G(2)) = mex(1, 2) = 0

When n = 4; G(4) = mex(G(2), G(3)) = mex(2, 0) = 1

When n = 5; G(5) = mex(G(3), G(4)) = mex(0, 1) = 2

When ever the value of number is zero, it is a losing state (wrt the player that land on that number)

As we can see this is a recursive function with exponential time complexity. The time complexity can be reduced to polynomial time using dynamic programming

Here is a sample code. We can use any hash set to find the mex values. Here i have used an unordered set.

Sprague-Grundy theorem

For a composite game, it is a winning state if the XOR of the Grundy numbers of all the reachable positions is non-zero. If the XOR evaluates to zero, that state is a losing state.

A composite game is a game consisting of more than one simple games/ having more than one sub-game.

The idea is to individually calculate the Grundy numbers of all the sub-games is take their XOR sum.

If this sum evaluates to zero, it is a losing state, otherwise it is a winning state.

For example lets consider a game with 3 piles having 3, 4 and 5 coins, and the players can pick up any positive number of coins upto 3 only form any of the piles. Here there are three sub-games consisting of 3, 4 and 5 coins respectively. We calculate of Grundy number for these sub-games which come out to

G(3)=3

G(4)=4

G(5) =1

On taking the XOR of these three values: G(3)^G(4)^G(5) = 2

Which is non-zero. So by Sprague-Grundy theorem, the first player will win.