Monthly Archives: October 2014

HearthSim Miscellaneous — Number of Possible Moves

The HearthSim AI employs a brute-force search of (potentially) all possible moves that it can make in a given turn to determine the best sequence of moves that it can make each turn. This defers from the more heuristic approaches taken by most bots out there (remember… HearthSim is not a bot and does not have the ability to connect to Hearthstone), and it almost always produces better results given enough computational power. The computational power is the key though because the number of different permutations of move sequence possible in Hearthstone is quite large.

Let’s first look at the simplest case. We assume that the player has no cards in hand and that the board has \(N\) friendly minions and \(M\) enemy minions. How many different ways are there to play the minions?

It turns out that this question depends on the Attack and Health values of the minions, but let’s consider the worst possible case where the player is not able to kill a single enemy minion. It this case, each of your \(N\) minions have \(M + 1\) targets (including the enemy hero), so our first guess is that the total number of permutations is \((M+1)^N\). But, the order of attacking actually matters, so we have to multiply that number by the total number of different attacking orders. In all, the total number of moves (\(V\)) is given by
$$V = (M + 1)^N N!,$$
which is a scary fast growing number. Think about it this way… the first part, \((M+1)^N\), scales exponentially in \(N\) and the second part, \(N!\), scales faster than \(N\), and you are multiplying the two parts! For the max board of 7 minions on each side, the number of permutations is 10,569,646,080… more than 10 billion. Other combinations of \(N\) and \(M\) are shown below:

The number of permutations of move sequence
N M
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 1 2 3 4 5 6 7 8
2 2 8 18 32 50 72 98 128
3 6 48 162 384 750 1296 2058 3072
4 24 384 1944 6144 1.50E+04 3.11E+04 5.76E+04 9.83E+04
5 120 3840 2.92E+04 1.23E+05 3.75E+05 9.33E+05 2.02E+06 3.93E+06
6 720 4.61E+04 5.25E+05 2.95E+06 1.13E+07 3.36E+07 8.47E+07 1.89E+08
7 5040 6.45E+05 1.10E+07 8.26E+07 3.94E+08 1.41E+09 4.15E+09 1.06E+10

On my Mac, HearthSim can simulate somewhere around 100,000 moves per second. For 10 billion moves, it would take around 27 hours. This is the reason why HearthSim AI has a “max think time” limit of 20 seconds.

Of course, that is not the whole story. We assumed that we had no cards in hand, but what if we do?

Again, let’s imagine the worst case possible. We assume that we have \(K\) number of Holy Smite in our player’s hand. Then, for each card in hand, we have \(N + M + 2\) possible targets on which to use the card. And again, we need to consider the order of playing the cards; the hand can be played in \(K!\) different orders, and for each order, it can be intertwined into the minion attack order in \((N+1)^K\) ways. The grand total is
$$ V = (M + 1)^N N! (N+1)^K K!,$$
which is a stupidly big number. For example, with 7 minions on each side and 10 cards in hand, the total number of permutations is something like \(5\times10^{30}\)… it would take about \(10^{18}\) years to simulate on my Mac, about 100 million times longer than the age of the Universe. Not gonna happen.

And lastly, there are battlecries that further increase the number of permutations, though it’s not straight forward to calculate the exact numbers in those cases.

In reality, the actual number of permutations is much lower because enemy minions die during the move sequences. In addition, a good portion of the permutations are actually identical, so the actual number of unique permutations is much smaller yet. But, even if we reduce the number of permutations by a factor of a million, it would still take 100 times the age of the Universe in the worst case. My next goal with HearthSim is to reduce the number of permutations as much as possible using heuristic arguments, e.g., it is never favorable to use Holy Smite on your own hero. If you have any good ideas on how to reduce the computational load, let me know!

Azure Drake vs Sludge Belcher

Lately, Sludge Belcher has become a really popular card. It seems like almost every deck out there, besides the zoo decks, are playing Sludge Belcher, and it has caused the games to slow down quite a bit.

