Nim.

A student of Java from Wisconsin in the USA, recently asked me if I had ever heard of the game Nim. I said no, and he directed me to a website which ran a version of the game. The student had been given the game as a Java programming assignment. He asked me if I would help him. I said I would try - first of all I would need to study the game to see how it works. Here is an explanation of the game from the Encyclopaedia Britannica1:

"A game so old that its origin is obscure, Nim lends itself nicely to mathematical analysis. In its generalized form, any number of objects (counters) are divided arbitrarily into several piles. Two people play alternately; each, in turn, selects any one of the piles and removes from it all the objects, or as many as he chooses, but at least one object. The player removing the last object wins. Every combination of the objects may be considered "safe" or "unsafe"; i.e., if the position left by a player after his move assures a win for that player, the position is called safe. Every unsafe position can be made safe by an appropriate move, but every safe position is made unsafe by any move. To determine whether a position is safe or unsafe, the number of objects in each pile may be expressed in binary notation: if each column adds up to zero or an even number, the position is safe. For example, if at some stage of the game, three piles contain 4, 9, and 15 objects, the calculation is:

Since the second column from the right adds up to 1, an odd number, the given combination is unsafe. A skillful player will always move so that every unsafe position left to him is changed to a safe position.

A similar game is played with just two piles; in each draw the player may take objects from either pile or from both piles, but in the latter event he must take the same number from each pile. The player taking the last counter is the winner.

Games such as Nim make considerable demands upon the player's ability to translate decimal numbers into binary numbers and vice versa. Since digital computers operate on the binary system, however, it is possible to program a computer (or build a special machine) that will play a perfect game. Such a machine was invented by E.U. Condon and an associate; their automatic Nimatron was exhibited at the New York World's Fair in 1940 …"

Nim was also used to demonstrate one of the first computers available for commercial use at the 1951 Exhibition in London.

This is how my version of Nimatron works: on the Nimatron window, select who will start the game: you, the Player, or Nim, the computer. Do this by clicking on the appropriate radio button. Enter the number of matches you want to remove in one of the three blank boxes. Then click the button underneath the box you have chosen. When the game is over, you can play another game by pressing the Play again button and a new random selection of matches will be appear in the top row of boxes. If the random selection of matches is a safe selection and Nim is the first player to move, then because an unsafe move always follows a safe combination, and Nim is programmed to search until a safe result is found, then Nim would never stop. To avoid this endless loop, Nim is forced, by default to limit its search to 500 attempts. On the 500th attempt it must accept the result, safe or unsafe. If you see that Nim has reached this limit, this is your opportunity to beat Nim. You can change the limit by altering the value of the "maxNimAttempts" parameter,

You can run Nimatron as a Java application:

java Nimatron d

The d option runs the program in debug mode so you will be able to see how and when Nimatron selects a safe combination. Debug information is displayed in the MDSOS (or other) shell runing the program.

To run Nimatron as an applet:

appletviewer Nimatron.htm

To run the applet in debug mode, use the following parameter:

<INPUT PARAM="debug" VALUE="true">

It can, of course, also be run from a Netscape or Explorer browser:

Run Nimatron.

Download (40Kb) Nimatron source, class, audio and documentation files.

1. Encyclopædia Britannica, 1994-1999.

philip@imageviewer.co.uk more free applets www.imageviewer.co.uk
Last Updated: