25 de Noviembre, 2010

Google AI Challenge: Planet Wars

Ayer estuve jugando un rato con el Google AI Challenge, y al final hasta voy a participar (por lo pelos, la inscripción acaba el próximo día 27), para no ganar y ver cómo se comporta mi bot en el gran torneo ;).

Existen diferentes juegos de este tipo, en los que se definen unas reglas y un sencillo interfaz en modo texto independiente del lenguaje de programación (los distintos kits implementan la comunicación con ese interfaz). Habitualmente contamos con un simulador que implementa las reglas y se comunica con los jugadores para ejecutar la partida, y alguna forma de visualizar el resultado con más o menos gracia.

Ya había tenido alguna experiencia hace años con Robocode (en Java, lo promocionó IBM por el año 2001), pero era demasiado complicado para mi (análisis estadístico, redes neuronales, ... ¡si apenas conseguía detectar al tanque enemigo!).

Sometimes you have to roll a hard six

No sé si es porque estamos disfrutando Battlestar Galactica, pero el juego propuesto para esta edición de la Google AI Contest me ha parecido muy atractivo y asequible.

Visor de partidas
Visor de partidas en Java (flotas van y vienen)

Jugamos en un escenario en el que empezamos en un planeta, nuestro enemigo en otro, y tenemos una serie de planetas neutrales.

Los planetas no neutrales incrementan su contingente en 5 naves por turno, y nuestra principal acción es mandar flotas con el número de naves que deseemos, desde un planeta a otro. Si el planeta destino es nuestro se comporta como un refuerzo, y sino... hay un combate (sencillo: el que más naves tiene, gana).

El objetivo es eliminar al contrincante, con las restricciones de que nuestro turno no puede exceder 1000 milisegundos, no podemos escribir ficheros en disco (¡nada de aprender de cada batalla jugada!) y tampoco está permitido crear nuevos procesos ni hilos.

Las reglas son sencillas y la clave al final es el tiempo, pero solo si implementamos estrategias muy complejas (no es mi caso, me sobran muchos milisegundos :P).

Mi bot conseguirá algunas victorias, desde luego, pero no le he dedicado suficiente tiempo a los puntos clave:

  • Estudiar el problema a fondo, evaluando estrategias. Algunas ideas funcionan en unos mapas, otras con determinados contrincantes. Hay que adaptarse a cada caso.
  • Emplear los algoritmos necesarios para optimizar las estrategias en el tiempo permitido. Yo no tengo en cuenta la distancia entre planetas, y calcular ese dato puede ser muy costoso (aunque solo sería necesario hacerlo una vez, los planetas no se mueven).
  • Tomarse el juego en serio ;). Saber algo de inteligencia artificial puede ayudar también.

Desde luego hay jugadores que se lo han trabajado mucho, incluso hay varias entradas que dicen implementar estrategias basadas en programación genética, pero si lo enfocamos como pasar un rato entretenido programando, tampoco hace falta más que probar un par de ideas y ver como nuestras flotas aplastan al enemigo ;).

Hay kits para diferentes lenguajes y todos incluyen simulador y visor (en Java, al menos el que he probado yo). Yo he utilizado Python para mi bot (aunque no sé si es buena idea, porque usan la versión 2.5 y mi Fedora 14 ya viene la 2.7, lo que puede hacer que empleemos algo que no va en la versión vieja :S), y la velocidad es más que suficiente (no hace falta irse a por C o C++ para tener resultados).

No es necesario inscribirse para jugar en casa, pero si te animas... aún estás a tiempo de enviar tu bot al concurso ;).

Actualización: acerté en mi pronóstico de no ganar :P. Al final, puesto 2683 de 4617.

En las anécdotas estadísticas comentar que España quedó sexto (yo jugué por UK, para no bajar la media :P), y que hay 5 españoles entre los 100 primeros. ¡Enhorabuena!

El ganador ha utilizado tecnología alienígena secreta, y hay un post explicándolo todo: Planet Wars Post-Mortem.

Anotación por Juan J. Martínez, clasificada en: python, programming.

Hay 2 comentarios

Gravatar

Si es que me dejo llevar, lo sé, pero nunca había participado en un reto de programación y esta vez Juanjo me ha puesto los dientes largos, así que antes de lo que pensaba ya estaba inscrito y con el starter pack descargado para empezar a analizar que era eso del Google AI Challenge.

— trackback manual ;)

por r0sk, en 2010-11-26 10:02:54

Gravatar

La ilusión es una, la realidad otra muy distinta (lamentablemente!).

Lo digo porque, en general, me están haciendo polvo… y en particular hasta hay veces que pierdo por puntos (en la web ahora mismo el límite son 200 turnos).

Además no nos queda tiempo para rumiar qué estamos haciendo, así que nos conformaremos con ser buenos sparrings :D

por Juanjo, en 2010-11-26 10:11:36

Los comentarios están cerrados: los comentarios se cierran automáticamente una vez pasados 30 días. Si quieres comentar algo acerca de la anotación, puedes hacerlo por e-mail.

Algunas anotaciones relacionadas: