1 oct. 2014

AI MasterMind [Python]

Tras mucho tiempo sin publicar nada nuevo, traigo de mi propia mano un nuevo proyecto donde poder practicar vuestras dotes de programación en Python, así como poner a prueba algoritmos de inteligencia artificial aplicados al famoso juego de MasterMind.

Para el que no lo conozca, MasterMind es un pequeño y sencillo juego de mesa que consiste en tratar de adivinar, en el menor número de pasos (a ser posible), una contraseña codificada por colores.


Tablero de MasterMind (la contraseña se oculta en la parte inferior).


En lugar de limitarme a implementar el juego, he tomado como base la idea general del juego y la he llevado más allá, dando la posibilidad de incrementar el tamaño de las contraseñas e incluso añadiendo un modo multijugador.

Mi idea no es que los jugadores humanos jueguen MasterMind en sí, sino que jueguen a desarrollar algoritmos más o menos complejos y los pongan a prueba contra otros algoritmos creados por otras personas. Una buena forma de mejorar las dotes de optimización y uso de estructuras de datos básicas, así como de aprender o refrescar los conocimientos en Python.

El juego difiere ligeramente del modelo original. A continuación podréis ver la lista de características que trae consigo:
  1. Capacidad para 1 o más jugadores IA.
  2. Configuración del tamaño de contraseña (nº de dígitos)
  3. Configuración del rango de valores que pueden tomar los dígitos.
  4. Dos modos de juego: Equilibrado y Aleatorio.
  5. Monitoreo y almacenamiento de estadísticas de los jugadores.
  6. Control de tiempos de ejecución, intentos y victorias.
  7. Posibilidad de realizar N partidas consecutivas. 


El juego está compuesto por los siguientes ficheros:

Lista de ficheros del proyecto.

main.py: código fuente principal del juego. Posee todas las funciones de configuración del mismo (tamaño de las contraseñas, configuración de los jugadores, modos de juego, etc) además de ser el encargado de dibujar en pantalla la interfaz.

Incluye los siguientes controles de teclado para manipular parte de la ejecución del juego sin tener que editar algunas variables:
  • Q: finaliza la aplicación.
  • R: resetea las estadísticas y reinicia el juego (como si acabase de iniciarse).
  • S: inicia la partida y se para cuando alguien gana.
  • A: igual que el anterior, pero finaliza cuando se ejecutan N partidas.
  • C: cambiar entre modo de juego Equilibrado y Aleatorio.
  • D: cambiar entre modo de visualización ASCII y Entero (solo la salida por pantalla).

Para agregar nuevos jugadores o eliminar otros tantos, primero hay que importar el fichero correspondiente a la IA (import ai_player_N) y luego agregarlos como en las siguientes líneas:

Código fuente de main.py: añadiendo nuevos jugadores.


aimastermind.py: incluye la clase AiMasterMind, que se encarga de implementar las reglas de juego así como funciones para mostrar las estadísticas de los jugadores y la partida. Es el núcleo mismo del juego.


ai_player_N.py: códigos fuente que implementan las IAs de cada jugador. Es necesario implementar tantos ficheros como jugadores quieran jugar, y luego añadirlos a la lista de jugadores en main.py como se ha mostrado previamente. Incluyen dos métodos a implementar:
  • generarSolucion(pass_len, digit_size): éste método es ejecutado cuando el gestor de juego solicita que el jugador i (el que posea el turno) dé una posible solución. El método debe retornar obligatoriamente un vector de tamaño pass_len con valores enteros cuyo máximo valor puede ser digit_size.
  • recibirRespuesta(respuesta, finalizado): éste método es invocado justo después de ser ejecutado el anterior y se encarga de recibir y capturar el vector de respuesta del gestor de juego. También permitirá a las IAs saber cuando ha finalizado una partida, que en ese caso, respuesta será una lista vacía y finalizado tomará el valor True. El vector de respuesta tiene el siguiente formato:

    [ 0 , 1 , 2 , 2 , 0 ]

    Su longitud es del mismo tamaño que el de la contraseña e indica, para cada dígito d, si la solución propuesta ha acertado, fallado o bien es erronea.

    Veámos ésto con un ejemplo:

    Supongamos que tenemos una contraseña como la siguiente: [1,2,4,1,5] y que nuestro algoritmo ha propuesto la solución [1,1,3,5,1]. El resultado que recibiríamos sería [0,1,2,1,2], donde 0 significa acierto, 1 es un semifallo (no hemos acertado pero el dígito está en otra posición) y 2 es un fallo completo (no existe ese dígito o bien hemos superado la cantidad existente en la solución, en el anterior ejemplo el tercer 1 de nuestra solución es un fallo de nivel 2 porque en la contraseña solo existen dos unos y el primero ya era un semifallo).

Resources: carpeta que contiene todos los recursos gráficos externos usados por el juego.


debug.bat: ejecutable por lotes usado para debuggear el programa y sus errores. Úsalo para probar tus algoritmos.


launcher.bat: ejecutable por lotes que lanza el juego y monitorea la ejecución almacenando los errores en un fichero error.log y las salidas del programa en game.log. Si se desean almacenar las estadísticas de las partidas realizadas, usad éste ejecutable.


El aspecto de la interfaz es como el mostado en la siguiente captura:

Interfaz AiMasterMind con 4 IAs en modo Equilibrado.

En cuanto a los modos de juego existen por el momento solo dos:

  • EQUILIBRADO: modo de juego pensado para probar los algoritmos bajo las mismas circustancias de juego. Se genera una contraseña común a todos los jugadores, de forma que el algoritmo que logre descubrirla en un menor número de intentos gana. El orden de rotación parte del jugador 1 hasta el último.
  • ALEATORIO: similar al anterior, con la salvedad de que cada jugador tiene una contraseña diferente para descubrir (eso si, del mismo tamaño y con la misma variedad de dígitos). El orden de rotación se escoge aleatoriamente antes de comenzar la partida, reseteándose en cada juego. Aquella IA que descubra su contraseña en menos intentos gana el juego.

Como se puede apreciar, al lado de los nombres de cada jugador hay un número entre paréntesis. Dicho valor es una estimación de la posición actual respecto al resto de jugadores, y viene dado según el % descubierto de su contraseña.



Puedes descargar el proyecto y comenzar a jugar contra tus amigos o alumnos del siguiente enlace en dropbox:


Es necesario tener instalado en el equipo Python 2.7.8 y las librerías PyGame 1.9.1.

Cualquier duda puedes comentármela o bien por correo electrónico o bien en la sección de comentarios de ésta entrada.


Ejemplo de simulación de enfrentamiento entre 7 IAs:



Para ese enfrentamiento se han usado contraseñas de longitud 1000, donde cada dígito puede tomar hasta 288 valores diferentes. El resultado final tras 100 partidas consecutivas fué una aplastante victoria de mi algoritmo BIS (Búsqueda Inteligente Selectiva), la cuál utiliza un sistema similar al divide y vencerás en otros algoritmos pero aplicado a éste problema.




Saludos.

No hay comentarios:

Publicar un comentario en la entrada