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

[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

Aplicando algoritmos genéticos a un controlador ‘fuzzy’ para una gestión adaptativa del tráfico

Recientemente se ha aceptado el artículo «A hybrid Fuzzy Genetic Algorithm for an adaptive traffic signal system» en la revista open-access Advances in Fuzzy Systems. En él participamos varios de los investigadores de GeNeura.

El abstract es:

This paper presents a hybrid algorithm that combines Fuzzy Logic Controller (FLC) and Genetic Algorithms (GAs) and its application on a traffic signal system. FLCs have been widely used in many applications in diverse areas, such as control system, pattern recognition, signal processing, and forecasting. They are, essentially, rule-based systems, in which the definition of these rules and fuzzy membership functions is generally based on verbally formulated rules that overlap through the parameter space. They have a great influence over the performance of the system. On the other hand, the Genetic Algorithm is a metaheuristic that provides a robust search in complex spaces. In this work, it has been used to adapt the decision rules of FLCs that define an intelligent traffic signal system, obtaining a higher performance than a classical FLC-based control. The simulation results yielded by the hybrid algorithm show an improvement of up to 34% in the performance with respect to a standard traffic signal controller, Conventional Traffic Signal Controller (CTC), and up to 31% in the comparison with a traditional logic controller, FLC.

Esperamos que os guste (y que lo citéis, claro :D).

Ms. PacMan in IEEE Transactions on CI and AI in Games

Our fans and followers must be happy! ;D

They can now access the excellent work by Federico Liberatore in IEEE ToCIAIG journal.

This is the best journal concerning Artificial Intelligence in games, with a very strict reviewing process, so, we are very proud of this success. ;)

This is the next step in the research started one year and a half ago designing competitive  Ghost Teams for catching Ms. PacMan.

The abstract is:

In the last year, thanks to the Ms. Pac-Man vs Ghosts competition, the game of Ms. Pac-Man has gained increasing attention from academics in the field of Computational Intelligence. In this work, we contribute to this research stream by presenting a simple Genetic Algorithm with Lexicographic Ranking (GALR) for the optimization of Flocking Strategy-based ghost controllers. Flocking Strategies are a paradigm for intelligent agents characterized by showing emergent behavior and for having very little computational and memory requirements, making them well suited for commercial applications and mobile devices. In particular, we study empirically the effect of optimizing homogeneous and heterogeneous teams. The computational analysis shows that the Flocking Strategy-based controllers generated by the proposed GALR outperform the ghost controllers included in the competition framework and some of those presented in the literature.

The paper can be found here: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7093170&tag=1

Enjoy it!

(And cite us) :D

Call for papers: Special issue of JSSC on Complex Systems and Sports

Call for papers:
Special Issue on Complex Systems and Sports
Journal of Systems Science and Complexity

AIMS and SCOPE

Complex networks are networks with non-trivial topological features (scale-free degree distribution, high clustering coefficient or small-world properties). They sit at the edge of chaos between regular lattices and fully random networks, and can capture many natural and social phenomena, e.g., gene interactions or social relationships. In particular, team sports have a strong network component, since they are essentially a network developed along time and space, with nodes being players and links being passes and other interactions. The network paradigm allows for a strong quantitative description of a whole match, while at the same time offers some insight on how performance is achieved. This could result, eventually, in a prediction of game outcome according to network characteristics. Complex networks, and thus emergent behavior, appear also in other aspects: transfers, and even sports support and interaction among them.

Complex networks are an example of complex systems, a paradigm that has been applied in the past to sports and which is the focus of this special issue. There are many aspects in the dynamics of sports (related to scoring or performance) that can be analyzed from this general perspective in order to
model the game, find hidden patterns and phase transitions, etc. From an even more general viewpoint, the analysis can be extended beyond the actual game dynamics and tackle other sport-related issues: transfer networks, sport fans networks and their dynamics, etc. Submissions dealing with the use of complex systems in this context are welcome.

Related topics thus include (but are not limited to):

• Complex networks in team-sport games
• Networks of teams
• Transfer networks
• Relationship between economics and complex networks in sports
• Sports fans networks and their dynamics
• Complex systems analysis and simulation of robotics sports
• In general, anything that bridges the gap between complex systems and sports
• Agent-based models of sport games
• Complex systems and sports physiology

Both theoretical and applied works related to the topics of the special issue are sought. The target audience of the special issue is composed of computer, social and sports scientists, interested in unravelling the dynamics and emergent patterns of games in team sports.

ABOUT JSSC

The Journal of Systems Science and Complexity is a quarterly journal indexed in the Science Citation Index (impact factor = 0.564 in 2010).

Further information at the journal’s web site

IMPORTANT DATES

Submission of papers: January 20th, 2012
Notification of acceptance: March 31st, 2012
Final versions due: April 30th, 2012

SUBMISSION INSTRUCTIONS

The manuscript should be written in English with an informative abstract of no more than 200 words and 5 key words maximum. The manuscript should be concise and grammatically correct. It should be typed double-spaced and include an abbreviated title with no more than 40 English characters for the running head. Authors are requested to type all letters and mathematical symbols clearly. References should be cited in the text with numerals in square brackets, e.g. [3]. All references should appear and be numbered in a separate bibliography at the end of the paper. Papers should be typeset in LaTeX (or AMSTeX, TeX).

Please, submit a PDF version of the paper through this web form

If you have any question, please address it to sports.jssc (at) gmail (dot) com

EDITORS

——-

J.J. Merelo ,
Universidad de Granada, Spain

A.M. Mora ,
Universidad de Granada, Spain

C. Cotta ,
Universidad de Malaga, Spain.