About fergunet

PhD at Computer Science. I like Doctor Who.

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

See you in future adventures!!!


Master of Evolution! Using Genetic Algorithms to generate decks for the game HearthStone

This September we attended to the IEEE CIG 2017 Conference in Santorini, Greece, to present the paper “Evolutionary Deckbuilding in HearthStone”. This paper was written in collaboration with our colleagues Alberto Tonda and Giovanni Squillero.

The story of this paper started a (not so) long time ago while me and Alberto were discussing about how awesome HearthStone is. Suddenly, we thought about how easy it would be to create the constraints for the uGP framework, and that there were some open source simulators of the game. In a while, we already had the constraints, the simulator adapted to accept individuals from uGP, and some experiments running.

And we finished the paper after, of course.

You can download the paper draft from here (the electronic original version is not available yet).

And here is the presentation:

The abstract:

—One of the most notable features of collectible card games is deckbuilding, that is, defining a personalized deck before the real game. Deckbuilding is a challenge that involves a big and rugged search space, with different and unpredictable behaviour
after simple card changes and even hidden information. In this paper, we explore the possibility of automated deckbuilding: a genetic algorithm is applied to the task, with the evaluation delegated to a game simulator that tests every potential deck against a varied and representative range of human-made decks.
In these preliminary experiments, the approach has proven able to create quite effective decks, a promising result that proves that, even in this challenging environment, evolutionary algorithms can find good solutions.

Starcraft GP nominated to the HUMIES award

This year we participated in the HUMIES awards with our paper “Towards Automatic StarCraft Strategy Generation Using Genetic Programming“, accepted at CIG2015, wrote in collaboration with Politecnico di Torino and INRA. Our paper was elected from 28 candidates to be part of the 8 finalists, so we can consider it a great achievement. Although we didn’t won, because the astounding quality of the other works, we are thrilled about our nomination :)

Here is the presentation. It even includes a reference to Starship Troopers!

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.

This was a triumph: Evolving intelligent bots for videogames. And for Science.

Today I gave the talk entitled “This was a triumph: Evolving intelligent bots for videogames. And for Science” to the students of the High School IES Montes Orientales. I talked about the concept of Evolutionary Algorithms, and then I presented some of our results of their application in games such as Planet Wars, Unreal, Starcraft or Content Generation.

Other members of the ETSIIT gave other amazing talks about Free Software, Artificial Vision, Robotics or Language Processing. Hopefully we will get some of these student working with us in several years!


[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

GeNeura en la Noche de los Investigadores 2015

GeNeura estuvo presente dentro de la Noche Europea de los Investigadores en el stand de la actividad El Ojo que todo lo ve. En este evento estuvimos realizando difusión de los proyectos SIPESCA, MOSOS, PETRA y el recientemente solicitado SiMoPE. Dentro del stand estuvimos mostrando el estado de los proyectos, sus avances, los dispositivos de captación, y los datos de dispositivos móviles que habíamos ido tomando. Tuvo una gran afluencia de público, que participó de forma activa a través de preguntas y opiniones. Además, estuvimos midiendo el paso de las personas que estuvieron asistiendo al evento con uno de nuestros dispositivos.

Algunas fotos del evento:

La Noche Europea de los Investigadores 2015Noche Europea de l@s Investigador@s 2015

La Noche Europea de los Investigadores 2015

Muchas gracias a todos los asistentes!