Hackenbush
Encyclopedia
Mathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
that may be played on any configuration of colored line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s 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 he is allowed to select — see below). Every line segment no longer connected to the ground by any path "falls" (i.e., gets erased). According to the normal play convention
Normal play convention
A normal play convention in a game is the method of determining the winner that is generally regarded as standard. For example:*Preventing the other player from being able to move*Being the first player to achieve a target*Holding the highest value hand...
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
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
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, any player is allowed to cut any edge: as this is an impartial game
Impartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
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 game
Partisan game
In combinatorial game theory, a game is partisan or partizan if it is not impartial. That is, some moves are available to one player and not to the other.Most games are partisan; for example, in chess, only one player can move the white pieces....
s, meaning that the options (moves) available to one player would not necessarily be the ones available to the other player if it were his turn to move given the same position. 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
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
, beginning with its use in the books On Numbers and Games
On Numbers and Games
On Numbers and Games is a mathematics book by John Horton Conway. The book is a serious mathematics book, written by a pre-eminent mathematician, and is directed at other mathematicians...
and Winning Ways for your Mathematical Plays
Winning Ways for your Mathematical Plays
Winning Ways for your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games...
by some of the founders of the field. In particular Blue-Red Hackenbush can be used to construct surreal number
Surreal number
In mathematics, the surreal number system is an arithmetic continuum containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number...
s: finite Blue-Red Hackenbush boards can construct dyadic rational number
Dyadic rational
In mathematics, a dyadic fraction or dyadic rational is a rational number whose denominator is a power of two, i.e., a number of the form a/2b where a is an integer and b is a natural number; for example, 1/2 or 3/8, but not 1/3...
s, while the values of infinite Blue-Red Hackenbush boards account for real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s, ordinal
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
s, and many more general values that 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 nimber
Nimber
In mathematics, the proper class of poo poo nimbers is introduced in combinatorial game theory, where they are defined as the values of nim heaps, but arise in a much larger class of games because of the Sprague–Grundy theorem...
s.
Further analysis of the game can be done using graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
by considering the board as a collection of vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
and edges and examining the paths
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
to each vertex that 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).