hackendot

Hackendot

Josef Ùlehla [1] attributes the invention of the game Hackendot to John von Neumann. JP Mayberry christened it based upon its similarity to Conway's Hackenbush.

Figure 1
Ready for a game of Hackendot.

Hackendot is played on a collection (ie forest) of rooted trees. Figure 1 shows one possible such tree, with its root r at the bottom. (The black and white node coloring in Figure 1 should be ignored for the moment).

A move in Hackendot is to select a node v from one tree in the forest, and to delete the node v and all nodes on the (unique) path leading from a to its tree root r, along with all edges adjoining that path. If v itself is a root node, only v and its adjoining edges—if any—are deleted.

The player causing the deletion of the final node wins.

A strategy stealing argument credited to Von Neumann shows that the first player wins on a single tree, but doesn't provide a constructive strategy or any indication of who wins in a forest:

(Strategy Stealing in Hackendot): Suppose that the second player to move did have a forced win on some single non-empty tree. Consider the first player's move to be the deletion of the root node only. Then whatever the second player's winning node deletion reply x may be, the first player could have stolen this strategy by instead himself deleting the node x as his first move.

A complete analysis of Hackendot forest outcome classes involves the computation of a nim heap equivalent for each component tree.

To illustrate Ùlehla's method for computing such nim heap equivalents, consider Hackendot restricted to simple paths, such as represented in the Figure 2, below (where the colors on nodes should still be ignored).

Simple paths in Hackendot are disguised Nim heaps. Figure 2 is a *5.

Figure 2
Coloring a simple path in Hackendot.
Now color all leaf nodes of a general Hackendot position white, and inductively color a nonleaf node black if and only if it has at a least one white follower in the direction leading away from the root. The colorings in Figures 1, 2, 3 and 4 were all obtained in this manner.

If we were to imagine that we are not playing Hackendot at all on the tree, but rather a game involving sliding a coin down the tree from node to node, one edge at a time in the direction of the terminal leaves, then Ùlehla's white vertices would correspond to its P (Previous player) winning nodes, and the black vertices to its N nodes (Next player) winning nodes.

Of course, this coin-sliding game is not the same as Hackendot. It merely illustrates the coloring rule.

The surprising thing about Ùlehla's result is that this seemingly unrelated coloring plays a central role in the analysis of Hackendot.

We need one more definition.

Ùlehla contracts a Hackendot tree T by forming a new tree L(T) on the black nodes of T only. The edges of L(T) preserve all the original black-black edges of T. Each black-white-black adjacency pair in T is replaced by a black-black edge.

Recoloring a newly contracted tree using the same coloring rule as before, it is then ready to be contracted again to form L(L(T)), etc.

Figures 3 and 4 and illustrate successive contractions of the trees in Figures 1 and 2, respectively.

Figure 3
Contracting Figure 1 twice.

Figure 4
Contracting Figure 2 twice.

The nim heap equivalent of the leftmost Hackendot path in Figure 2 is *5. In fact, for any simple path we can "read off" the binary representation of its nim heap equivalent by noting which of its successive contractions has its root colored white—the initial path T will have a white root if and only if the number of nodes in the path is odd (the 2⁰ bit), and the first contraction L(T) will have a white root if and only if the 2¹ bit is set, and so on. Of course for a simple path, this nim heap equivalent is also equal to the number of original nodes in the path.

We prefer the contraction method, however. Why? Because Ùlehla proves that the same method applies to trees not just simple paths as well!

So Figure 3 shows that Figure 1 is a *7 nim heap equivalent (all three root bits are "on", and 7 = 2⁰+ 2¹ + 2²).

Both Ùlehlas reduction and the Von Neumann strategy-stealing argument end up with a focus on the root of the tree. Do other strategy-stealing arguments conceal similar reductive nim heap calculation techniques?

References

[1] Josef Ùlehla, A complete analysis of Von Neumann's Hackendot, International Journal of Game Theory, Vol 9, Issue 2, pages 107-113.