nim

This game is ripe for winning drinks at bars and parties. You play against a computer removing balls from 4 rows. The rows have 3, 4, 5, and 6 balls in them. When it is your turn you can take any number balls away from a single row. Then it is the computers turn. The player who takes the last ball is the loser. The reason it is fun is that it seems impossible to beat the guy. Go ahead and try. If you don't make all the right moves it is impossible. The computer makes no mistakes in strategy and this is a game where once someone has the upper hand they technically cannot lose it.

The generic name of the game is nim. There can be any number of rows or number of balls within a row. Of course Wikipedia has some information on the game including how to beat the game. However the explanation is quite cryptic since it deals with binary numbers and "nim-summing" rather than heuristics. Here's a more straight forward explanation on how to beat it with a few heuristics.

The first thing you need is a list of the binary numbers for all the possible numbers of balls in the rows:

1 ball = 001
2 balls = 010
3 balls = 011
4 balls = 100
5 balls = 101
6 balls = 110

Now treat these binary numbers as base 10 numbers. For example, 5 balls = "one-hundred and one" rather than true binary numbers.

When it is your turn add up the numbers that remain. At the start of the game this (011 + 100 + 101 + 110) = 322.

The first heuristic is to always remove balls so that the remaining number only contains "2"s and "0"s. No "3"s and no "1"s.

This is a little harder than it seems at first. You need to look at all 4 numbers at the beginning to figure out how to do this. The obvious first move is to remove all the balls in the 4 ball row. This removes 100 from our sum which leaves us with a sum of (322 - 100) = 222.

Keep doing this until the very 'end'. And when I say 'end', I don't really have a good description of what I mean. The second heuristic is that near the end you need to just use your brain on how to make sure the computer has to take the last ball. If you keep leaving "2"s and "0"s all the way through then you will eventually lose. You need to flip to odd at the 'end'. This is best illustrated as an example,

3 4 5 6 (game start; sum = 322)
3 0 5 6 (I remove the 4 ball row; sum = 222)
1 0 5 6 (computer remove 2 balls from the 3 ball row; sum = 212)
1 0 5 4 (my move leaves 202)
1 0 5 2 (computer leaves 112)
1 0 3 2 (my move leaves 22)
0 0 3 2 (computer leaves 21)

At this point I'm starting to see what the remaining moves are and if I can force an ending to the game. There are still too many permutations left so I keep on strategy.

0 0 2 2 (my move leaves 20)
0 0 2 1 (computer leaves 11)

Now at this point there are very few permutations of moves left. If I stuck to my "2"s and "0"s strategy my next move would be to leave (0 0 1 1). But clearly the computer will take one ball and I'll be stuck with the last losing ball. So at this point I make a different move to end the game.

0 0 0 1 (sum = 1 but the computer is left with last loser ball)

I wish I had a better way to describe when to move off the first heuristic but I don't. For example if you are left with 1 0 0 6 you again would want to go off strategy to leave 1 0 0 0. Play around and you'll get the hang of it.