Towards automatic StarCraft strategy generation using genetic programming

I forgot to mention that we published our paper “Towards automatic StarCraft strategy generation using genetic programming” in CIG 2015 conference, held in Taiwan. This was a work made in collaboration with Alberto Tonda (INRA) and Giovanni Squillero (Politecnico di Torino), starting a new research line using this game (and also, starting other nice collaborations that are still a secret!)

The abstract:

Among Real-Time Strategy games few titles have enjoyed the continued success of StarCraft. Many research lines aimed at developing Artificial Intelligences, or “bots”, capable of challenging human players, use StarCraft as a platform. Several characteristics make this game particularly appealing for researchers, such as: asymmetric balanced factions, considerable complexity of the technology trees, large number of units with unique features, and potential for optimization both at the strategical and tactical level. In literature, various works exploit evolutionary computation to optimize particular aspects of the game, from squad formation to map exploration; but so far, no evolutionary approach has been applied to the development of a complete strategy from scratch. In this paper, we present the preliminary results of StarCraftGP, a framework able to evolve a complete strategy for StarCraft, from the building plan, to the composition of squads, up to the set of rules that define the bot’s behavior during the game. The proposed approach generates strategies as C++ classes, that are then compiled and executed inside the OpprimoBot open-source framework. In a first set of runs, we demonstrate that StarCraftGP ultimately generates a competitive strategy for a Zerg bot, able to defeat several human-designed bots.

Do you want to know more? Download the paper draft or electronic version in IEEE web.

Advertisements

[Paper] Studying the effect of population size in distributed evolutionary algorithms on heterogeneous clusters

Finally we have published in Applied Soft Computer journal the last paper related with my thesis. We used OSGiLiath to perform a number of cool experiments related with automatic adaptation of dEAs on heterogeneous clusters.

The abstract:

Distributed Evolutionary Algorithms are traditionally executed on homogeneous dedicated clusters, despite most scientists have access mainly to networks of heterogeneous nodes (for example, desktop PCs in a lab). Fitting this kind of algorithms to these environments, so that they can take advantage of their heterogeneity to save running time, is still an open problem. The different computational power of the nodes affects the performance of the algorithm, and tuning or fitting it to each node properly could reduce execution time.

Since the distributed Evolutionary Algorithms include a whole range of parameters that influence the performance, this paper proposes a study on the population size. This parameter is one of the most important, since it has a direct relationship with the number of iterations needed to find the solution, as it affects the exploration factor of the algorithm. The aim of this paper consists in validating the following hypothesis: fitting the sub-population size to the computational power of the heterogeneous cluster node can lead to an improvement in running time with respect to the use of the same population size in every node.

Two parameter size schemes have been tested, an offline and an online parameter setting, and three problems with different characteristics and computational demands have been used.

Results show that setting the population size according to the computational power of each node in the heterogeneous cluster improves the time required to obtain the optimal solution. Meanwhile, the same set of different size values could not improve the running time to reach the optimum in a homogeneous cluster with respect to the same size in all nodes, indicating that the improvement is due to the interaction of the different hardware resources with the algorithm. In addition, a study on the influence of the different population sizes on each stage of the algorithm is presented. This opens a new research line on the fitting (offline or online) of parameters of the distributed Evolutionary Algorithms to the computational power of the devices.

The paper (currently “In press” form) can be downloaded from http://www.sciencedirect.com/science/article/pii/S1568494615006468

[Paper] My life as a sim: evolving unique and engaging life stories using virtual worlds

Our latest publication My life as a sim: evolving unique and engaging life stories using virtual worlds, using our framework MADE (created by @rubenhek), has been published in the ALIFE 2014 conference. The abstract:

Stories are not only painfully weaved by crafty writers in the solitude of their studios; they also have to be produced massively for non-player characters in the video game industry or tailored to particular tastes in personalized stories. However, the creation of fictional stories is a very complex task that usually implies a creative process where the author has to combine characters, conflicts and backstories to create an engaging narrative. This work describes a general methodology to generate cohesive and coherent backstories where desired archetypes (universally accepted literary symbols) can emerge in complex stochastic systems. This methodology supports the modeling and parametrization of the agents, the environment where they will live and the desired literary setting. The use of a Genetic Algorithm (GA) is proposed to establish the parameter configuration that will lead to backstories that best fit the setting. Information extracted from a simulation can then be used to create the literary work. To demonstrate the adequacy of the methodology, we perform an implementation using a specific multi-agent system and evaluate the results, testing with three different literary settings.

