Nim (1901) — The First Stone-Taking Game to Be Solved, and the Machines That Played It

Introduction — A Game of Taking Stones, and the First to Be Solved

This is a game that received its name in 1901. Several heaps of stones sit in a row. Two players take turns removing any number of stones from any one heap. Whoever takes the last stone wins (a version in which the taker of the last stone loses has also been played for a long time). That is all.

Charles L. Bouton of Harvard University gave the game the name 'Nim' and published a paper, 'Nim, a game with a complete mathematical theory,' in the Annals of Mathematics. As the title says, the winning logic was laid out completely.

I want to place this game at the entrance to the history of puzzles. It is among the first clear cases in which people saw that a two-player game without any luck could be solved to the end by mathematics. This essay follows that logic, and then how electric machines came to play the game.

Heaps of stones on a table (illustration, AI-generated)

Context — Origins in Fog, a Name in 1901

Stone-taking games like Nim are thought to be very old. It has been suggested that the game may come from a Chinese game resembling jiǎn-shízǐ ('picking stones'), but there is no firm evidence, and the origin remains unknown. European records go back to the early sixteenth century.

In 1901 Bouton supplied the name and a complete analysis. The Oxford English Dictionary traces the name to the German 'nimm' ('take'). I have not, however, confirmed in his own words why he chose it.

At that time the game was solved with paper and pencil. There were no electronic computers, only stones on a table and a mind that arranges numbers. This 'solvable by hand' quality is what later made it fit for machines.

A desk where Nim is worked out on paper (illustration, AI-generated)

Mechanics — Written in Binary, Win and Loss Become Visible

The key to winning is the 'nim-sum.' Write each heap's size in binary, add column by column, and discard the carries (exclusive-or, XOR). For example, heaps of 3, 5 and 6 are 011, 101 and 110 in binary. Added column by column they give 000.

If the nim-sum is 0, the player to move loses. If it is not 0, the player to move can win: choose one heap and reduce it so that the nim-sum returns to 0. Whatever the opponent does, the nim-sum stops being 0. Repeat this, and in the end you take the last stone.

In the reversed version (the taker of the last stone loses), most positions are played with the same moves, and only the ending changes. When the heaps are about to be all single stones, the parity of the number of heaps of size one decides it, and that calls for a different way of thinking.

So Nim is a game whose outcome is fixed from the start, even though its rules are simple. 'The one who knows always wins' is a cruel trait for a game. As mathematics, however, it could hardly be more beautiful.

Three heaps matched to binary columns (illustration, AI-generated)

Legacy — A Standard Part of Mathematics, and an Early Game Machine

Nim's logic became a foundation for later theory. In the 1930s R. P. Sprague (1936) and P. M. Grundy (1939), independently, showed that every game with no chance element in which both players have the same moves behaves like a single Nim heap. This is the Sprague–Grundy theorem.

On the machine side, too, Nim appears early. The Nimatron, conceived by Edward Condon in the winter of 1939 and built by Westinghouse engineers Gerald Tawney and Willard Derr, was shown at the 1940 New York World's Fair. It had four rows of seven light bulbs and ran on relays. The patent was granted in September 1940.

The number of people who played varies by source, from 50,000 players to 100,000 games. What the sources share is that the machine won overwhelmingly, and it is reported that it could play only a limited set of patterns. Condon is reported to have said later that he regarded it as a kind of gag.

In 1951 the British firm Ferranti built the Nimrod. John Bennett designed it and Raymond Stuart-Williams built it; it was shown at the Festival of Britain (May 5) and at the Berlin Industrial Show that October. Its accompanying pamphlet argued that a machine able to play a game could also tackle far more complex practical problems.

Some sources say the Nimatron may have influenced the Nimrod, but I have not confirmed any statement to that effect from the designers themselves. I will record only the fact that two machines chose the same game. The reasons are easy to imagine: short rules, a clear winning method, and a board that light bulbs could display.

Rows of bulbs leading to a vacuum tube (illustration, AI-generated)

References

Sources consulted for this article (the bibliographic details of Bouton's paper follow Wikipedia; the paper itself was not checked):

・Wikipedia: Nim

・Wikipedia (Japanese): ニム

・Wikipedia: Sprague–Grundy theorem

・Wikipedia: Nimatron

・The Nimatron of Edward Condon (Brandeis University hosted document)

・Wikipedia: Nimrod (computer)

Closing — What a Solved Game Left Behind

What history shows is that Nim is not a game that 'lost.' Precisely because it was solved, it became a part of theory and a first opponent for machines. A solved game may end as a game, but it lives on as a way of thinking.

Today's puzzles stand on the same question. Can this position be solved? Who wins? How many moves at minimum? We are still answering the question that began on paper in 1901.

Pick up a single stone and think. Facing three heaps, what would you take first?

One stone left on a quiet table (illustration, AI-generated)