# Creating Hearthstone decks by using Genetic Algorithms

I’m glad you’re here, friend! There’s a chill outside, so pull up a chair by the hearth of our inn and prepare to learn how the Ancient Gods use the power of the secret and ancient branch of the Evolution to generate Hearthstone decks by means of the magic and mistery!!

Several months ago, my colleague Alberto Tonda and I were discussing about our latest adventures playing the Digital Collectible Card Game Hearthstone, when one of us said «Uhm, Genetic Algorithms usually work well with combinatorial problems, and solutions are usually a vector of elements. Elements such as cards. Such as cards of Hearthstone, the game we are playing right now while we are talking. Are you thinking what I’m thinking?»

Five minutes later we found an open-source Hearthstone simulator and started to think how to address the possibility of automatically evolve decks of Hearthstone.

The idea is quite simple: Hearthstone is played using a deck of 30 cards (from a pool of thousands available), so it is easy to model the candidate solution. With the simulator, we can perform several matches using different enemy decks, and obtain the number of victories. Therefore, we have a number that can be used to model the performance (fitness) of the deck.

Soooo, it’s easy to see one and one makes two, two and one makes three, and it was destiny, that we created a genetic algorithm that generates deck for Hearthstone for free.

Our preliminary results where discussed here, but we wanted to continue testing our method, so we tested using all available classes of the game, with the help of JJ, Giovanny and Antonio. All the best human-made decks were outperformed by our approach! And not only that, we applied a new operator called Smart Mutation that it is based in what we do when we test new decks in Hearthstone: we remove a card, and place another instead, but with +/-1 mana crystals, and not one completely random from the pool. The results were even better. Neat!

Maybe you prefer to read the abstract, that it is written in a more formal way than this post. You know, using the language of the science.

Collectible card games have been among the most popular and profitable products of the entertainment industry since the early days of Magic: The Gathering in the nineties. Digital versions have also appeared, with HearthStone: Heroes of WarCraft being one of the most popular. In Hearthstone, every player can play as a hero, from a set of nine, and build his/her deck before the game from a big pool of available cards, including both neutral and hero-specific cards.
This kind of games offers several challenges for researchers in artificial intelligence since they involve hidden information, unpredictable behaviour, and a large and rugged search space. Besides, an important part of player engagement in such games is a periodical input of new cards in the system, which mainly opens the door to new strategies for the players. Playtesting is the method used to check the new card sets for possible design flaws, and it is usually performed manually or via exhaustive search; in the case of Hearthstone, such test plays must take into account the chosen hero, with its specific kind of cards.
In this paper, we present a novel idea to improve and accelerate the playtesting process, systematically exploring the space of possible decks using an Evolutionary Algorithm (EA). This EA creates HearthStone decks which are then played by an AI versus established human-designed decks. Since the space of possible combinations that are play-tested is huge, search through the space of possible decks has been shortened via a new heuristic mutation operator, which is based on the behaviour of human players modifying their decks.
Results show the viability of our method for exploring the space of possible decks and automating the play-testing phase of game design. The resulting decks, that have been examined for balancedness by an expert player, outperform human-made ones when played by the AI; the introduction of the new heuristic operator helps to improve the obtained solutions, and basing the study on the whole set of heroes shows its validity through the whole range of decks.

You can download the complete paper from the Knowledge-based Systems Journal https://www.sciencedirect.com/science/article/pii/S0950705118301953

# 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.

# [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.

# [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.

# 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.

# Pervasive evolutionary algorithms on mobile devices

Last week I received the paper aceptance notification for the DCAI conference in Salamanca. This time we are going to present a distributed algorithm framework for mobile devices using Bluetooth. Ok, today I am quite lazy (today, and all the days, actually), so I think the best idea is to copy the abstract.

Abstract. This work presents a Java framework which allows to implement easily connectivity applications via Bluetooth. Nowadays it is difficult to program Bluetooth devices, so it is necessary to use a high-level Application Programming Interface (API) to make easy the creation of applications in Java ME and Java SE platforms, the most extended ones. As a solution we show the development of a distributed computing environment using a layered, client-server, and event-based with asynchronous communication architecture. In addition we solve two well-known evolutionary computation problems (the Traveler Salesman Problem and the Wave Function Problem), as an example of use.

The most interesting thing is that we have used real mobiles in order to execute the experiments, with all associated problems. It is difficult to find a compatible mobile phone with a Bluetooth stack that works properly. Even is not easy communicate two phones of the same fabricant but different model! But finally we managed to start the experiment, as you can see in the next photo.

Two Nokias executing our distributed algorithm. Photo by DraXus.