Cómo resolver el buscaminas

Cómo resolver el buscaminas

¿Cómo resolver el buscaminas? El juego original emplea un mecanismo automático: cuando revelas un cuadrado que tiene cero minas adyacentes, el motor del juego revela todos los cuadrados adyacentes. Esto trivialmente no tiene riesgo, por lo que es seguro dejar que la computadora lo haga, y es trivialmente obvio para el jugador que este es el caso, por lo que no debería arruinar ninguna diversión hacerlo.Este razonamiento es completamente local: la información de un solo cuadrado se utiliza para determinar qué acción tomar a continuación.

Es difícil argumentar que el juego sería mejor sin esta ayuda automática. Prueba el siguiente juego para tener una idea de cómo actúa cuando no hay revelación automática:

Razonamiento para resolver el buscaminas

Un jugador nuevo no debería tardar mucho en darse cuenta de que cuando el número de minas adyacentes, es decir, el número que se muestra en el cuadrado, es el mismo que el número de cuadrados adyacentes no revelados, todos esos cuadrados deben ser minas, por lo que Se pueden marcar como tales.

Del mismo modo, cuando el número de minas adyacentes es igual al número de banderas adyacentes, los cuadrados adyacentes no revelados restantes deben ser seguros.

Estas reglas tienen en cuenta un cuadro y si los cuadros adyacentes se revelan o se marcan o no.

Realizar estas reglas manualmente puede ser entretenido. En combinación con un temporizador, entrenas para poder ejecutar estas reglas de forma rápida y precisa. Esto convierte a Buscaminas en un juego de contracciones . Entonces, ¿qué sucede si automatizamos estas reglas.

Un efecto secundario interesante de hacer esto automático es que colocar una bandera en el lugar equivocado ahora puede ser un error fatal inmediato.

Para el resto del juego, nos quedan situaciones que se dividen en tres categorías:

  1. Juegos completamente resueltos por las reglas automáticas.
  2. Elaborar situaciones que requieren razonamiento que implique más cuadrados
  3. El juego afirma que no tiene un camino lógico hacia adelante: el jugador no tiene otro recurso que no sea adivinar al azar, tal vez ponderado por la probabilidad

Si bien la situación 1 anterior es bastante clara, no es muy satisfactorio jugar muchos de estos juegos. ¿Habrían sido mejores esos juegos sin la resolución automática? Tal vez no; tales juegos son muy sencillos incluso cuando los resuelves manualmente, y no es muy satisfactorio ganar en juegos en los que no te has sentido desafiado. Por supuesto, para un juego de contracción siempre hay algún desafío en actuar más rápido.

La situación 2 me parece muy satisfactoria. Nos enfocamos más en resolver requisitos lógicos y menos en apuntar con precisión y hacer clic en los botones correctos. Esto hace que Buscaminas sea más un juego de rompecabezas .

La situación 3, sin embargo, arruina completamente la diversión. Aunque he oído hablar de personas a las que les gusta jugar juegos de azar .

¿Podemos eliminar la situación 3?

Cómo resolver el buscaminas

Solución completa: razonamiento global

Para descubrir algorítmicamente todas las necesidades lógicas del estado del juego, tenemos que recurrir a la búsqueda exhaustiva de todos los estados del juego. En realidad, se ha comprobado que el Buscaminas es NP-completo.

El siguiente es un ejemplo pequeño, pero interesante e ilustrativo de un estado del juego que solo tiene una solución lógica, pero debe tener en cuenta todo el estado del juego para encontrarlo:

El ingenuo algoritmo

El objetivo del algoritmo es encontrar todas las necesidades lógicas de un estado de placa dado. Es difícil razonar sobre esto de una manera inteligente; la computadora es mejor para hacer muchas cosas estúpidas rápidamente.

Lo que podemos hacer estúpidamente es generar todas las permutaciones posibles de las posiciones de las minas para todas las minas restantes. Si tal permutación encaja con todos los números revelados, podría ser la solución correcta para el juego. Cuando exploramos todas las permutaciones posibles, encontramos todas las soluciones posibles, pero aún no sabemos cuál es la correcta.

Si hay algo en común, ya sea cuadrados abiertos o cuadrados marcados como minas, entre todas las soluciones posibles, sabemos que esto debe ser parte de la solución correcta para el tablero actual. De hecho, es imposible crear una solución sólida que no tenga esto en común, de lo contrario lo habríamos descubierto.

De esta manera, podemos encontrar todas las necesidades lógicas del estado actual de la placa.

Cuadrados restringidos y no restringidos

