LIKE CODING: MJ [19] Who wins ||-- The Game of Nim

LIKE CODING: MJ [19] Who wins ||-- The Game of Nim
Given n piles of coins, two player take turn to remove coins. Every pile may have any number of coins. Each time a player can remove any number of coins but only from 1 pile. The player removes the last coin wins the game and the other player loses. Determine whether the first player can win. Note that the first player loses if there is no coins at the beginning because he/she cannot remove the last coin.

    bool isWin(vector<int> coins){

        return (accumulate(coins.begin(), coins.end(), 0, bit_xor<int>())==0);

    }

http://letuskode.blogspot.com/2014/08/grundy-numbers.html

Consider a simple game which two players can play. There are N coins in a pile. In each turn, a player can choose to remove one or two coins. The players keep alternating turns and whoever removes the last coin from the table wins.

Suppose that N were 1 or 2. The first player could just remove all coins and win straightaway. If N were 3, whatever the first player did, the second player would end up getting 1 or 2 coins and win in their move. If N were 4 or 5, the first player could remove the required number of coins to make the second player receive 3 coins and lose. Continuing in this fashion, we find that the first player is guaranteed a win unless N is a multiple of 3. The winning strategy is to just remove coins to make N a multiple of 3.

what if I make a simple modification to the problem? The game now starts with K piles of coins. Initially there are N1,N2…NK coins in the piles. Each player is allowed to remove one or two coins from a single pile in their turn. Once again, the player who makes the last move of removing the last coin from the last existing pile wins the game. Is there a strategy now?

Not so easy anymore right? However, it turns out that there is a strategy in this case as well. However, to find it and to deal with more general games, let us try to identify the salient features of the above games.

• The games are sequential. The players take turns one after the other, and there is no passing
• The games are impartial. Given a state of the game, the set of available moves does not depend on whether you are player 1 or player 2.
• Both players have perfect information about the game. There is no secrecy involved
• The games are guaranteed to end in a finite number of moves.
• In the end, the player unable to make a move loses. There are no draws. (This is known as a normal game. If on the other hand the last player to move loses, it is called a misère game)

Let’s call the  games satisfying these properties as solvable games. For such games, there is a theory to find the winning strategy. This involves the Sprague–Grundy theorem, which reduces every such game to a game of Nim.

So first, let us analyse the game of Nim. In this game, there are K piles of coins containing N1,N2…NK coins. In a turn, a player chooses a pile and removes any number of coins from it. Once again, the player who manages to remove the last coin from the last remaining pile wins.

It turns out that the first player loses Nim iff xor(N1,N2…NK)=0. The winning strategy is thus to ensure that the set of piles passed on to the opponent has xor=0. This seems an extremely strange result, so we will derive it here to convince you.

The current state of the game in Nim can be uniquely specified by the ordered K-tuplet of remaining coins in each pile : (n1,n2…nK). Out of all such K-tuplets, some states are winning states - that is, if the current player receives that state, they will win if they play optimally. The remaining states are losing states - whatever the player does, the other player can manage to win. If we can identify the winning and losing states in Nim, we can find a strategy to play the game as well. The best way to do this is to identify a property P such that:

• The eventual losing states (the ones from which no further move can be made) satisfies P. In Nim, there is only one eventual losing state - when all piles become empty.
• From a state that satisfies P, it is impossible to move to another state that satisfies P
• From any state that does not satisfy P, it is possible to move to some state that satisfies P.

Then it is easy to see that a state is a losing state iff it satisfies P.

In Nim, the supposed losing states are exactly those with xor(n1,n2…nK)=0. Does this satisfy the three criteria?

• The eventual losing state has n1=n2=…nK=0. Hence xor(n1,n2…nK)=0 ⇒ The eventual losing state is a P state
• Suppose that xor(n1,n2…nK)=0. If we remove some coins from pile 1 to reduce the number of coins to n1'. The the new result is xor(n1',n2…nK)=xor(n1,n2…nK) ⊕ n1 ⊕ n1' = n1 ⊕ n1' ≠ 0. That is, it is not possible to move from a P state to another P state.
• Proving the third criterion is slightly tougher. Let s=xor(n1,n2…nK). Consider the leading bit of s. There should be some ni with this bit set in it. WALOG, let it be n1. Let n1' = s⊕n1. It is easy to see that n1'<n1. xor(n1’,n2…nK)=xor(n1,n2…nK) ⊕ n1 ⊕ n1' = s ⊕ n1 ⊕ s ⊕ n1 = 0. Thus reducing n1 to n1' allows us to move to a P state.

With Nim thus solved fully, we can move on to the general case of solvable games. Sprague-Grundy theorem reduces the state of every such game to a single Nim pile of a certain size. This pile size is called thenimber/Grundy number of the state. The theorem then essentially states that the state of a game is a winning/losing position iff the corresponding Nim pile is a winning/losing state. The power of the theorem is that it makes a game composed of a collection of independently played solvable games solvable as well. That is, suppose that the game is made up of subgames such that each player  can choose to make a move in exactly one of the subgames at each step. A simple example would be K independent piles of Nim. A game composed of K solvable subgames with Grundy numbers G1, G2 … GK is winnable iff the Nim game composed of Nim piles with sizes G1, G2… GK is winnable.

