Genetic Madness: Hide & Seek

Hace un tiempo vengo desarrollando (de gusto, no es que el mundo lo necesite) un framework de Algoritmos Genéticos (GA, por sus siglas en inglés) en Python. Si mal no recuerdo, lo empecé a armar estando en India, ya que lo necesitaba para el trabajo que estaba haciendo allá.

Para los que no sepan qué corno son los GA (y no fueron lo suficientemente curiosos para abrir el link a wikipedia que puse antes), la idea básica es que es un método de optimización algorítmico basado en la selección natural darwiniana. Uno opera sobre una población de soluciones a un problema, selecciona los más aptos (usando una función de fitness que nos dice qué tan buena es una solución), y los combina para obtener una nueva población, agregando alguna que otra mutación cada tanto para hacerlo más divertido :P. Con el correr de las generaciones simuladas, los individuos tienden a aumentar su aptitud (esto es, son mejores soluciones para nuestro problema!).

Hace aproximadamente un mes leí un gran libro referido al tema, escrito por David Goldberg, lo cual me dio un mejor fundamento teórico para mejorar el framework. Tuve ganas de hacer algo así como un juego, muy simple, que use los conceptos de GA, para poder enseñarle a alguien que no tiene idea de programación cómo opera un algoritmo genético. No se me ocurrieron muchas aplicaciones divertidas de GA como para llegar a llamarlas juego, pero uno de los experimentos que hice me pareció interesante como para compartirlo en el blog. La idea básica del programa es la siguiente:

Usando pygame, crea mini ventanitas de distintos colores (sin bordes ni "header", solo cuadraditos de colores). Al clickearlas, se cierran, y es como si el usuario "matara" esa ventanita. Un algoritmo genetico evoluciona la posicion y el color de las ventanitas, donde una ventanita se considera más apta que otra si  perduró más tiempo en el desktop sin ser clickeada. Cada generación dura hasta que no quedan más ventanitas vivas, tras lo cual se reinicia el ciclo (la nueva población de ventanitas se obtiene usando los métodos de selección, mutación y crossover típicos en los algoritmos genéticos).

El resultado: el comportamiento emergente es que las ventanitas se esconden en los iconos del escritorio y se mimetizan con tu desktop (tienden a tener los colores de tu background). Esto quiere decir que mientras más jugás los colores más tienden a ser los de tu background, por evolución artificial... no sé si me expliqué bien pero en este screenshot se ve: (acá está la versión grande)

Probé con varios tipos de fondos de pantalla, pero usando un color simple se ve más claramente. Fue divertido ver como, partiendo de una población inicial de ventanas ubicadas al azar y con colores totalmente aleatorios, de a poco se tendía a que las ventanas imiten el color wallpaper (haciéndolas más difíciles de ver) y se ubiquen en los bordes (llamando menos la atención).

El experimento es muy simple y podría ser refinado de infinitas maneras, pero me pareció una linda forma de mostrar cómo actúa la selección "natural" en cualquier ambiente en el que haya variación y presión sobre los individuos.


Por si a alguno le interesa, acá está el proyecto open-source del framework, actualmente en un muy temprano estado de desarrollo. Pueden bajarse el código de ahí y correrlo en sus máquinas... Y si alguno quiere colaborar con el proyecto no dude en contactarme!

Saludos,
Manuel

Resultados mini-comptencia: "Feudalismo"

Bueno, terminó la primera mini-competencia de programación!

Hubieron 11 estrategias inscriptas, pertenecientes a 3 concursantes.

Acá está la tabla de posiciones luego de los 80 años de simulación:

1. RunnerUpFeudalSimulation, con 10013.33 piezas de oro, de Santi
2. FFBCPN1, con 7734.44 piezas de oro, de Esteban, empate con 3.
3. ReallyPreventiveFeudalSimulation, con 7734.44 piezas de oro, de Santi
4. FFBCPN3, con 7609.16 piezas de oro, de Esteban
5. PreventiveFeudalSimulation con 7416.11 piezas de oro, de Santi
6. FFBCPN4 con 7303.61 piezas de oro, de Esteban
7. FFBCPN2 con 6943.88 piezas de oro, de Esteban
8. Modadicto Aleatorio con 6743.33 piezas de oro, de Marcos
9. FeudalSimulation, con 6526.11 piezas de oro, de Santi
10. BaseFeudalSimulation, con 5987.77 piezas de oro, de Santi
11. Modadicto, con 5987.77 piezas de oro, de Marcos

Y también les dejo el detalle de cuántas familias eligieron qué castillo en cada año. Felicitaciones y gracias a todos los participantes, y un fuerte aplauso para Santi, el indiscutido* ganador!


A mi me divirtió mucho hacer esto, espero que haya sido divertido para ustedes participar. Me hubiera gustado que hayan más participantes, pero bueno, esperemos que en el próximo haya mejor convocatoria. Además, sé de varias personas que llegaron a implementar una solución pero no la presentaron en el concurso. A ellos les digo: Anímense a presentarla! Ni que fuera algo importante este concurso!

* digo indiscutido porque de curiosidad corrí el torneo alrededor de 10 veces más, y en todas las corridas la estrategia ganadora fue RunnerUpFeudalSimulation. Una verdadera estrategia campeona!

