Hackenbush

From Wikipedia, the free encyclopedia

Hackenbush girl, introduced in Winning Ways for your mathematical Plays

Hackenbush is a two-player mathematical game which may be played on any configuration of colored line segments connected to one another by their endpoints and to the ground. More precisely, there is a ground (conventionally, but not necessarily, a horizontal line at the bottom of the paper or other playing area) and several line segments such that each line segment is connected to the ground, either directly at an endpoint, or indirectly, via a chain of other segments connected by endpoints. Any number of segments may meet at a point and thus there may be multiple paths to ground.

On his turn, a player "cuts" (erases) a line segment of his choice (from those which he is allowed to select--see below). Every line segment which is no longer connected to the ground by any path "falls" (also gets erased). According to the normal play convention of combinatorial game theory, the first player who is unable to move (because either all segments have been erased, or all those that remain belong to his opponent) loses.

Hackenbush boards can consist of finitely many (in the case of a "finite board") or infinitely many (in the case of an "infinite board") line segments. Note that the existence of an infinite number of line segments does not violate the game theory assumption that the game can be finished in a finite amount of time, provided that there are only finitely many line segments directly "touching" the ground. Even on an infinite board satisfying this condition, it may or may not be possible for the game to continue forever, depending on the layout of the board.

In the original folklore version of Hackenbush, also known as Nim, any player is allowed to cut any edge: as this is an impartial game it is comparatively straightforward to give a complete analysis using the Sprague-Grundy theorem. Thus the versions of Hackenbush of interest in combinatorial game theory are more complex partisan games, meaning that the options (moves) available to one player would not necessarily be the ones available to the other player if he were given the same exact board. This is achieved in one of two ways:

Blue-Red Hackenbush: Each line segment is colored either red or blue. One player (usually the first, or left, player) is only allowed to cut blue line segments, while the other player (usually the second, or right, player) is only allowed to cut red line segments.

Blue-Red-Green Hackenbush: Each line segment is colored either red, blue, or green. The rules are the same as for Blue-Red Hackenbush, with the additional stipulation that green line segments can be cut by either player.

Clearly, Blue-Red Hackenbush is merely a special case of Blue-Red-Green Hackenbush, but it is worth noting separately, as its analysis is often much simpler. This is because Blue-Red Hackenbush is a so-called cold game, which means essentially that it can never be an advantage to have the first move.

Hackenbush has often been used as an example game for demonstrating the definitions and concepts in combinatorial game theory, beginning with its use in the books On Numbers and Games and Winning Ways by some of the founders of the field. In particular Blue-Red Hackenbush can be used to construct surreal numbers: finite Blue-Red Hackenbush boards can construct dyadic rational numbers, while the values of infinite Blue-Red Hackenbush boards account for real numbers, ordinals, and many more general values which are neither. Blue-Red-Green Hackenbush allows for the construction of additional games whose values are not real numbers, such as star and all other nimbers.

Further analysis of the game can be done using graph theory by considering the board as a collection of vertices and edges and examining the paths to each vertex which lies on the ground (which should be considered as a distinguished vertex--it does no harm to identify all the ground points together--rather than as a line on the graph).