Impartial Games

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

Advertisements

Tags: , , , , ,

2 Responses to “Impartial Games”

  1. Ramprasad Says:

    Just one small point. When you mention that the grundy number of G1 union G2 is the XOR of the two grundy numbers, it sounded like this is the definition. But grundy numbers have already been defined as the smallest excluded number amongst the numbers of the children. The Sprague-Grundy theorem asserts that this is the XOR of the grundy numbers of those individual positions. This is what makes computation of grundy numbers of several pile games easy to analyze.

    And a few very nice references for these are this and this.

  2. Code Chef – Solving ASTRGAME using Sprague-Grundy theorem and caching. | dwjohnston Says:

    […] Me, myself and mathematics.  […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: