El Buscaminas es un juego que viene en muchas de las versiones de Windows. Básicamente es una malla cuadriculada (o rectangular) que contiene, en cada celda un cuadro que con un click del ratón, se descubre y se ve lo que contiene. Si tenemos la mala suerte de dar click en una mina, pues estalla y el juego termina. En caso contrario, la cajita sobre la celda desaparece y aparecen en las celdas contiguas algunos números. Estos son indicaciones de dónde hay bombas. Pistas para el jugador, pues. Por ejemplo, en una celda puede aparecer un 2, 3, 4, etcétera. Eso indica que hay bombas alrededor y hay que tener cuidado qué otra celda abrimos. El juego consiste en abrir todas las celdas sin que nos explote una sola bomba y de hecho, es un juego contra reloj. Hay diferentes versiones del Buscaminas, la de principiantes es una malla de 10 x 10, pero hay mallas más grandes y desde luego, lleva más tiempo poder resolverlas.
Cuando Windows apareció en muchas máquinas, el Buscaminas y el juego de cartas solitario fueron los más adictivos, y tan lo eran, que en algunas empresas se borraban de la distribución de Windows porque la gente jugaba y no trabajaba. Ahora ya no se mencionan mucho estos juegos y además, la moda parece haberse polarizado a las redes sociales. No obstante esto, a más de uno se le habrá ocurrido cómo hacer un programa que pueda jugar Buscaminas con éxito y mucho más rápidamente que cualquier humano.
Para poder escribir un programa semejante, se necesitan algunos elementos: un lenguaje de programación al que se le pueda programar dar click en la parte que queramos de la pantalla. Otro más que pueda “ver” lo que aparece en el juego, en este caso el Buscaminas, y así poder procesar esa información para así realizar la siguiente jugada.
Bai Li (luckytoilet), es un joven de 18 años, que se autodenomina geek/hacker, de Calgary, Canadá. Estudia Ciencias de la Computación en la Universidad de Waterloo y ha escrito un programa inteligente para jugar Buscaminas y desde luego, hacerlo mejor y más rápido que cualquier ser humano.
El mapa de acción inteligente para resolver con un programa (en Java en este caso), este juego, va así, de acuerdo a Li:
- Leer el tablero. Se usó la función screenshot, la cual puede darle un bitmap de regreso, con todos los pixeles del tablero. Solamente se necesitan leer los números en la pantalla. Por suerte, los programadores del Buscaminas usaron diferentes colores: 1 es azul, 2 es verde, 3 es rojo, etcétera.
- Calcular entonces dónde están las minas.
- Dar click en el casillero adecuado. Esto se hace con la clase Robot, que es una biblioteca estándar de Java y que envía clicks del ratón a la pantalla.
Y aunque el plan es muy sencillo, la implementación tiene su chiste, porque hay que distinguir en las celdas que dan pistas sobre dónde puede haber bombas y en las que no dicen nada. Aquí el programador utilizó cierta heurística basada en la variación de los colores de las celdas.
El algoritmo que resuelve, al menos en una primera aproximación, el Buscaminas, es dar click casi al azar. En algunos casos el nivel de principiantes se resuelve. No importa cuántas veces se pierda, sólose cuentan los triunfos. Pero esto no es interesante, por lo que hay que pensar en una estrategia más inteligente.
Li analiza con cuidado los casos que se pueden presentar y dio con un algoritmo que cuenta lo que hay en múltiples celdas al mismo tiempo. Esto lo llevó a un algoritmo que enumera todas las configuraciones posibles de minas para una posición en particular y entonces observó lo común entre esas configuraciones.
La primeras aproximaciones a su algoritmo hacían que el programa de pronto se detuviera a ver qué jugada tenía que hacer. Usando la teoría de regiones desunidas logró que la respuesta del programa fuese casi instantánea. Con ello quedó en claro que su método era incluso mejor que la deducción humana. Un resultado que bien podría discutirse ya en el tema de inteligencia artificial de forma más profunda.
Li también halló que el Buscaminas se convierte de pronto en un problema no determinístico, es decir, no se puede resolver siempre como cabría esperar. La razón es que hay configuraciones donde puede o no haber una mina en una celda, por lo que al final de cuentas es una apuesta de 50% vs 50%. Sin embargo, el autor de este fascinante programa reanalizó las configuraciones y llegó a la conclusión que puede utilizar la teoría de la probabilidad en algunas de las configuraciones, lo que le da un 82% de probabilidad de que el sistema resuleva acertadamente el acertijo para ciertas configuraciones en donde no se puede asegurar que no haya bomba en una celda.
Hay una estrategia extra que Li usa: la información que da el sistema sobre la cantidad de bombas que quedan en el tablero. Esto, aunado a un par de trucos sobre las configuraciones, le dio más posibilidades de resolver el juego con mayor éxito en promedio.
El artículo de Li, en donde analiza todas las dificultades a resolver es fantástico y vale la pena leerlo completo. El autor llega a la conclusión que:
- si se usa el primer algoritmo, el más ingenuo, se tienen muy pocas chances de resolver el juego
- si se usa el segundo esquema de las configuraciones, el sistema probabilístico, puede resolver el juego un 20% de las veces
- si se usan trucos extras (trucos finales, les llama Li), se puede tener hasta el 50% de éxito.
Li ha puesto su código a disposición de todos aquí.
Referencias: