The Math of Hearthstone. Part II: Arena - the American Dream.

In the previous part of "The Math of Hearthstone" I gave a very brief introduction to Hearthstone and discussed the effects of the star system on the player experience. Today I'll focus on the other game mode - which happens to be my favorite - Arena.

Background

Arena: In this mode, each player constructs their deck out of random cards: the game offers 3 random cards and the player chooses 1 - repeating this process 30 times until a deck of 30 cards is created. This deck is used to play Arena games vs other players (who created their decks using the same process) until it loses 3 times or wins 12 - at which point rewards are given and the deck disappears - thus ending the Arena run. 

Rewards: The longer you "last" in the Arena (until 3 loses) - the better are the prizes you get in the end. The rewards fall into 2 categories: constructed resources (card packs, specific cards etc.) and gold. While cards might be very valuable for constructed (standard) game play, only gold (or real money) can be used to pay for another Arena run. You can earn gold during constructed play and save for an Arena fee - but it's a slow process, often taking days. Thankfully, if you do well, you can win enough gold (in addition to other rewards) to pay for the next Arena run - and if you do well again then you'll get to buy the next one etc.

This "dream" of endlessly playing for free (all the while winning more cards for your collection) is called "Infinite Arena".

The great equaliser

Unlike constructed, in the Arena everyone has an equal opportunity. It doesn't matter if your opponent bought thousands of card packs and have all the best cards in their collection - out here in the Arena he gets to choose from the same random pool of cards as a guy who never payed a single dollar. On average, everyone is equal. That means that rewards are based only on skill - a true meritocracy.

Not only that, but there's a chance you'll be so good that you'll "go infinite" - play as many Arenas as you wish - earning cards along the way - for free. All you have to do is be really good.

Equal opportunity, meritocracy, the chance to win big: it's the American dream in its purest form. I think this is the main reason I love the Arena mode - as someone who never "payed-to-win" I feel it's genuinely fair. Fair in ways that the current American capitalism can never be - in real life the "American Dream" is mostly a myth.

How good is good enough?

But let's get back to Hearthstone. So how good do you have to be to "go infinite"? Arena entry fee is 150 gold - so you need to win 150 gold per run on average. The rewards are somewhat random - so let's check the statistics:

Source: arenamastery.com - a website dedicated to tracking Hearthstone Arena stats. Based on ~447000 completed runs by thousands of players.

The graph climbs steadily upwards - as expected - but has a sudden jump from 6 wins to 7 - going from an average of 106 prize gold to 166. The reasons is that at 7 wins you are guaranteed by the game to get at least 150 gold - enough for another Arena run. That's why 7 is usually considered the magic number - allowing infinite runs. Actually - since sometimes you get more than 150 - you can get away with a slightly lower average number of wins per run (~6.7).
Ok - so how hard can it be?

Warning! Math ahead

We're interested in the number of wins - X - a player accumulates before he loses r games (r=3 in our case), given a win probability p. Turns out this mathematical problem is encountered in various fields - and has a name: Negative Binomial Distribution. We say that X is distributed according to the NB distribution with success probability p and number of allowed failures r:

X ~ NB (r,p)

Note that we neglected for now the additional stopping condition of 12 wins - which we'll discuss in a moment. 

First, let's say the player has a coin-flip chance to win or lose against anyone - p=0.5. The average number of wins ( E[X] ) for the NB distribution is given by (from Wikipedia):

E[X] = 

In our case p=0.5 and r=3 - so we get an average of 3 wins. This makes intuitive sense - since we have 3 opportunities to fail and on average out of every 2 games we win 1 and lose 1 - so we'll average 6 games and 3 wins. From the gold vs wins graph above we can see that 3 wins give ~40 gold - very far from infinite Arena. 
But we're after the American Dream - we want to be better than a coin-flip. Let's plot the win rate (p) vs average number of wins (X) and see how much better than 50% we should strive for:

Turns out we need to win 70% of our games to reach a 7 win average (or ~69% for ~6.7 wins) - an impressive feat. At least now we have a simple way to relate between average wins and win rate.

