😪 👩🏾‍🎤 👨🏿‍🤝‍👨🏻 Kaboom: un zapador inusual 👨‍👦‍👦 📔 🚄

Cuando era niño, me sentaba en el trabajo de mi padre tres veces por semana durante una hora y media. Se me permitió ir a una computadora, donde desde el entretenimiento solo había un zapador y Paint. Estaba cansado de dibujar rápidamente, pero el deseo de abrir todo el campo y no explotar me motivó a buscar nuevas y nuevas formas de jugar este juego. Muchos años después, accidentalmente me topé con un artículo interesante sobre un clon de un zapador, y no pude pasar. Le sugiero que se familiarice con él. Esta es una historia sobre el desarrollo de Kaboom, un clon del legendario juego Buscaminas con su propio entusiasmo.

Buscaminas apareció hace bastante tiempo según los estándares de un juego de computadora. Pero me parece que la mayoría de la gente recuerda los juegos que formaban parte de versiones anteriores de Windows. Nunca fui bueno en Buscaminas, pero lo jugaba de vez en cuando. Algunas personas juegan más en serio . Y para aquellos que quieran animarse, les recomiendo ver Buscaminas - La película .

Idea

Recientemente tuve una idea: ¿qué pasa si tienes que jugar al Buscaminas contra una computadora más sabia?

Por lo general, la ubicación de las minas se determina al comienzo del juego (pero hay algunos trucos aquí, por ejemplo, para que no puedas perder el primer clic). Pero, ¿qué pasaría si la ubicación de las minas no se hubiera determinado de antemano y el juego hubiera podido elegir la ubicación de las minas después del inicio del juego?

Eso sería bastante cruel: si haces clic en un cuadrado que puede contener una mina, ¡siempre lo contendrá! Por lo tanto, debe probar de antemano que el cuadrado es seguro.

En la imagen de arriba, en las celdas marcadas con un punto, no hay minas garantizadas, y las celdas marcadas con un signo de exclamación contienen una. Los signos de interrogación significan incertidumbre: quizás si abre más celdas, puede calcular si una mina está oculta o no.

Por otro lado, hay situaciones en las que tiene que adivinar:

hay una mina en una de las celdas inferiores. Pero en cuál, es imposible de entender. Debes elegir uno de ellos. Pero de acuerdo con la condición de la que acabo de hablar, ¡esto significaría una muerte segura! Quería que el juego fuera brutal, pero ahora obviamente está perdiendo.
Por lo tanto, cambiaré ligeramente la idea. Puedes adivinar, pero solo si no quedan células seguras. Por lo tanto, el juego será cruel, pero justo.

En otras palabras:

, .
, , .
, :
1. , , .
2. , , .

¿Cómo implementar tal juego? Podría intentar calcular todos los campos posibles, pero esto no es realista: incluso un campo pequeño de 10x10 significa 2 ^ 100 posibilidades. Seleccionar solo aquellos que contienen exactamente N min no ayuda.

Afortunadamente, no necesito preocuparme por todo el campo. No sabemos nada sobre minas terrestres no adyacentes a las etiquetas. Solo estoy interesado en aquellos que están en la frontera, el resto puede determinarse por accidente.

Entonces puedo calcular todas las opciones para la ubicación de minas en el borde de acuerdo con las etiquetas. Retroceso (retroceso): una buena técnica que le permite ordenar todas las combinaciones, pero también puede retirarse rápidamente tan pronto como determinemos que una rama no puede calcular.

Las dos posibles ubicaciones de minas en la frontera se muestran arriba. Combinándolos, entenderemos qué celdas están garantizadas para estar vacías o extraídas.

También necesito rastrear el número total de minas. Por lo tanto, la ubicación realmente se ve como "5 minutos en la frontera, 5 minutos afuera". Esto es importante porque de lo contrario podría haber creado demasiadas minas en la frontera (¡o muy pocas!)

Entonces, tengo todas las opciones. ¿Qué sucede cuando un jugador decide abrir una jaula?

Elija una opción aleatoria (una que satisfaga las reglas "crueles pero justas"). Esto determinará la ubicación de las minas en la frontera.
Dispersa al azar a los que quedan fuera de la frontera.
Si hay una mina en la celda seleccionada, el juego termina.
De otra manera:
1. Definir una nueva etiqueta para la celda identificada
2. Revelar celdas adicionales si es 0
3. , ! .

Para campos pequeños esto es normal. Por lo general, solo hay unas pocas combinaciones posibles ... espera, ¿qué es?

¡Oh no!

De alguna manera, logré desbloquear 18 millones de posibles ubicaciones mineras. Mi Firefox devora 12 gigabytes de memoria, y abrir una celda lleva medio minuto. Obviamente, necesito un mejor algoritmo.

Alguien puede notar que Minesweeper es un juego NP-complete , y por lo tanto no se puede evitar un tiempo exponencialmente creciente. Y en el caso general, esto es cierto: habrá posiciones que tomarán mucho tiempo calcular. Pero para un área pequeña esto funciona.

