Nim Game

I was introduced to Nim by Martin Gardner's Mathematical Games column in Scientific American, Feb. 1958. It was there I learned the binary parity strategy that allows one to play perfect strategy easily. (Touched on in the Wikipedia article on Nim.)

I got a lot of milage out of Nim. In my first public technical presentation, I taught this to a classroom full of math-interested kids in a school district wide weekend event when I was 15 years old; and for my EE degree I used it as the basis of my semester project in Digital Design Lab. I build a Nim playing system out of NOR gates and flip-flops.

Perfect strategy for Nim is achieved by maintaining a simple invariant (call it even Nim parity) when it is your opponent's turn to move. At each turn, make a move that puts the game back into even Nim parity before your opponents turn. To compute even Nim parity, represent the number of counters/tokens in each pile in binary then xor together these binary values bit-wise.

For example with piles of 3, 5, and 7 tokens, the binary values are 11, 101, and 111, and the xor(011, 101, 111) == 001. This tells us that we have to make a move that changes the right-most bit position only so remove one token from any pile. This leaves the opponent in a position from which any move they make it is possible to respond in a way that puts the game back into even Nim parity. Eventually they lose, but your very last move will depend upon whether you are playing to win by taking the last piece or forcing your opponent to take the last piece.

Martin Gardner's column is, of course, much clearer than my explanation. In particular, he explains the a method of using ones fingers to keep the parity counts so that by just keeping one hand under the table and using the left pinky finger for rightmost (1's) bit position and ring finger for next (2's) bit position, etc. it is possible to play perfect strategy very rapidly.

Lately I've been going through a blog focusing on Combinatorial Game Theory, and right now he's at Dal 2016 highlighting talks about relevant games. I'm not familiar with very many of these perfect information games, but I see he'll often point out Nim variants.

https://combinatorialgametheory.blogspot.com

Kyle also keeps a pretty nice table of combinatorial games (and their properties) updated as new ones come his way:

http://turing.plymouth.edu/~kgb1013/rulesetTable.php

A lot of this is over my head, but I still find it interesting (and play a few games on the list).

I've been meaning to ask him about Hive, because it fits the mold, but isn't present.

Aha! In my 2nd year of college, my discrete mathematics professor tried to teach this to the class. We eventually figured out how to solve which player would win this for small games. Writing a proof of how this could be done was what we actually had to do. While I had figured it out along with other students, I was pretty lost when it came to the proof. Nearly everyone failed that class, including myself. I did, however, learn a lot of important concepts in that class. I never even got around to taking calculus, but the discrete mathematics and it's retake were my favorites of all the math classes I got to take.

I make all my beginning programming students code Nim as an assignment about halfway through the year.

http://programmingbydoing.com/a/nim.html

Growing up we had the Dr. Nim board game that was incredibly too good at playing for having just a few plastic levers.

https://en.wikipedia.org/wiki/Dr._Nim

More about the Nimatron: https://pbgames.wordpress.com/2012/07/08/1940-nimatron/

I learnt about the Nim Game from the movie "Last Year At Marienbad". Really nice movie, give it a try :D