Nim

Feb 4, 2004

Notes on the Nim flash game here: Pearls Before Swine 2

The object of the game is to force your opponent to pick up the last pearl.

From this we can infer that if you can force your opponent to leave you with a setup which allows you to force your opponent to pick up the last pearl, you'll win.

And so on and so on ad nauseum.

Because of this dependance backwards from the final turn, the game of Nim has "safe layouts" from which, if you play an optimal game, you can never lose. If you can reach one of these safe layouts, you can win everytime. I fooled around with that game a little more this morning and there are only three different moves which will get you to a "safe layout" on the first turn. After that, if the computer reaches it first, you can never win.

The three moves all involve removing four pearls, from any of the bottom three rows.

000       000       000       000
0000   =>        or 0000   or 0000
00000     00000     0         00000
000000    000000    000000    00

Any of these moves will keep your opponent on the defensive, and if you continue to play optimally, you have a chance at winning.

The key to winning is using binary code, as strange as that might seem. Simply write out the number of pearls in each row in binary code and line up the digits. Then treating each column separately (no carrying!) add up the ones and if the final number is even consider it a 0 and if odd consider it a 1:

3: 011
4: 100
5: 101
6: 110
   ---
   322 => 100

This final value (100) is called the Nim-Sum.

Knowing when you're in control of the board is hard to determine just by eye in Nim, but easy if you can write out the binary. The player in control of the board is the one who can continually give Nim-Sums of all zeros to their opponent.

Thus to win, just remove pearls from any row so that the Nim-Sum is 000 when you pass the turn to the computer. Near the end of the game, you'll come to an obvious point where going for a Nim-Sum of 000 will give the *computer* the win. By this time, you should be able to spot the pearls you need to remove in order to emerge the victor.

The following is a sample win including Nim-Sums. The computer in your case might play differently:

3: 011         3: 011  Comp: 2
4: 100         4: 100
5: 101  Me: 4  1: 001
6: 110         6: 110
   ---            ---
   100            000


1: 001         1: 001
4: 100         4: 100  Comp: 2
1: 001         1: 001
6: 110  Me: 2  4: 100
   ---            ---
   010            000

1: 001         1: 001
2: 010         2: 010  Comp: 1
1: 001         1: 001
4: 100  Me: 2  2: 010
   ---            ---
   110            000

1: 001  Here's where I change tactics to
1: 001  leave three single pearls, and
1: 001  the comp must take the last one:
2: 010  Me: 2
   ---
   011


1: 001  Comp: 1
1: 001           1: 001  Me: 1
1: 001           1: 001
   ---              ---
   001              000

1: 001  Comp: 1
   ---
   001

And he then goes away to sulk.

Getting there... ⇒

---