How much did we change the result by neglecting the 12 win condition? Imagine you had an amazing run - a combination of skill and luck got you a great deck and you're piloting it incredibly. You could perhaps get up to 20 wins before finally suffering the 3rd loss - only you can't, since the game will stop you at 12 no matter how perfect is your record. This 20 win run, though obviously very rare, would greatly boost your average number of wins - but instead you only get 12, reducing the size of the boost. The NB distribution doesn't know that and assumes a player can reach any number of wins - so for a given win rate p, the real average number of wins per Arena run would be somewhat smaller than what's given by our formula.
Let's see how close is our approximation to reality. The only situation our calculation gets wrong is when a player would finish with more than 12 wins. How probable is this occurrence? The probability of getting more than 12 wins, X > 12, is:

P [X > 12] = 1 - P [X <= 12]

Wikipedia tells us that given a certain win rate p, allowing r number of failures and looking for k wins - the formula for the probability is this:

P [X <= k] = 1 - I_p(k + 1, r)

I is the regularized incomplete beta function - which is quite complex so I won't go into it here. Instead, let's use it and plot P [X > 12] as a function of p (from casio.com):

The y axis represents P [X > 12] and the x axis is win rate (p). The red line is irrelevant for our purposes.

In our first exercise we took p=0.5 - which leads to P [X > 12] = ~0.37% - so we can wholeheartedly assume that, for any practical purpose, it never happens. So our approximation - which neglects this occurrence - is quite accurate.

For the American Dream we needed p=0.7 - leading to P [X > 12] = ~12.7%. So, perhaps unsurprisingly, when you're very good you tend to encounter the 12 win limit much more often - so the actual average number of wins will be less than our approximated 7 - meaning that even 70% win rate might not be enough. A slightly more rigorous calculation can show that with p=0.7 the probability of getting at least 7 wins is ~46% but with p=0.75 for example it jumps to 60% - easily enough for infinite arena.

Note that we didn't address the fact that the win rate doesn't remain constant between Arena runs - as it depends on the current deck - which is, at least partially, based on luck. Since we're interested only in long term averages across many runs - it doesn't affect any of the conclusions.

But there's a bigger point to address: win rate isn't constant even within a single run. The Hearthstone matchmaker tries to pair each player with an opponent that had a similar level of success, so if you went 2 wins 1 loss - for the 4th game it will try to find an opponent who likewise went 2-1. This additional effect reduces the variance of X - since, on average, you get weaker opponents at the start of your run and stronger ones as you progress - so it's less likely you'll go 0-3, but also less likely to get 12 wins. It doesn't effect the averages because we calculate win rate including this variation of opponent skill level - and actually makes the average more meaningful as a larger percentage of Arena runs will end with a result closer to the average.

Design conclusions

It's interesting to note that one of the prizes given at the end of a run is a card pack - regardless of the number of wins. The same pack can be bought at the store for 100 gold - so as long as we win 50 gold we at least break even on our 150 gold investment. Alas, a coin-flip player loses a little bit on an average Arena run (even after factoring card prizes in addition to the ~40 gold) - which, I'm sure, is intentional design by Blizzard. 

Another point to mention is that every Arena match has a winner and a loser - so if we think of the total pool of players currently playing Arena, each game costs a loss from the total pool of loses. Each Arena entry adds 3 new loses to the pool - allowing for 3 more wins by other players. If everyone were coin-flip players then everyone would have an average of 3 wins and that's it - but in order for "big winners" to exist there have to be players doing worse than coin-flip - getting less than their "fair share" of 3 wins. That's the nature of zero sum games. But, like in any other aspect of games or life, the more you try the better you get - so, at least in part, the good veteran players are being "sponsored" by the newer ones until they get better.

Until next time, may your real life be as fair as Hearthstone Arena.


Michael.


EDIT:
As was pointed out by Lorinda from the ArenaHS subreddit, the variance in number of wins per arena has a slight effect on the average gold. The prize distribution is slightly convex - meaning you'd get more gold for going 11-3 and 0-3 vs. 6-3 and 5-3 - even though the resulting win percentage is identical. This gives an advantage to higher variance - sometimes "scrubbing out" and sometimes "going all the way" is better than being consistent. Matchmaking reduces the variance of each run - but not to 0 so the convexity still adds a bit of gold. The difference makes "going infinite" roughly ~1% easier :)

{Thanks to Nataly Eliyahu for reading and commenting on earlier versions}

{If you find my ideas or analysis interesting - consider subscribing (box on the right). You'll never miss a post and I'll know I'm not talking only to myself :) }