Impartial Hackenbush can be completely solved by the three results:

- [General theory of impartial games:] The Nim value of a collection of disjoint components is the Nim sum of the separate components.
- [Tree principle:] The Nim value of a tree [in the biological, not the graph theoretic sense!] is one more than the value of the corresponding bush. [Proved in lectures, but in fact a special case of the Colon principle, see below.]
- [Fusion principle:]
If two nodes are joined by two disjoint sets of edges,
then these nodes may be fused,
*i.e.*joined into one node [distorting the edges between them to suit], without affecting the value of the picture. In particular, all the nodes in a loop may be fused. [Proved below.]

Note that this works perfectly well even in general Hackenbush, but we need it here only in the impartial version. In the impartial version, the value ofProof:Play the difference game,G:H-G:I. [For impartial games, equal to their own negatives, the difference game is the same as the disjunctive sum of the games.] SinceH-I = 0, to every move in eitherHor-Ithere is a winning reply inH-I; this same winning reply can be played in response to a move in the colon'ed version, and then we can appeal to induction, as the resulting picture is a simpler one to which the colon principle still applies. Equally a move inGhas a symmetric counter in-Gand vice versa; this move and counter either delete the articulation points and all that sail on them in both components [giving a zero game] or in neither, in which case we can again appeal to induction and the colon principle.

- Fusing any pair of nodes in a loop in
*G*must change the value of*G*, else this makes a simpler bad picture. -
*G*must consist of one single component, for if it has more, then each must be good [else*G*was not the simplest possible], and therefore so must be*G*. - No pair of nodes in
*G*may be connected by*three*different routes [with no edges in common]. Suppose the contrary. Then construct*H*by fusing these nodes; then*H*must be good [as*G*was minimal] and must have a different value from*G*. So*G-H*is non-zero, therefore a first-player win [impartial], and there is a winning move in it. Play the winning move, and then the corresponding move in the other component. As the winning move was to zero, the position is now again non-zero, all components are now simpler than*G*and so good; but the component which was originally*G*still contains a loop connecting these two points, and therefore fusing them will not change the value; contradiction. - Every loop in
*G*must touch the ground. Otherwise, it must be connected to the ground through at least one node. If at only one, then this is an articulation point, and the colon principle allows us to fuse any loops in the component off the ground [which must be good, as it is simpler than*G*]; if at two or more, then these points are connected in three or more ways [twice through the loop, and at least once through the rest of the picture, if necessary through the ground], contrary to the previous result. -
*G*must contain only one cycle. If there are two, then they cannot be disjoint [else*G*has two components], but nor can they be connected, else we fall foul of the `three route' rule because they are also connected at the ground, by the previous result. - So
*G*must be a bridge, somewhat as shown; we could in principle have trees at each articulation point, but the colon principle allows us to replace these by snakes. [It is irrelevant, of course, whether the `heads' are loops or straight, and some of the snakes could have zero length.]

What about moves in the bridge, typified by the greyed-out edge?
These too lose.
Such a move creates two trees.
Recall that to evaluate a tree, we have to Nim-add branches, add one
to go down, Nim-add, add one, *etc.*
As Nim addition is adding without carry, the least-significant [binary]
digit works out the same whether we Nim-add or ordinary-add;
in other words, if we replace all the Nim-adds by ordinary-adds, the parity
of the answer will be the same.
From this, it is easily seen that the parity of the value of the tree
is the same as the parity of its number of edges.
Now, whether we started out with an odd or an even bridge, that bridge
plus its fused version has an even number of edges [each snake occurs
twice, and there is a blade of grass only if the number of spans is odd].
So when we chop a span, we have an odd number of edges;
we have just demolished the last loop, so the whole picture is the
Nim-sum of a collection of trees, and so is an odd nimber, so cannot be zero.
In other words, any move in the bridge creates a picture which is a
win for the other player.

That completes the result in the case where the bridge is even.
When the bridge is odd, as in the picture shown, there is one final
move, to mow the grass.
The resulting picture has an odd number of edges, but it isn't a tree.
Any chop of a bridge span will create trees with, in total, an even
number of edges, but they could possibly all be *2 or *4 or whatever.
Can we move in a snake?
Well, if any snake on the bridge is *odd*, then chop off its head.
The resulting picture is good [as it is simpler than the one
we started with], so its value is lots of snakes that cancel out in pairs,
an odd bridge that fuses to *1, the original odd snake from the ground
worth *(2*n*+1) and the chopped snake from the bridge worth *(2*n*),
total zero, so the chop was a good reply.
So, we are left with the case where they are all even.

We finally have to show that in a bridge with an odd number of spans and a collection of even snakes, plus copies of all the snakes, there is a move to zero. Call the centre span `white', and then label spans alternately black and white out towards the ends of the bridge. It suffices to show that we can win by chopping some white span. Suppose we chop such a span. What is the resulting value of the two trees? Well, each has Nim-value

2[where `@' means Nim addition and lots of parentheses have been omitted, but the expression should be worked out strictly from left to right], where 2a+ 1 @ 2b+ 1 @ 2c+ 1 @ 2d+ 1 @ ...

2Now, everything in this is even, so the result is twice the result ofa@ 2b+ 2 @ 2c@ 2d+ 2 @ ...

But this is what you get if you halve each snake, then close up each black span to a point, Nim-adding the snakes at each end. [Each of the trees has a black span at its end, as we chopped a white span.] The resulting picture is good, and clearly has Nim-value 1, [or game value *1 = *]. [It has lots of snakes that can be paired off, and an odd-span bridge, as there are an odd number of white spans.] So, some move in the reduced bridge wins,a@b+ 1 @c@d+ 1 @ ...

The very astute will have noted a flaw: The win in the reduced bridge might not be by chopping a bridge span, but by chopping a snake. The fusion principle, as applied to the simpler picture, shows that you can in fact chop a bridge span instead, but finding which one is decidedly non-trivial. The way to proceed is a generalisation of the above `black-white' idea; for `how to do it', seeNone of the above is examinable!Winning Ways, p189.

E-mail me. My home page. The University of Nottingham.

Copyright © Dr A. N. Walker, 1997.

This Web page may be freely used for purposes related to the above module or for private study; requests for permission to make other uses should be referred to the author.