Estrategia óptima para 2 jugadores Variación del juego Lights Out

Considere un juego basado en turnos para 2 jugadores. Ambos están jugando en el mismo tablero. El tablero es de 8x8, generado aleatoriamente y cada celda tiene 0 o 1 (con probabilidades iguales), por ejemplo:

01101100
01010101
10111100
00001111
10101010
00000001
11100011
00101000

En turno 1 jugador 1 mueve, en turno 2 jugador 2 mueve, en turno 3 jugador 1 mueve y así sucesivamente.

Mover consiste en elegir las coordenadas (x, y) donde 1se encuentra. Voltea los elementos en las posiciones (x, y), (x+1, y) y (x, y+1), si están dentro de los límites del tablero. Por volteretas me refiero a vueltas 1hacia 0o 0hacia 1.

(0, 0) es la esquina superior izquierda. Entonces, después de jugar en (1, 1) el tablero se ve así:

01101100
00110101
11111100
00001111
10101010
00000001
11100011
00101000

Y después de jugar en (7, 1) así:

01101100
00110100
11111101
00001111
10101010
00000001
11100011
00101000

Ganas cuando después de tu jugada solo quedan 0a bordo.

Mi pregunta es: ¿cuál es la estrategia óptima para este juego?

Investigación hasta ahora:

Vale la pena leer la descripción de Lights Out en MathWorld .

El juego presentado es una variación de Lights Out, pero en lugar de voltear 4 celdas vecinas, volteamos solo 2 y podemos movernos solo en celdas con 1. También es similar a Nim .

De la misma manera que describe MathWorld, podemos encontrar S - un conjunto mínimo de movimientos para ganar. Para tableros de 8x8 siempre habrá exactamente una solución.

Dado que la suma de matrices es conmutativa, el orden en que se realizan los movimientos es irrelevante.

Si | S | (número mínimo de movimientos para ganar) es extraño: es una posición ganadora. Por ejemplo, si es 1, hacemos un solo movimiento y ganamos.

Si es 3, hacemos un movimiento desde S y el oponente obtiene un tablero con 2 movimientos en S . Ahora, si hace el movimiento de S , perderá, porque tendremos la jugada final. Entonces, si tiene una opción, no hará un movimiento de S .

Al probar algunos ejemplos, descubro que el oponente no se mueve desde S aumenta nuestro S por 1 movimiento - exactamente el movimiento que hizo. Entonces, recuperamos el tablero con 3 (diferentes) movimientos en S . Pero, él no puede detenernos así para siempre - finalmente todos sus movimientos posibles estarán en S .

Entonces, mi hipótesis es: cuando no haces un movimiento de S , | S | aumentará exactamente en 1 y su movimiento de "destrucción" se agregará al conjunto (para que luego podamos "deshacer" su movimiento de "destrucción").

Lo que significaría que el oponente solo puede hacer -1 (jugando un movimiento desde S ) o +1 (al no jugar un movimiento desde S ), por lo que no puede cambiar la paridad de nuestro | S | !

Entonces, si todo lo anterior es cierto, significa que los jugadores no tienen influencia en el resultado del juego. Incluso podríamos jugar al azar y si la inicial | S | fue impar - ganaremos, si fue par - perderemos.

Es difícil para mí creer en eso. ¿ Cuál será el sentido de hacer un desafío de IA en HackerRank con un juego así? Los jugadores en la tabla de clasificación tienen puntajes diferentes y estos puntajes son consistentes cada vez después del recálculo (las mismas personas en el top 10), lo que sugiere que los jugadores realmente tienen una influencia en el resultado del juego.

¿Tal vez puedas ver algún error que estoy cometiendo?

No has demostrado que el juego termina. Puede ser que el jugador que perdería pueda mantenerlo indefinidamente. De lo contrario, es un juego de información perfecta determinista, por lo que se aplica el concepto de posiciones N (ext) y P (anterior).
@RossMillikan Dibujé los 16 estados (con 32 bordes) para el juego 2x2 y no hay ciclos (puedo publicarlo si ayuda). Espero que esto sea suficiente para decir que el juego siempre termina. También tengo la fuerte sensación de que siempre termina, porque 1siempre van en la dirección correcta, no pueden regresar. Y no puedo crear un ejemplo de bucle. No estoy seguro de conocer el concepto que mencionaste, ¿quizás tengas un enlace para que pueda leer sobre él? Gracias.
No me había dado cuenta de que los otros dos cuadrados invertidos no estaban alineados. Sí, puede argumentar que los 1 tienen que barrer el tablero y el juego debe terminar. El teorema básico aquí es el teorema de Sprague-Grundy , que dice que en un juego imparcial finito sin empates, cada posición es ganada por el jugador anterior o por el jugador siguiente. Una posición N es aquella que puede moverse al menos a una posición P. La posición AP es aquella que solo puede moverse a N posiciones.
@RossMillikan Este es el gráfico completo del juego para 2x2. Sí, ese teorema definitivamente se cumple aquí, los estados dibujados en rectángulos en mi imagen son los estados ganadores. El número sobre el estado es el número mínimo de movimientos para ganar. Las flechas apuntan desde 1donde nos movemos al siguiente estado. Sin embargo, todavía no veo la estrategia óptima. Y expandir el árbol completo desde el tablero de 8x8 es demasiado grande, incluso para la computadora (2 ^ 64, alrededor de 10 ^ 19 estados).
No, no conozco la estrategia óptima. Básicamente, está demostrando que existe, siguiendo la idea de Sprague-Grundy. El teorema no proporciona una forma de encontrar la estrategia. A menudo, comienza con posiciones simples, las divide en P y N, encuentra un patrón y prueba que el patrón se mantiene. En este caso, todos los 0 son P, un solo 1 en la parte inferior derecha es N, 0 en la parte inferior derecha y 1 en una de las dos celdas vecinas es P, y así sucesivamente.
Creo que para cada cuadrado, la paridad del número de veces que puedes hacer un movimiento en él solo depende del estado del tablero hacia arriba/a la izquierda y no de los movimientos que hagas, por lo que la paridad del número total de posibles movimientos no depende de los movimientos que se juegan. Entonces, en un juego con 2 jugadores, ninguno de los jugadores tiene influencia sobre quién gana.

