Monday, February 8, 2010

Gotta Catch 'em All

I'm not normally one to complain that Blizzard can't do math1, because I generally feel that they can do math pretty well. There are some hilarious slips, like in the beta when Wild Growth was a better single-target heal than Holy Light, but generally these things happen before their math teams gets a hold of things and never make it live. Sure, things are off what they should be, but compared to pretty much every other game, computer or otherwise, that has ever been made, WoW is pretty remarkably well balanced.

But I am not here to talk about how Blizzard gets things right, and there is one particular area where they seem consistently incapable of doing the math required to understand how long certain things will take.

The new Love is in the Air redesign corrects a lot of the boredom and frustration of the old event and updates the achievements associated with it. Probably the most infamous achievement that has been updated is the Be Mine! achievement. This year you have to eat all eight different candies and you can trade them around to other people, so it's a matter of making candies and then trading until you get the complete set. Last year the achievement was to make each candy from a candy bag. And the candy bags, of course, were rewarded at random from giving out cards to people... and they were bind on pickup. "No problem," I'm sure someone thought. You see, you only need 8 different candies and each bag has 10 charges. What's more, if you are aggressive about giving out love tokens you'll probably get two bags before the holiday is over.

This is the math I'm talking about. How many charges of candy bags does it actually take to get this done? Well, the first charge you use definitely gives you a candy you don't have, since you don't have any of them. The second time you use one there is a seven-in-eight chance you get a new candy. Once you have two candies there is a 6/8 chance, and so on. That means the average number of attempts to generate all the candies is 8/8 (first candy) + 8/7 (second candy) + 8/6 (third candy) + ... + 8 (last candy). Stated otherwise this is 8 * (1 + 1/2 + 1/3 + ... + 1/8). In general, any time you want to collect N different objects that appear with uniform probability it will take you, on average, N * sum(1/1, 1/2, ..., 1/N) attempts.

That series we are summing, the reciprocals of the natural numbers, is called the Harmonic Series. Summing this series and multiplying by N gives us the average we are looking for, and so it is kind of amazing that Blizzard seems incapable of figuring out the impact of this series on the game. Perhaps they can be forgiven as there is no closed form algebraic expression for the sum of the first N terms of the Harmonic Series2, but it's really not that hard to do it by hand for numbers like 8 and we do have computers to do these things for us when the number gets into the double digits.

Notice that the average is a little over 20. That means on average you needed three entire bags of candy, because having all but one of the candies when you finished your second bag did you no good at all. This led Blizzard to change the achievement to give it to you when you had made 6 different candies. And it's good that they did that, but couldn't someone have noticed that the achievement was inordinately cumbersome by doing some simple math ahead of time?

Of course all of this is just averages, and averages tell only a small part of the story. Another question we could ask is: if I have to collect a number of things, what are the chances I am done after a certain number of attempts? Here is the answer:

That is the likelihood you will be done after a number of attempts given trying to collect 6, 8, 10 and 20 things. I've marked the multiples of 10 attempts at 8 items so you could see the results relevant to the task at hand. You see, if you got two bags of candy there was about a 53% chance you were going to be finished. If you got three bags, 86%. Now don't be so happy about 86%. That means that if you were trying really hard to get this achievement done, being very dedicated to giving out those tokens and getting those presents, about 1 in 7 times you would have failed anyway because those bags just wouldn't give you that last candy. A very frustrating situation. Sure, the fourth bag brings it up to 96.27%, but that still leaves over 1 in 30 people without, and getting four bags required not only a lot of dedication but a *lot* of luck too.

I graphed how many attempts it would take for numbers other than eight so you could see how this thing gets out of hand. With eight items to collect you cross the 50% chance of being done mark at 20 attempts. With ten you need 27 attempts. That means a 25% increase in items to be collected resulted in a 35% increase in attempts to get to 50% chance of getting them (and a similar increase in the number of attempts to get to a 95% chance of finishing). With 20 items to collect the 50% mark is crossed at 67 items collected. So multiplying the number of items to collect by 2.5 multiplies the number of attempts by 3.35. Collection time expands more than linearly with items to collect.

So how does this apply to what ought to be the most infamous achievement of all, A Mask for All Occasions? Each time you open a treat bag you have about a 1 in 4 chance of getting a mask. Each time you complete one of the dailies you have a 1 in 10 chance of getting a mask. There are 20 different masks to collect. How long is this going to take?

Well, when you trick or treat you don't necessarily get a treat bag. Let's say you get one about three in four times (I think it might be less than this, but this seems like a decent estimate). Based on that, I calculated the average number of 2 week periods it would take to complete this achievement based on three different standards:

Typical participation - Complete the daily every day and Trick or Treat three times a day
Aggressive participation - Complete the daily and Trick or Treat eight times a day
Insane participation - Complete the daily and Trick or Treat 24 times a day

Here is the graph:

So, if you are insane enough to trick or treat on the hour every hour for two weeks you have a whopping 44.9% chance to complete the achievement in a year. Less than 50%. If you are quite aggressive about it (for people go to work, go to school and don't set alarms to wake them in the middle of the night but try really hard) then you have a less than 50% chance of being done in three years, but a pretty good chance of being done in four, and about a 93% chance of being done in five years. That means of all people who put every waking non-occupied hour into this for five years, about 1 in 14 of them won't be done. If you trick or treat a few times a day forget about it. You don't cross the 50% chance threshold for eight years, and after five years your chances have barely cracked one in ten.

This achievement is worth 10 points! The achievement Veteran Nanny which requires completing an easy series of quests that take about an hour once a year for three years is worth 50 points in recognition of the dedication it requires. A typical person who is interested in this achievement but doesn't have the ability to take two weeks leave from work and life every year near hallowe'en will never get this.

Achievements are not examined with a fine-toothed math comb to weed out outliers like this, but this is seriously egregious, and pretty much outdoes everything else in the game. Someone needs to check the math on the gotta catch 'em all feats in this game and fix up the odds.

1. Ignore the fact that this blog is here mostly so I can complain that Blizzard can't do math
2. To understand what this means, consider the sum of 1 + 2 + 3 + ... + N. That is always equal to N * (N + 1) / 2. There being no closed form algebraic expression of the Harmonic Series means that there is no neat way to write it like there is a neat way to write the sum of the natural numbers. In fact, in involves using a function called the Psi function which is the natural logarithm of the derivative of the Gamma function, which is an expansion of the concept of factorials to the real numbers (Gamma of n where n is a natural number is the same as n!). The idea that blizzard could be forgiven not being able to do this math on this account was, naturally, sarcasm.


  1. I don't know if it's just my internet connection at work or not, but your superscript hyperlinks don't work. They seem to be pointing to a link in your post editor instead of to the bottom of the post.

  2. Fixed. I've noticed this happening every now and then, but I don't know how to stop blogspot from reinterpretting my links.