algorithm - pseudocodigo - como hacer un buscaminas en python
Buscaminas que resuelven algoritmo (8)
¿Has visto esta implementación C # del juego ? El código fuente es descargable y se explica el modelo de objeto.
Estoy bastante seguro de que la mayoría de ustedes conocen el juego del buscaminas. Quería codificar (en C #) mi propio juego de buscaminas y estaba buscando información sobre lo que sería un buen algoritmo para ese juego. He estado navegando por la web desde hace bastante tiempo pero no pude encontrar una buena solución. ¿Puede alguien ayudarme con eso?
Aquí está mi solucionador de minas:
- para cada número de cuadrados:
- si el recuento de números sin abrir alrededor de == número cuadrado: todos ellos son minas
- Si es un número cuadrado - recuento de marcados alrededor == 0: todas las que no están abiertas no son minas
- usar regla de subconjunto
Aquí hay una implementación real, observe que usó la regla de subconjunto, que es más difícil de explicar https://github.com/SHiNKiROU/Minesweeper/blob/master/src/org/shinkirou/minesweeper/MinesweeperSolver.java#L27
Por supuesto, mi algoritmo puede fallar a veces. Estoy planeando implementar un solucionador de seguimiento de estilo Prolog
Como mencionó Henri, la forma correcta de resolver el buscaminas es con las matemáticas, específicamente con la Matemática de Álgebra Lineal para la parte determinista. Tengo un post completo aquí que:
- explica como funciona ese método
- Tiene un código de trabajo que puede compilar y ejecutar en cualquier plataforma.
- Contiene el código para hacer el juego y un solucionador también.
Puede verlo todo aquí: https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/
Recomendaría leerlo y luego pensarlo bien. La parte probabilística de Minsweeper se puede resolver usando estadísticas también, pero todavía no tengo un buen plan para eso. Sin embargo, otras personas también lo han investigado.
Compruebe esto: http://quantum-p.livejournal.com/19616.html
Cualquier posición en el tablero que no pueda resolverse intuitivamente con el razonamiento de los monos es una matriz que podría resolver algunos cuadrados individuales (o toda la posición) que pueden conducir a mejores tasas de resolución. La simple adivinación aleatoria no produjo buenos resultados. Implementé este método en mi algoritmo de resolución en C ++ agregando un sistema lineal de resolución de ecuaciones. Estoy investigando la dificultad de Buscaminas ejecutando decenas de miles de juegos a través del algoritmo y haciendo estadísticas.
Mi algoritmo resuelve hasta el 85% de (9,9,10) buscadores de minas de nivel fácil. Todavía no he realizado pruebas completas en otros niveles de dificultad, pero las pruebas más pequeñas sugieren que el nivel medio (16,16,40) tiene una tasa de resolución del 55-60% y el nivel Hard (30,16,99) tan bajo como 5 -10%. Voy a agregar algunas cosas nuevas que lo harían óptimo.
Definitivamente no soy un experto en minas, pero aquí está el algoritmo que uso cuando trato de resolverlo:
Recorra todos los cuadrados que son el borde del área revelada. Para cada uno de estos cuadrados, cuenta el número de minas que has revelado al lado . Resta el número que está escrito en el cuadrado (el número real de minas que lo rodean). Ese es el número de minas no reveladas que quedan alrededor de esta plaza . Divida eso por el número de cuadrados no revelados alrededor del cuadrado actual . Esa es la probabilidad de que cada una de las plazas adyacentes contenga una mina . Si un cuadrado tiene una probabilidad de 1, lo marca como una mina. Si algún cuadrado tiene una probabilidad de 0, lo marca como seguro. A continuación, actualice los números pertinentes.
¿Qué haces si ningún cuadrado tiene probabilidad 0 o 1? Un algoritmo óptimo tomaría en consideración las restricciones de múltiples cuadrados. Pero como escribí al principio, no soy un experto en buscadores de minas, así que elijo aleatoriamente de las otras casillas que tienen probabilidad más cercana a 0 o a 1.
Generar la grilla es simple. Hay un par de algoritmos simples que necesitas al ejecutar el movimiento del jugador, para determinar qué casillas abrir y si han perdido o ganado.
Generando la grilla
El algoritmo más simple es colocar todas las minas al azar. (¡Asegúrate de no superponerlos!)
Problema: el primer clic del jugador puede ser mío.
Mejora: retrasar la generación de la cuadrícula hasta que el usuario haga clic en el primer cuadrado, y no ponga minas en ese cuadrado.
Problema: el primer clic del jugador puede revelar un número distinto de cero, y se verán obligados a hacer clic al azar hasta que se abra algo.
Mejora: tampoco genere minas en los (hasta) ocho cuadrados alrededor del primer clic.
Problema: el jugador podría verse obligado a adivinar en algún momento, lo que lo convierte en una triste excusa para un rompecabezas lógico.
Mejora: ejecute el solucionador junto con el generador, asegurándose de que el puzzle tenga una solución única. Esto requiere algo de inteligencia, y no se hace en la mayoría de las variantes.
Otra forma menos común de resolver ambigüedades es detectar cuándo el jugador sabe que está eligiendo entre posibilidades igualmente probables y "colapsar la forma de onda" en la posición que decidieron. Nunca he visto esto en acción, pero sería divertido.
Jugando el juego
Además de marcar banderas, el jugador puede hacer dos tipos de movimientos para tratar de descubrir cuadrados:
Conjetura: el jugador hace clic en un cuadrado con estado desconocido y sin bandera. Revela el cuadrado, ve si el jugador murió y pon un número en él. Si el cuadrado contiene un 0, repita esto recursivamente para todos los cuadrados circundantes. Esto debería estar en una función dedicada, para separarlo del controlador de eventos de la GUI, para facilitar la recursión, y porque se reutiliza en la multigresa.
Multiguess: el jugador hace clic en un cuadrado que está descubierto y que se sabe que es seguro. Si el número de banderas que rodean es igual al número en este cuadrado, abrimos los cuadrados sin escamas usando el mismo procedimiento que el anterior.
Ganando el juego
Si el número de cuadrados que están cubiertos es el mismo que el número de minas, entonces el jugador ha ganado, incluso si no ha colocado una bandera en cada cuadrado.
Cuando el jugador pierde, es costumbre marcar las conjeturas incorrectas que hicieron, las minas restantes y la mina que pisaron.
Los comentarios son que no necesitas un algoritmo para construir el juego. Creo que te refieres a un algoritmo en el sentido de resolver y todos pueden entenderlo de esa manera también.
Sin embargo, cualquier solución a un problema puede considerarse un algoritmo.
Como la mayoría de los problemas matemáticos, puedes analizar todo el algoritmo en algoritmos más pequeños y menos complejos, hasta que llegues a algo lo suficientemente pequeño como para resolverlo. Esto te dará la primera solución correcta. Más tarde, puede optimizar los algoritmos más pequeños en el contexto de todo el algoritmo.
El tablero de juego puede considerarse como una matriz bidimensional. Tendrás un algoritmo asociado a cada operación. La primera operación probablemente sería un conjunto de ubicaciones de minas generadas aleatoriamente con coordenadas x, y con un parámetro del número de minas y el tamaño del tablero. Tendrías otro algoritmo asociado con revelar un cuadrado, que toma el tablero y una ubicación y determina cuántas minas están adyacentes a él. El algoritmo final tomaría el tablero y verificaría si quedan cuadrados sin minas para revelar.
Ahora puede tomar cada uno de estos algoritmos e intentar optimizar cada uno de ellos para obtener un mejor rendimiento y decir "cuál es la mejor manera de contar los cuadrados con minas adyacentes a un cuadrado actual, dada una matriz bidimensional que usa coordenadas x, y".
Solo quiero agregar lo siguiente si intenta escribir un solucionador: el Buscaminas está NP completo (Enlace de archivo) . Eso significa que hasta que alguien demuestre que P = NP , es posible que no pueda hacer nada mejor que realizar una búsqueda de fuerza bruta en algunas situaciones (pero quizás el juego no esté completo para campos pequeños).