💻 computer science

Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding

This paper proposes a Deep Surrogate Assisted MAP-Elites framework that integrates an online-trained deep learning model to significantly improve the sample efficiency and performance of automated Hearthstone deckbuilding by balancing the discovery of diverse, high-quality strategies with accurate outcome prediction.

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

Published 2026-03-02

📖 4 min read☕ Coffee break read

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build the ultimate deck of cards for a game like Hearthstone. You want two things:

Quality: The deck must be incredibly strong and win a lot of games.
Diversity: You don't just want one winning deck; you want a whole library of different winning decks (some that attack fast, some that play defensively, some that use magic, etc.).

The problem is that the number of possible decks is astronomically huge (more than the number of stars in the galaxy). Testing every single combination by actually playing the game would take a human lifetime. Even a computer would take forever because every game involves luck, random card draws, and complex strategies.

This paper introduces a clever solution called Deep Surrogate Assisted MAP-Elites (DSA-ME). Here is how it works, explained with simple analogies.

The Problem: The "Endless Trial and Error" Trap

Imagine you are a chef trying to invent the perfect new recipe.

The Old Way (MAP-Elites): You try a recipe, cook it, taste it, and write down the result. Then you tweak the ingredients slightly and try again. To find a truly diverse set of amazing dishes, you have to cook thousands of meals. This is slow, expensive, and tiring.
The Challenge: In Hearthstone, "cooking" a deck means playing 200 actual games against opponents. Doing this for thousands of decks is too slow.

The Solution: The "Crystal Ball" Chef

The authors propose using a Deep Surrogate Model. Think of this as a Crystal Ball or a Super-Intelligent Apprentice Chef.

The Apprentice: Instead of cooking every single meal, you train an apprentice (the AI model) to predict how good a dish will be just by looking at the list of ingredients.
The Training: At first, the apprentice is terrible. You give them a few random recipes to taste (the "Ground Truth"). They learn from these.
The Loop:
- Step A (The Dreamer): The apprentice uses its crystal ball to imagine thousands of new, weird, and wonderful recipes. It picks the ones it thinks will be the best and most diverse.
- Step B (The Reality Check): You take only the top recipes the apprentice suggested and actually cook them (play the real games).
- Step C (The Lesson): You show the results of the real cooking to the apprentice. "Hey, you thought this spicy dish would be great, but it was actually terrible! Here is why."
- Step D (Repeat): The apprentice gets smarter. Next time, it predicts even better.

Why This is Special: The "Two-Way Street"

Most previous methods tried to train the apprentice offline (before starting). They fed it a massive database of random recipes.

The Flaw: The apprentice learns from random data, not from the specific "style" of the best chefs. It might get tricked by "adversarial examples"—recipes that look good on paper but taste awful in reality.

DSA-ME is different. It is an online learning loop.

The "Dreamer" (the AI searching for decks) finds weird, tricky decks that fool the apprentice.
The "Reality Check" (the real games) teaches the apprentice exactly where it was wrong.
The apprentice gets better while the search is happening. They help each other: The search finds data to train the model, and the model guides the search to better places.

The Result: A Library of Champions

By using this "Crystal Ball" method, the researchers were able to:

Save Time: They found high-quality decks using far fewer actual games (simulations) than before.
Find More Variety: They discovered a wider range of strategies (fast attacks, slow control, etc.) than previous methods.
Beat the Competition: Their method outperformed both the "no crystal ball" method and the "offline trained" method.

The Takeaway

Think of it like navigating a massive, foggy maze.

Without the model: You have to walk every single path to find the exit.
With a bad map: You might follow a map that leads you into a dead end.
With DSA-ME: You have a map that updates itself in real-time. Every time you hit a dead end, the map redraws itself to show you the correct path, helping you explore the whole maze much faster and find the best treasures hidden inside.

This approach doesn't just solve Hearthstone; it offers a blueprint for how AI can efficiently design complex things (like robot movements or new drugs) where testing every option is too expensive to do the old-fashioned way.

1. Problem Statement

The paper addresses the challenge of efficiently generating high-quality and diverse content in games, specifically focusing on automated deckbuilding in Hearthstone.

Context: Hearthstone is a collectible card game with a massive search space (approx. $1.42 \times 10^{35}$ possible decks using basic/classic sets).
The Challenge: Evaluating a single candidate deck is computationally expensive and stochastic. To get a reliable performance metric, a deck must be played against opponents roughly 200 times due to variance in initial states and player actions.
The Goal: The objective is to use Quality Diversity (QD) algorithms to generate a collection of decks that are not only high-performing but also diverse in terms of strategic gameplay (e.g., "Aggro" decks that end games quickly vs. "Control" decks that prolong them).
Limitation of Existing Methods: Standard QD algorithms like MAP-Elites require a prohibitive number of expensive game engine evaluations to discover a diverse set of elites.

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

The authors propose DSA-ME, a model-based QD algorithm that integrates a deep neural network (DNN) as an online surrogate model to guide the search process.

Core Architecture