To apply the theorem on arbitrary solvable games, we need to find the Grundy number associated with each game state. This is how it is done:

• The final losing position corresponds to the empty Nim pile and has Grundy number 0.
• Suppose that we have calculated the Grundy numbers of all states we can move to from the state currently under consideration. Then the Grundy number of the current state is the smallest whole number which is not the Grundy number of any state that can be reached in the next step (This is in direct analogy with what happens in Nim. If a Nim pile has n coins, we can remove coins to get 0,1…n-1 coins in the next step. The lowest number not reachable is n, thus a single Nim pile with n coins is equivalent to current state). Mathematically, if s1, s2 … sk are the game states directly reachable from s, 
  
  

  Grundy(s) = min({0, 1, …} - {Gundy(s1), Grundy(s2) … Grundy(sk)})

  
  The smallest non-negative integer which is not present in a set S is denoted by mex{S}.

• The Grundy numbers for each state can thus be enumerated recursively and the losing states are exactly those with Grundy number equal to 0.

To see how this works, let us apply it in the original game where we have a pile of coins and can remove one or two at a time. 0 coins corresponds to a Grundy number of 0. If we have 1 coin, the only state we can reach is 0 and thus the corresponding Grundy number is 1. With 2 coins, we can reach 0 and 1 - thus the Grundy number is 2. The difference comes once we move to 3 coins. Now we can only reach 1 and 2 coins - with their Grundy numbers 1 and 2 as well - and hence the Grundy number of this state is 0. In general, we can see that the state with n coins has Grundy number n mod 3, and hence the losing states are exactly those cases which have n as a multiple of 3.

The power of the Sprague-Grundy theorem comes when we have multiple subgames to choose from. In the game of Nim, we can choose which pile to play. The winnability is decided by the xor of Nim pile sizes. In the same way, in any game where you have multiple independent subgames to play, the winnability is decided by the xor of the Grundy numbers of the current states of the subgames.

This is the resolution of the modified 1-2 coin removal problem with multiple piles. Suppose that we have K piles initially with coins N1,N2…NK and we are playing 1-2 coin removal game with them.

We just found that the Grundy number for each pile is given by Ni mod 3. Sprague-Grundy theorem tells us that the state of piles is a losing state iff the xor of the Grundy numbers is 0. That is, iff (N1 mod 3) ⊕ (N2 mod 3) … (NK mod 3) = 0. Thus (3,4,5) is a winning state whereas (3,4,4) is a losing state.

So that’s the theory. Problems about impartial games and Grundy numbers appear often in programming contests. We will now have a look at a few such problems and how to utilise the theory to solve them.

Problem 1 : Matrix Game

The first thing we realise looking at the constraints is that anything like doing a DP on the states of all cells/rows in the matrix is simply not going to work. But then, the game on each row is independent of the game on other rows. Thus we can consider each row as a subgame, and this really looks like a problem where Sprague-Grundy theorem could be useful. So the question is, how do we assign a Grundy number to each row?

The empty row is a losing state since no further move can be made on it. Thus it has Grundy number 0. What if there is only one element in the row? Then reducing it is equivalent to removing coins from a Nim pile, and its Grundy number is just the value of the element. Now suppose there are two elements in the row (al,ar). If al=1, the only move we can make is reduce it and get to ar. Thus the Grundy number of (1,ar) is 0. Continuing along this, the Grundy number of (al,ar) can be found to be al-1. But there is a catch. If al=ar+1, the Grundy number has to be alinstead of al-1 since the Grundy number of (0, ar), which is reachable from (al, ar), is ar=al-1. Thus the Grundy number for (al,ar) = al-1 if al≤ar and al otherwise.

Now, notice that we have used only the Grundy number of ar in this description and not the value of the element directly. This means that we can keep adding elements to the left following the same procedure. Let G(i) be the Grundy number calculated for the rightmost i elements in the row and  ai be the ith element from the right. Then G(i+1)=ai+1-1 if ai+1≤G(i) and ai+1 otherwise.

Having calculated the Grundy number for each row in this fashion, the first player loses iff the xor of all the Grundy numbers is 0.

Problem 2 : A String Game

In this problem, every time we remove a word from the string, the string gets divided into two substrings. Now, the further moves on these substrings are independent and can be thought of as separate subgames - thus the Grundy number of the substring pair is just the xor of the Grundy numbers of the individual substrings.

We can thus calculate the Grundy numbers by dynamic programming. Let f(i,j) be the Grundy number corresponding to the substring S[i…j]. The set of Grundy numbers of all states reachable from the current string is given by Sreachable={f(i,k-1)⊕f(l+1,j)} for all S[k…l] which are substrings of S[i…j] and valid words at the same time. Then f(i,j)=mex(Sreachable). The base case for the DP is that Grundy number for an empty string is 0.

Tracy wins iff the Grundy number for the entire string is zero.

Practice Problems

• WPLAY
• G3

Read full article from LIKE CODING: MJ [19] Who wins ||-- The Game of Nim