Beating Nim

Warning! Don't read this unless you really want to know how to beat Nim. Because when you've read it (it's a quite easy algorithm), you will probably not be able to play Nim "normally" again (I sure couldn't once I learned).

The game

The Nim playing field consists of three piles of stones, normally each with between one and nine stones. The two players alternate on taking a number of stones away from one of the piles. The player who takes the last stone loses.

The winning algorithm

  1. Write the number of stones in each pile down as a binary number.
  2. Sum the binary numbers up, in decimal. Each summed column will now have one of the numbers 0, 1, 2 or 3.
  3. Remove from any pile a number of stones so that if you recalculate the number above, you will always get even (i.e 0 or 2) numbers in all the columns.
  4. Repeat the algorithm (steps 1-3) until there are now remove stones so that there is exactly one stone left. Your opponent will have to take this stone, and lose.

An example

Suppose the playing field looks like this:

Pile Stones Amount
1 * * * * * 5 = 101
2 * * * 3 = 011
3 * 1 = 001

Summing the binary number of stones up yields 101 + 011 + 001 = 113. To make this a number with all even numbers, removing three stones from pile one is a good idea:

Pile Stones Amount
1 * * 2 = 010
2 * * * 3 = 011
3 * 1 = 001

Summing the binary number of stones up yields 010 + 011 + 001 = 022. Your opponent can not get any winning position from this.

Now, go beat Nim!

This page has been validated to conform to the HTML 4.01 specification. $Date: 2005/11/24 22:05:43 $ | peter@softwolves.pp.se

Back to my webgame page