Nimand Hackenbush

—"William Shakespeare, Corporal Nym in The Merry Wives of Windsor

In recent decades a great deal of significant theoretical work has been done on a type of two-person game that so far has no agreed-on name. Sometimes these games are called "nim-like games," "take-away games" or "disjunctive games." All begin with a finite set of elements that can be almost anything: counters, pebbles, empty cells of a board, lines on a graph, and so on. Players alternately remove a positive number of these elements in accordance with the game's rules. Since the elements diminish in number with each move, the game must eventually end. None of the moves is dictated by chance; there is "complete information" in that each player knows what his opponent does. Usually the last player to move wins.

The game must also be "impartial." This means that permissible moves depend solely on the pattern of elements prior to the move and not on who plays or on what the preceding moves were. A game in which each player has his own subset of the elements is not impartial. Chess, for example, is partial because a player is not allowed to move an opponent's piece. It follows from the above conditions that every pattern of elements is a certain win for either the first or the second player if the game is played rationally. A pattern is called "safe" (or some equivalent term) if the person who plays next is the loser and "unsafe" if the person who plays next is the winner. Every unsafe pattern can be made safe by at least one move, and every safe pattern becomes unsafe through any move. Otherwise it is easy to prove the contradictory result that both players could force a win. The winner's strategy is playing so that every unsafe position left by the loser becomes a safe one.

The best-known example of such a game is nim. The word was coined by the Harvard mathematician Charles L. Bouton when he published the first analysis of the game in 1901. He did not explain why he chose the name, so we can only guess at its origin. Did he have in mind the German nimm (the imperative of nehmen, "to take") or the archaic English "nim" ("take"), which became a slang word for "steal"? A letter to The New Scientist pointed out that John Gay's Beggar's Opera of 1727 speaks of a snuffbox "nimm'd by Filch," and that Shakespeare probably had "nim" in mind when he named one of Falstaffs thieving attendants Corporal Nym. Others have noticed that nim becomes win when it is inverted.

Nim begins with any number of piles (or rows) of objects with an arbitrary number in each pile. A move consists in taking away as many objects as one wishes, but only from one pile. At least one object must be taken, and it is permissible to take the entire pile. The player who takes the last object wins. Bou-ton's method of determining whether a nim position is safe or unsafe is to express the pile numbers in binary notation, then add them without carrying. If and only if each column adds to an even number (zero is even) is the pattern safe. An equivalent but much easier way to identify the pattern (with practice one can do it in one's head) is to express each pile number as a sum of distinct powers of 2, eliminate all pairs of like powers and add the powers that remain. The final sum is the nim sum of the pattern. In current parlance this is called the "Grundy number" or "Sprague-Grundy" number of the pattern, after Roland Sprague and P. M. Grundy, who independently worked out a general theory of take-away games based on assigning (by techniques that vary with different games) single numbers to each state of the game.

For example, assume that a game of nim begins with three piles of three, five and seven counters.

Pairs of 4's, 2's and l's are crossed out as shown. The sum of what remains is 1. This is the nim sum of the pattern. If and only if the nim sum is zero is the pattern safe, otherwise it is unsafe (as it is here). If you play an unsafe pattern, you win by changing it to safe. Here removing one counter from any pile will lower the nim sum to zero. In three-pile nim, with no pile exceeding seven counters, the safe nim patterns are 0—n—n, where n in the first triplet is any digit from 1 through 7, and 1-2-3, 1-4-5, 1-6-7, 2-4-6, 2-5-7, 3-4-7, 3-5-6. If your opponent plays next, he is sure to leave a pattern with a nonzero nim sum that you can lower to zero again, thereby maintaining your winning strategy.

Like all games of this type, nim has its misere form, in which the player who takes the last piece is the loser. In many takeaway games the strategy of misere play is enormously complicated, but in nim only a trivial modification is required at the end of the play. The winner need only play a normal strategy until it is possible to leave an odd number of single-counter piles. This forces his opponent to take the last counter.

Many take-away games seem to demand a strategy different from that of nim but actually do not. Suppose the rules of nim allow a player (if he wishes) to take from a pile, then divide the remaining counters of that pile into two separate piles. (If the counters are in rows, this is the same as taking contiguous counters from inside a row and regarding those that remain as being two distinct rows.) One might expect this maneuver to complicate the strategy, but it has no effect whatever. To win, compute the nim sum of a position in the usual way and, if it is unsafe, play a standard move to make it safe. For example, in the 3—5—7 game suppose your first move is taking a counter from the three-pile, leaving the safe 2-5—7. Your opponent removes two counters from the seven-pile and splits the remaining five counters into a two-pile and a three-pile. The pattern is now 2—5—2—3. Its nim sum is six, which you make safe by taking two from the five-pile.

A pleasant counter-moving game on a chessboard is shown in Figure 83. No fewer than two columns may be used. In this example we use all eight columns. Black and white counters are placed on arbitrary squares in each column, black on one side, white on the other. (A randomizing device, such as a die, can be used for the placement.) Players sit on opposite sides and alternate moves. A move consists in advancing one of your counters any desired number of empty cells in its column. It may not leap its opposing counter, so that when two counters meet, neither may move again. The last player to move wins.

An astute reader may see at once that this game is no more than a thinly disguised nim. The "piles" are the empty cells between each pair of opposing counters. In the illustration, the piles are 5-1-4-2-0-3-6-3, which has an unsafe nim sum of

A nim game on a chessboard

4. The first player can win by moving the counter in column one, three or seven forward four spaces. If the game had begun with all the counters in each player's first row, the pattern would have been 6—6—6—6—6—6—6—6, a safe position because its nim sum is zero. The first player must lose. The second player groups the columns into four pairs, then duplicates each of his opponent's moves in the paired column, a strategy that ensures a zero nim sum after every move.

Suppose we complicate the rules by allowing either player to move backward as well as forward. Such a retreat is equivalent, of course, to adding counters to a nim pile. How does this affect the winning strategy?

A better-disguised game based on nim addition is a delightful pencil-and-paper game recently invented by John Horton Conway, the University of Cambridge mathematician who invented "Life," the topic of three of this book's chapters. Conway calls the new game Hackenbush, but it has also been called Graph and Chopper, Lizzie Borden's Nim and other names.

The initial pattern is a set of disconnected graphs, such as the Hackenbush Homestead as drawn by Conway [see Figure 84]. An "edge" is any line joining two "nodes" (spots) or one node to itself. In the latter case the edge is a "loop" (for example, each apple on the tree). Between two nodes there can be multiple edges (for example, the light bulb). Every graph stands on a base line that is not part of the graph. Nodes on the base line, which is shown as a broken line in the illustrations, are called "base nodes."

Two players alternate in removing any single edge. Gravity now enters the game because taking an edge also removes any portion of the graph that is no longer connected to the base line. For instance, removing edge A eliminates both the spider hfcH

0 0