Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding

Yulun Zhang, Matthew C. Fontaine, Amy K. Hoover, Stefanos Nikolaidis

Abstract

We study the problem of efficiently generating high-quality and diverse content in games. Previous work on automated deckbuilding in Hearthstone shows that the quality diversity algorithm MAP-Elites can generate a collection of high-performing decks with diverse strategic gameplay. However, MAP-Elites requires a large number of expensive evaluations to discover a diverse collection of decks. We propose assisting MAP-Elites with a deep surrogate model trained online to predict game outcomes with respect to candidate decks. MAP-Elites discovers a diverse dataset to improve the surrogate model accuracy, while the surrogate model helps guide MAP-Elites towards promising new content. In a Hearthstone deckbuilding case study, we show that our approach improves the sample efficiency of MAP-Elites and outperforms a model trained offline with random decks, as well as a linear surrogate model baseline, setting a new state-of-the-art for quality diversity approaches in automated Hearthstone deckbuilding.

Introduction

Generating diverse, high-quality decks in collectible card games (CCGs) like Hearthstone is a significant challenge for game designers. Automated tools are needed to explore the vast strategic landscape—ranging from fast "aggro" decks to slow "control" decks—to assist in playtesting and balancing. Quality Diversity (QD) algorithms, specifically MAP-Elites, are well-suited for this task as they search for a wide variety of high-performing solutions.

However, the stochastic nature of Hearthstone makes evaluation computationally expensive. A single candidate deck requires at least 200 simulated games to yield a reliable win rate. Standard MAP-Elites requires millions of such evaluations, which is often infeasible. While surrogate models (approximations of the game engine) can speed up search, models trained offline on random data are prone to exploitation; evolutionary algorithms quickly find "adversarial" decks that the model overestimates but fail in actual gameplay.

Methodology: Deep Surrogate Assisted MAP-Elites (DSA-ME)

To address these challenges, we introduce Deep Surrogate Assisted MAP-Elites (DSA-ME). This model-based QD algorithm trains a deep neural network surrogate model online during the search process. The architecture operates through two alternating loops:

The DSA-ME architecture featuring the inner loop (surrogate search) and outer loop (ground-truth evaluation and model retraining).
  1. Inner Loop (Exploitation): MAP-Elites runs using the deep surrogate model instead of the game engine. The model predicts both the objective (e.g., health difference) and behavioral measures (e.g., game length). This forward pass is extremely fast, enabling the generation of a large archive of hypothesized elites.
  2. Outer Loop (Evaluation & Update): The elites discovered in the inner loop are evaluated using the ground-truth Hearthstone simulator (SabberStone). These results are added to a final archive, and the new data is used to retrain the surrogate model.

By continuously updating the model with the very decks that "fooled" it, the surrogate becomes increasingly robust and accurate at evaluating complex strategies.

Experimental Setup

Experiments were conducted using the SabberStone open-source simulator. We focused on the Rogue class, using a "Bag-of-Cards" encoding for a search space of 180 candidate cards. Candidate decks were evaluated against a suite of six high-performing pre-existing decks representing various archetypes (Hunter, Paladin, and Warlock).

Results and Discussion

DSA-ME significantly outperforms standard MAP-Elites and other surrogate baselines across all key metrics.

Performance comparison of DSA-ME against baselines across QD-score, number of elites, and threshold percentage.
  • QD-Score: DSA-ME achieved a score of 338.52, compared to 136.89 for standard MAP-Elites and 194.94 for the offline-trained model.
  • Diversity: DSA-ME filled 31.86% of the behavioral archive, more than doubling the coverage of standard MAP-Elites (14.36%).
  • Quality: The maximum win percentage found by DSA-ME was 98.4%, significantly higher than the 90.6% achieved by the model-free baseline.

Key insights from our study include:

  • Online Training Advantage: Unlike offline models that are easily exploited, online training allows DSA-ME to turn adversarial examples into training data, patching the model's blind spots.
  • Archive Resetting: Wiping the MAP-Elites archive at the start of each inner loop iteration prevents the algorithm from getting stuck in local optima, leading to better overall coverage.
  • Representation Matters: Surprisingly, adding ancillary data (like mana wasted) as prediction targets did not improve performance, likely due to the simplicity of the "Bag-of-Cards" encoding.

Conclusion and Future Work

DSA-ME sets a new state-of-the-art for automated deckbuilding in Hearthstone by effectively combining deep learning with QD search. While successful, the current "Bag-of-Cards" encoding ignores card mechanics like mana cost and text. Future work will investigate richer deck representations and high-fidelity surrogate models that predict turn-by-turn dynamics to further improve the search for diverse, high-quality game content.

Summary updated

Abstract

We study the problem of efficiently generating high-quality and diverse content in games. Previous work on automated deckbuilding in Hearthstone shows that the quality diversity algorithm MAP-Elites can generate a collection of high-performing decks with diverse strategic gameplay. However, MAP-Elites requires a large number of expensive evaluations to discover a diverse collection of decks. We propose assisting MAP-Elites with a deep surrogate model trained online to predict game outcomes with respect to candidate decks. MAP-Elites discovers a diverse dataset to improve the surrogate model accuracy, while the surrogate model helps guide MAP-Elites towards promising new content. In a Hearthstone deckbuilding case study, we show that our approach improves the sample efficiency of MAP-Elites and outperforms a model trained offline with random decks, as well as a linear surrogate model baseline, setting a new state-of-the-art for quality diversity approaches in automated Hearthstone deckbuilding. We include the source code for all the experiments at: https://github.com/icaros-usc/EvoStone2.
BibTeX
@inproceedings{zhang2022deep,
  author = {Yulun Zhang and Matthew C. Fontaine and Amy K. Hoover and Stefanos Nikolaidis},
  title = {{Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding}},
  booktitle = {GECCO},
  year = {2022},
  doi = {10.1145/3512290.3528718},
}
Figure