Hackenbush is a two-player game invented by mathematician John Horton Conway. [1] It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line.
Hackenbush is a two-player game invented by mathematician John Horton Conway. [1] It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line.
The game starts with the players drawing a "ground" line (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 their turn, a player "cuts" (erases) any line segment of their choice. Every line segment no longer connected to the ground by any path "falls" (i.e., gets erased). According to the normal play convention of combinatorial game theory, 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. 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. On an infinite board, based on the layout of the board the game can continue on forever, assuming there are infinitely many points touching the ground.
In the original folklore version of Hackenbush, 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 it were their turn to move given the same position. This is achieved in one of two ways:
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 for Your Mathematical Plays 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 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 nimbers.
Further analysis of the game can be made using graph theory by considering the board as a collection of vertices and edges and examining the paths 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).
In the impartial version of Hackenbush (the one without player specified colors), it can be thought of using nim heaps by breaking the game up into several cases: vertical, convergent, and divergent. Played exclusively with vertical stacks of line segments, also referred to as bamboo stalks, the game directly becomes Nim and can be directly analyzed as such. Divergent segments, or trees, add an additional wrinkle to the game and require use of the colon principle stating that when branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum. This principle changes the representation of the game to the more basic version of the bamboo stalks. The last possible set of graphs that can be made are convergent ones, also known as arbitrarily rooted graphs. By using the fusion principle, we can state that all vertices on any cycle may be fused together without changing the value of the graph. [2] Therefore, any convergent graph can also be interpreted as a simple bamboo stalk graph. By combining all three types of graphs we can add complexity to the game, without ever changing the nim sum of the game, thereby allowing the game to take the strategies of Nim.
The Colon Principle states that when branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum. Consider a fixed but arbitrary graph, G, and select an arbitrary vertex, x, in G. Let H1 and H2 be arbitrary trees (or graphs) that have the same Sprague-Grundy value. Consider the two graphs G1 = Gx : H1 and G2 = Gx : H2, where Gx : Hi represents the graph constructed by attaching the tree Hi to the vertex x of the graph G. The colon principle states that the two graphs G1 and G2 have the same Sprague-Grundy value. Consider the sum of the two games. The claim that G1 and G2 have the same Sprague-Grundy value is equivalent to the claim that the sum of the two games has Sprague-Grundy value 0. In other words, we are to show that the sum G1 + G2 is a P-position. A player is guaranteed to win if they are the second player to move in G1 + G2. If the first player moves by chopping one of the edges in G in one of the games, then the second player chops the same edge in G in the other game. (Such a pair of moves may delete H1 and H2 from the games, but otherwise H1 and H2 are not disturbed.) If the first player moves by chopping an edge in H1 or H2, then the Sprague-Grundy values of H1 and H2 are no longer equal, so that there exists a move in H1 or H2 that keeps the Sprague-Grundy values the same. In this way you will always have a reply to every move he may make. This means you will make the last move and so win. [3]
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.
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. In other words, the only difference between player 1 and player 2 is that player 1 goes first. The game is played until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser. Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players.
In mathematics, the nimbers, also called Grundy numbers, are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)
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. It was first published in 1982 in two volumes.
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A directed path in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.
In combinatorial game theory, the zero game is the game where neither player has any legal options. Therefore, under the normal play convention, the first player automatically loses, and it is a second-player win. The zero game has a Sprague–Grundy value of zero. The combinatorial notation of the zero game is: { | }.
In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name "mex" is shorthand for "minimum excluded" value.
In the mathematics of combinatorial games, the sum or disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. The sum game finishes when there are no moves left in either of the two parallel games, at which point the last player to move wins. This operation may be extended to disjunctive sums of any number of games, again by playing the games in parallel and moving in exactly one of the games per turn. It is the fundamental operation that is used in the Sprague–Grundy theorem for impartial games and which led to the field of combinatorial game theory for partisan games.
In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.
Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns to knock out either one pin, or two adjacent pins, until all the pins are gone. Using the notation of octal games, Kayles is denoted 0.77.
The octal games are a class of two-player games that involve removing tokens from heaps of tokens. They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games.
Cram is a mathematical game played on a sheet of graph paper. It is the impartial version of Domineering and the only difference in the rules is that players may place their dominoes in either orientation, but it results in a very different game. It has been called by many names, including "plugg" by Geoffrey Mott-Smith, and "dots-and-pairs". Cram was popularized by Martin Gardner in Scientific American.
In the mathematical theory of games, genus theory in impartial games is a theory by which some games played under the misère play convention can be analysed, to predict the outcome class of games.
In combinatorial game theory, and particularly in the theory of impartial games in misère play, an indistinguishability quotient is a commutative monoid that generalizes and localizes the Sprague–Grundy theorem for a specific game's rule set.
In combinatorial game theory, poset games are mathematical games of strategy, generalizing many well-known games such as Nim and Chomp. In such games, two players start with a poset, and take turns choosing one point in the poset, removing it and all points that are greater. The player who is left with no point to choose, loses.
In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can choose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex.
In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins or loses. Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.
