Kayles

Kayles es un juego imparcial simple de la teoría de juegos combinatorios , inventado por Henry Dudeney en 1908. Dada una fila de bolos imaginarios, los jugadores se turnan para derribar un bolo o dos bolos adyacentes hasta que no queden bolos. Usando la notación de juegos octales , Kayles se denota como 0.77 .

Kayles se juega con una fila de fichas que representan bolos. La fila puede tener cualquier longitud. Los dos jugadores se turnan; cada jugador, en su turno, puede quitar un bolo (lanzando una bola directamente hacia él) o dos bolos adyacentes (lanzando una bola que los derribe a ambos). Según las reglas normales , un jugador pierde cuando no tiene ningún movimiento válido (es decir, cuando todos los bolos han sido eliminados). El juego también se puede jugar con las reglas de misère ; en este caso, gana el jugador que no puede mover .

Kayles fue inventado por Henry Dudeney . ^{[ 1 ] [ 2 ]} Richard Guy y Cedric Smith fueron los primeros en analizar completamente la versión de juego normal, utilizando la teoría de Sprague-Grundy . ^{[ 3 ] [ 4 ]} La versión misère fue analizada por William Sibert en 1973, pero no publicó su trabajo hasta 1989. ^{[ 5 ]}

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

La mayoría de los jugadores descubren rápidamente que, en el juego de Kayles normal, el primer jugador tiene la victoria asegurada siempre que la longitud de la fila sea mayor que cero. Esta victoria se puede lograr mediante una estrategia de simetría . En su primer movimiento, el primer jugador debe dividir la fila en dos secciones de igual longitud. Esto limita todos los movimientos posteriores a una sección u otra. A partir de ese momento, el primer jugador simplemente imita los movimientos del segundo jugador en la fila opuesta.

Es más interesante preguntar cuál es el valor nim de una fila de longitud${\displaystyle n}$Esto se suele denotar${\displaystyle K_{n}}$; es un nimber , no un número . Por el teorema de Sprague-Grundy ,${\displaystyle K_{n}}$es el mex sobre todos los movimientos posibles de la suma nim de los valores nim de las dos secciones resultantes. Por ejemplo,

${\displaystyle K_{5}={\mbox{mex}}\{K_{0}+K_{4},K_{1}+K_{3},K_{2}+K_{2},K_{0}+K_{3},K_{1}+K_{2}\},\,}$

porque desde una fila de longitud 5, uno puede moverse a las posiciones

${\displaystyle K_{0}+K_{4},\quad K_{1}+K_{3},\quad K_{2}+K_{2},\quad K_{0}+K_{3},{\text{ y }}K_{1}+K_{2}.\,}$

Cálculo recursivo de valores (comenzando con${\displaystyle K_{0}=0}$) proporciona los resultados resumidos en la siguiente tabla. Para hallar el valor de${\displaystyle K_{n}}$sobre la mesa, escribe${\displaystyle n}$como${\displaystyle 12a+b}$y mire la fila a, columna b:

En este punto, la secuencia de valores nim se vuelve periódica ^{[ 5 ]} con un período de 12, por lo que todas las filas siguientes de la tabla son idénticas a la última fila.

Debido a que ciertas posiciones en puntos y cajas se reducen a posiciones de Kayles, ^{[ 6 ]} es útil comprender Kayles para analizar una posición genérica de puntos y cajas.

En condiciones normales de juego, Kayles se puede resolver en tiempo polinomial utilizando la teoría de Sprague-Grundy. ^{[ 3 ]}

En la generalización del problema de Kayles a grafos , cada tazón "derriba" (elimina) un vértice deseado y todos sus vértices vecinos ^{[ 7 ]} , ^{[ 8 ]} . Alternativamente, este juego puede verse como dos jugadores que encuentran juntos un conjunto independiente . La determinación del ganador de la variante normal (el último en jugar gana) se puede resolver en tiempo polinomial para cualquier familia de grafos con número asteroidal acotado (definido como el tamaño del subconjunto más grande de vértices tal que la eliminación del vecindario cerrado de cualquier vértice en el conjunto deja los vértices restantes del conjunto en el mismo componente conexo). ^{[ 8 ]}

De manera similar, en el juego de formación de camarillas , dos jugadores deben encontrar una camarilla en el grafo. En la variante normal (el último en jugar gana), Schaefer ^{[ 9 ]} demostró en 1978 que decidir el resultado de estos juegos es PSPACE-completo (lo mismo se aplica a las versiones partidistas, en las que, para cada vértice, solo uno de los jugadores puede elegirlo como objetivo de derribo). Las variantes de misère de estos juegos fueron demostradas como PSPACE-completas en 2024 ^{[ 10 ]} y las variantes de optimización en 2025 ^{[ 11 ]} .

• Teoría de juegos combinatorios
• Juegos octales
• Kayles de Dawson
• Número