Author Archives: oyachai

Inspire Mechanic

AT_113AT_119AT_090

The Grand Tournament is coming soon, so it’s a good time to start looking at how the new mechanics introduced in the expansion will perform. As a starter, let’s look at the new mechanics: Inspire.

Inspire is an effect that triggers when you play a hero ability. There are various effects available, but in general, the mechanics allows you to use the hero ability without losing tempo, and this is a pretty big deal. There has been a lot of debate as to how effective this new mechanics is because the baseline minion bodies of Inspire minions are somewhat weaker compared to other equivalently costed minion. The goal of this post is to shed some light on how the mechanics might fare.

In this post, let’s take a look at three 5-mana Inspire cards: Recruiter, Kvaldir Raider, and [Mukla’s Champion]. We will take as the baseline super basic deck with Booty Bay Bodyguard replaced by Silver Hand Knight, and pit it against the same deck replaced by the Inspire cards. For each deck, we will create a Priest and a Warrior version.

I’ve only had the time to run about 1,000 games per simulation, but the results so far are somewhat surprising:

The win rate of the Inspire deck vs the Silver Hand Knight deck. Click on the data to see the actual simulation runs.
Priest Warrior
Recruiter deck 52.2% 59.0%
Kvaldir Raider deck 54.6% 67.4%
Mukla’s Champion deck 53.3% 59.6%

Overall, all three Inspire cards seem to be stronger than the baseline Silver Hand Knight. Granted, the AI used here isn’t tuned to play against Inspire cards, but it’s also not tuned to play Inspire cards either, so it’s difficult to say how much of an effect that would have. It’s also worth noting that the Inspire decks have almost no Inspire synergies. Part of the strength of Inspire cards comes from the fact that a single hero ability use can trigger Inspire effects of multiple minions on the board, but these decks do not have any other Inspire cards to take advantage of that. There are also cards that reduce the cost of hero abilities and buffs their effects, which are also missing from these decks. Basically, these simulations are the worst case scenarios for these Inspire cards — and yet, they still outperform a card that many consider as good value.

Based on these results, it looks like Inspire is going to be a strong mechanic. I can’t wait to try out some Priest inspire decks.

Soulfire

529

Soulfire is a card that was recently nerfed from 0 mana cost to 1 mana cost. It used to work really well as a cheap removal or a finisher, and the fact that Warlock can just life tap to replenish its card negated the downside of the card to a large degree. I want to get a feel for how big of a nerf this was, so let’s run some simulations.

Modeling Soulfire

In HearthSim, Soulfire is modeled as a damage spell card with an extra “reluctance” penalty to account for its downside. In other words,
$$V_{\rm Soulfire} = V_{\rm ds} + V_{\rm penalty},$$
where \(V_{\rm ds}\) is the card’s score as a vanilla damage spell and \(V_{\rm penalty}\) is the penalty term. Keep in mind that the higher the score of a card is, the more reluctant the AI becomes when using it; the AI looks to get more value than the value of the card being played. The penalty term can be further broken down into two components: the penalty value for the card that will de discarded, and a constant term to allow us to adjust the AI’s Soulfire usage further. The card discard penalty is just the expected value of the card that will be discarded, or, in other words, the average value of the other cards in the hand. In the end, we have
$$V_{\rm Soulfire} = V_{\rm ds} + \overline{V}_{\rm others} + V_{\rm a},$$
with \(V_{\rm a}\) representing the adjustable constant penalty value.

Simulation Setup

We’ll use the standard super basic deck, replace the two Goldshire Footman with two Soulfire, and play that against the vanilla super basic deck. We use Warlock as our hero and run 10,000 simulations per configuration, resulting in a 95% confidence range of less than 1% each way.

To quantify the effects of the nerf, and to investigate how to tune the AI for best Soulfire usage, we will run simulations with Soulfire mana cost at 0 and 1, while varying the parameter \(V_{\rm a}\).

Results

Below is a plot of Player0’s (Soulfire using player) win rate:

PlotRaw Data
V_a 0 Mana Cost 1 Mana Cost
-2 61.12% 60.15%
-1 64.78% 62.50%
0 64.42% 63.24%
1 64.80% 64.53%
2 62.10% 63.40%
5 51.22% 51.32%

First of all, we can see that Soulfire is a pretty good card overall, increasing the win rate by as much as 14% compared to Goldshire Footman. This fact may not be surprising, but it is nice to be able to quantify the difference.

Tuning \(V_{\rm a}\)

