Evostar 2015 mandatory post

We can never skip the chance to assist the Evostar conference, and aside learn the latest trends in Evolutionary Computation and present our results, we also have a good time with our other colleagues.

This time the conference was held in Copenhagen (Denmark), and because Antonio and me were part of the organization we didn’t have much time to go sightseeing, but we went to Tivoli Gardens and ride the flying chairs (and screamed like babies).

On the scientific part, we presented two papers to EvoGames track, related with our research lines on content generation for videogames and AI optimization. The first paper, How the World Was MADE: Parametrization of Evolved Agent-Based Models for Backstory Generation, presents a study on parametrization of the values that define a virtual world to facilitate the emergence of archetypes, and be able to generate interesting backstories (for videogames, for example). See the poster here:

The poster

Also, as we are commited to open science and open software, you can download the MADE environment from its web. The abstract:

Generating fiction environments for a multi-agent system optimized by genetic algorithms (with some specific requirements related to the desirable plots), presents two main problems: first it is impossible to know in advance the optimal value for the particular designed fitness function, and at the same time, it creates a vast search space for the parameters that it needs. The purpose of this paper is to define a methodology to find the best parameter values for both, the evolutionary algorithm, and the own fictional world configuration. This design includes running, to completion, a world simulation represented as a chromosome, and assigning a fitness to it, thus composing a very complex fitness landscape.
In order to optimize the resources allocated to evolution and to have some guarantees that the final result will be close to the optimum, we systematically analyze a set of possible values of the most relevant parameters, obtaining a set of generic rules. These rules, when applied to the plot requisites, and thus, to the fitness function, will lead to a reduced range of parameter values that will help the storyteller to create optimal worlds with a reduced computation budget.

Evostar 2015 - Copenhagen(That’s me with the IKEA rat plushies I used to describe our system)

Our other paper, It’s Time to Stop: A Comparison of Termination Conditions in the Evolution of Game Bots, describes a methodology to compare different termination conditions in noisy environments such as the RTS games. The abstract:

Evolutionary Algorithms (EAs) are frequently used as a mechanism for the optimization of autonomous agents in games (bots), but knowing when to stop the evolution, when the bots are good enough, is not as easy as it would a priori seem. The first issue is that optimal bots are either unknown (and thus unusable as termination condition) or unreachable. In most EAs trying to find optimal bots fitness is evaluated through game playing. Many times it is found to be noisy, making its use as a termination condition also complicated. A fixed amount of evaluations or, in the case of games, a certain level of victories does not guarantee an optimal result. Thus the main objective of this paper is to test several termination conditions in order to find the one that yields optimal solutions within a restricted amount of time, and that allows researchers to compare different EAs as fairly as possible. To achieve this we will examine several ways of finishing an EA who is finding an optimal bot design process for a particular game, Planet Wars in this case, with the characteristics described above, determining the capabilities of every one of them and, eventually, selecting one for future designs.

Evostar 2015 - Copenhagen(Here’s Antonio presenting the paper)

You can see the rest of the Evostar photos in their flickr account.

Advertisements

Aplicación de Programación Genética para la generación de bots del RTS Planet Wars en CoSECiVi 2014

Este trabajo se publicó dentro del Primer Congreso de la Sociedad Española para las Ciencias del Videojuego (CoSECIVI), que se celebró en conjunción con el Gamelab 2014 en Barcelona.

En él se presentó el artículo titulado “Designing Competitive Bots for a Real Time Strategy Game using Genetic Programming”, cuyo resumen (en inglés) es:

The design of the Artificial Intelligence (AI) engine for an autonomous agent (bot) in a game is always a difficult task mainly done by an expert human player, who has to transform his/her knowledge into a behavioural engine. This paper presents an approach for conducting this task by means of Genetic Programming (GP) application. This algorithm is applied to design decision trees to be used as bot’s AI in 1 vs 1 battles inside the RTS game Planet Wars. Using this method it is possible to create rule-based systems defining decisions and actions, in an automatic way, completely different from a human designer doing them from scratch. These rules will be optimised along the algorithm run, considering the bot’s performance during evaluation matches. As GP can generate and evolve behavioural rules not taken into account by an expert, the obtained bots could perform better than human-defined ones. Due to the difficulties when applying Computational Intelligence techniques in the videogames scope, such as noise factor in the evaluation functions, three different fitness approaches have been implemented and tested in this work. Two of them try to minimize this factor by considering additional dynamic information about the evaluation matches, rather than just the final result (the winner), as the other function does.
In order to prove them, the best obtained agents have been compared with a previous bot, created by an expert player (from scratch) and then
optimised by means of Genetic Algorithms. The experiments show that the three used fitness functions generate bots that outperform the optimized human-defined one, being the area-based fitness function the one that produces better results.

La presentación del artículo se puede ver aquí:

El artículo se puede encontrar en: http://gaia.fdi.ucm.es/sites/cosecivi14/es/papers/24.pdf

Esperamos que os guste.

Y que nos citéis. :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.

Reactive Planning for RTS games

The paper “Reactive Planning Idioms for Multi-Scale Game AI” (Weber et al.), published last year in the proceedings of the IEEE Conference on Computation Intelligence and Games (CIG 2010), proposes a technique called reactive planning for designing a bot for Real-time strategy games (RTS). The agent is implemented in ABL (a behavioral language), an environment that allows the programmer to embed the multi-level reasoning that is required for efficient and complex RTS bots. A bot for RTS games (such as the StarCraft) must deal simultaneously with several goals, making intelligent high-level decisions while micromanaging units in combat, and ABL provides features such as daemons, messaging (memory), managers and micromanagement behaviors that can be of great help for such task. The authors propose a specific framework, for the structure of the bot and interfaces, and demonstrate that the resulting agent is able to beat the built-in StarCraft bot. However, when tested against moderately skilled human players, the agent performs poorly. As far as we understood, this work deals mainly with traditional Artificial Intelligence. The open question now is: can we model some kind of adaptive behavior in this ABL environment?