El problema inmediato con el algoritmo anterior es la cantidad de estados que tiene que explorar, como se calculó anteriormente. Pero no todos los cuadrados son iguales. Los cuadrados no revelados que son adyacentes a un número obviamente están restringidos por este número. Llamaremos a estos cuadrados los cuadrados restringidos. Llamaremos a los cuadrados restantes los cuadrados no restringidos.

Si implementamos el algoritmo anterior pero solo buscamos el espacio de estado de los cuadrados restringidos, y nos aseguramos de dar marcha atrás tan pronto como violemos una restricción, podemos resolver todos los requisitos lógicos en un tiempo razonable para muchos juegos.

No restringidos

Para los cuadrados sin restricciones no tenemos forma de saber a dónde van las minas, y lo sabemos lógicamente por adelantado. Esto significa que podemos eliminarlos del cálculo y solo considerar la colocación de minas adyacentes a los números revelados.

Sin embargo, sabemos que una cierta cantidad de minas puede entrar en el conjunto de cuadrados sin restricciones; Si hay 6 minas y 4 cuadrados restringidos, como máximo 4 minas van en los cuadrados restringidos, por lo tanto, al menos 2 minas van en los cuadrados sin restricciones. Por una lógica similar, a veces podemos determinar que todos los cuadrados sin restricciones deben estar vacíos o que todos tienen minas.

Para el siguiente caso, conocemos la posición de todas las minas, por lo que la IA debería ser capaz de darse cuenta de que los cuadrados restantes están desocupados:

Para el siguiente caso, no sabemos la posición de todas las minas, pero podemos decir que necesitamos colocar la mina restante en uno de los dos cuadrados superiores izquierdos. Esto significa que el cuadrado restante en la esquina inferior derecha es libre:

La versión casual

Si ejecutamos automáticamente el solucionador global, tenemos la versión optimizada de buscaminas podemos dividir los juegos de esta versión en tres categorías:

  1. Juegos en los que tomas decisiones arbitrarias y ganas
  2. Juegos en los que tomas decisiones arbitrarias y pierdes
  3. Juegos en los que la IA tarda mucho en ejecutarse, y en realidad puedes razonar

Esto es claramente un juego de azar. ¿Cuál es el atractivo de tales juegos? En un sentido lógico, el juego anterior es similar al siguiente:

¿Pero cuál es el mejor juego de azar? Parece que otros juegos de azar hacen un punto de tener una conexión elaborada entre tus acciones y si ganas o no. Los dibujos de números de lotería utilizan máquinas complicadas que deliberadamente toman tiempo para seleccionar un número y mostrar qué número se elige.

Tal vez el tablero grande que se resuelve automáticamente es un juego de azar bastante bueno, dado el espectáculo de ver todos los cuadros ser revelados.

¿Podemos hacer otro tipo de juego?

La versión determinista.

Ahora tenemos una IA que puede determinar cuáles son todos los pasos lógicos de un estado de juego dado. A veces no encontrará pasos lógicos. Estas son las situaciones en las que el jugador tiene que adivinar y puede perder el juego debido a la mala suerte.

¿Qué pasa si agregamos una nueva regla? Cuando el juego no tiene un camino lógico, puedes pedir ayuda. Si la IA acepta que no hay nada que puedas hacer, obtienes ayuda. De lo contrario, inmediatamente pierdes el juego. Esto puede ser interesante. ¿Cuál debería ser la ayuda? Tal vez puedas revelar un cuadrado sin importar si tiene o no una mina:

En este punto, realmente nos hemos librado del juego forzándote a situaciones en las que puedes perder por casualidad.

Solo hay una excepción a esto, a saber, que todavía es posible entrar en situaciones degeneradas para las cuales el solucionador global no terminará de evaluar en un período de tiempo razonable. Desafortunadamente, este es un resultado inevitable de que el problema sea NP-completo, como se señaló anteriormente.

¿Cómo afecta el botón “Solicitar ayuda” al juego? Es un juego enfocado lógicamente. Esta es la última variante de juego de rompecabezas de Buscaminas. Uno podría pensar que el juego sería más fácil, pero en cambio se vuelve más difícil. Ya no tienes ninguna excusa para cometer errores, y el botón seguramente te llamará por cualquier cosa que te hayas perdido.

Sin el botón, es fácil llegar a la conclusión de que ha agotado todas las posibilidades lógicas y que el único curso de acción es adivinar al azar. Con el botón, debe ser correcto en esta evaluación.

También te puede interesar:
Buscaminas

Déjanos tu opinión

Si continuas utilizando este sitio aceptas el uso de cookies. más información

Los ajustes de cookies de esta web están configurados para «permitir cookies» y así ofrecerte la mejor experiencia de navegación posible. Si sigues utilizando esta web sin cambiar tus ajustes de cookies o haces clic en «Aceptar» estarás dando tu consentimiento a esto.

Cerrar