applets.

Nim

← All apps

About Nim

Nim looks like a game of luck or hunches: a few rows of lamps (or matches, or coins), and two players take turns to put out as many lamps as they like, from one row only. Under the usual rule, whoever takes the last lamp wins. But there's a perfect strategy hidden in binary, so simple that a machine of relays or valves could play it, and some of the first game-playing machines did.

PLAY: press a lamp and it goes out with every lamp to its right in that row. Then the machine replies. CLEVER plays the secret perfectly, so you can only beat it by playing perfectly from a position where the player to move can win; EASY picks its moves at random. LAST TAKES LOSES is misère play, where you want your opponent to take the last lamp. With HINTS on, the card says who is winning, but not how. The heaps can be a preset, RANDOM, or your own: up to five rows of 1 to 7. Changing the rule or who goes first in the middle of a game fades the panel until you press NEW GAME. Keys: N new game, H hints, arrow keys move between lamps, Enter takes.

THE SECRET: the same heaps written in binary on a register of green lamps (4s, 2s and 1s), with the nim-sum underneath, and the working for the next good move. STEP plays a game one move at a time: whoever can win plays the secret move, and the other player, who can't, takes a lamp at random. You can also press lamps to play either side yourself. Keys: S step, B back.

THE MACHINES tells the story. OTHER GAMES shows that nim is the key to many other games of taking things.

THE STORY

Games of taking objects from heaps are old and found in many places, but the mathematical theory is from 1901, when Charles L. Bouton of Harvard published "Nim, a game with a complete mathematical theory" in the Annals of Mathematics. He named the game and gave its secret. Where he got the name isn't known for certain; the German nimm, "take", is the usual guess.

At the New York World's Fair in 1940, Westinghouse showed the Nimatron, a nim-playing machine of electric relays designed by the physicist Edward Condon with colleagues. It played tens of thousands of games against visitors and won most of them.

For the Festival of Britain in 1951, the electronics firm Ferranti built Nimrod, designed by John Bennett: an electronic computer, built from valves, that played nim on a panel of lamps against visitors. It was shown at the Festival's Exhibition of Science in South Kensington and then in Berlin. It was built to show what a computer does, using a game anyone could follow, and it is one of the first computers made to play a game.

Roland Sprague in 1935 and Patrick Grundy in 1939, working separately, showed that every game of this kind behaves like a nim heap of some size, which is what the OTHER GAMES tab is about. The 1961 film Last Year at Marienbad made the 1, 3, 5, 7 rows famous; in the film, taking the last one loses.

HOW IT WORKS

Write each heap in binary and add the columns without carrying: a column with an odd number of 1s gives a 1. That's the nim-sum, the same as the exclusive-or of the heap sizes; for 3, 4 and 5 (011, 100, 101) it is 010, which is 2. If the nim-sum is 0, the player to move loses against perfect play: any move changes one heap, so at least one of its binary digits, which makes that column odd. If it isn't 0, there is always a move back to 0: take the leftmost 1 in the nim-sum, find a heap with a 1 in that column, and cut that heap to (heap XOR nim-sum), which is always smaller. The player who keeps handing back a nim-sum of 0 takes the last lamp, because the empty board has a nim-sum of 0 too.

Misère changes one thing. Play exactly as usual until your move would leave no row with more than one lamp. Then, instead, leave an odd number of single lamps, so your opponent is left with the last one.

Sprague-Grundy numbers: give the finished position the number 0; any other position gets the smallest whole number that isn't the number of a position you can move to (the "mex"). A nim heap of n gets n. A position numbered 0 loses for the player to move, and several games played side by side (on each turn, move in one of them) are worth the nim-sum of their numbers.

SIMPLIFICATIONS

The cabinet and the history drawing are impressions made for this page, not copies of the Nimatron or Nimrod; how many rows and lamps those machines used, and how their panels looked, isn't reproduced here. The machine here works out its move in a few lines of code, then waits a moment so you can see its move. When CLEVER can't win, it takes one lamp from the biggest row to make the game last. EASY plays entirely at random. Rows hold at most 7 lamps here so that three binary columns are enough.

FURTHER WATCHING AND READING

NIM · A MACHINE THAT PLAYS
Rule
Machine
First
Hints
Heaps