Maths encyclopedia and lessons  
Search

Mathematics Encyclopedia and Lessons

 
     
 

Lessons

Popular
Subjects

algebra
arithmetic
calculus
equations
geometry
differential equations
trigonometry
number theory
probability theory
more
 

References

applied mathematics
mathematical games
mathematicians
more
 
 

Hackenbush

Hackenbush is a two-player partisan mathematical game that consists of several colored line segments connected to the ground. More precisely, there is a ground (usually, 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 or indirectly, via one or more paths.

On his turn, a player "cuts" (erases) a line segment of his choice (from those which he is allowed to select--see below for more details). Every line segment which is no longer attached to the ground by any path "falls" (also gets erased). As usual, the first player who is unable to move 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, given that there are only finitely many line segments directly "touching" the ground.

Hackenbush is a partisan game, 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. In common practice, there are two versions of the game:

  • 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.

Hackenbush is fundamental to the study of combinatorial game theory and, indeed, is often one of the very first games taught to students in this field (see Combinatorial game theory (pedagogy)).

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 a property of the vertex, rather than an actual line on which the points are drawn).

Finally, Hackenbush is directly related to the study of surreal numbers. Finite Blue-Red Hackenbush boards can construct dyadic rational numbers, while the values of infinite Blue-Red Hackenbush boards account for the entire set of real numbers. Furthermore, Blue-Red-Green Hackenbush allows for the construction of additional values, such as star and all other nimbers.

In the movie A Day at the Races Groucho Marx played a vet called Dr. Hugo Z. Hackenbush.

01-04-2007 01:18:14
The contents of this article are licensed from Wikipedia.org
under the GNU Free Documentation License. How to see transparent copy