Kayles

---

title: "Kayles" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["combinatorial-game-theory", "mathematical-games"] description: "Mathematical game" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Kayles" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Mathematical game ::

::callout[type=note] the combinatorial game ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/2/2e/Bowling_ball_and_pins_for_strike_-_front_view.jpg" caption="A row of bowling pins. On their turn, a player may choose to eliminate a single pin, or two adjacent ones."] ::

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.

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

History

Kayles was invented by Henry Dudeney. Richard Guy and Cedric Smith were first to completely analyze the normal-play version, using Sprague-Grundy theory. 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 pins".

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 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 n. This is often denoted K_n; it is a nimber, not a number. By the Sprague–Grundy theorem, K_n is the mex over all possible moves of the nim-sum of the nim-values of the two resulting sections. For example,

: K_5 = \mbox{mex}{K_0 + K_4, K_1 + K_3, K_2 + K_2, K_0 + K_3, K_1 + K_2},,

because from a row of length 5, one can move to the positions

: K_0 + K_4,\quad K_1 + K_3,\quad K_2 + K_2,\quad K_0 + K_3,\text{ and } K_1 + K_2.,

Recursive calculation of values (starting with K_0 = 0) gives the results summarized in the following table. To find the value of K_n on the table, write n as 12a + b, and look at row a, column b:

::data[format=table title="Kayles nim-values through K_{83}"]

K_n	0	1	2	3	4	5	6	7	8	9	10	11	0+	12+	24+	36+	48+	60+	72+
0	1	2	3	1	4	3	2	1	4	2	6
4	1	2	7	1	4	3	2	1	4	6	7
4	1	2	8	5	4	7	2	1	8	6	7
4	1	2	3	1	4	7	2	1	8	2	7
4	1	2	8	1	4	7	2	1	4	2	7
4	1	2	8	1	4	7	2	1	8	6	7
4	1	2	8	1	4	7	2	1	8	2	7
::

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, 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 Sprague-Grundy theory.

Generalizations

In the generalization of Kayles to graphs, 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 of the normal variant (the last to play wins) 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).

Similarly, in the clique-forming game, two players must find a clique in the graph. In the normal variant (the last to play wins), Schaefer proved in 1978 that deciding the outcome of these games is PSPACE-complete (the same holds for the partisan versions, in which, for every vertex, only one of the players is allowed to choose it as the knock down target). The misère variants of these game were proved PSPACE-complete in 2024 and the optimization variants in 2025 .

References

References

1. Dudeney, H. E.. (2002). "The Canterbury puzzles". Dover.
2. Conway, John H. ''On Numbers and Games.'' Academic Press, 1976.
3. R. K. Guy and C. A. B. Smith, The ''G''-values of various games, Proc. Cambridge Philos. Soc., 52 (1956) 514–526.
4. T.E. Plambeck, [http://www.plambeck.org/oldhtml/mathematics/games/misere/MISEREPA.PDF Daisies, Kayles and the Sibert-Conway decomposition in misere octal games] {{Webarchive. link. (2010-07-14 , Theoret. Comput. Sci (Math Games) (1992) 96 361–388.)
5. Plambeck, Thane. "Kayles".
6. [[E. Berlekamp]], [[J. H. Conway]], R. Guy. ''[[Winning Ways for your Mathematical Plays]].'' Academic Press, 1982.
7. (2002). "Kayles and Nimbers". Journal of Algorithms.
8. (2015). "Exact algorithms for Kayles". Theoretical Computer Science.
9. (1978). "On the complexity of some two-person perfect-information games". Journal of Computer and System Sciences.
10. (2024). "The general position avoidance game and hardness of general position games". Theoretical Computer Science.
11. (2025). "The Convex Set Forming Game". Theoretical Computer Science.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::