http://aichallenge.org/

Antonio M. Mora García

Grupo GENEURA. Depto ATC.

Qué es el Google AI Challenge Es una competición internacional (mundial) en la que

puede participar cualquiera.

Está ‘patrocinada’ por Google, aunque la organizan otras entidades como universidades o grupos de amiguetes (ésta la organiza el grupo de ciencias de la computación de la Universidad de Waterloo).

El objetivo es crear un bot (jugador autónomo) que se comporte de forma ‘inteligente’ y sea capaz de ganar a los bots diseñados por los demás participantes.

REGLAS GENERALES: - la fecha límite de envío de bots es el 18 de Diciembre

- se pueden enviar versiones y revisiones hasta el día antes de la competición

- compiten todos contra todos (durante una semana) y se hace un ranking general (algoritmo TrueSkill de M$)

- restricciones de los programas: no se pueden guardar ficheros de una partida a otra, ni usar hebras

Juego ANTS (1) Juego de estrategia en tiempo pseudo-real (turnos de

muy poco tiempo) para varios jugadores en el que debemos controlar a un grupo de hormigas.

Tenemos uno o más hormigueros y el objetivo es arrasar los de los demás jugadores y eliminar a todas sus hormigas (¡¡¡NO HAY PRISIONEROS!!!).

La hormigas se mueven en

un mapa/rejilla toroidal.

El agua marca obstáculos

que no pueden atravesar.

Cada hormiga puede ‘percibir’ parte del entorno que la rodea, obteniendo información de: - celdas con agua (obstáculos) - hormigas que se ven (incluyéndola a ella) - comida - hormigueros (propios o enemigos) - hormigas muertas (en el último ataque)

Juego ANTS (2)

Cada cierto tiempo se van depositando unidades de comida en el mapa (en lugares aleatorios, pero simétricos a todos los jugaores).

Si una hormiga ‘come’ una unidad, automáticamente saldrá una nueva hormiga del hormiguero.

Hay un número máximo de turnos por partida para evitar que se alarguen indefinidamente.

Fases en cada turno:

- se mueven todas las hormigas

- se atacan las que están dentro del radio de acción

- se arrasan los hormigueros si hay enemigos cerca

- se come

- aparecen nuevas hormigas al comer

Juego ANTS (3) La puntuación depende del número de hormigueros

que tenga el jugador. Comienza con 1 punto por hormiguero y ganará 2 puntos por arrasar el de un rival. Si pierde uno de sus hormigueros, perderá un punto.

Se obtendrán 2 puntos extras por cada hormiguero que permanezca al finalizar la partida.

Los combates entre hormigas son difíciles de resolver, pero grosso modo, un combate lo gana quién más hormigas tenga en las celdas colindantes. En los enfrentamientos 1 contra 1, se eliminarán las dos hormigas.

Una hormiga arrasará un hormiguero si puede alcanzarlo en la fase de ataque.

El juego terminará de forma automática si: - las hormigas no son capaces de comer - las hormigas no arrasan hormigueros - sólo queda un bot - se llega al límite de turnos

Juego ANTS (Mapas de ejemplo)

El Bot (entradas) Al principio el bot recibirá información del mapa

(tamaño, máximo número de turnos y tiempo por turno).

En cada turno, el bot recibirá datos de las celdas que pueden ver sus hormigas.

El bot indicará sus movimientos y, una vez terminado el turno, recibirá datos de la partida como resultado.

El mapa se trata como una matriz de texto con caracteres especiales, dónde cada carácter representa una celda y su contenido.

El Bot (salidas)

En cada turno, la salida indicará, para cada hormiga, un movimiento en el sentido: norte, sur, este u oeste.

La hormiga se moverá (si es posible) una celda en dicho sentido.

Si se envían dos hormigas a la misma celda, ambas morirán (aunque sean del mismo jugador).

Si el bot falla o tarda demasiado, las hormigas permanecerán quietas durante ese turno.

Los datos se pasan al motor del juego como estructuras u objetos con el mapa y un array con las hormigas.

Lista de Starter PackagesHay para casi todos los lenguajes de programación, pero algunos no implementan ciertos elementos.

Trabajar con ANTS

En la página de la competición se puede ver un completo tutorial de cómo instalar el entorno, probar ejemplos, algunos consejos y trucos, etc.

http://aichallenge.org/ants_tutorial.php

Para los más impacientes se ofrece una ‘guia’ de inicio rápido, consistente en bajarse el paquete de ejemplo que queramos, crearnos una cuenta y subirlo tal cual… de esa forma empezaremos a aparecer en los rankings (aunque no en muy buena posición, me temo).

Finalmente se ofrecen herramientas para visualizar combates (que se pueden grabar) y probar nuestro bot de forma local. El motor está implementado en Python, por lo que habrá que instalar el intérprete del lenguaje.

Algunas estrategias

Camino mínimo: será recomendable implementar un método de búsqueda de camino mínimo para llegar en pocos movimientos a una zona que nos interese (con mucha comida, lejos de enemigos, un objetivo a atacar).

Movimiento en grupo: dada la forma de resolver los combates, es una buena idea intentar que las hormigas se muevan formando grupos, en lugar de por separado.

Especialización de Hormigas: tener distintos tipos de hormigas puede facilitar las tareas (exploradoras, recolectoras de comida, guerreras, guardianas del hormiguero).

Posibles algoritmos a utilizar

Aunque lo habitual es crear una ‘inteligencia scriptada’, es decir, crear una serie de reglas predefinidas en base a nuestra propia experiencia, es posible aplicar diversos algoritmos para el aprendizaje de la IA, tanto durante el juego (on-line), como previamente a él (off-line).

Algunos métodos que se pueden considerar son: - OCH Optimización Basada en Colonias de Hormigas. ¿Adivináis por qué?

- Algoritmos Genéticos para evolucionar parámetros a considerar en las reglas

- Programación Genética para diseñar el conjunto de reglas.

- PSO Optimización de enjambre de partículas. Para diseñar los movimientos en grupo.

- Redes Neuronales para predecir enfrentamientos, por ejemplo.

¡¡¡Al Ataque!!!