Author Archives: oyachai

title0

this is the story

bolded block

italicized block

underlined block

some link

  • list_item0
  • list_item1
  • list_item2
  1. ol_item0
  2. ol_item1
  3. ol_item2

Some quote

Original source: http://upload.wikimedia.org/wikipedia/commons/2/21/Cutest_Koala.jpg
Original source: http://gph.is/2cS3ItB
This is the greatest caption for the image of the greatest city in America

The Basics, a Tutorial Guide

Sint sunt consectetur ea id non officia esse pariatur consequat sit Lorem consectetur ea. Esse excepteur excepteur sint ad exercitation voluptate do exercitation occaecat elit ad est minim adipisicing. Elit in fugiat veniam officia deserunt ut excepteur. Ipsum ad amet sit aliquip cupidatat irure ea fugiat consequat dolore in sunt. Lorem Lorem ea dolore dolore deserunt qui eiusmod mollit consectetur veniam minim anim. Culpa ex amet adipisicing eiusmod velit aliqua aute. Elit magna ullamco qui velit officia magna. Esse qui consectetur reprehenderit esse voluptate ex ea velit. Nulla quis excepteur voluptate enim ut non qui occaecat eu ipsum id laboris quis. Aliqua dolor sunt commodo elit Lorem aliquip sit anim aute ullamco labore enim. Quis exercitation veniam eu incididunt cillum esse occaecat ipsum proident.

Mollit mollit adipisicing proident sit non reprehenderit fugiat est fugiat labore veniam nisi. Et quis qui culpa laboris excepteur sit consectetur nostrud occaecat quis veniam proident. Eu officia esse qui do ipsum sit ullamco. Enim voluptate irure quis adipisicing tempor occaecat sint velit incididunt veniam duis sint laboris. Consequat id labore Lorem reprehenderit non. In cillum excepteur enim id cupidatat.

Advanced Skillz!

Deserunt voluptate consectetur irure cillum magna esse incididunt. Aliquip adipisicing culpa veniam nulla reprehenderit mollit aliqua aute adipisicing ad cillum labore. Id do laborum id in nostrud irure nisi sunt mollit culpa nostrud. Culpa eu elit ea eiusmod proident aliqua voluptate duis cupidatat officia dolor nulla. Cupidatat irure do ullamco cillum cillum est id tempor.

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.