The data above shows that the optimal value of \(V_{\rm a}\) seems to be somewhere between -1 and 1. What this tells us is that Soulfire’s value can be more or less completely modeled by treating each of it’s effects independently: the 4 damage spell and the card discard effect. It turns out to be a relatively simple card to understand.

Effect of the Mana Cost Increase

What is more surprising is that the increase in mana cost (the nerf) doesn’t seem to affect the strength of the card all that much, as long as the card is being used optimally. In the 0 mana cost world, the data tells us that it was ok to use the card aggressively; the win rate with \(V_{\rm a}\) = -1 (aggressive) and \(V_{\rm a}\) = 1 (conservative) AIs performed similarly. In other words, it was such a cheap and efficient spell that you didn’t have to worry about getting the most value out of it. In the 1 mana cost world though, the demerits of using Soulfire sub-optimally are more pronounced, and a conservative and value oriented usage tends to do better. As long as proper value is realized, it appears that the mana cost difference is rather negligible, with 0 mana and 1 mana cost cases coming well within the margin of error with \(V_{\rm a}\) = 1.

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.

Hero Battle

In this post, we are going to take a look at how each hero’s ability affects their performance.

In Hearthstone, there are 9 different hero classes. Each hero has a hero ability that cost 2 mana

Setup

We will once again take the all minion super basic deck and have the deck played with different hero classes. Each of the 9 hero classes will play against a “no hero” player with the same deck, and we will look at the various statistics to see how each hero ability affects the outcome.

This time around, we will randomize the player’s play order. With this randomization, two identical deck/hero/ai combination played against each other are each expected to achieve a 50% win rate. We run 10,000 games for each hero combination.

As a side note, because the deck that we are using is composed of minions only and because there aren’t too many synergies between the cards in the deck, the simulations here are more analogous to arena games. We will see how our results compare to real arena stats (e.g., HearthStats).

Results

First, let’s take a look at the win rates of each hero class played against a no-hero player.

We see that there are broadly three categories:

  1. Mage — > 85% win rate
  2. Druid, Paladin, Priest, Rogue, Shaman, Warlock — ~70% win rate
  3. Hunter, Warrior — ~53% win rate

Mage

The Mage class is clearly in a league of its own. The Mage hero ability is so versatile and effective; able to efficiently finish off weak or weakened enemy minions and to do extra damages to the enemy hero when there’s nothing else to do. Not too surprisingly, Mage is one of the most effective class in the arena, and it consistently ranks among the top win rate in HearthStats arena data.

Druid, Paladin, Rogue

These three classes are also very strong. Not surprisingly, the three hero abilities are quite similar to Mage’s ability; they are effectively ways to deal 1 damage to any enemy character. This 1 damage can be used to efficiently gain board control. The key difference between these abilities and the Mage ability is that these abilities have drawbacks. A druid or a rogue typically end up taking damage when using their respective abilities, putting them slightly closer to death. As for Paladin, it’s hero ability effectively has a 1-turn delay; the ability can be used for efficient trading only on the next turn, and there is no guarantee that the summoned minion will survive the enemy’s turn. These drawbacks show up as the ~10% win rate difference.

Warlock

Hearthstone is a card game, so it’s not surprising that an ability to let a player draw cards is powerful. Warlock hero ability is particularly useful because it can be used many times, as long as the hero doesn’t die from the 2 damage it takes to use it. Warlock will typically play with a sizable (1 – 2 cards) card advantage against a no-hero. One puzzling thing though is that it is one of the least effective class to play in the arena, and the reason for this discrepancy is the result of interactions with the enemy’s hero ability. In this simulation, we had Warlock play against a no-hero, but in real arena games, it plays against other hero classes that typically has abilities that hasten Warlock’s death. Coupled with the fact that a warlock damages itself every time it uses its ability, it ends up dying before it can take full advantage of its extra cards. For example, Warlock versus Hunter using the same deck has Warlock pretty much even with Hunter, even though Hunter fares much worse against a no-hero than Warlock facing a no-hero.

Shaman

Shaman ability is decent, but it is random. The bigger problem is that one of the totem that it summons, Wrath of Air Totem, is completely useless in with this deck because the deck does not contain any spells. Given a deck with some spells, Shaman will probably fare slightly better.

Priest

What we see from the results is that healing is not as effective of a mechanics compared to dealing direct damage. It can still allow efficient trades by prolonging the life of cheaper minions, but the opportunities to use it is somewhat limited. Consider the situation where you (playing Priest) just killed an enemy minion with your own minion and your minion survived (yay, efficient trade!). The question then becomes, do you heal the damaged minion or do you use a card in your hand and place a new minion on the board? I’d usually go with the new minion…