Paper Seminar: Reactive Planning Idioms for Multi-Scale Game AI

El viernes que viene, a las 12:30 y en la sala de reuniones de la ETSIIT, Carlos Fernandes hará una presentación sobre el trabajo Reactive Planning Idioms for Multi-Scale Game AI. En este seminario veremos cuáles son las claves de este trabajo en un ambiente más o menos informal, con el objetivo principal de aplicarlo a nuestra investigación sobre juegos en tiempo real

Google AI Challenge 2010

La Universidad de Waterloo Computer Science Club con la colaboración de Google organizan un año más el Google AI Challenge. Este año, el objetivo es crear un algoritmo que juegue a Planet Wars de la forma más inteligente posible.

Problema:

Planet Wars es un juego de estrategia en el espacio exterior. El objetivo es conquistar todos los planetas del mapa o eliminar todas las naves enemigas. Podemos ver un ejemplo de juego en el siguiente vídeo.

Planet Wars está inspirado en Galcon, un popular juego de Iphone, Android y PC. Puedes jugar a Galcon aquí para hacerte una idea del juego y sus estrategias. Es un juego basado en turnos. El bot a implementar es una función que recibe la lista de planetas y flotas y devuelve una lista de órdenes.

Cada planeta, tiene los siguientes campos o propiedades:

  • Coordenadas (x,y)
  • ID del propietario
  • Número de naves alojadas
  • Tasa de crecimiento

Los planetas neutrales tienen un ID de cero, mientras que los de tu bot tiene el ID de 1 y los enemigos el ID de 2. Tras cada turno, el número de naves en los planetas no neutrales aumenta de acuerdo a la Tasa de crecimiento de dicho planeta.

Las flotas son los números de colores que vuelan entre los planetas. Cuando una flota llega a su planeta de destino, pueden suceder dos cosas. Si el planeta del destino pertenece al bot, las naves se añaden como refuerzos al planeta. En caso contrario, las naves de la flota se restan a las naves que ocupan en ese momento el planeta. Si el resultado es menor que cero, entonces el bot gana el control del planeta. Si el resultado es exactamente 0, entonces el control del planeta no cambia.

Las flotas tienen los siguientes campos o propiedades:

  • ID del propietario
  • Número de náves
  • ID Planeta de origen
  • ID Planeta de destino
  • Longitud total del viaje
  • Número de turnos hasta la llegada

El bot puede emitir tantas órdenes como quiera durante el turno. Cada orden especifica un planeta de origen, un planeta de destino y un número de naves. Una vez que la orden se ejecuta, el número determinado de naves abandona el planeta para ir hacia su destino.

El juego termina cuando solo queda un solo jugador o se excede un determinado número de turnos.

Timeline:

  • 1 Septiembre 2010: publicación del material oficial.
  • 10 Septiembre 2010: Fecha de inicio oficial.
  • 27 Noviembre 2010: Fecha límite de entrega.
  • 1 Diciembre 2010: Los resultados finales y la clasificación final se darán a conocer.

Reglas:

  • La clasificación final se determinará mediante un torneo computerizado diseñado por la organización. El ranking actual en la clasificación no son los oficiales y pueden no ser representativos de los resultados finales.
  • Solo se puede poseer una cuenta. Si usted mantiene el control efectivo sobre más de una cuenta incluso si las cuentas son nominalmente propiedad de otra persona, las cuentas serán descalificadas.
  • Su programa no puede tomar más de un segundo en hacer cualquier jugada personal. Si se quieren hacer cálculos intensivos, asegúrese de agregar código que compruebe el tiempo a intervalos regulares para que no sobrepase la cuota de un segundo. Si el programa viola la cuota de tiempo, será suspendido.
  • Los mecanismos que se consideren que violan el espíritu de la competencia leal y deportiva será descalificado sin ninguna posibilidad de apelación. En particular, la exploración de memoria, perder juegos de forma intencionada y la conducta condicionada al ID del oponente están prohibidos.
  • El código no puede escribir en archivos. Sin embargo, puede leer archivos en el directorio de representación, que será el directorio actual.
  • El uso de múltiples procesos o hilos está prohibido.
  • Cualquier intento de perturbar el funcionamiento normal del software de los servidores del concurso dará lugar a la intervención de los agentes del orden.
  • Queda reservado el derecho a modificar estas reglas en cualquier momento y sin previo aviso.

Paquetes iniciales de software:

La organización proporciona unos paquetes de software inciales. Cada paquete es un archivo ZIP que contiene:

  • Una entrada sencilla y funcional para ser usada como punto incial.
  • Las herramientas que permiten ejecutar el bot y un entorno gráfico de ejecución.
  • Algunos oponentes para testear nuestros bots.
  • Un centenar de mapas generados al azar para testeo.

Los paquetes iniciales se encuentran disponibles para C++, Java, Python y C#.

En la web de la organización pueden encontrarse la especificación funcional de las herramientas así como guías de estrategias y decisiones sobre el problema.

Web oficial: http://ai-contest.com

Especificación oficial: http://ai-contest.com/specification.php

Foro del contest: http://ai-contest.com/forum/

Play Galcon Online: http://www.galcon.com/flash