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:

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!