0

## The Secrets of Nim (Wrap-up)

Published on Sunday, August 08, 2010 in , , , , , , ,

()

I hope you've enjoyed The Secrets of Nim series. I'm going to wrap it up today, with a brief, yet possibly surprising, look back at Nim.

For most of history, the various versions of multi-pile Nim were played as a regular game, as opposed to a swindle. It was known that if you got to certain positions in some select games that you could win from that point on, but nobody knew whether it was possible to guarantee a win from the start.

That all changed in 1901, when Charles L. Bouton of Harvard University discovered the approaches to multi-pile nim that were detailed in part 2 and part 3 of this series.

Just over three decades later, R. P. Sprague and P. M. Grundy, working independently, both discovered that larger numbers of objects in Nim (among other games) could be made easier to handle by reducing them to smaller ones via certain functions. A good introduction to the Sprague–Grundy theorem, as well as variations of Nim, is available via this PDF from the UCLA Math Department.

If you really want to see where analysis of Nim can take you, including a mind-boggling array of variations, I highly recommend checking out Winning Ways, for Your Mathematical Plays, Volume 1, Volume 2, Volume 3, and Volume 4, by Elwyn R. Berlekamp, John Horton Conway, and Richard K. Guy.

Naturally, once it was proven that you could win Nim from the beginning, and safe moves could be determined throughout, it quickly became a favorite of swindlers. Equipment began to show up to make the game portable and easy to play. The Gambler's Beads were an interesting version of single pile Nim, but multi-pile versions were also developed.

Even while the earliest computers were being developed, compters such as Nimatron were being displayed at the 1940 New York World's Fair. The Nimrod computer, a vastly improved version of Nimatron, was displayed at the 1951 Festival of Britain.

This effectively makes Nim among the first, if not THE first, computer games!

Thanks to the simplicity of Nim, it can also be played against mechanical computers, instead of just electronic ones. In 1961, a single-pile Misère game called Dr. Nim was released. Check out the impressive operation of this simple plastic machine in the video below:

In one of his Scientific American columns, Martin Gardner discussed Hexapawn (PDF), and how you can play against a simple set of matchboxes and stones that learn to improve their play via a system of punishments and rewards (More on this in my Computing . . . Without Computers! post).

On the last page of that same column, there's mention of a Bell Labs research director who used a similar approach to build a matchbox learning machine for Nim! Impressively, the machine required only 18 matchboxes, could go first or second in different games, and yet would play almost perfectly after only around 30 games. I think if I lost a game of Nim to a set of matchboxes and stones, I'd feel dumber than a box of rocks.

When the first pocket calculators were released in the 1970s, Nim was adapted to those just as quickly as it had been with the first electronic computers. I wouldn't be surprised to learn that someone tried getting several pocket calculators together and use them to play some form of multi-pile Nim.

It's not hard to find Flash versions today, but there are a few that really stand out. Pearls Before Swine goes for the whole experience, and constantly challenges you with more and larger piles, while keeping track of your wins and losses.

Ricardo Rix's version of Nim (multi-pile Misère Nim) lets you choose the level of your opponent's play, as well as how many piles will be involved, so you can develop your skill and analytical abilities at your own pace.

1961 must've been a great year for Nim. Not only was the aforementioned Dr. Nim released, but it was also featured in a French art film that year, called Last Year in Marienbad, where it makes 3 appearances. At that link, you can see 2 of them via an embedded Flash or downloadable iPod video. The 3rd can be seen on YouTube:

As a matter of fact, to this day, many people refer to multi-pile Misère Nim played with 1, 3, 5, and 7 objects as Marienbad Nim, or simply Marienbad. You can try a Javascript version here, and try a Flash version here.

If you're geeky enough to analyze and enjoy Nim, as well as being geeky enough to enjoy XKCD, you'll probably get a good laugh from this Spiked Math cartoon, which pays tribute to both.

I'd like to hear your comments and criticisms, especially concerning The Secrets of Nim posts, in the comments below!