No necesito recordar todas las combinaciones. Ni siquiera necesito calcular todas las combinaciones. Todo lo que se requiere es una forma:

verificar si la celda es segura, peligrosa o vaga,
(, , ).

En lugar de probar las opciones yo mismo, voy a usar el solucionador SAT . Estas son herramientas que toman una fórmula que consiste en variables lógicas y buscan un conjunto de valores que hagan que la fórmula sea verdadera. Un método tan imaginario pero bastante válido para nuestra tarea.

Una clase de software más potente son los solucionadores SMT que funcionan con una gama más amplia de valores y fórmulas, como la lógica de primer orden (cuantificadores), matrices, enteros, etc. Esto ayudará al menos a definir algunas ecuaciones para enteros. Pero necesito algo que funcione en el navegador. La gente logró portar algunas herramientas sofisticadas como Z3Prover al navegador, pero la versión de WebAssembly pesa17 MB , y eso es demasiado.

Encontré MiniSat , un pequeño solucionador SAT que fue compilado para Javascript por Joel Galenson. El archivo compilado solo toma 200 kilobytes, así que lo uso.

Fórmulas CNF

Los solucionadores SAT funcionan con fórmulas conjuntivas normales ( CNF ). La fórmula de CNF es "un AND de OR", por ejemplo:

(a | ~ b | ~ c) & (c | d ~ e) & f

puede convertir cualquier fórmula de lógica de oración (variables y, o, no, implicación) a CNF, por lo que es un formato universal.

¿Cómo lo usamos? Supongamos que tenemos una tabla: si creo variables para celdas desconocidas (en el sentido de las agujas del reloj: x1, x2, x3), tendrán que satisfacer las siguientes ecuaciones: ¿Pero cómo expresar "la suma de las variables es 2" en CNF? Encontré un método que, como supe más tarde, se llama "codificación binomial" y es la codificación más simple. Debe considerar todos los subconjuntos posibles de variables. Por ejemplo, para necesitar las siguientes fórmulas:

? ? 1
2 ? 1

1 + 2 + 3 = 2
2 + 3 = 1
2 + 3 = 1 ( )

x1 + x2 + x3 = 2

Para cada subconjunto de 2 variables, al menos una es verdadera. Esto asegura que la cantidad sea mayor que 1.
(x1 | x2) & (x1 | x3) & (x2 | x3)
Al menos una variable es falsa. Esto asegura que la cantidad sea inferior a 3.
(~ x1 | ~ x2 | ~ x3)

Para x2 + x3 = 1mí necesito un conjunto similar de fórmulas:

Al menos una de las variables es correcta: (x2 | x3)
Al menos una de las variables es falsa (~ x2 | ~ x3).

Al combinar esto, obtengo una fórmula CNF con 6 puntos. En el formato DIMACS estándar: todas las líneas de posición terminan en 0 y la negación se marca con un signo menos. Si lo conecto a MiniSat (pruébelo usted mismo), obtengo: Esto significa que MiniSat encontró una solución donde x1 y x2 son verdaderas y x3 son falsas. Así se verá el tablero: todo el programa es un poco más complicado: esta es solo una solución, hay otra. Por lo tanto, para saber si x1, x2, x3 puede ser verdadero (o falso), debe realizar más solicitudes. Necesito preguntar: “Dada la fórmula anterior, así como x1, ¿es factible? ¿Qué tal la fórmula anterior, así como ~ x1 "?

SAT 1 2 -3

! ! 1
2 . 1

La codificación significa que necesito encontrar todas las combinaciones posibles (por ejemplo, todos los subconjuntos de 3) de un conjunto de variables. Sin embargo, para esta ecuación solo habrá hasta 8 variables, por lo que la fórmula suele ser lo suficientemente pequeña como para que MiniSat pueda resolverla rápidamente.

Seguimiento mínimo

¡Desafortunadamente, esta no es una solución completa! Todavía necesito rastrear cuántas minas quedan. Algunas combinaciones son imposibles, porque de lo contrario puedes crear más minas de las permitidas, y será imposible ganar.

De hecho, el caso contrario también es posible: si hay muy pocas minas, el juego terminará, porque no habrá nada que colocar.

Por lo tanto, necesito indicar en la fórmula SAT que "el número de minas no es menor que X ni mayor que Y". Al principio pensé que podría usar el truco con todas las combinaciones. Desafortunadamente, no funciona demasiado bien con grandes números. Si hay, por ejemplo, 20 celdas y 10 minutos, luego de conectar los números al coeficiente binomial, ¡descubrimos que el número de combinaciones ya es de 6 dígitos!

Entonces descubrí que hay muchas otras formas de codificar la suma de variables en la fórmula SAT. Necesita crear un esquema que combine las variables individuales. Vea, por ejemplo, esta respuesta en StackExchange o esta .