Otro dato curioso: corrí varias simulaciones extra agregando una estrategia que elegía siempre una ciudad al azar, y salió siempre más o menos en el 5to o 6to puesto. Estos dos últimos análisis me sacaron la duda de que el problema sea demasiado librado al azar, y que dependiendo de la corrida los resultados pueden ser muy diferentes. Lo que queda a determinar es qué tanto depende el resultado de la cantidad de participantes, o de qué estrategias forman parte. Digamos, ¿qué tan caótico es el juego? Si se agrega UNA estrategia al sistema, los resultados cambian mucho?


Los que tengan ganas (especialmente los participantes) comenten dejando qué análisis hicieron del problema y todo lo que hayan descubierto que les parezca interesante. Gracias de nuevo a todos!

Saludos,
Manu

Mini-Competencia de programación: Feudalismo

Hoy, volviendo de la facu, me quedé casi literalmente sin plata encima (tenía nada más ni nada menos que 15 centavos en la billetera), así que tuve que caminar desde el tren a casa en vez de tomarme el bondi. Durante esa caminata se me ocurrió hacer esta competencia.  Y quizá cada tanto organice más de estas mini-competencias, dependiendo de la respuesta que tenga.

Estuve pensando un rato los detalles del problema, pero lo que más tiempo me llevó es pensar cómo hacerla accesible a la mayor cantidad de gente posible. Al final se me ocurrió cómo hacerlo independiente del sistema operativo e independiente del lenguaje de programación. Casi lo limito a Java para hacerme la vida más fácil al evaluar soluciones, pero sabía que muchos iban a salir corriendo jaja. En fin, vamos al problema:

Supongamos que sos el jefe de una familia campesina en la edad feudal. Estás en una zona donde hay 2 castillos, pertenecientes a los señores feudales A y B. Ambos son señores feudales muy bondadosos, por lo que aceptan a cualquier familia que se quiera unir a su feudo, prometiendo pagarles a todas distribuyendo uniformemente una parte de sus ingresos. El señor feudal A gana 700 piezas de oro por año, y el B gana 300 piezas de oro por año. Esto es independiente de la cantidad de familias pertenecientes al feudo de cada señor. Al final de cada año, el señor feudal divide sus ganancias equitativamente entre todas las familias que le fueron leales ese año, y les da la opción de quedarse o de marcharse. 

Así, si hay 10 familias trabajando en el feudo del señor A y 3 en el feudo del señor B, a fin de año las que están con el señor A ganarán 70 piezas de oro cada una, y las que están con el señor B 100.

El objetivo es hacer un programa que decida a qué feudo ir cada año buscando maximizar las piezas de oro ganadas luego de 80 años. Los únicos datos con los que se cuenta en cada año es  la cantidad de familias en cada feudo del año pasado.

Especificación del programa a realizar:

1. Se puede usar cualquier lenguaje de programación mientras se pueda compilar y correr en Linux.
2. Para la simulación, las únicas familias participantes serán los programas que envíen los concursantes, por lo que la cantidad de familias se mantendrá constante durante los 80 años (lo que varía es en qué feudo está cada familia cada año).
3. El programa debe respetar estrictamente un protocolo basado en entrada/salida. Al comenzar su corrida, debe imprimir en salida estándar una línea con un único carácter indicando en qué castillo se desea empezar(una ´A´ o una ´B´). Luego, sucesivamente, debe leer una línea de entrada estándar de la que recibirá los datos de la simulación y volver a outputtear una línea con un único carácter indicando la opción para el año siguiente. La línea de datos que recibirá serán 2 numeros enteros separados por un espacio que indican la cantidad de familias en el castillo de A y la cantidad de familias en el castillo de B, respectivamente.
4. Notar que los intercambios input/output son en forma interactiva. El programa debe leer los datos, escribir su opción, luego vovler a leer los datos, y escribir su nueva opción, sucesivamente, hasta terminar los 80 años (no es necesario que el programa termine al pasar los 80 años).
5. Ejemplo de intercambio input/output:
   A
   
   5 2
   A
   3 4
   B
   1 6
   A
   etc...
6. Un programa simple en python que descarta los datos de la simulación y, empezando por el castillo A, va siempre cambiando de castillo, podría ser este: ver código. (sketch, sin testear)
7. Para evitar problemas en la simulación, sería bueno que luego de imprimir a salida estándar cada línea con la decisión, el programa se ocupara de flushear el buffer de salida (en caso de existir). Notar que aunque el programa no usa los datos de la entrada, igualmente debe leerlos para respetar el protocolo input/output.

Bueno, creo que eso es todo. Espero que se haya entendido. Para participar manden su código fuente a feudalismo@7cerebros.com.ar. Cada participante puede mandar hasta 5 estrategias diferentes. En el mail incluir tu nombre, un nombre para la estrategia, y de ser necesario instrucciones para compilar y correr el programa, o cualquier aclaración que se crea necesaria. Si tenés ganas, también dejá un comentario en este post avisando que estás participando para que los demás lo sepan. 

Otra opción: si te da fiaca hacer el programa o no tenés conocimientos de programación, podés mandar por mail una explicación de la estrategia y yo hago el programa!

En una semana, el 24/7/2010, si se llega a una buena cantidad de estrategias participantes, voy a correr la simulación, y postear los resultados. El martes 27/07/2010 voy a correr la simulación y postear los resultados. La estrategia que consiga más monedas de oro luego de los 80 años se gana un gran aplauso (?). Gracias!

saludos,

Manu

pd: cualquier pregunta dejen un comentario así la aclaración le sirve a todos!