Hunter, Warrior

These two classes have abilities that do not affect the player’s ability to control the board. Hence, in this game of board control (typical arena), their abilities do not really help them win games. Both of these classes are typically near the bottom of the arena win rate stats on HearthStats, though I think the strengths of Warrior class cards help it somewhat.

Miscellaneous Data

Here are some other data that might be of interest.

Most hero abilities hasten the game. Not surprisingly, Warrior ability significantly increases the average game duration.

We can see clear differences between abilities that help with board control and abilities that don’t.

Summary

So, the results so far are largely consistent with the actual arena stats. It will be interesting to see the complete all classes vs all classes results, though this takes a long time to run. It will also be interesting to see the results using other decks… perhaps that will be the next post.

HearthSim — Card Draw

Hearthstone is a turn based card game. The more cards you (the player) has in your hand, the more options you have, and your chance of winning increases dramatically. It stands to reason, then, that any mechanics that draws extra cards from your deck should provide you with a sizable advantage. How big is this advantage?

Let’s use HearthSim to gauge the power of a card draw mechanic.

Card Draw AI Model

In HearthSim, the AI deals with a card draw event using the following procedure:

  1. Compute all moves and their associated board scores assuming that all card draw mechanics are disabled.
  2. For each move (node on the moves tree) that has a card draw, add the expected score of the drawn card to the node’s score.
  3. Start to actually play the best scoring sequence of moves.
  4. At any point when it encounters a card draw event, draw the card and pause.
  5. Starting from the paused board state (after the card draw), go back to step 1 and repeat. Repeat until the sequence of moves end.

The rational for the AI handling of card draw comes down to the fact that the AI is not allowed to cheat. The AI is not allowed to backtrack the sequence of moves based on the outcome of the card draw, so it has to make the decision to play that move based on some expectation of what will happen when the unknown card is drawn. In situations like this, it often pays to assume the worst outcome, which is the outcome that the card that it draws is completely useless. What is a completely useless card? A card that can never be used… a card that was not drawn. So, the AI simulates the remaining moves assuming that no card was drawn.

Simulation Setup

We will once again use the all-minion super-basic deck used in the previous study with a generic no-hero. This time, we will replace the Oasis Snapjaw with a Gnomish Inventor. Both cards are 4 mana cost, and the only difference is 3 toughness points vs a card draw battlecry. Player0 will play either the original deck or the Gnomish Inventor deck. Player1 will always play the original deck.

Results

First, let’s look at the win rates.

Player0 Deck P0 Win P1 Win P0 Win % 95% Conf. Range
Oasis Snapjaw 23130 16870 57.83% 57.34% — 58.31%
Gnomish Inventor 26003 13997 65.01% 64.54% — 65.48%

So, the Gnomish Inventor deck is quite a bit stronger than the basic deck, at least in this setup.

Let’s look at the results in more detail to understand why the Gnomish Inventor deck does so much better. Below, we plot the average number of cards that each player has at the end of a given turn:

So, clearly, the Gnomish Inventor is helping to increase the number of cards that Player0 has in its hand past turn 4 (the earliest it can play a Gnomish Inventor is turn 3, but typically the AI will have used up [The Coin] by that turn, so it usually plays the Gnomish Inventor on turn 4). The consequence of the increased number of options provided by the bigger hand is quite striking; below, we plot the average number of minions on the player’s board at the end of a given turn:

The initial dip in the number of minions for Player0 past turn 4 is a consequence of the fact that a Gnomish Inventor is much easier to kill than a Oasis Snapjaw. It’s a 4 toughness vs 7 toughness thing. However, Player0 quickly catches up because it has an extra card that it can use. By turn 10, Player0 is almost half a minion ahead of Player1, and in the game of value trading, the slight minion advantage quickly magnifies into a serious advantage.

Summary

We see that in a minion heavy deck, card draw is a significant advantage. This partially (or wholly) explains the success of a Warlock zoo deck; Warlocks have an almost unlimited source of extra card draw in the form of its hero power. It’s an open question as to how this conclusion changes when we introduce spell cards into the deck, but my guess would be that card draws help just as much. I’ll leave that as a future study.

HearthSim — Modeling Unpredictable Outcomes

We have so far employed an AI strategy similar to how modern day chess or go AIs work: working out all possible outcomes of all possible actions that the player can perform and picking out the best series of actions. In games such as chess, the strategy works out well (witness recent computer vs humans chess games) as chess is inherently a deterministic game. However, Hearthstone is not deterministic. There are various cards with random effects that prevents us from simply following the footsteps of successful chess AIs.