Al final, me di cuenta de la idea de un artículo titulado "Codificación CNF efectiva con restricciones de cardinalidad booleana", escrito por Olivier Baillot y Yasin Bufhad. Vemos un árbol que agrega recursivamente números unarios (o clasifica bits para que todos estén al principio):

Al final de este diagrama, obtendrá un conjunto ordenado de variables de "salida". Para confirmar que la suma no es menor que X, verifique que la primera X de las variables resultantes sea 1. Para afirmar que la suma no es mayor que Y, verifique que el último N - Y de las variables resultantes sea 0.

Esto es mucho mejor que usar todas las combinaciones posibles, sin embargo, este esquema sigue siendo irracional porque genera oraciones Ө (N ^ 2). Cuando el número de celdas abiertas es de aproximadamente 100, el juego se vuelve lento. Podemos optimizar el juego aún más.
Reducir solicitudes

Mientras estudiaba el problema, noté que puedo reducir la cantidad de consultas al solucionador. Quería determinar el estado de todas las celdas (es decir, verificar si se garantiza que son peligrosas, seguras o no). Hice esto usando un bucle simple. Digamos que el tablero se describe mediante la fórmula F:

Decide F & ~ x1si x1 puede ser 0
Decide F & x1si x1 puede ser 1
Decide F & ~ x2 si x2 puede ser 0
Decide F & x2si x2 puede ser 1
Etc.

¿Qué noté? Si obtengo una solución para F & ~ x1, también contendrá los valores de todas las demás variables. Esto ya responde muchas otras preguntas: si la solución contiene x2 = 0, no necesito preguntar si x2 puede ser 0, porque ya lo sé. Esto me permite reducir la cantidad de solicitudes entre 2 y 5 veces.

Almacenamiento en caché

Esto no resuelve el problema de la enorme fórmula generada por el circuito de "conteo". Como dije, el número de oraciones está en el orden de N ^ 2. En un tablero grande, la fórmula puede tener hasta 10,000 suposiciones.

Afortunadamente, la mayoría de las veces sabemos el significado exacto de muchas células. Si la celda está garantizada vacía o garantizada llena, ¡el valor nunca cambiará! Esto significa que podemos almacenarlo en caché y no incluirlo en la fórmula SAT. Una vez que determinamos el estado de la celda, ya no necesitaremos incluirla nuevamente en el cálculo. Las celdas se usarán siempre que no estén definidas.

Esta optimización es ligeramente peligrosa: ya no tenemos una fórmula que confirme la corrección de toda la placa. Si todo lo demás funciona según lo planeado, esto no es un problema, pero puede complicar el seguimiento de errores.

Otro caso: jugar en el extranjero

¿Se le permite hacer clic en cualquier parte del mapa fuera del borde entre el área abierta y sin abrir del campo?

Inicialmente, pensé que era lo mismo que adivinar: si no hay celdas seguras, simplemente puede hacer clic en cualquier parte del campo. Pero a algunos les resulta extraño que esto garantice la apertura de una jaula vacía.

Por lo tanto, cambié el juego para que siempre se castigue un clic fuera del borde. Con la excepción del comienzo del juego, por supuesto, porque entonces todo el tablero está "afuera".

Pero resulta que hay otro escenario: ¿qué pasa si todos los campos fronterizos son mortales? No tienes más remedio que revelar algo más. Esta situación puede hacer que el juego sea intransitable desde el principio. Entonces ahora hay una excepción más. Puedes jugar fuera de las fronteras si:

3 . .
. . .
. . .

El campo no está abierto
Las celdas extraídas pueden estar ubicadas en el borde (hacer clic en el exterior debe ser seguro), o
Debe haber bombas en todas las celdas en el borde (debe hacer clic afuera).

Actualización : El cambio resultó ser controvertido, ya que la restricción es algo artificial. Agregué un interruptor que permitirá / prohibirá jugar con estas condiciones.

Es todo

Puedes jugar Kaboom aquí . Intenta activar el modo de depuración: hace que el juego sea trivial, pero muestra bien cómo funciona.

Código fuente de Github . El no es muy guapo.

Usted también podría estar interesado en un juego similar de Simon Tatham, creador de PuTTY. Su versión tiene un giro diferente: siempre se puede resolver sin especulaciones.

Juega sabiamente!

¿Qué más puede ser útil para leer en el blog de Cloud4Y

→ Cómo se "rompió" el banco
→ Privacidad personal? No, no escucharon
→ La gran teoría de los copos de nieve
→ Diagnósticos de conexiones de red en un enrutador EDGE virtual
→Los virus resistentes a CRISPR construyen refugios para proteger los genomas de las enzimas que penetran en el ADN. ¡

Suscríbase a nuestro canal de Telegram para que no se pierda otro artículo! Escribimos no más de dos veces por semana y solo por negocios. Te recordamos que las startups pueden obtener 1 millón de rublos. de Cloud4Y. Términos y condiciones para quienes lo deseen - en nuestro sitio web: bit.ly/2sj6dPK