Apr 142012
 

As mentioned in my previous post, here I will give several example of impartial game which turn out to be exactly equivalent to Nim Game.

Nimble
Given a line of squares labeled 0, 1, 2, …. Several coins are placed on some squares (it’s possible to have more than one coin on a single square). Two players take turns. One move consists of taking any one coin and moving it to any square to the left of it. It’s possible that the coin moved into a square already containing coins.

solution
This game is exactly a Nim Game where one coin in kth square is a pile of k stones. Moving a coin from kth square to its left is equivalent to removing stones from a pile of k stones in Nim Game.

Poker Nim
This game is played as a standard Nim Game, but players have option to either substracting stones (like in standard Nim Game) or adding more stones in a pile but not exceeding the original number of stones in that pile. To ensure the game termination, each player is allowed to add stones at most k (a finite number of) times.

solution
If you already have a winning position in standard Nim Game, then when your opponent adds some stones to a pile, all you have to do is reverse your opponent’s move by removing the exact number of stones he/she added to that pile, thus restoring your winning position. Hence, this kind of game can be viewed as standard Nim Game.

Actually the “not exceeding the original number of stones in that pile” part is not neccesary in this game, one can have the same winning strategy despite of the number of stones added by the opponent.

This type of Nim Game where player can add stones is called Bogus Nim.

Turning Turtles
Given a horizontal line of N coins with some coins showing heads and some tails. Each turn, a player have to flip one coin from head to tail, and in the same time (if he/she wants), flip one more coin to the left of it.

For example, consider this sequence of N = 10 coins:

1 2 3 4 5 6 7 8 9 10
T H T T H H T T T H

Possible moves from this position are:

  • Flip one coin from head to tail. Eg., coin in position 6 from head to tail.
  • Flip one coin from head to tail and flip another coin (from tail to head) to the left of it. Eg., coin in position 6 from head to tail and flip coin in position 3 from tail to head.
  • Flip one coin from head to tail and flip another coin (from head to tail) to the left of it. Eg., coin in position 6 from head to tail and flip coin in position 2 from head to tail.
solution
This game is equivalent to Nim Game with each coin showing head in kth position equals to a pile of k stones.

  • Flip one coin of position k from head to tail. This move is equivalent with removing all stones from a pile with k stones.
  • Flip one coin of position k from head to tail and flip another coin (from tail to head) to the left of it in position t. This move is equivalent with removing some stones from a pile with k stones leaving t stones in that pile.
  • Flip one coin of position k from head to tail and flip another coin (from head to tail) to the left of it in position t. This move is equivalent with removing some stones from a pile with k stones leaving t stones in that pile. Note that having two piles with a same number of stones is the same as having none of both piles, since if you already have a winning position and your opponent make a move on one of those identic piles, you can always reverse his/her move by moving on the other pile (remember xx = 0).

Silver Dollar Game (without silver dollar)
This game is played on a line of squares labeled 0, 1, 2, … with several coins are placed in some square such that no two coins are placed in a same square. One move consists of moving one coin to its left onto any empty square and not passing any other coin. The game ends when a player cannot make any legal moves, since all the coins are jammed at the left-end of the strip.

For example, given these 4 coins in position {2, 5, 7, 10}:

1 2 3 4 5 6 7 8 9 10 11
0 1 0 0 1 0 1 0 0  0  1

Possible moves from this position is:

  • Move coin in position 11 to position 10, 9 or 8.
  • Move coin in position 7 to position 6.
  • Move coin in position 5 to position 4 or 3.
  • Move coin in position 2 to position 1.
solution
The solution to this problem is a bit tricky.

We can think spaces between coins as pile. For example, if we have coins in position {2, 5, 7, 11}, then the gaps between coins are {1, 2, 1, 3}. Then moving a coin from position 7 to 6, is like removing one stone in 3rd pile. But then, that same move also increase the size of 4th pile by one stone. In other word, any stones removed from a pile will increase the size of its immediate right pile by the same size, except for the right most pile. This decomposition is not good, because the subgames are not independent (moving one pile could increase another pile). We should think another way to make this work.

The problem in above decomposition was with adjacent piles, so we can try to skip every second piles. In fact, this is the solution to this problem. From right most pile, skip every second piles, and take the remaining piles as piles in standard Nim Game. For example, coins in position {2, 5, 7, 11} will have piles {1, 2, 1, 3} and if we remove all second piles from the right most, we’ll get {2, 3}.

In the example above, coins in position 2 and 5 correspond to one pile of 2 stones, while coins in position 7 and 11 correspond to one pile of 3 stones.

  • Moving coin in position 2 is equivalent with adding more stones to the respective pile (of 2 stones).
  • Moving coin in position 5 is equivalent with reducing stones from the respective pile (of 2 stones).
  • Moving coin in position 7 is equivalent with adding more stones to the respective pile (of 3 stones).
  • Moving coin in position 11 is equivalent with reducing stones from the respective pile (of 3 stones).
1 2 3 4 5 6 7 8 9 10 11
0 1 * * 1 0 1 * *  *  1

Each * character represent the stone in each pile. So, this decomposition gives us a Bogus Nim (review the solution to Poker Nim), which can be viewed as a standard Nim Game.

But why from “right most pile”? If we remove every second stone from left most pile, we’ll leave the right most coin without any corresponding pile, which is bad, because it’s like allowing player to not make any move.

  5 Responses to “Nim Game Example”

  1. Hi there, just saw your blog and ranking on hackerrank. Would you consider discussing a job with us? It would be a work from home job.

  2. Awesome post! I was trying to solve POJ 1704 Georgia and Bob, and found this article. Learned new stuffs about Game Theory. Thanks.

  3. Thanks , very useful.

  4. Awesome stuff!
    In the last example, you can also add a bogus pile with 0 coins initially on the right and then reverse the order of piles {0, 3, 1, 2, 1}. Now this is exactly similar to the first example.

  5. Thanks for the post!

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)