Kayles

Usando la notación de juegos octales, Kayles se denota 0.77.

Kayles se juega con una fila de fichas, que representan bolos.

Los dos jugadores se alternan; cada jugador, en su turno, puede quitar cualquier pin (una bola lanzada directamente en ese pin), o dos pins adyacentes (una bola lanzada para golpear a ambos).

Según la convención de juego normal, un jugador pierde cuando no tiene un movimiento legal (es decir, cuando todos los pines se han ido).

El juego también se puede jugar usando las reglas de misère; en este caso, el jugador que no puede moverse gana.

[5]​ El nombre "Kayles" es una anglicización del francés quilles, que significa "bolos".

Esto restringe todos los movimientos futuros a una sección u otra.

En un juego normal, Kayles se puede resolver en tiempo polinomial utilizando la teoría de Sprague-Grundy.

(Alternativamente, este juego puede verse como dos jugadores que encuentran juntos un conjunto independiente).

Schaefer (1978)[7]​ emostró que decidir el resultado de este juego es PSPACE-completo.