There are primarily three ways where randomness comes into play in Hearthstone:

  1. Random effect cardsMad Bomber, Arcane Missiles, etc
  2. Card draw effectsNovice Engineer, Northshire Cleric, etc
  3. SecretsCounterspell, Explosive Trap, etc

The first item is pretty obvious. The second and third effects are problematic since the AI does not (supposed to not) know which cards are drawn or which secrets were played. So, it is not right to just draw a card immediately during the BoardState search tree generation.

So, we will introduce the concept of a StopNode. A StopNode is a BoardState search tree node that triggers a “stop” in the search tree generation. All nodes subsequent to a StopNode must be discarded, and the score of the StopNode must be computed solely from the information available at the StopNode without actually playing out the outcome of the random effect.

Each type of random effect node will have different strategies when it comes to deciding the score for its StopNode.

  1. Random effect cards — For random effects node, the strategy should be to work out the outcome of all possible random outcome and pick the expected value of the random outcomes’ scores. In practice, this is almost always impossible because the number of subsequent nodes explodes exponentially. For example, given a full opponent board, there are potentially up to 16.8 million ways in which Avenging Wrath can hit, with potentially millions of subsequent nodes for each Avenging Wrath outcome. In these situations, we will resort to a Monte Carlo simulation of the outcomes.
  2. Card draw effects — For card draw effects, the AI StopNode is necessary because the card to be drawn is unknown to the AI, and after the card is drawn, the AI must not go back and pick a sequence of moves that does not involve drawing a card (that would be cheating). The strategy to use here is, at a card draw StopNode, to pretend that a card draw does not happen and continue with the simulation. The score for the card draw node becomes the score of the best possible outcome without the card draw, plus the expected increase in the score due to the cards to be drawn. The expected increase can be computed because the AI knows exactly which cards remain in the deck, even though it doesn’t know which order the cards are in.
  3. Secret — The strategy for the AI will be to simulate all possible secrets that the opponents might have and work out the best subsequent moves for each one. Once the moves are computed, the AI will assume the best moves from the most penalizing secret and will start playing that sequence, until the actual secret is triggered. If the AI’s guess turns out to be correct, fine, at least it will be able to make the best out of it. If the AI’s guess turns out to be wrong, great, it can now go and play an even more optimal sequence of moves.

That’s the summary. I will write more details for each type once the implementations are done and tested.

HearthSim: Divine Shield Modeling — Part 2

This is part 2 of our Divine Shield modeling.

Setup

Let’s take our Super Basic Deck, with a generic no-good Hero (with no hero abilities), and pit it against an opponent with the same deck with Scarlet Crusader replaced by Magma Rager. We will call the player with Scarlet Crusader Player0, and the opponent Player1.

We take \(w_{\rm ds} = 0\) as a base case and will compare the performance of our AI as we tweak \(w_{\rm ds}\).

As a side note… the Scarlet Crusader is a much better card than the Magma Rager under this circumstance (and probably under any other circumstances). Player0’s base win rate is something like 64.8%, compared to 57.1% if Player0 used the same deck as Player0 (i.e., Magma Rager instead of Scarlet Crusader).

Results

The result of running the simulation with different divine shield weighting looks like this:

Raw Data

Recall from part 1 that our initial guess was that the optimal weighting will be somewhere between 0 and 1. Well, we were close. At least in this situation, the optimal weighting seems to be 1. Let’s try to understand the results in more detail.

Case: \(w_{\rm ds} < 0\)

When the weight is negative, the AI thinks that having a divine shield on a minion is a disadvantage, and it will prioritize removing the DS. Because attacking the enemy hero doesn’t remove the DS, the AI will pretty much always attack another minion with the Scarlet Crusader. This strategy turns out to be ok, and it maintains a >60% win rate, but it’s obvious that it’s not optimal.

As a side note, with the weight less than -1, the AI will never put the Scarlet Crusader onto the board because doing so will result in decreasing the score. So, there is a lower limit on \(w_{\rm st}\).

Case: \(w_{\rm ds} = 1\)

With \(w_{\rm ds}\) set to 1, the AI seems to perform optimally. This is because it ends up making decent trade decisions. At this weight, the divine shield on a Scarlet Crusader is worth 4, while if it is used to attack an enemy minion but fails to kill it, it does 3 damage. So, in the attack, the AI loses 4 score from DS and gains 3 from the enemy minion health going down — a losing proposition. The AI typically won’t make that attack and will go after something else with better value, such as hitting the hero. The simulation suggests that that is indeed the correct thing to do.

