Hearthstone in Academia

Mapping Hearthstone Deck Spaces through MAP-Elites with Sliding Boundaries

Matthew C. Fontaine, Scott Lee, L. B. Soros, Fernando De Mesentier Silva, Julian Togelius, Amy K. Hoover (2019)

Keywords - Quality Diversity, Illumination Algorithms, Games, Card Games, Balancing

Full paper

Abstract

"Quality diversity (QD) algorithms such as MAP-Elites have emerged as a powerful alternative to traditional single-objective optimization methods. They were initially applied to evolutionary robotics problems such as locomotion and maze navigation, but have yet to see widespread application. We argue that these algorithms are perfectly suited to the rich domain of video games, which contains many relevant problems with a multitude of successful strategies and often also multiple dimensions along which solutions can vary.

This paper introduces a novel modification of the MAP-Elites algorithm called MAP-Elites with Sliding Boundaries (MESB) and applies it to the design and rebalancing of Hearthstone, a popular collectible card game chosen for its number of multidimensional behavior features relevant to particular styles of play. To avoid overpopulating cells with conflated behaviors, MESB slides the boundaries of cells based on the distribution of evolved individuals. Experiments in this paper demonstrate the performance of MESB in Hearthstone. Results suggest MESB finds diverse ways of playing the game well along the selected behavioral dimensions. Further analysis of the evolved strategies reveals common patterns that recur across behavioral dimensions and explores how MESB can help rebalance the game."

Introducing the Hearthstone-AI Competition

Alexander Dockhorn, Sanaz Mostaghim (2019)

Keywords - Artificial Intelligence, Competition, Challenges

Full paper

Abstract

"The Hearthstone AI framework and competition motivates the development of artificial intelligence agents that can play collectible card games. A special feature of those games is the high variety of cards, which can be chosen by the players to create their own decks. In contrast to simpler card games, the value of many cards is determined by their possible synergies. The vast amount of possible decks, the randomness of the game, as well as the restricted information during the player's turn offer quite a hard challenge for the development of game-playing agents. This short paper introduces the competition framework and goes into more detail on the problems and challenges that need to be faced during the development process."

Evolving the Hearthstone Meta

Fernando de Mesentier Silva, Rodrigo Canaan, Scott Lee, Matthew C. Fontaine, Julian Togelius, Amy K. Hoover (2019)

Keywords - Evolutionary Algorithm, Multi-Objective Optimization, Game Balancing

Full paper

Abstract

"Balancing an ever growing strategic game of high complexity, such as Hearthstone is a complex task. The target of making strategies diverse and customizable results in a delicate intricate system. Tuning over 2000 cards to generate the desired outcome without disrupting the existing environment becomes a laborious challenge. In this paper, we discuss the impacts that changes to existing cards can have on strategy in Hearthstone. By analyzing the win rate on match-ups across different decks, being played by different strategies, we propose to compare their performance before and after changes are made to improve or worsen different cards. Then, using an evolutionary algorithm, we search for a combination of changes to the card attributes that cause the decks to approach equal, 50% win rates. We then expand our evolutionary algorithm to a multi-objective solution to search for this result, while making the minimum amount of changes, and as a consequence disruption, to the existing cards. Lastly, we propose and evaluate metrics to serve as heuristics with which to decide which cards to target with balance changes."

Why Do Players Misuse Emotes in Hearthstone? Negotiating the Use of Communicative Affordances in an Online Multiplayer Game

Jonne Arjoranta, Marko Siitonen (2018)

Keywords - Emotes, Griefing, Online Games, Player Interaction, Player Community

Full paper

Abstract

"This paper examines player-to-player interaction in Hearthstone: Heroes of Warcraft (Blizzard Entertainment, 2004). The game designers have attempted to limit what they see as negative interaction by forcibly limiting player-to-player social interaction. Based on an analysis of forum discussions, this empirical study illustrates how players utilize Hearthstone's restricted communication affordances for negative and insulting purposes, and how players negotiate their shared symbolic reality concerning this type of interaction, labeled "Bad Manner(s)" or "BM". The continuous debate over an issue which ultimately cannot be solved shows that players care deeply about the game and the surrounding culture. This study contributes to our understanding of player-to-player communication, and offers insight into game design from a social interaction point-of-view. By doing so, it connects with the larger questions of emergent negotiations of meaning related to human communication behavior in technology-mediated settings with designed limitations on communicative affordances."

Improving Hearthstone AI by Combining MCTS and Supervised Learning Algorithms

Maciej Świechowski, Tomasz Tajmajer, Andrzej Janusz (2018)

Keywords - MCTS, Machine Learning, Neural Networks, Heuristic

Full paper

Abstract

