Xl

The Hackenbush Homestead and the window since both would fall to the ground, but removing the edge joining the spider to the window removes only the spider. Taking edge B chops down the entire apple tree. If one edge of the streetlight's base is taken, the structure still stands, but taking the second edge on a later move topples the entire structure. The person who takes the picture's last edge is the winner.

As in nim, every picture is either safe (second-player win) or unsafe (first-player win), and the winner's strategy is to convert every unsafe pattern to safe. To evaluate a picture each graph must be assigned a number measuring the graph's "weight." To arrive at the assignment the first step is to collapse all the "cycles" (closed circuits of two or more edges) to loops, turning the graph into what Conway calls an apple tree, although in many cases the loops are best regarded as being flower petals. To see how it works, consider Conway's girl [see Figure 85]. She incorporates two cycles: her head and her skirt. First the two nodes of her head are brought together and then the two edges are bent into loops. Do the same with the five nodes and five edges of the skirt. The girl is now a flower girl [middle figure], The next step is to change her to an ordinary tree by replacing each loop with a single branch [figure at right].

We now calculate this tree's weight. First, label 1 all edges with a terminal node (a node unconnected to another edge) or, to put it differently, all edges that, if removed, cause no other edges to fall off the tree. Label 2 all edges that support only

Girl on one foot

one edge. Each remaining edge is labeled with one more than the nim sum of all the edges it immediately supports. Consider the edge corresponding to the girl's hair between her head and her hair ribbon. It immediately supports 1—1—1. A pair of l's cancel, giving a nim sum of 1. Add 1 to the nim sum and this edge has a weight of 2. The edge that forms the body above the skirt immediately supports edges of values 2—1—2—1—2. The nim sum is 2. Add 1 and the edge has a weight of 3.

The girl's unraised thigh supports 3-1-1-3-1-1-1, a nim sum of 1, to which 1 is added to give the thigh a value of 2. The calf below it has a value of 3, the foot a value of 4. (In each case we simply add 1 to the value of the single, immediately supported edge.) Since the foot is the only support of the entire graph, the girl has a weight of 4. All edge values are now transferred to corresponding edges on the original girl.

With practice, edge values can be computed directly on the original graph, but it requires great care. For example, the girl's five skirt edges, raised thigh, and body are all "immediately" supported by her unraised thigh. This is clear in the tree graph but is not so obvious in the original graph because many of the immediately supported edges are not close to the thigh.

If a graph has more than one base node, such as the door, barrel and lamp in the Homestead, collapse the base cycle into loops, remembering that the broken line segment between a pair of base nodes is not part of the graph. The door's transformations are shown in Figure 87b. Since the nim sum of 1—1—1 is 1, the door's weight is 1. A girl standing on both feet [see Figure 86] has a weight of 3. Note how the two cycles formed by her skirt and legs collapse into seven loops. A winning move, for a game played with her alone, is taking the top of her head or one of her hairs. This lowers the value of her chapter 14

WEIGHT = 3

Girl on both feet head to zero, her body to 1 and her weight to zero. In this manner a weight can be assigned to each of the five graphs that make up the Hackenbush Homestead: The apple tree, house (including window, spider, chimney, television antenna and drainpipe), door, barrel and streetlight.

If Hackenbush is played with only the girl on one foot, the game is as trivial as playing nim with only one pile. The first player can win at once by taking the supporting foot. The poor girl collapses and he acquires all her edges. In the case of a figure with more than one base node, such as the door, we must remember to take an edge so that the remaining nim sum is zero. A first player can do this only by taking the door's top edge, leaving two graphs of weight 1 each, or a combined nim sum of zero. Taking either side leaves only one graph (of weight 2), which can be taken entirely by the second player.

A picture consisting of n graphs, such as the five graphs of the Homestead, is treated exactly like five piles in nim. The nim sum of all the weights is the total Grundy number. If and only if this number is zero is the picture safe and the second player assured of winning. As in nim, the winning strategy is to play so that the nim sum of what remains is always zero.

The reader is invited to determine the weight of each graph in the Hackenbush Homestead and verify that the Homestead's nim sum is 10. Since this is not zero, the first player can win. It turns out (of course Conway designed it that way) that there is only one edge the first player can take that will guarantee a win by lowering the nim sum to zero. Which edge is it?

My account of hackenbush is only a brief introduction to this game. For a fantastic amount of additional information about the game, its deep theorems and its numerous variations, see

Conway's On Numbers and Games, and the two volumes of Winning Ways by Berlekamp, Conway, and Guy. Both works also contain an abundance of material on other nim-like games and the theory behind them in both standard and misère play.

The first problem was to explain how the winning strategy in a chessboard version of nim is affected by allowing players to move their counters backward. The answer: It has almost no effect. If the loser retreats, the winner merely advances his opposing counter until the number of spaces separating the two men is the same as before. This preserves the status quo, leaving the basic strategy unaltered. The winner never retreats and, since the chessboard is finite, the loser's retreats must eventually cease. This variation of the game has been attributed to D. G. Northcott and is known as Northcott's nim.

How the various parts (graphs) of John Horton Conway's Hackenbush Homestead are transformed, as explained, into apple trees, then trees and labeled is shown in Figures 87, 88. The graphs have weights of 15-1-1-4-1, therefore the Homestead's nim sum is 10. The only way the first player can reduce this Grundy number to zero is by lowering the apple tree's weight to 5. "The tree trunk supports two branches of 8 and 6," Conway writes, "and these must be changed to 2 and 6, or

0 0

Post a comment