Sistemas Clasificadores

Los sistemas clasificadores son una fusión entre los algoritmos evolutivos, el aprendizaje por refuerzo y el supervisado. Se conocen como Learning Classifier Systems. El viernes pasado aproveché la reunión del grupo para presentar una breve revisión histórica y dar detalles sobre quizá el algoritmo más importante introducido en este campo, el eXtended Classifier System o XCS de Wilson.

Básicamente, el algoritmo busca mediante evolución genética y aprendizaje un conjunto de reglas que modelen la solución a un problema donde existe recompensa. Las reglas se componen de una condición y una acción. La población de reglas representa para cualquier condición dada, cual será la mejor acción. Esto se consigue asociando al espacio de entrada una predicción de la mejor recompensa futura obtenida para cada acción posible.

Entonces, dado un estado que representa el entorno, se buscan las reglas cuya condición coincide, y de ellas se toma la acción que ofrece mejor recompensa futura.

La tarea no es fácil, los algoritmos formales de aprendizaje por refuerzo, necesitan a priori un conocimiento determinista de las posibles entradas y las transiciones resultantes de las acciones, dejando poco o nada para la búsqueda y aplicación de generalización.

Con XCS este problema se resuelve introduciendo algunos ajustes a la componente genética. La idea general es básicamente repartir los recursos (reglas) para que representen todo el espacio con la mayor precisión y generalización posible. Como no es algo que se pueda resumir en unas pocas líneas, aquí os dejo la presentación:

Modelando el conocimiento de un experto en Unreal Tournament (CEDI 2013)

En concreto, hemos presentado el artículo “Modelling Human Expert Behaviour in an Unreal Tournament 2004 Bot” dentro del Primer Simposio Español en Entretenimiento Digital, incluido dentro del CEDI 2013.

Y vosotros diréis, ¿por qué un artículo en inglés en un congreso español?. Pues porque los artículos en inglés que sean seleccionados podrán enviarse a un número especial de la revista Entertainment Computing (Elsevier). A ver si hay suerte. :D

El trabajo presenta el diseño de un bot (jugador autónomo) para jugar a Unreal Tournament 2004 (UT2K4). Dicho bot ha sido creado por Francisco Aisa y Ricardo Caballero, modelando el conocimiento y comportamiento de un jugador experto en dicho juego (el primero de ellos ;D).

La presentación podéis verla en:

Que la disfrutéis (y nos citéis, claro). :D

Saludos.

Unreal Expert Bots at IWANN 2013

Last week there was held IWANN 2013 at Tenerife, an international conference mainly devoted to researches inside the neural networks scope. In it, Antonio Fernández Leiva, Raúl Lara and Me organized the Special Session on Artificial Intelligence and Games.

There were five works in the session, one of them “Designing and Evolving an Unreal Tournament— 2004 Expert Bot“.

It describes the designing and improvement, through off-line (not during the game) evolution, of an autonomous agent (or bot) for playing the game Unreal Tournament 2004. This was created by means of a finite state machine which models the expert behaviour of a human player in 1 vs 1 deathmatch mode, following the rules of the international competition.

Then, the bot was improved by means of a Genetic Algorithm, yielding an agent that is, in turn a very hard opponent for the medium-level human player and which can (easily) beat the default bots in the game, even in the maximum difficulty level.

The presentation can be seen at:

Moreover, you can watch one example of the evolution in the following video:

Finally, the Unreal Expert and Genetic bot’s source code are available at https://github.com/franaisa/ExpertAgent

Enjoy them. ;)

Super Mario autonomous agents at LION 2013

Recently, inside the last LION 7 (2013) conference (Special Session on Games and Computational Intelligence) there was presented the paper entitled “FSM-Based Agents for Playing Super Mario Game”.

It describes the implementation and test of an autonomous agent which can play Super Mario game better than an expert user can do (in some trained levels).
It is build starting from a Finite State Machine and applying an Evolutionary Algorithm.

The presentation is:

You can watch one example of the obtained agent playing a game here:

Enjoy it. ;)

Science and Videogames Tutorial

Last 16th November, inside the GAME-ON 2012 Conference, I presented (with Antonio Fernández Leiva) a tutorial entitled “Computational Intelligence applied to videogames; past, present and future”.

It was a two parts tutorial, being the first one (mine) devoted to introduce the relationship between science and videogames, describing the integration of Computational Intelligence in this scope.

My part presentation can be seen here:

Enjoy it! :D

Genebot (again) in CIG2012

Adaptative bots for real-time strategy game via map characterization(A.Fernández-Ares, P.García-Sánchez, A.M. Mora, J.J Merelo) is the title of the paper we have presented in CIG2012. In this work we use Genetics Algorithms for improve an adaptative bot for play (and win!) to planet wars. We made it through the characterization of the maps, studing those features (calculated quickly) that influence in bot behavior:  

The abstract:

This paper presents a proposal for a fast on-line map analysis for the RTS game Planet Wars in order to define specialized strategies for an autonomous bot. This analysis is used to tackle two constraints of the game, as featured in the Google AI Challenge 2010: the players cannot store any information from turn to turn, and there is a limited action time of just one second.They imply that the bot must analyze the game map quickly, to adapt its strategy during the game. Based in our previous work, in this paper we have evolved bots for different types of maps. 

Then, all bots are combined in one, to choose the evolved strategy depending on the geographical configuration of the game in each
turn.
Several experiments have been conducted to test the new approach, which outperforms our previous version, based on an off-line general training.

