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.
Kayles is played with a row of tokens, which represent bowling pins. The row may be of any length. The two players alternate; each player, on his or her turn, may remove either any one pin (a ball bowled directly at that pin), or two adjacent pins (a ball bowled to strike both). Under the normal play convention, a player loses when they have no legal move (that is, when all the pins are gone). The game can also be played using misère rules; in this case, the player who cannot move wins.
Kayles was invented by Henry Dudeney. [1] [2] Richard Guy and Cedric Smith were first to completely analyze the normal-play version, using Sprague-Grundy theory. [3] [4] The misère version was analyzed by William Sibert in 1973, but he did not publish his work until 1989. [5]
The name "Kayles" is an Anglicization of the French quilles , meaning "bowling pins".
Most players quickly discover that the first player has a guaranteed win in normal Kayles whenever the row length is greater than zero. This win can be achieved using a symmetry strategy. On their first move, the first player should move so that the row is broken into two sections of equal length. This restricts all future moves to one section or the other. Now, the first player merely imitates the second player's moves in the opposite row.
It is more interesting to ask what the nim-value is of a row of length . This is often denoted ; it is a nimber, not a number. By the Sprague–Grundy theorem, is the mex over all possible moves of the nim-sum of the nim-values of the two resulting sections. For example,
because from a row of length 5, one can move to the positions
Recursive calculation of values (starting with ) gives the results summarized in the following table. To find the value of on the table, write as , and look at row a, column b:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0+ | 0 | 1 | 2 | 3 | 1 | 4 | 3 | 2 | 1 | 4 | 2 | 6 |
| 12+ | 4 | 1 | 2 | 7 | 1 | 4 | 3 | 2 | 1 | 4 | 6 | 7 |
| 24+ | 4 | 1 | 2 | 8 | 5 | 4 | 7 | 2 | 1 | 8 | 6 | 7 |
| 36+ | 4 | 1 | 2 | 3 | 1 | 4 | 7 | 2 | 1 | 8 | 2 | 7 |
| 48+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 4 | 2 | 7 |
| 60+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 8 | 6 | 7 |
| 72+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 8 | 2 | 7 |
At this point, the nim-value sequence becomes periodic [5] with period 12, so all further rows of the table are identical to the last row.
Because certain positions in Dots and Boxes reduce to Kayles positions, [6] it is helpful to understand Kayles in order to analyze a generic Dots and Boxes position.
Under normal play, Kayles can be solved in polynomial time using Sprague-Grundy theory. [3]
Node Kayles is a generalization of Kayles to graphs in which each bowl “knocks down” (removes) a desired vertex and all its neighboring vertices. Alternatively, this game can be viewed as two players finding an independent set together. Winner determination is solvable in polynomial time for any family of graphs with bounded asteroidal number (defined as the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component). [7]
Similarly, in the clique-forming game, two players must find a clique in the graph. The last to play wins. Schaefer (1978) [8] proved that deciding the outcome of these games is PSPACE-complete. The same result holds for a partisan version of node Kayles, in which, for every node, only one of the players is allowed to choose that particular node as the knock down target.
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.
Sprouts is an impartial paper-and-pencil game which can be analyzed for its mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s. The setup is even simpler than the popular Dots and Boxes game, but gameplay develops much more artistically and organically.
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.
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 combinatorial game theory, star, written as or , is the value given to the game where both players have only the option of moving to the zero game. Star may also be denoted as the surreal form {0|0}. This game is an unconditional first-player win.
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: { | }.
Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and "eat it", together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.
Hackenbush is a two-player game invented by mathematician John Horton Conway. It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line.
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.
Wythoff's game is a two-player mathematical subtraction game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile must be equal. The game ends when one player removes the last counter or counters, thus winning.
Subtract-a-square is a two-player mathematical subtraction game. It is played by two people with a pile of coins between them. The players take turns removing coins from the pile, always removing a non-zero square number of coins. The game is usually played as a normal play game, which means that the player who removes the last coin wins. It is an impartial game, meaning that the set of moves available from any position does not depend on whose turn it is. Solomon W. Golomb credits the invention of this game to Richard A. Epstein.
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 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.
