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!!

The_Innkeeper's_Tale_-_The_Innkeeper's_Tale2.jpg

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!!!

Advertisements

A better TORCS driving controller presented in EvoStar 2018

Amazing bench
Last year, we presented along with Mohammed Salem, from the university of Mascara, in Algeria, our TORCS driving controller. This controller effectively drives a simulated vehicle, considering input from its sensors, and deciding on a target speed and how to turn the steering wheel.
Poster session, with our poster in the first position
This year, in Evostar 2018 in Parma, we had again our paper accepted for the poster session, which took place in the incredible corridor to the right of these words. The poster included interactive elements, such as a small car used for demonstration on how the driver worked.

And it works really well, or at least better than the previous versions. The key element was the design of a new fitness function that includes damages, and also terms related to speed. Still some way to go; in the near future we will be posting our new results in this area.

The book of proceedings can be downloaded from Springer. Our paper is in page 342 and you can also download just the paper from here, but we do open science, so you can follow our writing process and download the paper from this GitHub repository too

 

 

Early prediction of the outcome of Starcraft Games

As a result of Antonio Álvarez Caballero master’s thesis, we’ll be presenting tomorrow at the IJCCI 2017 conference a poster on the early prediction of Starcraft games.
The basic idea behind this line of research is to try and find a model of the game so that we can do fast fitness evaluation of strategies without playing the whole game, which can take up to 60 minutes. That way, we can optimize those strategies in an evolutionary algorithm and find the best ones.
In our usual open science style, paper and data are available in a repository.
Our conclusions say that we might be able to pull that off, using k-nearest neighbor algorithm. But we might have to investigate a bit further if we really want to find a model that gives us some insight about what makes a strategy a winner.

37404346594_a261c62e38_k.jpg

Dark clouds allow early prediction of heavy rain in Funchal, near where IJCCI is taking place

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.

How good are different languages at runnig evolutionary algorithms?

As part of the EvoStar conference, which took place last week, we presented the poster Benchmarking Languages for Evolutionary Algorithms, where, with help from many friends in Open Science fashion, we tested several a bunch of compiled and scripting languages on several common evolutionary operations: crossover, mutation and OneMax.

It was presented in poster form, and you had to be there to actually understand it. Since you are not, it’s better if you use this comments (or those at the poster) to inquire about it. Or you can check out the interactive presentation we also did, which in fact includes data and everything in the source.
This work is ongoing, and you are very welcome to participate. Just take a peek at the repo, and do a pull request.

Enviada la versión definitiva del trabajo “Predicción a muy corto plazo de series temporales de volumen de tráfico rodado mediante co-evolución de RNFBR”

Tras realizar las correspondientes modificaciones indicadas por los revisores del congreso MAEB 2015, hemos procedido a enviar la versión definitiva del trabajo, usando para ello la famosa plataforma EasyChair.
Cabe recordar que MAEB’2015 se celebrará en Mérida-Almendralejo, durante los días 4 al 6 de Febrero de 2015, y estará organizada por el Centro Universitario de Mérida, el cual pertenece a la Universidad de Extremadura.
Toda la info del congreso en: http://www.eweb.unex.es/eweb/maeb2015/

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