HearthSim — Intro

By | June 10, 2014

HearthSim is a general Hearthstone simulator that I am developing. It is designed to allow one to perform simplified theoretical analysis on Hearthstone decks.

The Setup

The simulator pits two AI controlled players against each other, playing a large number of simulated games. The game setup is similar to that of Hearthstone, but mulliganing is not supported at this time due to the difficulty in modeling it.

The AI Model

Currently, the AI is a simple, rudimentary score maximizing model. On each turn, the AI simulates all the possible moves that can be played and assigns scores to them based on how good the outcome is. Thus, the AI’s performance is going to be determined mostly by the function used to assign the scores.

Scoring Function

Note: Henceforth, variables with tilde denote values associated with the opponent (enemy).

The scoring function can be written as
$$S = S_{\rm b} + \tilde{S}_{\rm b} + S_{\rm c} + S_{\rm h} + \tilde{S}_{\rm h} $$
where \(S_{\rm b}\) is the friendly board score, \(\tilde{S}_{\rm b}\) is the enemy board score, \(S_{\rm c}\) is the hand’s score, \(\tilde{S}_{\rm h}\) is the enemy health score, and \(S_{\rm h}\) is the own hero’s health score. Let’s go through each one in a little more details.

\(S_{\rm b}\) — Friendly board score

The friendly board score is the sum of all attack and health value of the friendly minions that you have out on the battlefield. In other words,
$$S_{\rm b} = \sum_{i} (w_{\rm a} a_{i} + w_{\rm h} h_{i})$$
where, \(a\) is the attack value and \(h\) is the health value for all friendly minion \(i\). The attack and health values are weighted by \(w_a\) and \(w_h\) respectively. The rational for this score function is straight forward. The more attack value and health value your minions have, the better it is for you. The weightings are tunable parameters so that the AI can potentially have different focus: one AI might value health values more and play a vary control oriented game, while another AI can value attack values more and play an aggressive game. The weightings are currently set to 1.

\(\tilde{S}_{\rm b}\) — Enemy board score

The enemy board score is pretty much the same as the friendly board score, except it is the negative of it. That is,
$$\tilde{S}_{\rm b} = -\sum_{j} (\tilde{w}_{\rm a} \tilde{a}_{j} + \tilde{w}_{\rm h} \tilde{h}_{j})$$
for all enemy minion \(j\). In other words, the higher the health and the attack values of your opponent’s minions, the worse it is for you.

\(S_{\rm c}\) — Hand (card) score

In general, the more cards you have in your hand, the better it is for you. So, the hand score is pretty straight forward:
$$S_{\rm c} = w_m \sum_{k} m_{k}$$
where \(m_k\) is the mana cost of card \(k\). It’s debatable whether higher mana cost cards are actually more “valuable” or not, but for now this seems to work pretty well.

\(\tilde{S}_{\rm h}\) — Enemy health score

Most often, the less health the enemy hero has, the better it is for you. The enemy health score captures this observation:
$$\tilde{S}_{\rm h} = \left\{ \begin{array}{1 1} -\tilde{w}_{\rm hh} \tilde{h} && \quad \text{if $\tilde{h} > 0$} \\ \infty && \quad \text{if $\tilde{h} \le 0$} \end{array} \right. $$
where \(\tilde{h}\) is the enemy hero’s health value and the weight \(\tilde{w}_{\rm hh}\) is taken to be \(0.1\). The infinity is there to make sure that if there is a lethal, then it is always picked. In practice, it’s not infinity but rather a large positive number like 1e12.

\(S_{\rm s}\) — Your hero health score

Most often, the more health your hero has, the better. So,
$$S_{\rm s} = \left\{ \begin{array}{1 1} w_{\rm hh} h_{\rm s} && \quad \text{if $h_{\rm s} > 0$} \\ -\infty && \quad \text{if $h_{s} \le 0$} \end{array} \right. $$
where \(h\) is the enemy hero’s health value and the weight \(w_{\rm hh}\) is taken to be \(0.1\). The negative infinity is there to make sure that you never to anything that would kill yourself.

Move Generation

The simulation AI engine tries to brute force all possible moves that one can make given the current hand and board in the current turn. The number of possible moves scale exponentially with the number of minions on board and cards in hand, so the AI is limited to 30 seconds of computation, after which it gives up and plays the best sequence of moves that it has found thus far. On my Macbook Pro, this limits the total number of candidate moves to about 1.5 million moves per turn. It’s fair enough for now… after all, there is a 30 second limit per turn in the real game too.

One thing that the AI does not consider at this time is the possible moves beyond the current turn. I’m working on modeling this, but the sheer number of possibilities prohibit brute force approach to this. For now, it’s ok because I’m only looking at simple, idealized cases, but it’s definitely something I’m working on.

The Code

I plan to open up the code base in the near future.

Discussion

Head over to All Things Hearthstone on Versify to discuss or ask me any questions. I’ll be happy to answer anythings.

4 thoughts on “HearthSim — Intro

  1. Kallin Nagelberg

    Awesome. I’m looking to build something similar, and so happy to have this foundation as a starting point.

    Reply
  2. Leo

    Let us know how you consider possible moves beyond the current turn

    Reply

Leave a Reply

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