Algoritmo de resolución de juegos (Buttonia, variante de luces apagadas)

Question

Estoy tratando de crear una función de solución para un algoritmo de juego. Básicamente, una función que devuelve verdadero o falso para un juego dado si es solucionable o no.

El juego es Buttonia.com (que todavía no implementa el algoritmo), un tipo de juego de luces apagadas. Básicamente tiene una cuadrícula de botones, cada uno de los cuales, cuando se presiona, cambiará el estado de algunos de sus vecinos. Actualmente genero una configuración de juego aleatoria y luego aplico la heurística en la medida de lo posible. El resto se decide por búsqueda de fuerza bruta.

Mi progreso hasta ahora fue crear un sistema de ecuaciones para modelar el juego. Como cada botón necesita cambiar de estado un número impar de veces para terminar en un estado inactivo, su ecuación sería esta:

button_A = 1 - (button_1 + button_2 + ... + button_X)% 2

Donde button_1 hasta button_X son los estados de los botones con efecto en button_A. Algunos botones pueden resolverse inmediatamente si no dependen de otros. Por lo demás, pruebo una configuración hasta que tengo un conflicto y luego retrocedo.

Actualmente este algoritmo es práctico para configuraciones más pequeñas de juegos. Lo he probado desde juegos 3x3 hasta tamaños de 10x10. Donde 6x6 está cerca de un límite superior para el juego práctico.

Las ecuaciones reducen enormemente el espacio de búsqueda de la fuerza bruta, haciéndolo práctico. Puede haber una forma puramente matemática de resolver el sistema de ecuaciones.

---

Ejemplo de juego 3x3 en ascii (de buttonia.com/?game=2964 ):

||#
-o-
+#|

Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors

Solución, presione estos: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

Ecuaciones para este juego:

Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2

Solución potencial:

Cambiar las funciones matemáticas para evitar la necesidad del módulo nos permite mover los términos del lado izquierdo hacia la derecha, creando la configuración ordenada de la matriz que necesitamos para el método gaussiano. Entonces las dos primeras ecuaciones se convertirían respectivamente a:

-1 = -1*B00 +  0*B10 +  0*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22
-1 =  0*B00 + -1*B10 + -1*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22

Solución discutida aquí: Eliminación gaussiana con operadores personalizados

Acercarse. Casi listo para publicar la solución completa: Inversión de redes binarias

Answer 1

Este es un sistema de ecuaciones lineales sobre F ₂ , el campo que contiene los dos elementos 0 y 1.

Puedes resolverlo como ecuaciones lineales normales, pero tienes que hacer el módulo aritmético 2.

Editar: El álgebra lineal para este caso funciona exactamente igual que para los números reales, excepto que debe reemplazar las operaciones:

• La suma y la resta se vuelven exclusivas o, es decir, 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

• La multiplicación se convierte en AND: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

• La división solo es posible por uno: 0/1 = 0, 1/1 = 1.

Todos los coeficientes en sus ecuaciones y los posibles valores de incógnitas son 0 o 1.

Por lo tanto, el módulo no se aplica en el exterior de las ecuaciones como escribió, está implícito en las operaciones.

Si su sistema de ecuaciones no tiene solución, obtendrá una ecuación 0 = 1, que obviamente no tiene solución.

Answer 2

En lugar de comenzar con un estado aleatorio, ¿por qué no generar la posición inicial activando interruptores aleatorios, es decir, trabajar hacia atrás desde un estado resuelto a un estado inicial? De esa forma solo generarás acertijos solucionables.

Answer 3

Esto se ve casi como un sistema de ecuaciones lineales (excepto el mod 2), por lo que es posible que pueda adaptar una de las técnicas normales para resolverlas, p. ej. reducción de filas del sistema en forma matricial (wikipedia) .

Answer 4

Como este no es un problema de tiempo limitado (bueno, suponiendo que se pueda hacer en menos de un día), probablemente haría una búsqueda de amplitud limitada en profundidad, tomando cada movimiento posible en un nivel y luego cada movimiento que sigue a cada movimiento.

