## Nim

`Feb 4, 2004`

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

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... ⇒ |