Probability in Hearthstone
Author - madmaxx On: Twitter | Youtube | TwitchTV | GitHub
Maximizing Chance 2: Card Draw
Calculating the chance you draw a particular card is the most straightforward thing in the world. Hover over your deck to see how many cards you have left. Lets say 20. You have 2 Flamestrike in your deck? Chance of drawing one Flamestrike with one card draw is 2/20 = 1/10. Chance of drawing a Flamestrike with two card draws is roughly 2/20 + 2/19 ~ 21%. This is not strictly mathematically true but you cannot do complicated math in your head when playing Hearthstone so its a good enough approximation.
Now that the straightforward thing is out of the way lets get into some more advanced topics - specifically, when you should mulligan, and how high the chance is that you will draw a card before the turn you actually need it. Or, consequently, how high the chance is that your opponent will have drawn, lets say, a consecration till turn 4.
The chance to NOT draw the card (after starting hand) is )26-1-N/27-2)*(26-2-N/27-2-N)*….*(26-C-N/27-C-N), where N is the quantity of that card in your deck, and C is the cost of the card. From the laws of probability it then follows that the chance to draw the card is: 1-(26-C-N/27-C)*….. Note that this assumes no additional card draw which of course betters your chances (it is basically equivalent of raising C by 1).
With that explanation out of the way here is the table from the beginning slightly modified to show the chance you get a specific card before or at the time you need it. This is for when you go first:
| Cost | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| n | ||||||||||
| 1 | 3.3 | 6.7 | 10.0 | 13.3 | 16.7 | 20.0 | 23.3 | 26.7 | 30.0 | 33.3 |
| 2 | 6.7 | 13.1 | 19.3 | 25.3 | 31.0 | 36.6 | 41.8 | 46.9 | 51.7 | 56.3 |
| 3 | 10.0 | 19.3 | 28.0 | 36.0 | 43.3 | 50.1 | 56.4 | 62.1 | 67.2 | 71.9 |
| 4 | 13.3 | 25.3 | 36.0 | 45.4 | 53.8 | 61.2 | 67.7 | 73.3 | 78.2 | 82.3 |
| 5 | 16.7 | 31.0 | 43.3 | 53.8 | 62.7 | 70.2 | 76.4 | 81.5 | 85.7 | 89.1 |
| 6 | 20.0 | 36.6 | 50.1 | 61.2 | 70.2 | 77.3 | 83.0 | 87.4 | 90.9 | 93.5 |
| 7 | 23.3 | 41.8 | 56.4 | 67.7 | 76.4 | 83.0 | 88.0 | 91.6 | 94.3 | 96.2 |
| 8 | 26.7 | 46.9 | 62.1 | 73.3 | 81.5 | 87.4 | 91.6 | 94.5 | 96.5 | 97.8 |
| 9 | 30.0 | 51.7 | 67.2 | 78.2 | 85.7 | 90.9 | 94.3 | 96.5 | 97.9 | 98.8 |
| 10 | 33.3 | 56.3 | 71.9 | 82.3 | 89.1 | 93.5 | 96.2 | 97.8 | 98.8 | 99.4 |
Here is the same table for when you go second:
| Cost | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| n | ||||||||||
| 1 | 3.8 | 7.7 | 11.5 | 15.4 | 19.2 | 23.1 | 26.9 | 30.8 | 34.6 | 38.5 |
| 2 | 7.7 | 15.1 | 22.2 | 28.9 | 35.4 | 41.5 | 47.4 | 52.9 | 58.2 | 63.1 |
| 3 | 11.5 | 22.2 | 31.9 | 40.8 | 48.8 | 56.2 | 62.7 | 68.6 | 73.8 | 78.5 |
| 4 | 15.4 | 28.9 | 40.8 | 51.1 | 60.0 | 67.6 | 74.1 | 79.5 | 84.1 | 87.8 |
| 5 | 19.2 | 35.4 | 48.8 | 60.0 | 69.1 | 76.4 | 82.3 | 87.0 | 90.6 | 93.4 |
| 6 | 23.1 | 41.5 | 56.2 | 67.6 | 76.4 | 83.2 | 88.2 | 91.9 | 94.6 | 96.5 |
| 7 | 26.9 | 47.4 | 62.7 | 74.1 | 82.3 | 88.2 | 92.3 | 95.2 | 97.0 | 98.3 |
| 8 | 30.8 | 52.9 | 68.6 | 79.5 | 87.0 | 91.9 | 95.2 | 97.2 | 98.4 | 99.2 |
| 9 | 34.6 | 58.2 | 73.8 | 84.1 | 90.6 | 94.6 | 97.0 | 98.4 | 99.2 | 99.6 |
| 10 | 38.5 | 63.1 | 78.5 | 87.8 | 93.4 | 96.5 | 98.3 | 99.2 | 99.6 | 99.8 |
This has some interesting consequences for the mulligan: mulligan..ing a card is basically a free new card draw. Player one thus gets up to three additional card draws, player two gets four additional card draws. Lets say you are in arena and you have only one fireball in your deck - usually you wouldn’t keep a fireball in your starting hand. But the chance of drawing it so you can play it against a potential Chillwind Yeti on turn 4 is surprisingly low with only 19%. I leave it to the reader to make strategy decisions based on these numbers.
Common Misconceptions and Fallacies
There are some things you need to be aware of when working with random events. Humans are notoriously bad when it comes to judge probabilities. See this Nobel prize winning work: Kahneman, Tversky: Judgement under uncertainty: Heuristics and biases. So in order for you to make the right calls, be aware of the following:
1. The gamblers fallacy:
You are throwing a fair coin. It has landed on head the last one thousand times. You throw again, what is the chance the coin will land on head?
The answer, of course, is that the chance that a fair coin will land on head is ALWAYS 1/2. It doesnt matter what has happened before. If you are thinking the probability is lower than 1/2, you are falling victim to the gamblers fallacy: “I lost the last ten games so now my chance of winning is higher.”. No, its not. If its truly random, the chance is always the same. Now, if you would ask the question: “What is the chance that a fair coin lands on head 1001 times in a row?”
The answer is 1 : 2 1 4 3 0 1 7 2 1 4 3 7 2 5 3 4 6 4 1 8 9 6 8 5 0 0 9 8 1 2 0 0 0 3 6 2 1 1 2 2 8 0 9 6 2 3 4 1 1 0 6 7 2 1 4 8 8 7 5 0 0 7 7 6 7 4 0 7 0 2 1 0 2 2 4 9 8 7 2 2 4 4 9 8 6 3 9 6 7 5 7 6 3 1 3 9 1 7 1 6 2 5 5 1 8 9 3 4 5 8 3 5 1 0 6 2 9 3 6 5 0 3 7 4 2 9 0 5 7 1 3 8 4 6 2 8 0 8 7 1 9 6 9 1 5 5 1 4 9 3 9 7 1 4 9 6 0 7 8 6 9 1 3 5 5 4 9 6 4 8 4 6 1 9 7 0 8 4 2 1 4 9 2 1 0 1 2 4 7 4 2 2 8 3 7 5 5 9 0 8 3 6 4 3 0 6 0 9 2 9 4 9 9 6 7 1 6 3 8 8 2 5 3 4 7 9 7 5 3 5 1 1 8 3 3 1 0 8 7 8 9 2 1 5 4 1 2 5 8 2 9 1 4 2 3 9 2 9 5 5 3 7 3 0 8 4 3 3 5 3 2 0 8 5 9 6 6 3 3 0 5 2 4 8 7 7 3 6 7 4 4 1 1 3 3 6 1 3 8 7 5 2 .
But every time you throw the coin, there is a 50:50 chance it will land on head it does not matter what happened before. In fact, the above number is the chance that any particular succession of 1001 coin throws will happen. In Hearthstone terms: if Mad Bomber hits you two times in a row, the chance its going to hit you next time on an empty board is.. 1/2.
2. Overestimating percentages
If I tell you Mad Bomber has a 60% chance of killing a Blood Imp, you would most likely take your chances. But 60% is pretty poor. It is only 3/5. In fact, in statistics you say something is random until it happens 75-80% of the cases (3/4 - 4/5). Humans constantly overestimate what percentages actually mean.
3. Overestimating anecdotal evidence/small sample sizes
If Mad Bomber worked great for you in the last ten games, it does not mean its a great card. Ten uses is a very small sample size, which means the sample is not representative of the actual situation.
Methodology
I’m not infallible so here is the software and methods that I used. For table 1 hit chance with large numbers of minions or projectiles I used this python script:
[su_spoiler title=”Python Script Source Code” style=”fancy” icon=”plus-circle”]import numpy
for projectiles in [3,4,5,6,8,9]:
for hits in range(1,projectiles+1):
results=[]
for minions in range(2, 6):
binomial = numpy.random.binomial(projectiles, 1.0/minions, 100000)
results.append(round(sum(binomial>hits-1)/1000., 1))
Which draws an actual random sample from a binomial distribution. So it basically simulates 100000 games per datapoint. For card draw I used this:
for cards in range(1,11): #for 1-10 cards in your deck
results=[]
probability = (startAtCards-cards)/startAtCards # so for 30 thats 29/30 - chance of drawing one card
results.append(probability)
for turn in range(1,10): # for turn 1-10
probability = probability*(startAtCards-cards-turn)/(startAtCards-turn)
results.append(probability)
with open(‘results.txt’, ‘a’) as f:
f.write(‘n </p>
<tr>n <th>’+str(cards)+’nn’)
for item in results:
f.write(‘ <th>’+str(round((1-item)*100, 1))+’n’)[/su_spoiler]
[su_spoiler title=”For Nat Pagle Card Draw: Python Script Source Code” style=”fancy” icon=”plus-circle”]
import numpy
results=[]
for turns in range(1,11):
results.append([])
binomial = numpy.random.binomial(turns, 0.5, 100000)
for cards in range(0,turns):
results[turns-1].append(round(100*sum(binomial>cards)/100000., 1))
with open(‘results.txt’, ‘a’) as f:
for i in range(0,10):
f.write(‘<tr>n <th>’+str(i+1)+’ cardsnn’)
for j in range(0,10):
if i < len(results[j]):
print ‘[‘+str(j)+’][‘+str(i)+’]’
f.write(‘n <th>’+str(results[j][i]))
else:
f.write(‘n <th>-‘)
[/su_spoiler]
For everything else I drew probability trees by hand and counted. In fact, at first I wrote a python program to do that for me:
[su_spoiler title=”Probability Python Script” style=”fancy” icon=”plus-circle”]
import itertools
minionHealth = 100
alphabet=(‘A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’,’J’,’K’,’L’,’N’,’O’,’P’,’Q’,’R’,’S’,’T’,’U’,’V’,’W’,’X’,’Y’,’Z’)
minionsOnTheBoard=’M’
for projectiles in [3]:
for minions in range(2, 6):
results=[]
for hitsToGet in range(1,projectiles+1):
for i in range(0, minions-1):
minionsOnTheBoard += alphabet[i]
permutations = [item for item in itertools.product(minionsOnTheBoard, repeat=projectiles)]
cleanedUpPermutations=[]
minionHits=.0
for item in permutations:
completeString = ”.join(item)
if completeString.count(‘M’) <= minionHealth:
cleanedUpPermutations.append(”.join(item))
if completeString.count(‘M’) >= hitsToGet:
minionHits += 1
numberOfPermutations = len(cleanedUpPermutations)
results.append(round(100*minionHits/numberOfPermutations, 1))
[/su_spoiler]
But permutations get too large to fit in memory for 4 projectiles, so it wasn’t used
Thanks for reading!
|
|
Unless it’s been changed in a recent patch, Mad Bomber (and Arcane Missiles) sample each hit individually. I’ve tested this extensively. The twenty permutations in your mad bomber table do not happen with equal probability.
Your conclusion on page 2 that random damage spells have a higher chance of hitting a high health creature is false. A Mad Bomber kills a lone Blood Imp just over 70% of the time. An Arcane Missiles kills a lone Blood Imp 87.5% of the time, and kills a Faerie Dragon 50% of the time.
Your right if the hits are sampled individually all the permutations do not happen with same probability: for example:
P(HHH) = (1/3)^3 and P(IHH) = (1/3)*(1/2)^2
The easiest way to calculate the probability of killing an imp with 3 random shots is :
P(“Killing imp”) = 1 - P(“Not Killing imp”) = 1 - (2/3)^3 = 19/27 wich is just above 70%
Unless it’s been changed in a recent patch, Mad Bomber (and Arcane Missiles) sample each hit individually. I’ve tested this extensively. The twenty permutations in your mad bomber table do not happen with equal probability.
Your conclusion on page 2 that random damage spells have a higher chance of hitting a high health creature is false. A Mad Bomber kills a lone Blood Imp just over 70% of the time. An Arcane Missiles kills a lone Blood Imp 87.5% of the time, and kills a Faerie Dragon 50% of the time.
Hey man!
Great article. I’m glad to see others trying to work out the math behind the game. The code was a nice addition!
In your article, you gave … well let me just quote it:
Now what’s that? I read the article over and over to try and deduce how card cost relates to draw probability, and I don’t think it does, man. They are what’s known as independent variables.
I’m pretty sure the forumula you’re looking for is still just a regular old hyper geometric distribution. External
Here’s a great calculator for it: External
For turn 1 drop in population size 26 as there are 26 cards left to draw and you can assume you’re looking for *a* specific one. Mulligan would be 23 because you’re discarding 3 before you draw three. The sample size is always 1. The number of successes in sample is 1 as well, because “duh”. And the number of successes in the population is either 2 or 1, unless you’re running arena.
Your math doesn’t run up with what I’ve been doing. Why do you include the card cost in calculating draw odds at all? It literally doesn’t matter, right?
@Rafajafar he mentions that it’s “to show the chance you get a specific card before or at the time you need it.”
That said, I’m sad my two math-related articles weren’t linked to/mentioned in this article =(
Yes, but that makes no sense, my man. The cost has zero impact on drawing whatsoever.
Let’s say you need a 4 drop and it’s turn 3. Lo! You draw a card and it is a 4 drop! Oh but it’s not the one you needed… see what I mean?
Here’s another one. You need a 4 drop and you get it! What are the odds that that happens rather than you do not get the card you needed? The same, right?
So what is the probability that you draw a 4 drop before turn 4? Is that the question? Well, that wasn’t clear. He said a “specific card.” and the odds of that happening follow the hypergeometric distribution.
Card cost plays no role.
I agree, the article isn’t calculating this correctly. The probability of the first shot from the mad bomber hitting imp should be 1/3.
This is probably pretty obvious, but I would calculate it as follows:
(chance hit imp) + (chance miss imp) times (chance hit imp) + (chance miss imp twice) times (chance hit imp):
mad bomber:
(1/3) + (2/3)*(1/3) + (2/3)*(2/3)*(1/3) ~= 70%
arcane missile:
(1/2) + (1/2)^2 + (1/2)^3 = 87.5%
(Of course its possible the game calculates it the way the article says, but based on the comments it dosn’t sound like it, nor does it seem like a hugely intuitive way to code it)
@Rafajafar
I thought he was using the cost to determine the turn you needed the card.
Really, C represents the number of draws you get to use before you need the card, not the cost. “What is the odds that you will get this specific card by turn C, or after C draws”. If you have no extra draws (roughly including mulligan but thats not exact since those cards go back into your deck), then we might assume that you usually want to play a card, one you really NEED, the first turn you can. This sets C = cost of the card for this specific but not uncommon situation.
@Turamarth: Handy tip: probabilities often become easier to calculate if you look at the chance of something not happening and then negate it:-
What’s the chance to miss the imp three times? (2/3)^3 ~= 29%. So what’s the chance to kill the imp? 100-~29 ~= 71%.
@Rafajafar: If you’re asking the question “What are the chances that I have this card that costs X by turn X” then an appropriate expansion of the hypergeometric function will certainly include X as a term.
You’re right, though. The formula posted in the article is wrong. Even before you account for the mulligan, the probability that you’ll have one of your two Leper Gnomes on turn 1 after your draw going first is just over 25%, not 6.7% as quoted in the table. Similarly, the probability that you’ll have one of your two Faerie Dragons on turn 2 after your draw going first is just over 31%, not 13.1%. If you have six two-drops and you mulligan for them going second, the probability you’ll have at least one is over 70%, not 41.5%.
There’s also some really weird rounding in the Nat Pagle table on page 1. 75.2% chance of at least 1 card after two turns? 25.1% chance of two cards after two turns? It doesn’t really make much difference, but I’m really curious about what method was used that would result in any error at all… O.o
Hey, as the author of this article, I might be ablte to shed light on some questions.
First, thanks for discussing this, I included all formulas, code, etc. for exactly the reason of review. So good on you for trying to shoot holes in this.
1. You are right that there is a mistake in the article, this was also extensively discussed in the reddit thread. The chance to hit an imp is equal to the chance to hit any other creature.
2. Card draw: cost doesnt factor in to card draw, but I use C to determine when you need the card. Flamestrike for example has a cost 7 so you have 7+starting hand draws to get flamestrike.
3. Weird rounding: I use random samples from a binomial distribution, bascially I didnt want to code binomial distribution myself, because I didnt want to mess it up. The numpy library has a random number generator based on the binomial distribution. So I just draw 100000 samples from that. That means its an approximation, but a really good one. As you said, the second decimal really doesnt matter.
Welcome to ihearthu!
#2 clears that up. Don’t think that was evident in the article, but that may be my poor reading.
“12 of which hit the one-health. 12/20 = 6/10 = 3/5 = 60%.
For a three health minion however, there are 27 potential outcomes, 19 of which are favourable. 19/27 = 70% chance Mad Bomber hits at least once.”
This logic is wrong. The first scenario only has 20 outcomes, but each outcome is not equally likely. After the bomber hits the 1 health minion, there are only 2 possible outcomes for future shots, each with a 50% chance.
That’s why the math should be as someone else said
1/3 to hit on first shot +
2/3 miss first * 1/3 hit second +
2/3 miss first * 2/3 miss second * 1/3 hit third
It’s 70% to hit one time, no matter how much health the minion has.
[…] original author- madmaxx for ihearthu.com […]
GREAT article! I’d peer-review it if I had the time. Basic-counting-probability and Hearthstone forever, Brother!