Presentation:

Dealing with Noisy Fitness in the Design of a RTS Game Bot

This paper is a part of my Final Degree Project and it’s the result of our participation in the Google AI Contest of 2010. It’s also my first presentation in an conference, and the first time in English. In this paper we talk about the design of a bot that can play (and win) to the game Planet Wars. In this post we can read the rules of the contest and the game.

In this paper, we study the impact of the noisy fitness in the desing of the bot, because the choose of a bad fitness can make useless the genetic algorithm.

The presentation can be found here:
http://www.slideshare.net/antaress/dealing-with-noisy-fitness-in-a-rts-game-bot-design

This paper was accepted in the EvoGame and was nominated for the best paper.

MorAnts. Mi primera investigación ‘rentable’

Pues si. :D

Recientemente y compaginando, por una parte el I Hackatón del reto de inteligencia artificial de Google en la UGR, propuesto por la Oficina de Software Libre de dicha universidad, y por otra el Google AI Challenge 2011, me decidí a participar en ambos ‘concursos’, creando un bot capaz de jugar de forma autónoma (y combatir contra otros rivales) al juego ANTS, implementado para la ocasión por el Computer Science Club de la Universidad de Waterloo.

Grosso modo, se trata de un juego de estrategia en tiempo real en el que debemos dirigir a una serie de hormigas en mapas generalmente laberínticos, con el objetivo de eliminar a todas sus rivales, principalmente los nidos de los que salen. Para ello deberemos buscar comida (para generar nuevas hormigas), sortear obstáculos en el mapa y aplicar reglas algo complejas en los enfrentamientos, para los que es conveniente moverse en grupos.

En la siguiente presentación, que yo mismo hice durante la introducción a dicho Hackaton, se pueden ver los pormenores de la competición:

En definitiva, a pocos días de la finalización del plazo de ambos concursos, diseñé un bot con una sencilla máquina de estados finitos, en la cual se tenían 4 estados básicos. A modo de resumen:

  •  Explorando -> estado en el que las hormigas se mueven de forma pseudoaleatoria, ya que según su ID (módulo 4) se mueven en una dirección, consiguiendo que éstas se agrupen al tiempo que exploran zonas diferentes del mapa.
  •  Ir hacia comida -> las hormigas se mueven hacia la unidad de comida más cercana.
  •  Ataque a enemigo -> todas las hormigas que lo vean se dirigen hacia un enemigo.
  •  Ataque a colinas -> todas las hormigas que la vean se dirigen hacia una colina enemiga.

En dichos estados se hacían varias consideraciones, como evitar obstáculos (con movimientos simples) o evitar el choque entre hormigas propias (que supone la ‘muerte’ de las mismas).

El bot lo bautizé como MorAnts (original, ¿verdad? :D) y lo liberé con una licencia GPL en la Forja de Rediris, dado que era requisito imprescindible del concurso de la OSL-UGR. ;)
El paquete con los fuentes, así como varios ejemplos de uso y el juego ANTS, se puede decargar -> aquí <-

Por falta de tiempo (en gran parte debido a los requititos de mi nenita, Julia :)), no pude hacer una mejor aproximación, dejando para un futuro mejoras (sustanciales) de los estados, como por ejemplo: búsqueda de caminos mínimos, rodear obstáculos, evaluar enemigos antes de atacar (número, agrupación), etc.

Además, como ‘buenos’ investigadores que somos, queda pendiente la aplicación de técnicas de las que a nosotros nos gustan, es decir, cosicas de Soft Computing (Algoritmos Genéticos, Algoritmos basados en Colonias de Hormigas o Redes Neuronales, por ejemplo). :D

Finalmente y yendo a la parte pragmática del trabajo, el caso es que aún siendo mi bot bastante ‘regulero’ (en comparación con otros del AI Challenge de Google), conseguí ganar el concurso propuesto por la Oficina de Software Libre de la UGR, cuyo premio consistía en un cheque regalo para coger ‘material’ en una tienda de informática. :D

Para los interesados diré que mis regalos fueron un e-reader y un disco duro multimedia, Yuhuuuuuu! :D

Así da gusto investigar. ;)

Optimización evolutiva de bots para el juego Planet Wars

Aquí está la presentación del trabajo que da título al post. Es una versión actualizada del trabajo que se presentó en el IWANN 2011, así que os refiero primero a esa versión por si no estáis al tanto.
For information about an early version of this work (in English) please check here.

Estudio de un Operador de Mutación para Algoritmos Genéticos Basado en la Teoría de la Criticalidad Auto-Organizada

Our studies on the sandpile mutation operator were extended, presented at MAEB2012 and published in the proceedings (in spanish). The abstract:

La mutación montón de arena es un operador para Algoritmos Genéticos basado en un modelo de Criticalidad Auto-Organizado con el mismo nombre. El operador ha sido desarrollado con el objetivo de resolver problemas con función objetivo variable. Este artículo propone un estudio del operador y la optimización de su desempeño, experimentando diferentes estrategias que conectan el modelo auto-organizado y el Algoritmo Genético. Las pruebas sobre el algoritmo se desarrollan con un gran conjunto de problemas dinámicos, diseñados con un generador de problemas a partir de funciones-base no dinámicas. Las mejores configuraciones del algoritmo son comparadas con dos AGs recientemente propuestos para optimización dinámica. Demostramos que un AG con el operador de mutación montón  de arena es eficiente para el conjunto de pruebas que es propuesto.