Estrategia ganadora para un juego tipo nim (Teoría de Juegos Combinatorios)

Question

Las reglas del juego son las siguientes:

• Hay dos jugadores.
• El juego comienza con N cantidad de piezas de juego colocadas una al lado de la otra en una fila.
• Tomando turnos, cada jugador remueve una pieza de juego.
• Una pieza solo puede ser removida si hay otra pieza inmediatamente a su derecha.
• Un jugador pierde si no puede remover una pieza.

Por ejemplo, si el estado actual del juego es XOOXXX, donde X denota una pieza de juego y O un espacio vacío, solo se pueden remover las piezas en los espacios 4 y 5. Las piezas en los espacios 1 y 6 no tienen otra pieza inmediatamente a su derecha. Si se remueve la pieza en el espacio 5, el estado del juego se convierte en XOOXOX. Ahora no hay piezas removibles, y el jugador cuyo turno es remover una pieza pierde.

No he podido deducir una estrategia óptima para este juego, pero aquí están algunas de las ideas que he tenido (que quizás no sean de interés):

Hay esencialmente dos tipos de movimientos, uno donde se remueve una pieza OXX --> OOX, y uno donde se remueve una pieza y otra queda sin remover XXX --> XOX (la pieza más a la izquierda ya no se puede remover). Dado que el segundo tipo es esencialmente quitar dos piezas del grupo de piezas removibles, pensé que debería ser posible hacer algo con la paridad, por ejemplo, asegurarse siempre de que haya un número impar de piezas removibles, pero no he llegado a ninguna parte con esto.

A medida que avanza el juego, las piezas se dividen en grupos más pequeños y más pequeños de piezas adyacentes, así que otra idea que tuve fue tratar cada grupo como su propio subjuego, pero creo que esto es un callejón sin salida ya que el mismo jugador puede hacer varios movimientos en un grupo si el otro jugador lo deja solo.

También pensé que podría ser posible aplicar algún tipo de lógica de inducción o programación dinámica, pero no soy muy bueno en eso.

¡Cualquier comentario sobre el tema es muy apreciado! :)

Answer 1

No es una respuesta completa, pero algunas notas:

• Bastante directamente, no hay interacción entre segmentos de X; tan pronto como hay un O entre ellos, la presencia de uno ya no afecta ningún movimiento en el otro. Esto significa que solo tenemos que hacer un seguimiento de las longitudes de los segmentos.
• Un poco menos obvio, el único segmento en el que importa la restricción de 'hay una pieza inmediatamente a su derecha' es en el segmento de una sola pieza. Por ejemplo, para un segmento de longitud cuatro, no se nos permite tomar la X más a la derecha y convertirla en un segmento de longitud tres, pero aún podemos tomar la X más a la izquierda con exactamente el mismo resultado, por lo que la restricción no tiene efecto.

Entre estos puntos, obtenemos que el valor de nim $\nu_n$ de una serie de longitud $n$ es $\mathop{mex}_{0\leq i\lt n}(\nu_i\oplus\nu_{n-i-1})$, donde $\mathop{mex}$ denota el valor 'mínimamente excluido', con condiciones iniciales $\nu_0=\nu_1=0$. Ahora, lo más simple sería buscar en Winning Ways for your Mathematical Plays, pero como mi copia está actualmente a 3000 millas de distancia, lo siguiente más simple es empezar a calcular y buscar un patrón. Obtenemos $\{\nu_i: i\geq 0\}$ $=\{0, 0, *1, *2, 0, *1, *2, *3, *1, *2, *3, *4, 0, \ldots\}$, y esto es suficiente para buscar un patrón — es decir, 'hacer trampa' y buscar en OEIS la secuencia. Haciendo esto, llegamos a https://oeis.org/A046695 que tiene más información y referencias.