¡Será lento, sin embargo, es casi seguro encontrar una respuesta, si hay una!

Answer 5

Suponga que construyó un sistema de ecuaciones y las resolvió lo mejor que pudo, pero algunas filas terminaron con todos los 0 en el lado izquierdo de la ecuación (estoy representando las ecuaciones como una matriz aumentada) Supongamos que intenta resolver el sistema en el anillo Z2 (que en términos prácticos para este ejemplo en particular significa que el único cambio es que 1 + 1 = 0, de lo contrario todo sigue igual ... ergo, el único operador que necesitamos es XOR) y terminó con la siguiente matriz:

1001 1
0100 1
0011 0
0000 0

Como puede ver en este ejemplo, la cuarta fila es toda 0, lo que significa que no tenemos una respuesta para ello. Sin embargo, piense de esta manera: una fila de todos los 0 significa que esa variable no afecta la solución. Esa es en realidad una mala elección de palabras ... solo significa que pueden tener cualquier valor (y estamos de suerte aquí, ya que todos los valores significan 1 o 0, a diferencia de los números reales ... Entonces, esto significa que tenemos 2 soluciones para este sistema).

He aquí por qué: lo que necesitas saber en este momento es que la columna de la derecha todavía contiene una solución válida para tu juego. Tomemos la primera línea, por ejemplo. Dice que

button_0 + button_3 = 1

pero sabemos que el botón 3 puede ser cualquier cosa (ya que la línea 3 son todos ceros). En este punto, el botón 3 es 0 (la columna más a la derecha en la fila 3 es 0 en este punto), así que ahora sabemos que significa

button_0 + 0 = 1

entonces sabemos con certeza que button_0 es 1. Por lo tanto, en este sistema, aunque no pudimos descubrir directamente button_3, todavía tenemos una solución válida.

La matriz generada anteriormente es suficiente para verificar la solubilidad. Si una fila contiene todos los 0, entonces esencialmente está diciendo que

nothing = nothing

o, para visualizar mejor por qué esto funciona,

0x = 0

lo cual tiene sentido, el sistema sigue siendo válido. Sin embargo, si encontramos una fila que es todos ceros excepto el bit más a la derecha, es decir,

0000 1

eso sería decir

0x = 1

lo cual es imposible, por lo tanto, ahora sabemos que el sistema no se puede resolver, ya que no podemos resolver una situación imposible como esta.

Por lo tanto, en pocas palabras, intente resolver la ecuación lo mejor que pueda, no se preocupe si no puede averiguar exactamente cuáles son algunas de las variables, siempre y cuando no encuentre, en ningún momento, lo imposible fila que acabo de mencionar, entonces el juego es solucionable.

¿Pero qué pasa si queremos la solución más corta para el sistema? Aquí tendremos que examinar todas las soluciones posibles. Tenemos button_3 que puede ser cualquier valor, por lo que significa que 1 en la columna 3 significa que la fila en la que se encuentra se ve afectada por button_3. Supongamos que queremos verificar si la solución usando button_3 será más corta. Creamos otra matriz, pero establecemos button_3 en 1 ahora (ya que establecimos anteriormente que podría ser cualquier cosa, y ya teníamos un 0 allí, así que ahora buscamos 1). Ahora terminamos con la siguiente matriz:

1001 1
0100 1
0011 0
0001 1

Reducimos eso tanto como podemos y ahora terminamos con esta matriz:

1000 0
0100 1
0010 1
0001 1

Esta sigue siendo una solución válida, sin embargo, podemos ver que la solución es más larga (requiere 3, en lugar de presionar 2 botones), por lo tanto, la descartamos. Tenemos que hacer esto para cada permutación de establecer las filas que encontramos como todos 0 a 1. Por lo tanto, si tenemos x filas que eran todas 0, entonces el sistema tiene soluciones x ^ 2, y tenemos que verificarlas todas.