Case: \(w_{\rm ds} > 1\)

When \(w_{\rm ds} > 1\), the AI starts to consider the DS more and more valuable. At \(w_{\rm ds} = 1.25\), the DS is worth 5; at \(w_{\rm ds} = 1.5\), it’s 6; and so on. This increase makes the AI less eager to attack the another minion with the Scarlet Crusader, and it ends up pretty much always going for the face. Needless to say, always going for the face is a losing strategy (see this post for a demonstration of that), so the win rate plummets.

Miscellaneous Results

As suggested in a previous comment, I thought it would be interesting to look at the distribution of the duration of the game; i.e, how many turns does a typical game last given different strategies employed by the AI. In this setup, let’s compare the cases where \(w_{\rm ds} = 0\), \(w_{\rm ds} = 1\), and \(w_{\rm ds} = 2\). Below is the plot of the fraction of games that end at a given turn.

Games played with \(w_{\rm ds} = 2\) clearly tend to end earlier. This trend makes sense from the strategy point: the AI is being quite aggressive, and aggro games tend to be shorter. It’s also a hint that the AI at such weight isn’t losing close games; rather, it is usually on the receiving end of a beat down.

Summary

In conclusion… I think this is a fair divine shield model for the AI. DS certainly seems to help make the deck better, and as long as you use it to smack and kill other minions, it provides good value for its cost. You’d certainly want to pick Scarlet Crusader over Magma Rager, and most likely Argent Squire over Murloc Raider and so on.

As always, leave any comments or suggestions on our on our discussion board!

HearthSim: Divine Shield Modeling — Part 1

Let’s take a look at how we might go about modeling Divine Shield.

Recall that the AI scoring function is given by
$$S = S_{\rm b} + \tilde{S}_{\rm b} + S_{\rm c} + S_{\rm h} + \tilde{S}_{\rm h} $$
(see the original post). In particular, for each minion that one has on the board, the score goes up proportionally to the attack and health value of the minion:
$$S_{\rm b} = \sum_{i} (w_{\rm a} a_{i} + w_{\rm h} h_{i})$$
When a minion has divine shield, we expect it to be valued higher than a regular minion. But, by how much?

The essence of divine shield is that it allows the minion to be used (attack) once for “free.” That free attack does not damage or kill the minion, removing the divine shield instead and leaving a regular minion on the board. This observation suggests that we can think of a divine shield as effectively doubling the score of the minion. So, let’s propose to model each minion’s score as follows: for each minion \(i\) that has divine shield,
$$S_{\rm b} = (w_{\rm a} a_{i} + w_{\rm h} h_{i} + (a_{i} + h_{i}) * w_{\rm ds})$$
where \(w_{\rm ds}\) is the divine shield weight. When the divine shield is removed, it goes back to the regular minion score. Note that setting \(w_{\rm ds} = 0\) means that the AI pretty much ignores divine shield, while setting it to a high number (say, 2) means the AI highly values the divine shield and will try to keep it as much as possible.

In real game situations, we don’t expect divine shield to provide us with exactly twice the value that a minion would have without DS. In fact, there are quite a lot of ways in which the opponent can efficiently remove the DS: silence, any battle cry damage, hit it with a weak or almost dead minion, etc. Thus, we should expect the optimal weighting to be somewhat lower than 1, though by how much is a question we can only answer by running some simulations. Part2 will go into some simulation results.

Continues on part 2.

HearthSim: Super Basic Deck for Testing

Here’s the first real deck that I’ll be using for testing HearthSim in the next couple of posts.

Goldshire Footman × 2
Murloc Raider × 2
Bloodfen Raptor × 2
Frostwolf Grunt × 2
River Crocolisk × 2
Ironfur Grizzly × 2
Scarlet Crusader × 2
Silverback Patriarch × 2
Chillwind Yeti × 2
Oasis Snapjaw × 2
[Sen’jin Shieldmasta] × 2
Booty Bay Bodyguard × 2
Fen Creeper × 2
Boulderfist Ogre × 2
War Golem × 2

Hearthpwn deck list here.

It’s a super basic deck with no special abilities / battle cries, so the AI should be able to handle the deck well. The only untested part is the AI’s divine shield modeling, so that’s the first thing I’ll test and tune using this deck.

You can find the deck as part of “example2” in the examples directory of HearthSim. As usual, head over to HearthSim-dev board for any questions or discussions.