I created a demo for the mathematical game of Nim. The demo is here. (Also known by many other names, I learned it as Pearls Before Swine) The game of Nim is played with several piles or stacks of various sizes. (What the piles are actually of is unimportant) Players take turns removing any number from a single pile. The winner is the player who takes the last turn, leaving all piles empty at the end of their turn.


What makes Nim interesting, is not that it is a particularly exciting game (or even all that fun, really) is that there is a mathematical trick to winning the game. Before reading on, I would advise that you try the game, and watch as the computer repeatedly beats you (unless you know the trick or get repeatedly lucky).


Once you're done (or if you've ignored me)...



----------------------------------
The trick
--------------------------------

The trick to the game of Nim is the bitwise XOR operation. For a basic look at binary numbers and XOR: Bit Flags.

(The XOR symbol is ^ in DM)

Every turn, your goal should be to leave a total XOR (if you have piles A, B, and C, then the total XOR is A ^ B ^ C) of 0. Calculating the total XOR is actually very easy to do by hand. To get the XOR total, simply convert them to binary in a column and in each column, if there are an odd number of '1's put a 1 otherwise a 0. (Another way to think of it is adding in binary without carrying any digits over) Say, for example, we have piles of A B and C with 3, 5, and 8 respectively:

3   0011
5   0101
8   1000
--------
    1110

In this case the XOR total is 14. Now, with a little intuition, (and some time) you may see that the correct move to reduce the XOR total to 0000 is to remove 2 from pile C, leaving:

3   0011
5   0101
6   0110
----------
    0000

Now, no matter what the opponent does on their next turn, it's impossible for them to leave a XOR total of 0, thus if a single wrong move is played against the computer (or any player playing a perfect game) the player is "locked-out" and can't win.


While simple intuition is usually enough for a player to find the correct next move, it does not work for a computer, and thus there is also a formula for a computer to calculate the correct move.
By once again performing the XOR between the total XOR of all the piles and each individual stack, you get the size of the stack needed to have an XOR of 0.
To go back to the original example, the XOR total is 14.

3 ^ 14       5 ^ 14       8 ^ 14

 0011         0101         1000
 1110         1110         1110
---------------------------------
 1101 = 13    1011  =11    0110 = 6

If you'll notice, only B decreases, leaving B as the only option for a move (as you cannot add to a pile).


One reason why this game is interesting for programming is that you can create pseudo-AI. It's not really intelligence, but it seems like it.


So, for all of you who learned binary and wondered "What the heck am I ever going to do with this crap?", here's your answer: You can win at a simple game all the time and impress, annoy, or cheat friends. (Not necessarily in that order) With a little practice, you can play the game perfectly without writing anything down. You're welcome.

(For those wondering how to play the game on paper, I usually write out an X for each unit in each pile)