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.

Pool based evolutionary algorithm presented in EvoStar 2012

This is the first internationally published paper (it was previously published in a Spanish conference of a series that deals with a system, intended for volunteer computing, that uses a pool for implementing distributed evolutionary algorithms. The basic idea is that the population resides in a pool (implemented using CouchDB), with clients pulling individuals from the pool, doing stuff on them, and putting them back in the pool. The algorithm uses, as much as possible, CouchDB features (such as revisions and views) to achieve good performance. All the code (for this and, right now, for the next papers) is available as open-source code.
The paper was accepted in the first edition of EvoPar as poster, and mainly concentrates on studying the effect of different parameters on scaling and performance, and comparing it with a canonical GA. Here’s the poster

The paper Pool-Based Distributed Evolutionary Algorithms Using an Object Database is available from SpringerLink if your university subscribes to it. If it does not, please send us an email.

Using free cloud storage services for distributed evolutionary algorithms in GECCO 2011

Esta semana ha sido el GECCO en Dublin. Yo he asistido desde el jueves 14 hasta el sábado 16 y aunque no he podido ir a la totalidad del congreso si me ha dado tiempo a ver el ambiente general.
En este congreso he presentado el artículo titulado Using free cloud storage services for distributed evolutionary algorithms. Y la presentación la podéis encontrar en SlideShare.

En este artículo podéis encontrar cómo hemos usado Dropbox para crear un multicomputador que evoluciona un conjunto de islas que cooperan para resolver un Algoritmo Evolutivo Paralelo que actúa sobre dos problemas típicos de Computación Evolutiva (MMDP y 4-TRAP) y que, hasta el número de computadores donde lo hemos probado, es escalable puesto que los tiempos de evaluación de los individuos disminuyen a medida que añadimos nodos de computación al multi-computador.

Después de la presentación algunos de los asistentes realizaron algunas preguntas que os puedo aclarar por si os surge la duda. La primera era si todo el tráfico que se genera en la red que comparten los nodos del multi-computador llega al servidor de Dropbox para después distribuirse. Y la respuesta a esta pregunta es claramente “no”. Está claro que a la vista de los resultados de este artículo y el presentado en Nueva Orleans en CEC (Cloud-based Evolutionary Algorithms: An algorithmic study) Dropbox distribuye los datos primero a los ordenadores donde está sincronizado y después de eso al servidor de Dropbox.

Respecto a la segunda pregunta, estaba relacionada con el esquema de evolución de las islas y en el artículo podéis encontrar cómo está especificado con detalle. Una descripción general sería que cada isla evoluciona una población de individuos con un esquema generacional y un algoritmo evolutivo clásico con un operador de cruce uniforme y un mutador tipo flip-flop para codificación binaria.

From Emergence to Emergency (exit)

Despite the hotel’s firealarm, which forced us all to leave the room, out to the “pleasant” New Orleans’ weather, when I was on slide 12, I eventually finished the presentation of this paper in the 2011 Congress on Evolutionary Computation:

Fernandes, Isidoro, Barata, Merelo, Rosa, From Pherographia to Color Pherographia – Color Sketching with Artificial Ants

Abstract—Ant algorithms are known to return effective results in those problems that may be reduced to finding paths through a graph. However, this class of bio-inspired heuristics have raised the interest of the artistic community as well, namely of the artists that work on the blurred border between art and science. This paper describes an extension of an ant algorithm that, although has been designed as an edge detection tool and a model for collective perception, has also been used for creating artworks that were exhibited to a heterogeneous audience. The algorithm is a self-organized and stigmergic social insects’ model that is able to evolve lines along the contours of an image, in a decentralized and local manner. The result is the emergence of global patterns called pheromone maps. These maps – which were later named with the term pherographia – are grayscale sketches of the original black-and-white image on top of which the model evolves. This work goes beyond grayscale images and addresses colored pherographia, by proposing several image transformation and border selection methods based on behavioral variations of the basic algorithm.

From Pherographia To Color Pherographia

View more presentations from Carlos Fernandes

Parallel Ants at IWANN 2011

Some days ago we presented at the IWANN Conference our new work devoted to study the parallelization of Multi-Objective Ant Colony Optimization algorithms (MOACOs) following different schemes.

It was a very funny presentation (and very interesting, of course :D), because the slides included some CC memes. ;)

