Kayles is a simple
impartial game in
combinatorial game theory
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 player ...
, invented by
Henry Dudeney
Henry Ernest Dudeney (10 April 1857 – 23 April 1930) was an English author and mathematician who specialised in logic puzzles and mathematical games. He is known as one of the country's foremost creators of mathematical puzzles.
Early life
...
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 The octal games are a class of two-player games that involve removing tokens (game pieces or stones) from heaps of tokens.
They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games. Revised and repr ...
, Kayles is denoted 0.77.
Rules
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 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 va ...
, a player loses when he or she has 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''.
History
Kayles was invented by
Henry Dudeney
Henry Ernest Dudeney (10 April 1857 – 23 April 1930) was an English author and mathematician who specialised in logic puzzles and mathematical games. He is known as one of the country's foremost creators of mathematical puzzles.
Early life
...
.
[Conway, John H. ''On Numbers and Games.'' Academic Press, 1976.] Richard Guy and
Cedric Smith were first to completely analyze the normal-play version, using
Sprague-Grundy theory.
[R. K. Guy and C. A. B. Smith, The ''G''-values of various games, Proc. Cambridge Philos. Soc., 52 (1956) 514–526.][T.E. Plambeck]
Daisies, Kayles and the Sibert-Conway decomposition in misere octal games
, Theoret. Comput. Sci (Math Games) (1992) 96 361–388. The
misère version was analyzed by
William Sibert in 1973, but he did not publish his work until 1989.
The name "Kayles" is an Anglicization of the French ''
quilles'', meaning "bowling".
Analysis
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 his or her 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
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 ' ...
, not a
number
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers c ...
. By the
Sprague–Grundy theorem
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 ...
,
is the
mex over all possible moves of the
nim-sum
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 ' ...
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:
At this point, the nim-value sequence becomes periodic
with period 12, so all further rows of the table are identical to the last row.
Applications
Because certain positions in
Dots and Boxes reduce to Kayles positions,
[ E. Berlekamp, ]J. H. Conway
John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...
, R. Guy. '' Winning Ways for your Mathematical Plays.'' Academic Press, 1982. it is helpful to understand Kayles in order to analyze a generic Dots and Boxes position.
Computational complexity
Under normal play, Kayles can be solved
in polynomial time using the Sprague-Grundy theory.
''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). Analogously, in the ''clique-forming'' game, two players must find a
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
in the graph. The last to play wins. Schaefer (1978)
[{{cite journal, last1=Schaefer, first1=Thomas J., title=On the complexity of some two-person perfect-information games, journal=Journal of Computer and System Sciences, date=1978, volume=16, issue=2, pages=185–225, doi=10.1016/0022-0000(78)90045-4, doi-access=free] proved that deciding the outcome of these games is
PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...
. 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.
See also
*
Combinatorial game theory
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 ...
*
Octal games The octal games are a class of two-player games that involve removing tokens (game pieces or stones) from heaps of tokens.
They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games. Revised and repr ...
*
Dawson's Kayles
*
Nimber
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 ' ...
References
Combinatorial game theory
Mathematical games