Kayles

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.

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

For example, because from a row of length 5, one can move to the positions Recursive calculation of values (starting with

Under normal play, Kayles can be solved in polynomial time using Sprague-Grundy theory.

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.