Check out the presentation by @jjmerelo at http://jj.github.io/alife14-made/#/home. You can download the proceedings of the conference (CC license), or download the paper draft.

More information is available on the project page.

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

Sistema para la evaluación de la confianza en redes distribuidas

El pasado lunes se presentó el artículo ya anunciado en el anterior post. Como conclusiones, discutimos sobre:

  • La necesidad de confianza entre participantes dentro de una red distribuida, principalmente enfocada a actividades P2P.
  • La manera de medir esa confianza, de modelarla y los beneficios de hacerlo.
  • El obtener las medidas de confianza bien por observación o bien por recomendaciones, y las condiciones que se han de cumplir para una correcta propagación de los valores.
  • Conocimiento de los distintos ataques de: bad mouthing, on-off, Sybli, new user creación de conflictos.
  • Discusión sobre los módulos que compondrían un sistema que gestiona la confianza.
  • Comentarios sobre las gráficas de resultados y los posibles beneficios de usar este sistema cuando se presentan los ataques mencionados.

La presentación puede consultarse a continuación:

Paper Seminar: A Trust Evaluation Framework in Distributed Networks: Vulnerability Analysis and Defense Against Attacks

El lunes que viene, 21 de enero, se discutirá sobre el trabajo A Trust Evaluation Framework in Distributed Networks: Vulnerability Analysis and Defense Against Attacks, colaboración de los departamentos de Ingeniería Electrónica y de Computación de las universidades de Rhode Island y Maryland. En él se propone una manera de aumentar la seguridad en arquitecturas de red distribuidas, basándose en una medida cuantitativa de la confianza en cada entidad participante. Será en la Sala de Reuniones de la ETSIIT, estáis todos invitados.

Things I’ve learned reading just ONE paper

One of the most important parts of the research job is reading papers. As an early stages of a new research line you are going to deep, first month of reading may seem fruitless, because you can think you are not doing anything, nor developing new experiments or whatever. But, I realized, reading one of my friends’ (and another member of GeNeura) paper how many information you can learn in just one paper. As an example, I am going to write here all concepts I’ve learned reading his paper “EvAg: a scalable peer-to-peer evolutionary algorithm” (you can download it from here).

It is a paper about P2P populations where each individual of a GA is present in a different node (fine-grain) in the network and explain how to interchange information among the nodes. Many experiments are performed and all that stuff, but I am going to concentrate in some concepts, not in the paper results, because Juanlu explained them in previous posts of this blog.

Panmictic population: each member of the population has the same probability to reproduce with the others. Applying to a graph, it is a fully connected graph.

Selectorecombinative GA: Is a mutation-free GA. It is used in population studies, due to all diversity source is from the initial population.

Trap functions: scalable and decomposable functions (divided in Building Blocks, BB). Varying the number k of each block also varies the problem difficult. Fitness depends of the number of 1s in the block. For example, in a k=4. F(0) = 3, F(1)=2, F(11)=1, F(111)=0, F(1111) = 4. It could be deceptive (one of the edges leads to a sub-optimun, and other to a global optimum).

Watts-Strogatts network: It is a small-world graph where nodes forms clusters, like real Internet. It is very easy to create a WS network from a ring topology (just alter each edge to connect another node with a probability p, so some connections are deleted). In these networks, selective pressure is equivalent to panmitic populations, but more scalable due there are a lower number of edges.

Takeover time: time that the best individual take over the entire population.

Metrics for experiments:

  • Success Rate: number of times algorithm finds the optimum.
  • Average Evaluations to find Solution (AES)
  • Best fitness convergence
  • Genotipic entropy: diversity of the population based in the genotipic distance to optimum genome (using Hamming Distance, for example). Wilcoxon test can be used.

As you can see, no information about the results of this paper is presented in this post, I’ve just written about new things I didn’t knew.

Tip: I am using Evernote to take notes of every paper I read. Evernote is like Dropbox, but with notes. I annotate shops, projects, todo lists… and I have full synchronization with all my computers (in Mac OS X, GNU/Linux) and mobile devices (Android or iPhone). There exist many usages of this program, so I recommend to take a look.

Pablo.