Kayles
In combinatorial game theory, Kayles is a simple impartial game. In 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 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.
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, 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[1] 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,[2] it is helpful to understand Kayles in order to analyze a generic Dots and Boxes position.
History
Kayles was invented by Henry Dudeney.[3][4] Richard Guy and Cedric Smith were first to completely analyze the normal-play version, using Sprague-Grundy theory.[5][6] The misère version was analyzed by William Sibert in 1973, but he did not publish his work until 1989.[1]
The name "Kayles" is an Anglicization of the French quilles, meaning "bowling."
See also
References
- ↑ 1.0 1.1 Plambeck, Thane. "Kayles." http://www.plambeck.org/oldhtml/mathematics/games/misere/077/index.htm
- ↑ E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays. Academic Press, 1982.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.. Originally published in 1908.
- ↑ Conway, John H. On Numbers and Games. Academic Press, 1976.
- ↑ 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.