No doubt, Sludge Belcher is a good card at the 5 mana spot. But, before the Naxxramas expansion came out, the consensus was that Azure Drake was the best card at the 5 mana spot for non-Zoo (and non-Hunter) decks. This begs the question… which card is better? Let’s try to answer that question with HearthSim.

Of course, the answer is going to depend on the actual composition of the deck and the hero class played. But to a large extend, the difference comes down to a card draw + spell damage vs a great Taunt that slows down the game. We’ve already seen how extra card draw can be, and we have some hints to how effect Taunts can be given some moderation.

Test Setup

The test will consist of playing variations on three decks: super basic deck with Booty Bay Bodyguard replaced by either Azure Drake or Sludge Belcher (Deck0), the first deck with War Golem replaced by Argent Commander (Deck1), and the second deck with Murloc Raider replaced by Holy Smite (Deck2) (it’s no secret that I main a Priest). The first deck favors the Sludge Belcher as it’s an all minion deck with no spells that can take advantage of the spell damage provided by Azure Drake. The second deck adds Argent Commander, which is largely consider to be the best counter to Azure Drake. The third deck adds a spell to the mix, witch should favor Azure Drake due to its spell damage.

For each deck, we will pit the Azure Drake version of the deck with the Sludge Belcher version of the deck, using no-hero, Priest, Hunter, and Rogue classes. We will simulate 10,000 games for each combination, which should give us a roughly +/- 1% range on the 95% confidence levels of our results.

Finally, since I don’t have the time nor the patience to simulate games for all Hero class combinations, we use 4 hero classes: No-hero, Hunter, Priest, and Rogue. I think it’s a representative sample, with Hunter representing the aggressive play style, Priest representing a control oriented style, and Rogue being somewhere in between.

Results

Below is a table summarizing the win rate of Player0, who is using Azure Drake in its deck.

Deck0 Deck1 Deck2
No Hero 55.95% 55.07% 58.48%
Hunter 52.72% 52.51% 53.48%
Priest 54.10% 50.84% 54.18%
Rogue 52.04% 51.73% 55.01%

Graphically,

The first thing to note is that all of the P0 win rates are above 50%. In other words, using Azure Drake is better than using Sludge Belcher in all of the cases that we have simulated. This result is surprising given the current popularity of Sludge Belcher, but the gist of the it seems to be that a Card Draw is better than a good Taunt minion. Keep in mind that Sludge Belcher will trade favorably against Azure Drake, leaving a 1/2 Taunt on the board… apparently, that is not enough of an advantage to overcome the card advantage afforded by the Azure Drake’s card draw.

Win rate differences between the decks are more or less what we expected. The use of Argent Commander helps Player1 to a small extent; the difference being small is probably due to the fact that there are only 2 of them in the deck and the chance of using it effectively is small. On the other hand, the use of Holy Smite swings the games in Player0’s favor, showing us that spell damage cards are quite powerful. Against a Sludge Belcher, that extra 1 damage (for a total of 3) with Holy Smite is especially effective, as it allows a player to efficiently kill it with a cheap 2 attack minion.

Between classes, the differences between Azure Drake and Sludge Belcher are more subtle. Priest seems to do well with Sludge Belcher in deck1, presumably because meaty Taunts + heal + effective counter against the opponent’s best card is a good combination of abilities to have.

Coming back to Deck0, let’s look at how Player0 and Player1 does at different points of the games. Below are Player0’s card advantage and minion advantage plotted versus turn.

This is becoming a familiar pattern: the extra cards from Azure Drake turns into a substantial card advantage, which turns into a substantial minion advantage a few turns later. Card draw is king (in moderation, of course).

Summary

The results here indicate that using Azure Drake is better than using Sludge Belcher under most circumstances. It’s probably interesting to look for edge case in which SB can outperform AZ… in due course.