Respuestas (2)

Colorea recursivamente el tablero en blanco y negro, de modo que para cualquier movimiento legal, haya un número impar de cuadrados negros que se voltean.

En su caso, la coloración se verá como un patrón serpinski invertido desplazado en diagonal:tablero de colores

Luego considere la paridad del número de 1 s en cuadrados negros. En cada movimiento, inviertes un número impar de cuadrados negros, por lo que la paridad cambia sin importar lo que hagan los jugadores. El número de 1 s en cuadrados negros aumenta en 1 o disminuye en 1 o 3 .

En tu ejemplo, hay 17 1 s en cuadrados negros, por lo que el jugador 1 siempre verá un número impar de 1 s en cuadrados negros. 0 no es impar por lo que siempre habrá al menos uno 1 en un cuadrado negro. Es imposible que reciba un tablero vacío, por lo que no puede perder: está obligado a ganar.

No sé qué está haciendo su sitio web. Si algunos algoritmos ganan más que otros, las reglas son diferentes (nunca dice lo que sucede en los bordes del tablero) o tiene una forma injusta de generar tableros aleatorios. Además, no sé qué hace cuando vuelve a calcular las puntuaciones. Tal vez esto sea solo un experimento para alimentar resultados aleatorios a un marcador de elo.

Lo siento, no entiendo la primera oración: ¿cómo debo colorear el tablero? ¿Podría proporcionar un ejemplo simple en un tablero de 3x3 o una imagen?
Agregué una imagen.

tomemos un tablero simple de 1x3

101

Esta es una pérdida para el jugador 1.

Pero la pérdida es más rápida si se elige primero la celda de la izquierda.

Dado que hay un límite de movimientos, la jugada perdedora puede exprimir un empate deteniéndose tanto como sea posible.

El jugador ganador, cuando sea posible, necesita hacer un movimiento que no se pueda deshacer.

Probemos con un tablero simple donde el jugador 1 gana.

1011

el jugador 1 puede sacar al derecho 2, lo que obliga al juego a 5 movimientos. el jugador 1 puede tomar a la izquierda para

0111

el jugador 2 no puede tomar izquierda o derecha, lo que le permite al jugador 1 ganar en el movimiento 3.

en cambio, el jugador 2 tomará el centro, lo que recrea la misma situación que si el jugador 1 hubiera comenzado con la derecha.

Así que ahora tenemos la estrategia.

  1. resolver el tablero lo más rápido posible. haciendo los movimientos requeridos que no se pueden deshacer, trabajando desde la esquina superior izquierda hacia la esquina inferior derecha. Cuente el número de movimientos que tomó. Esto es muy facil. Simplemente barra desde la parte superior izquierda a la parte inferior derecha, haciendo clic en cada 1. Esto revelará todos los movimientos requeridos actualmente, y siempre es una solución óptima.

  2. Si es impar, usted es el ganador. Trate de encontrar un movimiento que no se pueda etiquetar de nuevo (siempre hay al menos uno) que no se superponga con las celdas requeridas, pero que se superponga con tantas celdas no requeridas que sean 1 como sea posible, para negárselas a su oponente en su doblar. Digamos que está comenzando en un tablero completo de 3x3. la esquina superior izquierda es el movimiento ideal porque elimina permanentemente la esquina 1 y elimina dos movimientos no necesarios junto a él para que el oponente no pueda seleccionarlos. Prefiera apagados permanentes de celdas no requeridas, pero elija siempre uno que no pueda volver a encenderse. Por lo tanto, nunca alargarás directamente el juego.

  3. si PAR, eres un perdedor, y debes evitar esos movimientos requeridos si puedes. en su lugar, elija un movimiento NO requerido que desactive 2 movimientos requeridos si es posible, y si no, desactive uno 1. Si solo las celdas requeridas están disponibles actualmente, intente elegir la que está más cerca de la parte inferior derecha. Si está comenzando con el tablero de 3x3 con la celda inferior derecha ya ocupada, elegir una de las dos no requeridas al lado del inicio es un buen movimiento, porque etiqueta dos celdas requeridas, pero no es un movimiento requerido en sí mismo. el movimiento superior izquierdo aún es obligatorio y etiquetará la celda que eligió nuevamente, convirtiéndola en una nueva celda requerida. Con suerte, si sigues haciendo esto, extenderás el juego más allá de la marca de 100 movimientos y salvarás un empate. También puede tener la oportunidad de forzar clics adicionales en las celdas requeridas. llévatelas si las encuentras.

Y aquí vamos. :)

si estuvieras jugando solo, el orden no importaría para los movimientos requeridos. pero como estás compitiendo, lo importante que debes hacer es eliminar permanentemente tantas oportunidades para que el oponente extienda el juego como puedas.

Estrategia óptima para 2 jugadores Variación del juego Lights Out
RespuestasAquíPolítica de privacidad1y, 0v