Buscaminas es un juego simple con reglas simples, sin embargo, algunas de sus configuraciones crean dificultades interesantes. En este artículo, crearemos un solucionador de Buscaminas con una complejidad creciente y reflexionaremos sobre cómo cambia la dinámica del juego con un aumento gradual en el nivel de ayuda. Al final, desarrollaremos una nueva versión del juego con una jugabilidad mucho más interesante.
Razonamiento local: cero minas vecinas
En el
juego original , se usa un mecanismo automático: cuando un jugador abre una celda, junto a la cual no hay minas, el motor del juego abre todas las celdas vecinas. Esto no amenaza el juego, por lo que puedes dejar que la computadora lo haga con seguridad, y la situación en sí misma es clara para el jugador y no interfiere con el juego.
Este razonamiento es completamente local: solo se tiene en cuenta la información de una celda para decidir la siguiente acción.
Es difícil encontrar una situación en la que el juego empeore sin esta ayuda automática. Intenta jugar a un juego para tener una idea de cómo funciona sin abrir automáticamente las celdas [en el artículo original, todos los ejemplos son interactivos]
:
Consideraciones locales basadas en el medio ambiente.
Para un nuevo jugador será fácil comprender que si el número de minas vecinas, es decir, el número que se muestra en la celda, es igual al número de celdas vecinas no descubiertas, entonces todas estas celdas deben ser minas, por lo que debe colocar banderas en ellas. Del mismo modo, cuando el número de minas vecinas es igual al número de banderas vecinas, las celdas vecinas restantes no descubiertas deben estar vacías.
En estas reglas, se tiene en cuenta una celda, así como el estado de las celdas vecinas (abierto / marcado).
La implementación manual de estas reglas puede ser divertida. Si agrega un temporizador, el jugador comienza a aprender cómo aplicarlos de forma rápida y precisa. Esto convierte al Buscaminas
en un juego de reacción . ¿Qué sucede si automatizamos estas reglas?
Dicha automatización tiene un efecto secundario interesante: marcar la casilla puede tener consecuencias fatales al instante.
De lo contrario, podemos experimentar situaciones que se pueden dividir en tres categorías:
- Juegos completamente resueltos aplicando reglas automáticas
- Situaciones complicadas que requieren más celdas para razonar
- Estados del juego en los que no hay un camino lógico a seguir: el jugador solo puede elegir por casualidad, posiblemente teniendo en cuenta las probabilidades.
La situación 1 parece hermosa, pero no particularmente interesante si surge con demasiada frecuencia. ¿Serían tales juegos mejores sin una solución automática? Quizás no; tales juegos son muy simples incluso cuando se resuelven manualmente, y el jugador no está particularmente interesado en jugar juegos en los que no hay dificultades. Aunque, por supuesto, siempre hay dificultades en el juego de reacción: debes actuar lo más rápido posible.
La situación 2 me parece muy atractiva, nos centramos más en resolver condiciones lógicas, dedicamos menos tiempo a apuntar con precisión y presionar los botones correctos. Esto hace que Sapper se parezca más a un
rompecabezas activo .
La situación 3 destruye por completo toda la diversión. Sin embargo, escuché que a algunas personas les gusta jugar
juegos con aleatoriedad .
¿Es posible deshacerse de la situación 3?
Solución completa: razonamiento global
Para la detección algorítmica de todas las condiciones lógicas necesarias para el estado del juego, debemos realizar una búsqueda exhaustiva de todos los estados del juego.
Se probó que el
Buscaminas es una tarea NP-completa . A continuación se muestra un pequeño pero interesante e ilustrativo ejemplo del estado del juego, que solo tiene una solución lógica, pero para encontrarlo debe tener en cuenta el estado del juego en su conjunto:
¿Es posible buscar en todo el espacio de estado del juego? ¿Cuántas variaciones del estado
s existen?
Dado:
w = ancho de campo
h = altura del campo
k = número de minutos
n = wEntonces el número de estados posibles
s es
Para los niveles estándar "Principiante", "Amateur" y "Profesional" esto nos da:
Entendemos que un enfoque ingenuo es completamente inapropiado aquí. Veamos cómo podría verse un algoritmo ingenuo y descubramos si puede optimizarse para que funcione.
Algoritmo ingenuo
La tarea del algoritmo es encontrar todas las condiciones lógicas necesarias para el estado dado del campo. Sería difícil implementar esto considerando cuidadosamente las soluciones; la computadora hace un trabajo mucho mejor al realizar rápidamente un montón de estúpidas acciones.
¿Qué podemos hacer "estúpido": generar todas las permutaciones posibles de las posiciones de mina para todas las minas restantes. Si tal permutación corresponde a todos los números abiertos, entonces será la solución correcta para el juego. Luego estudiamos todas las permutaciones posibles, encontramos todas las soluciones posibles, pero aún no sabemos cuál es la correcta.
Si en todas las soluciones posibles hay algo en común, ya sea entre celdas abiertas o entre celdas marcadas como minas, entonces entendemos que este común debería ser parte de la decisión correcta para el campo actual. Y de hecho: es imposible crear la solución correcta que no tenga tales elementos coincidentes, de lo contrario los habríamos descubierto.
Por lo tanto, podemos encontrar todas las condiciones lógicas necesarias para el estado actual del campo.
Celdas con y sin restricciones
El algoritmo anterior tiene un problema obvio: la cantidad de estados que necesita investigar. Pero no todas las células son iguales. Las celdas sin abrir junto a un número obviamente están limitadas a ese número. Llamaremos a estas células limitadas. Las celdas restantes las llamaremos ilimitadas.
Si implementamos el algoritmo anterior, pero solo buscaremos en el espacio de estados de celdas restringidas, y volveremos tan pronto como rompamos la restricción, entonces en muchos juegos podemos resolver todas las condiciones lógicas en un tiempo razonable:
En el caso de celdas ilimitadas, no podemos averiguar dónde se encuentran las minas, y lógicamente lo sabemos de inmediato. Esto significa que puede excluirlos del cálculo y considerar solo la ubicación de las minas junto a los números abiertos.
Sin embargo, sabemos que un cierto número de minas puede entrar en muchas celdas ilimitadas; si hay 6 min y 4 celdas restringidas, entonces en celdas limitadas puede haber un máximo de 4 minas, es decir, al menos 2 minutos deben estar en celdas ilimitadas. Por la misma lógica, a veces podemos determinar que todas las celdas ilimitadas deben estar vacías o todas deben contener minas.
En el caso que se muestra a continuación, conocemos las posiciones de todas las minas, por lo que la IA debería poder entender que las celdas restantes no están ocupadas:
En el siguiente caso, no conocemos las posiciones de todas las minas, pero podemos entender que la mina restante debe colocarse en una de las dos celdas en la esquina superior izquierda. Esto significa que la celda que queda en la esquina inferior derecha es libre:
Versión aleatoria
Si ejecutamos automáticamente el solucionador global, obtendremos una versión optimizada al azar de Buscaminas:
Puedes dividir los juegos de esta versión en tres categorías:
- Juegos en los que el jugador toma decisiones arbitrarias y gana.
- Juegos en los que el jugador toma decisiones arbitrarias y pierde.
- Juegos en los que la IA requiere mucho tiempo, y el jugador puede usar el razonamiento.
Obviamente, este es un juego de azar. ¿Cuál es el atractivo de tales juegos? En términos de lógica, el juego que se muestra arriba es similar a esto:
¿Pero qué juego aleatorio es mejor? Parece que el significado de otros juegos con aleatoriedad radica en la existencia de una relación compleja entre las acciones del jugador y ganar / perder. Para dibujar números de lotería, se utilizan máquinas complejas que no tienen prisa por seleccionar un número y hacer un espectáculo completo de mostrar este número.
Quizás un campo grande que se decide automáticamente es un juego bastante bueno
con aleatoriedad, dado que el jugador está observando la apertura gradual de todas las celdas.
¿Podemos idear un tipo diferente de juego?
Versión determinista
Ahora tenemos una IA capaz de determinar todos los pasos lógicos de un estado de juego dado. A veces no podrá encontrar pasos lógicos. En tales situaciones, el jugador tiene que adivinar y puede perder si no tiene suerte.
¿Qué pasa si agregamos otra regla? Cuando el juego no tiene un camino lógico, podemos pedir ayuda. Si la IA acepta que el jugador no puede hacer nada, entonces él viene en su ayuda. De lo contrario, el jugador pierde de inmediato. Esto puede ser interesante. ¿Qué tipo de ayuda puede ser esto? Tal vez necesite abrir una celda, independientemente de la presencia de minas en ella:
Por lo tanto, eliminamos por completo las situaciones en las que uno podría perder por casualidad.
Sin embargo, hay una excepción: todavía existe la posibilidad de situaciones degeneradas en las que el solucionador global no puede completar los cálculos en un período de tiempo razonable. Desafortunadamente, este es el resultado inevitable de que la tarea Buscaminas es NP-completa.
¿Cómo afecta el botón "Pedir ayuda" al juego? Conduce al hecho de que el juego se centra más en la lógica; Esta es la versión más "desconcertante" de "Buscaminas". Alguien podría pensar que el juego será más fácil, pero de hecho se está volviendo más complicado. Ahora no hay excusas para los errores del jugador, y el botón lo castigará si se le pasa algo. Sin un botón, es fácil concluir que ha agotado todas las posibilidades lógicas y la única opción para el desarrollo de eventos es tratar de adivinar al azar. Pero debido a la existencia del botón, el jugador debe tener razón en esta evaluación.
En conclusión
Habiendo implementado el solucionador "Buscaminas" completo, pudimos crear una variación del juego, libre de su maldición: ahora es imposible perder debido al hecho de que tienes que elegir por casualidad cuando casi has decidido todo el campo. Esta versión difiere del juego original solo en los momentos en que necesita adivinar al azar, por lo que puedo suponer que es mucho más divertido que el juego original.
Además, desarrollamos una versión del juego que resuelve automáticamente reglas locales simples. Si usar esa ayuda depende de usted. Cambia el enfoque del juego del clic mecánico a una jugabilidad más desconcertante. Al mismo tiempo, no es necesario utilizar la mejora de juego proporcionada por el botón "Pedir ayuda".