What is the Best Hearthstone Deck Composition?

A friend recently introduced me to Hearthstone, an online collectible card game made by Blizzard.  The rules are described in detail at the link above, but the general idea is that you spend some resources ('mana crystals') to use cards in your hand with the goal of defeating your opponent by doing 30 damage to them.

Like many collectible card games, there are two major elements to Hearthstone's strategy.  First, you must design a deck of 30 cards which you believe will give you the best opportunities to thwart your opponent.  Second, you must play the hand you actually draw wisely in order to best take advantage of the opportunities presented to you during the game.

This post focuses on the former phase.  In particular, I want to know what the distribution of casting costs (in mana crystals) of the cards in my deck should be in order to make maximum use of the resources available to me.  If you are not interested in my methodology, you should skip to the results section below.

The Model of Hearthstone

Hearthstone is a complicated game.  There are numerous synergies between cards that would make you want to play them together, and there are equally many situations where you might not want to play them at all based on the cards your opponent has played.  I start with a simple assumption:  the player who uses the most mana crystals will tend to win.  This isn't strictly true, but it's easy to see that the player who has used more of his resources will probably be better off more often than not.

It's immediately clear that there's a flaw in my model:  the cards in a player's hand have a non-zero value just for being there!  There are cards with zero casting cost, and they are undeniably useful in real play.  So, how much is a card in your hand worth?

Figure 1:  Arcane Intellect card.  Card and artwork is copyrighted by Blizzard, and is used here for non-profit educational purposes only.

Figure 1 shows a card called Arcane Intellect.  It costs 3 mana crystals to use, and it allows you to draw two cards.  However, when you use Arcane Intellect the card itself is used up.  I am now left with a simple equation:

3 mana crystals + value of 1 card = value of 2 cards

Solving for the value of 1 card, I see that a card in my hand is worth 3 mana crystals.

Finally, I assume that the game is balanced.  That is, each card's usefulness is roughly equal to its casting cost in mana crystals plus the value of 1 card in my hand.

Action	Usefulness in Mana Crystals
Character Ability	2
Cost 0 Card	3
Cost 1 Card	4
Cost 2 Card	5
Cost X Card	3+X

The Greedy AI

The AI that I use to model plays with my deck is greedy.  Given the turn T that I wish to win at, it will try to maximize the total usefulness of cards and abilities played at that turn.  Thus, I can design an early-game win deck that attempts to win at turn 8, or a late-game deck that attempts to win later, around turn 17.

Note that my AI plays with complete disregard for the opponent or the opponent's plays, and it does not know or care about what card it is playing beyond its casting cost.  It is not possible for my AI to win or lose--the opponent in the simulation never does anything.  My AI greedily seeks to maximize the usefulness of the cards played at every turn.

My AI always goes first.  At the beginning of the game when all or part of the hand can be re-drawn, it tries to minimize the casting cost of cards in its hand.  The AI thus discards all cards whose casting cost is greater than the expectation value of the cost of cards remaining in the deck.

Each turn, the AI draws exactly one card.  I assume that it never draws any additional cards due to spells like Arcane Intellect in Figure 1.  If it does, then the value of the card drawn is represented by that card's usefulness in mana crystals (in the case of Arcane Intellect, the usefulness is 6 as shown in the table above).  Then, the AI will play the combination of cards and abilities that maximizes the total usefulness of cards played this turn.  If multiple combinations have the same usefulness, the combination that leaves the AI with the largest hand size is chosen.  This is identical to the knapsack problem where the items are the set of cards in the player's hand plus the character's innate ability, the weights are the cost in mana crystals, the backpack is the player's current pool of mana crystals, and the values are the usefulness from the table above.

For example, if the AI had 3 mana crystals and it had a cost 1, 2 and 3 card in its hand, it would play the cost 1 and cost 2 cards for a usefulness of 9.  A player in an actual game might find that it is actually more useful to play the cost 3 card, or to use the character's innate, cost-2 ability.

At turn T, the AI reports the total utility achieved in this simulated game.  This varies from simulation to simulation and the average is reported from a large number of simulations.

The Deck Designer

To design the deck with the highest chance of winning at turn T, the deck designer starts with 30 random cards with casting costs from 0 to 8 mana crystals.  The designer does not care specifically what cards these are, only their cost in mana crystals.  The AI is run on this deck composition a large number of times, and the average usefulness at turn T is reported.

Next, the gradient descent algorithm is run by taking a card out of the deck and replacing it with a card with a different casting cost for each possible combination of removed card and inserted card costs in mana crystals.  If any of the modified decks has a better usefulness than the original, then gradient descent is applied again on the modified deck.  If none of the modified decks has a better usefulness, then we have reached a local maximum of utility and this composition is saved as a candidate best deck.

The deck designer is run a large number of times, and the mana cost distribution with the best average utility is reported as the best overall composition.  Both the deck designer and the results of the simulated games are non-deterministic, so it's possible that a better deck exists than the result reported by the deck designer.

Results

I had the deck designer optimize for several different compositions:  an 8-turn quick kill composition, an 11-turn mid-game kill composition, a 14-turn late-game composition, and a 17-turn ultra-late game composition.  These were the best deck compositions according to my model, but when using these as a guideline in designing your deck, please keep in mind that the heuristic model should certainly come second to the actual synergies between your cards.  If you don't have exactly the same number of cards of each casting cost as the ideal composition, don't sweat it.  The error bars on the predicted strength are large enough that a difference of a few cards here or there is not going to make a noticeable difference.

Figure 2:  Simulated optimal deck compositions in mana crystals for decks designed to win at particular turns. 

Figure 2 shows the best simulated deck compositions.  Again, these compositions should be used as a flexible guideline as the synergies between the actual cards in your deck are going to make a much more significant difference than a slight deviation from the optimal casting cost distribution.  It seems that for all decks, the cost-3 and cost-4 cards are the most important workhorses.  A deck designed for an 8-turn kill has over half of the cards in the deck of 30 with casting cost 3 and a sprinkling of cards from cost 0 to 5.  On the other hand, a deck designed for a 17-turn kill has only one cost-2 and cost-3 card, with roughly equal parts cost-4 to cost-7+ cards.

Figure 3:  Total usefulness versus turn for the four optimal deck compositions shown in Figure 2.  Note that decks that take an earlier lead pay a price for that agility in the late game.

Obviously, a deck loaded with cost-3 cards like the 8-turn kill deck is going to pay a price in the late game.  Figure 3 shows this tradeoff between early-game strength and late-game strength.  The 8-turn kill deck gains a sharp advantage early on, then fizzles.  After turn 10, it's at a huge strength disadvantage compared to the other decks.  On the other hand, the 11 and 14-turn kill decks strike a better balance between early game strength and late game staying power.  Given that the 17-turn kill deck has only a slight advantage over the 14-turn kill deck at turn 20, I don't believe it would be worth designing a deck that is to win this late in the game.

Conclusions

Since running these simulations, I've changed my deck compositions to strive for an 8-turn kill.  This has been enormously successful for me in practice.  By choosing cards that harmonize well and selecting a deck composition with a high chance of getting these cards into play before my opponent can react, I've realized a substantial improvement in win rate.

I would recommend that the reader starts out with the 8-turn or 11-turn kill compositions depending on the desired play style.  The 14-turn composition may work best for a deck whose concept is to simply survive in the early game and to outgun the opponent in the late game.