The algorithm operates via a two-loop structure (Inner and Outer loops):

Outer Loop (Ground Truth Evaluation):
- Evaluates candidate decks on the actual Hearthstone simulator (SabberStone).
- Each evaluation involves playing 200 games to extract ground-truth data: objective (winning/health difference) and measures (game length, hand size).
- This data is stored in a Ground-Truth Archive and a Data Buffer.
Inner Loop (Surrogate Exploration):
- Runs the MAP-Elites algorithm entirely on the Deep Surrogate Model.
- The surrogate model predicts the objective and measures for candidate decks without running the full game engine.
- This allows for rapid exploration of the search space to find diverse "elites" based on the model's predictions.
Online Training Cycle:
- The elites discovered in the Inner Loop are passed to the Outer Loop for expensive evaluation.
- The resulting ground-truth data is added to the training buffer.
- The Surrogate Model is retrained on this new, diverse dataset.
- A new Inner Loop is initialized with the updated model.

Key Technical Components

Surrogate Model: A Multi-Layer Perceptron (MLP) that predicts the objective (average health difference) and measures (turns, hand size).
Input Encoding: Decks are encoded as a "Bag-of-Cards" integer vector (frequency of each card, 0–2 copies).
Ancillary Data: The authors experimented with adding extra prediction targets (e.g., total damage, mana spent, win rate) to the surrogate model to improve internal representations, though results were mixed (see Results).
Perturbation: Decks are mutated by replacing $k$ cards with random cards from the cardset.

3. Key Contributions

Novel Algorithm (DSA-ME): Introduction of a model-based QD algorithm that uses a deep neural network trained online to assist MAP-Elites. This overcomes the dimensionality limitations of Gaussian Process-based surrogates (like SAIL) which struggle with high-dimensional, discrete data.
Online vs. Offline Training: Demonstrates that training the surrogate model during the search (using data generated by the algorithm itself) is superior to training on static, offline random data. The online approach allows the model to correct its own errors and focus on promising regions of the search space.
State-of-the-Art Performance: Sets a new benchmark for automated Hearthstone deckbuilding, outperforming model-free MAP-Elites, linear surrogate models, and offline-trained deep models.
Insight on Adversarial Examples: The paper highlights how the interaction between the search algorithm and the surrogate model helps identify and correct "adversarial" solutions (decks the model thinks are good but are actually bad), refining the model's accuracy over time.

4. Experimental Results

The experiments were conducted on the Rogue class using basic and classic card sets, evaluated against six diverse opponent decks.

Metrics:
- QD-Score: Sum of objective values of all solutions in the archive (measures both quality and diversity).
- Cells Filled: Percentage of the measure space covered (diversity).
- Max Win % / Max Health Diff: Peak performance quality.
Comparative Performance:
- DSA-ME (Online Deep) significantly outperformed all baselines.
  - QD-Score: 338.52 (DSA-ME) vs. 276.23 (Linear Surrogate) vs. 194.94 (Offline Deep) vs. 136.89 (MAP-Elites).
  - Cells Filled: 31.86% (DSA-ME) vs. 27.89% (Linear) vs. 21.64% (Offline Deep).
- Online vs. Offline: The offline deep model (trained on 10,000 random decks) performed worse than the linear model, indicating that random data is insufficient for training deep surrogates for this domain.
- Linear vs. Deep: The deep surrogate (DSA-ME) significantly outperformed the linear surrogate (LSA-ME), proving the necessity of non-linear modeling for complex deck interactions.
Ancillary Data Findings:
- Contrary to the hypothesis, adding ancillary data (e.g., mana spent, damage) did not improve performance and, in some cases, degraded it. The authors attribute this to the simplicity of the "Bag-of-Cards" encoding, which lacks the semantic context (card text, stats) needed to utilize the extra data effectively.
Post-Hoc Analysis:
- The surrogate model achieved high accuracy on measures (turns, hand size) but lower accuracy on the objective (health difference).
- Despite not predicting the exact "cell" in the MAP-Elites grid perfectly, the model successfully guided solutions to the correct region of the archive.
- Resetting the Inner Loop: Periodically re-initializing the MAP-Elites archive in the inner loop (rather than continuing from the previous run) was found to be crucial for covering the search space and avoiding local optima.

5. Significance and Impact

Efficiency: DSA-ME drastically reduces the number of expensive game engine evaluations required to find diverse, high-quality strategies.
Scalability: By using Deep Neural Networks instead of Gaussian Processes, the approach scales to high-dimensional, discrete search spaces common in procedural content generation (PCG).
Game Design Application: The method provides a tool for game designers to automatically balance collectible card games by generating diverse strategic archetypes that might be missed by human designers.
Generalizability: While tested on Hearthstone, the framework is applicable to any Quality Diversity problem where evaluations are expensive and the search space is high-dimensional.

In conclusion, the paper establishes that online training of deep surrogate models within a QD framework is a powerful strategy for solving expensive, stochastic optimization problems in game AI, outperforming both traditional model-free methods and static model-based approaches.