G13GAM -- Game Theory
[This is a copy of http://www.maths.nottingham.ac.uk/personal/anw/G13GAM/hack.html]
Impartial Hackenbush can be completely solved by the three results:
Every non-empty picture can be evaluated using these principles:
the fusion principle allows us to get rid of all loops, leaving a
picture which is a collection of [mathematical this time, but hence
biological!] trees which can be evaluated inductively from
the tree principle.
Of course, with experience, much of this process can be short-cut.
- [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
[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.
The Colon Principle
In the figure, let us suppose that H and I,
viewed as pictures in their own right, have equal value, and that
they are joined to the rest of their components, G, only
at the `articulation point' marked by the red dot.
[The colours in this and other figures here are purely decorative
and to draw attention to parts of the picture;
they are not meant to indicate that parts `belong' to one or other player.]
Then the two components, which we can write as G:H and G:I,
also have the same value.
[More generally, if H>=I, then G:H>=G:I.
Impartial pictures are always either zero or fuzzy (first-player wins),
so this generalisation is unimportant here.]
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.]
Since H-I = 0, to every move in either H or -I there is
a winning reply in H-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 in G has a symmetric counter in -G
and 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.
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 of H will perforce be a nimber,
so the component I might just as well be a `snake', a simple chain
of n edges, n>=0, value *n,
of the appropriate length.
In the particular case where G is just a single edge, this shows
that G:H is equivalent to a snake of length n+1, which is
the tree principle.
The Fusion Principle
Suppose we call a picture good if the FP applies to it, and
bad if it doesn't -- that is, if the picture includes a loop
whose fusion would change its value.
Suppose bad pictures exist.
Then there must be simplest possible bad pictures, meaning with as
few edges as possible, and among those with the same number of edges
one with the fewest possible nodes [counting the ground as one node].
Choose such a simplest bad picture, G.
We conclude the proof by showing that such a G is in fact good,
contrary to supposition.
Note that any move in G either makes a simpler bridge, which is
good by supposition [and can be evaluated by the fusion principle], or
[by removing a span of the bridge] makes two trees, whose value we can
So this is now a technical problem of evaluating a fairly specific picture,
which you can take on trust, or see the next section.
- 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
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;
- 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
- 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.]
Bridges are good!
If we fuse a bridge, then we turn each span of the bridge into a blade
of grass, and each snake becomes attached instead to the ground.
The blades of grass cancel in pairs. so the FP tells us that
the value of a bridge is the value of its snakes, together with
a blade of grass if the number of spans is odd.
So we need to show that a picture typified by this one has value zero,
i.e. is a first-player loss.
Clearly any move in any snake loses;
the other player can make the same move in the corresponding snake,
to give a simpler bridge, which must be good [or we can use induction].
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 *(2n+1) and the chopped snake from the bridge worth *(2n),
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
2a + 1 @ 2b + 1 @ 2c + 1 @ 2d + 1 @ ...
[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, 2b, ... are the snake heights working out from
the chopped edge.
But now if you look at the way the odds and evens go, the first, third,
fifth, ... `+ 1' have the same effect as `@ 1', which means that they
commute with the next `@ 2b', and the sum is the same as
2a @ 2b + 2 @ 2c @ 2d + 2 @ ...
Now, everything in this is even, so the result is twice the result of
a @ b + 1 @ c @ d + 1 @ ...
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, i.e. chops it to zero,
and therefore the corresponding move in the original bridge also chops
to [twice] zero.
That concludes the proof.
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
The way to proceed is a generalisation of the above `black-white' idea;
for `how to do it', see Winning Ways, p189.
None of the above is examinable!
top of page
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.