"We investigate the impact of supervised prediction models on the strength and efficiency of artificial agents that use the Monte-Carlo Tree Search (MCTS) algorithm to play a popular video game Hearthstone: Heroes of Warcraft. We overview our custom implementation of the MCTS that is well-suited for games with partially hidden information and random effects. We also describe experiments which we designed to quantify the performance of our Hearthstone agent's decision making. We show that even simple neural networks can be trained and successfully used for the evaluation of game states. Moreover, we demonstrate that by providing a guidance to the game state search heuristic, it is possible to substantially improve the win rate, and at the same time reduce the required computations."

Exploring the Hearthstone Deck Space

Aditya Bhatt, Scott Lee, Fernando de Mesentier Silva, Connor W. Watson, Julian Togelius, Amy K. Hoover (2018)

Keywords - Game Balancing, Deck Building, Evolutionary Computation, Evolution Strategies

Full paper

Abstract

"A significant issue in game balancing is understanding the game itself. For simple games end-to-end optimization approaches can help explore the game's design space, but for more complex games it is necessary to isolate and explore its parts. Hearthstone, Blizzard's popular two-player turn-taking adversarial card game, has two distinct game-playing challenges: choosing when and how to play cards, and selecting which cards a player can access during the game (deckbuilding). Focusing on deckbuilding, four experiments are conducted to computationally explore the design of Hearthstone. They address the difficulty of constructing good decks, the specificity and generality of decks, and the transitivity of decks. Results suggest it is possible to find decks with an Evolution Strategy (ES) that convincingly beat other decks available in the game, but that they also exhibit some generality (i.e. they perform well against unknown decks). Interestingly, a second ES experiment is performed where decks are evolved against opponents playing the originally evolved decks. Since the originally evolved decks beat the starter decks, and the twice evolved decks beat the originally evolved decks, some degree of transitivity of the deck space is shown. While only a preliminary study with restrictive conditions, this paper paves the way for future work computationally identifying properties of cards important for different gameplay strategies and helping players build decks to fit their personal playstyles without the need for in-depth domain knowledge."

Automated Playtesting in Collectible Card Games using Evolutionary Algorithms: a Case Study in HearthStone

Pablo García-Sánchez, Alberto Tonda, Antonio M. Mora, Giovanni Squillero, Juan Julián Merelo (2018)

Keywords - Genetic Algorithm, Collectible Card Games, Artificial Intelligence

Full paper

Abstract

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

Programming a Hearthstone Agent using Monte Carlo Tree Search

Markus Heikki Andersson, Håkon Helgesen Hesselberg (2016)

Keywords - Monte Carlo Tree Search, Experiment, Simulation

Full paper

Abstract

"This thesis describes the effort of adapting Monte Carlo Tree Search (MCTS) to the game of Hearthstone, a card game with hidden information and stochastic elements. The focus is on discovering the suitability of MCTS for this environment, as well as which domain-specific adaptations are needed. An MCTS agent is developed for a Hearthstone simulator, which is used to conduct experiments to measure the agent's performance both against human and computer players. The implementation includes determinizations to work around hidden information, and introduces action chains to handle multiple actions within a turn. The results are analyzed and possible future directions of research are proposed."

Latent Predictor Networks for Code Generation

Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiský, Fumin Wang, Andrew Senior (2016)

Keywords - Computation and Language, Neural and Evolutionary Computing

Full paper

Abstract

"Many language generation tasks require the production of text conditioned on both structured and unstructured inputs. We present a novel neural network architecture which generates an output sequence conditioned on an arbitrary number of input functions. Crucially, our approach allows both the choice of conditioning context and the granularity of generation, for example characters or tokens, to be marginalised, thus permitting scalable and effective training. Using this framework, we address the problem of generating programming code from a mixed natural language and structured specification. We create two new data sets for this paradigm derived from the collectible trading card games Magic the Gathering and Hearthstone. On these, and a third preexisting corpus, we demonstrate that marginalising multiple predictors allows our model to outperform strong benchmarks."

I am a Legend: Hacking Hearthstone using Statistical Learning Methods

Elie Bursztein (2016)

Keywords - Games, Statistical Learning, Prediction Algorithms, Entertainment Industry, Computer Crime, Ethics

Full paper

Abstract

"In this paper, we demonstrate the feasibility of a competitive player using statistical learning methods to gain an edge while playing a collectible card game (CCG) online. We showcase how our attacks work in practice against the most popular online CCG, Hearthstone: Heroes of World of Warcraft, which had over 50 million players as of April 2016. Like online poker, the large and regular cash prizes of Hearthstone's online tournaments make it a prime target for cheaters in search of a quick score. As of 2016, over $3,000,000 in prize money has been distributed in tournaments, and the best players earned over $10,000 from purely online tournaments. In this paper, we present the first algorithm that is able to learn and exploit the structure of card decks to predict with very high accuracy which cards an opponent will play in future turns. We evaluate it on real Hearthstone games and show that at its peak, between turns three and five of a game, this algorithm is able to predict the most probable future card with an accuracy above 95%. This attack was called “game breaking” by Blizzard, the creator of Hearthstone."



Academia in Hearthstone