These are the slides:

The whole paper can be found here.

Enjoy them! ;)

About Game Bots and Ambient Assisted Living

Last week we were in IWANN Conference, held in Torremolinos (Málaga), presenting two different works. The first one is about evolving IA bots for playing games in the Google AI Challenge. The basic idea is to improve the parameters of a hard-coded bot. Results shown that the default parameters we thought are important may be not work so good, and we can learn a lot of emerging behavior of the trained bot.

Here is the presentation:

Citation is here

The second one, is about a project I was working in last year. It’s about Ambient Assisted Living, Context-awareness and other stuff like that. The presentation is not so awesome. It was presented in the satellite workshop IWAAL.

You can download the paper in Springerlink here.

Doing evolutionary algorithms with Dropbox

Why not use Dropbox as its name implies, as a box for dropping individuals that could be interchanged among different islands running evolutionary algorithms?
That’s exactly what we are doing in a series of papers that are being published and presented in IWDECIE, CEC 2011 and GECCO, in last-in, first-out order. This presentation is for the second, presented today in CEC.

Using dropbox for distributed evolutionary computation

View more presentations from Juan Julián Merelo Guervós

What we try to test in this paper is whether we can add a good number of computers (up to 4) without a saturation of the network (or of Dropbox itself), and whether there is a difference between wired and wireless. It so happens there is, but it gets smaller when you increase the number of computers.

Still many tests to to, but for the time being this looks promising. We’ll link the paper when it’s available. For the time being, if you’re interested just send us an email

Going a bit farther (and a bit faster) solving MasterMind using evolutionary algorithms

We left MasterMind last year in a good state using estimation of distribution algorithms; however, if we want to find a solution for higher dimensions (more colors, more pegs) we have to improve the number of evaluations. In this case we use something we call endgames; same as chess playing algorithms use a database of endgames for ending a game in a straightforward way, in MasterMind we can recognize a few occasions in which the search space is reduced drastically and it’s better either change the strategy or just change the search space. When we know the colors (that is, we obtain as many white+blacks as the length of the combination) the best is to just revert to exhaustive search over combination space; when the answer is 0 whites/blacks we can also exclude those colors from the search space and start, maybe with a smaller population.
This is what we do in the paper Improving and Scaling Evolutionary Approaches to the MasterMind Problem , which was presented a short time ago in the EvoGames workshop in Torino

During the presentation, Carlos Cotta and Carlos Fernandes played the game shown above.
Here’s the presentation, which you can download at ease. Picture credits are included in the notes.

The Sandpile Mutation Operator at Torino, Italy

Last thursday morning, at the Evo* congress, I was presenting our study on the mutation rates evolved by the Sandpile Mutation Operator, an alternative mutation scheme for GAs, specifically designed for Dynamic Optimization Problems, based on the Self-Organized Criticality Theory and the Bak-Tang-Wiesenfeld Sandpile Model.

[EuroGP'2011] A Peer-to-Peer Approach to Genetic Programming

Right today, April 28th, we have been presenting the paper “A Peer-to-Peer Approach to Genetic Programming” in EuroGP 2011  held in Torino, Italy within the Evo* conference series.  You can find below the abstract and the presentation of the work.

This paper proposes a fine-grained parallelization of the Genetic Programming paradigm (GP) using the Evolvable Agent model (EvAg). The algorithm is decentralized in order to take full-advantage of a massively parallel Peer-to-Peer infrastructure. In this context, GP is particularly demanding due to its high requirements of computational power. To assess the viability of the approach, the EvAg model has been empirically analyzed in a simulated Peer-to-Peer environment where experiments were conducted on two well-known GP problems. Results show that the spatially structured nature of the algorithm is able to yield a good quality in the solutions. Additionally, parallelization improves times to solution by several orders of magnitude.