HearthSim Miscellaneous — Number of Possible Moves

By | October 9, 2014

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!

3 thoughts on “HearthSim Miscellaneous — Number of Possible Moves

  1. Xavier

    A possible idea would be to consider each minion as an agent, each minion would etablish he’s own list of priority from the minion he want to attack the most, to the minion he want to attack the less. Then we first try the combinaisons that satisfy a maximum of minions.
    Bonus or malus can be given to make the list, killing a minion while surviving , killing a dangerous minion , killing a minion stronger than you would give bonus.

    It is only a first idea, with a lot of weaknesses, because it ignores that minions can join forces to kill a bigger minion.

    A different approach could be : “How do we kill this minion ?” or “How do we bring them to 2 heath each in order to consecrate ?”
    -Make an ordered list of the minions we want to kill. Starting with the dangerous ones.
    -For each minion in the list find the cheapest way to deal with it.
    -If we can’t kill, go face

    Reply
  2. Hjulle

    Using MCTS would be an obvious way, but I guess that is cheating?

    Another thing that could make a huge difference would be to search (locally) for options that gives the same end result and see them as one. Most of the time the order of playing or attacking doesn’t matter, so this should help a lot. For example: Attacking one 2/5 minion with one 3/2 and one 2/3 will give the same outcome regardless of order.
    You could also try to search for independent moves (or sequences of moves according to the above) where the order is irrelevant. Example: Attacking minion A with minion B and then attacking minion C with minion D will be equivalent to doing it in the reverse order (unless deathrattle).

    Most of this should be possible to do automatically (but possibly hardcode the most common cases) and it should reduce the possibilities to a reasonable amount, especially if you find some more ways to lump together and ignore equivalent/independent moves.

    Reply
    1. oyachai Post author

      I don’t know much about MCTS, but my guess is that it does not always give you the optimal sequence of plays since it’s only a probabilistic search that only covers a small subset of the possible set of plays.

      As for pruning duplicate moves, that’s definitely possible. In fact, it’s already being done in HearthSim, at least to some degree. It becomes a tradeoff between memory usage and speed (it’s not trivial for the AI to “remember” all the sequence of plays that it has already tried), but it really does help in most situations.

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *