## Posts Tagged ‘sprague-grundy theorem’

### Impartial Games

November 15, 2010

Well,

Today’s post is outcome of a fruitful discussion and puzzle solving with Ramprasad.

Problem : Given two pile of coins (n,m) – denoting that there are n coins in 1st pile and m coin in the second. In this two player game, a player is allowed to take as many coins as he/she wishes from any one pile. He/she has to take at least one coin. If a player does not have a valid move, he loses. Which player has a winning strategy and what is the winning strategy?

Solution : It turns out that the first player has a winning strategy if $n \neq m$, otherwise the second player has a winning strategy. The strategy is that a player always make the configuration (i,i) and pass it on to the next player. Okay, for two pile this is simple enough. What about 3 piles? Who wins? What is the strategy?

In general, one can ask questions about such impartial games regarding the winning strategy. Grundy numbers and Sprague-Grundy theorem allows one to easily build strategy for wide class of such games.

As we are talking about finite impartial games, the leaves of game tree are assigned grundy number zero ( losing position ). Now for any node in the game tree, assign the smallest non-negative integer which is not equal to the grundy number of any of its child. Hence, in the two pile game, (n,0) configuration has a grundy number n.

So now, for a union game G1+G2 ( one can make a move in either game ), the grundy number of the node ( i , j)  is nothing but XOR of grundy number of i in G1 and the grundy number of j in G2.

For example, in the game of three coin piles with configuration ( 3, 4, 5 ) the XOR is 2 ( 011 XOR 100 XOR 101  = 010 ). Hence, any one getting a configuration with grundy number zero loses if the other player is smart enough :-). So, in a 3 pile game, a player’s job is to always make a move such that the grundy number of the resulting configuration is zero. Assume A XOR B XOR C = X. Now, we need to make a move such that A becomes A XOR X, or B becomes B XOR X or C becomes C XOR X so that the resulting configuration always yields a zero grundy number. Because X is non-zero look at the most significant 1-bit. You can choose A or B or C depending upon which of these have 1-bit in the corresponding position.

Not only this, one can have games like, a player is allowed to take at most 3 coins from 1st pile, upto 5 coins from 2nd pile or upto 8 coins from 3rd pile. It is easy to see that now grundy number of G1, G2, G3 is N mod 4, N mod 6, N mod 9 respectively. And resulting grundy number can be found by XORing these mod-ed numbers 🙂

Pardon for a not so clear and untidy article. I had to compromise a bit to keep the length tolerable :-). Please see corresponding wikipedia links and other relevant material for more details on games.

— Saurabh Joshi