iamcal.com

18

World of Warcraft - Beating the RNG Boss

By Cal Henderson, March 4th 2010.

One of the hardest bosses to fight is the RNG, or Random Number Generator. While the tactics are fairly straight forward (try, try, try again), defeating this boss can take a lot of patience. Lots of players don't understand quite how this boss fight works, so i'll attempt to explain.

A few months back, I created a World of Warcraft addon called BunnyHunter, to help you track your progress when farming for rare pets.

BunnyHunter Screenshot BunnyHunter Screenshot

The rarest pet of all is the Hyacinth Macaw which drops from Bloodsail Pirates off the south coast of Stranglethorn Vale. Each pirate has a 1 in 10,000 chance of dropping this rare pet. I built the addon especially to help me in my quest to find the macaw.

Misunderstandings

Quite a few people have misunderstood how BunnyHunter calculates its percentage score. For instance, a BunnyHunter user posted this message to one of my favorite WoW blogs:

1. The app lets you know that there is a 1/1000 chance of an Azure Whelp dropping per kill when you are farming specific mobs in Aszhara.
2. The app lets you track "progress" toward getting a better chance of your drop because it lets you know how many whelp carriers you have killed. If you kill 150 mobs, it lets you know you have approximately a 15% chance "so far" of getting the whelp.
3. It has a tracking bar that shows you your progress - so after 1000 kills, you have a 100% chance so far of getting your drop.

This shows a real fallacy in the RNG analysis which is that successive kills actually increase your chance of getting a rare drop. Despite the multiple attempts, you have the same chance of getting the drop on your first kill as you do on your 999th kill which is 1/1000.

Of course, BunnyHunter doesn't work this way at all. This is an all-too-common misconception, however. The thing which governs this is called Probabilistic Independence - the fact that whether one mob dropped the loot or not, this has no bearing on whether a second mob will drop the loot. By extension, having looted 1000 consecutive mobs which did not drop the loot has no effect on the next mob you loot. If the drop chance is 1 in 100, there will still be a 1 in 100 chance that the next mob you loot will drop the item.

But if you use BunnyHunter and loot 1000 mobs that drop the Azure Whelp, it wont say 100%; it'll say 63.2%. The reason we can come up with any number at all, is because we can derive the probability that a piece of loot will drop at least once in a given sequence of lootings.

Say that we have 3 mobs and each has a 50% chance to drop the thing we're looking for. There's an 87.5% chance we'll get the item (7/8ths) after looting all 3. To see why, we'll construct all of the possible outcomes, which are all equally likely (we're cheating by using a 50% drop chance, to make the example easier):

first mob / second mob / third mob

1) no drop / no drop / no drop 
2) no drop / no drop / drop 
3) no drop / drop / no drop 
4) no drop / drop / drop 
5) drop / no drop / no drop 
6) drop / no drop / drop 
7) drop / drop / no drop 
8) drop / drop / drop 

In only one of these 8 possible outcomes did we fail to get the item, so the chance we'll get it is 7/8 = 87.5%. The trick here is that we care about the chance to have gotten the drop one or more times, from 3 mobs. Another way to look at it is that the chance of getting the drop is 100% minus the chance of none of the 3 mobs dropping it.

This last part is the important bit. The chance of having gotten the Azure Whelp after 1000 loots is the same as one minus the chance to have not seen it. We can calculate the chance to have not gotten it, 1000 times in a row, by taking the chance to not get it once (1 - 0.001 = 0.999) and multiplying it by itself 1000 times (for the 1000 mobs we looted). This gives us a 36.8% chance of not seeing it drop once, so the inverse is that there's a 63.2% chance (100 - 36.8) that we will have seen it drop. Easy!

The generalized formula is:

chance to have dropped at least once =  1 - ((1 - per-loot drop chance) ^ loots)

That little symbol is the power operation.

BunnyHunter uses this formula to give you a percentage score of how likely you are to have gotten the drop so far. It won't tell you when that drop will happen - it could be the next mob or 1000 mobs from now - but it will tell you how (un)lucky you have been.

A quick diversion

Not all drop rates in World of Warcraft actually exhibit probabilistic independence. Since WotLK, quest item drops actually use a progressive drop rate. This is to avoid the situation where you grind and grind but are the unlucky person who kills 50 mobs and doesn't get a single quest item.

Blizzard probably did this for two reasons. Firstly, unlike vanity drops (such as the mythical macaw), you get stuck if you can't get the item. This is bad game design, since you need the items to continue the quest. Secondly, and probably more importantly, is that until you start getting drops you are not sure you're doing the right thing. Having a quest item only drop after 50 loots gives you 49 chances to think you're doing the wrong thing and give up.

But we're farming pets here, so it doesn't apply to us!

World of Dropcraft

The problem with probability calculations is that not only are they confusing, but people often use the wrong calculation and then stand behind their results. Rather than try and convince you with math, I'll use good old brute force.

I created a simple PHP script which runs a number of 'drop trials', which simulate looting mobs in WoW. The script 'loots' a mob by creating a random number between 1 and the inverted drop chance - for the Hyacinth Macaw, this is 1 in 10,000, so the script will generate a random number between 1 and 10,000 (inclusive). If the random number is 10,000, then we count it as a drop - the mob dropped our parrot. If the number is anything else, we count it as the mob dropping something else (or nothing at all). In this case, we roll another number and start over. We keep rolling numbers until we get a drop, and then we note down how many times we rolled a random number. This is how many loots it took to get our drop. So far, simple.

Because computers are nice and fast, we'll take this trial and perform it 10,000 times, noting down each time how many loots it took before we saw a drop. This will give us a big picture of how many loots it generally takes to get our drop. So let's run the script!

World of dropcraft
Drop chance is 1/10000, running 10000 trials
....................................................................................................

Mean loots per drop: 9958.6041
Median loots per drop: 6888

Luckiest loots: 2
Unluckiest loots: 106335

After running 10,000 trials (it takes about 30 seconds on my PC), we're left with a list of 10,000 numbers - each of them how many loots it took on that trial to find our item. So, some analysis!

We can take the biggest and the smallest numbers and call them the luckiest and the unluckiest. Of our 10,000 trials (the equivalent of farming 10,000 Hyacinth Macaws in the game, and noting down how many loots it took you each time), the quickest we ever saw the item drop was after 2 loots. Wow! I'd be pretty damn happy if that happened to me in game. I'd be very very lucky. At the other end of the scale, one of the trials took 106,335 loots (over one hundred thousand!) before they got the drop. That would really suck. At my farming speed, that would take almost 2 solid weeks of farming.

We can see the average (mean) loots taken, by adding together all of the numbers and dividing them by the number of trials. When we do this, we get 9958.6, which is pretty close to 10,000. We would expect this, since the drop rate is 1 in 10,000. If we ran more trials, we would expect this number to get closer to 10,000 (this is called convergence).

We can also calculate the median, which is the number of loots at which 50% of players would have gotten the drop. This is different to the mean, but can be a little confusing, so I'll explain with an example.

Say you had a drop that was very common - most people got it on the first loot. If 9 players got it after the first loot, but 1 poor player took 10 loots, the average would be 1.9 ([1+1+1+1+1+1+1+1+1+10]/10). However, we can easily see that more the half of the players would have gotten the drop after the first loot. That's because the median is 1. We calculate the median by sorting the list into order and picking the middle value. The mode is another kind of similar average, but we'll ignore that here because it gets hard to calculate once we use big numbers and can be misleading.

So in this trial, the median is 6888. Why do 50% of trials get the drop after 6888 loots, while the average is 10,000? The answer lies in the way drops work. The fewest number of loots you can get a drop in is 1; you have to loot at least one corpse to get a drop. But the highest number of loots is infinite. You could loot one million pirates and never get the parrot. It's unlikely, but it's possible. So while there's a chance it will take one million loots, which throws off the mean, very few players will take this long, so the median stays lower.

Calculating the median

So what is the median good for? Well, it can tell us at what point we go from being lucky to unlucky. Someone who is lucky gets the drop in less loots than the majority of other players. Someone who is unlucky gets the drop after more loots. While drop probabilities can't tell us when we will get a drop, they can tell us who unlucky we have been to not get it so far, or how lucky we would have to be to get it by a certain number of loots.

So how do we calculate the median? Let's run another 10,000 trials against my favorite pet, the Hyacinth Macaw.

World of dropcraft
Drop chance is 1/10000, running 10000 trials
....................................................................................................

Mean loots per drop: 10082.6048
Median loots per drop: 6996

Luckiest loots: 2
Unluckiest loots: 91637

So after 10,000 trial sequences, it took an average of 10,082 loots to get the item. If we ran a lot more trials, this number would approach 10,000 (since it's a 1 in 10,000 drop chance).

The median, however, is around 7000, as before. This is the number of loots at which 50% of trials had found the drop. If you took less than 7k, you were lucky. If you took more than 7k, you were unlucky. But where does this number come from?

Take our formula for drop chance in a sequence of n loots:

dropped_at_least_once_chance = 1 - ((1 - drop_chance) ^ loots)

We can rebalance this formula using logarithms into this:

loots = log(1 - dropped_at_least_once_chance) / log(1 - drop_chance)

If we plug in our numbers, 50% chance to have dropped at least once and a 1/10,000 drop chance, we get 6931, which is pretty close to the 6888 and 6996 results we saw in our tests.

We can confirm this by using higher drop rates, since the trials will converge faster. Using the formula, we can make the following predictions:

1/100  -> 50% after 69 loots
1/1000 -> 50% after 692 loots
So let's run the trials again with these drop rates and see what we get...
World of dropcraft
Drop chance is 1/1000, running 10000 trials
....................................................................................................

Mean loots per drop: 994.0178
Median loots per drop: 689

Luckiest loots: 1
Unluckiest loots: 11067
World of dropcraft
Drop chance is 1/100, running 10000 trials
....................................................................................................

Mean loots per drop: 100.116
Median loots per drop: 70

Luckiest loots: 1
Unluckiest loots: 915

Yup, that pretty much seals it. If you take less than 6931 loots to get the Hyacinth Macaw, you're lucky. If you took more than 6931 loots, you're unlucky. If you took exactly 6931 loots, well, you're Mr Average.

An Odd Side-effect

So, earlier I said that the mode is an odd measure of 'averageness' for drop chances, but it can be used to point out something pretty strange. We can use some simple math to calculate the probability that a drop will happen on a given loot. We'll generalize a little here - let's say that p is the chance to drop the loot we want.

drops on 1st loot = p
drops on 2nd loot = p * (1-p)
drops on 3rd loot = p * (1-p) * (1-p)
drops on 4th loot = p * (1-p) * (1-p) * (1-p)

A strange thing happens when we plug in the numbers. Let's use the good old macaw's 1/10000 drop rate.

drops on 1st loot = 0.0001                            = 0.00010000
drops on 2nd loot = 0.0001 * 0.9999                   = 0.00009999
drops on 3rd loot = 0.0001 * 0.9999 * 0.9999          = 0.00009998
drops on 4th loot = 0.0001 * 0.9999 * 0.9999 * 0.9999 = 0.00009997

Yes, that's right - the chance goes down over time. Remember, this is not the chance that we will have gotten the drop by now (the cumulative chance), but the chance we'll get it exactly now. This means that the loot in which you are the most likely to see a drop, regardless of the drop chance, is always the first loot. More people will get the macaw on their first loot than on their second. The mode is always 1. Yeah, that's weird.

Loot drops are a form of binomial distribution, inverted with a k of zero.

Extrapolation

So we know that 50% of players will have gotten the Hyacinth Macaw after looting 6931 mobs, and the average number of loots is 10,000.

BunnyHunter tells me how long I've spent farming a particular mob. It does this by noting down each time I loot the relevant kind of mob. If the time between loots was less than a limit (5 minutes), then the time between them is added to my total time. If the time between them was greater than this limit, by total is left as-is. This means that it measures the time spent running between mobs and fighting, but not the 10 minute break I took to get coffee or check the auction house. There's a little bit of under estimation, since it doesn't include the time spent to find and kill the first mob in each "session", but so long as you farm a few mobs at a time and not one every now and then it's fairly accurate.

After I killed my 3600th pirate, I saw that my timer just ticked off 11 hours. Wow. I'm wasting my life. However, this also tells me that I loot roughly 327 mobs for every hour I spend farming (3600 / 11). I can use this to calculate how long it should take me on average to get the macaw and after how much farming I'll start to be unlucky for not having seen it.

3600 loots / 11hrs = 327 loots/hr

median 6931 loots -> 21.2 hrs
mean 10,000 loots -> 30.6 hrs

Ok, so I probably have quite a bit of farming ahead of me.

Post-Script

I might be a bit of a math nerd, but I make mistakes too. If you spot any glaring mistakes or omissions, drop me an email and teach me: cal [at] iamcal.com

BunnyHunter can be downloaded here, or installed through the Curse Client.

The source code for World of Dropcraft can be found here.

I play a Night Elf Hunter called Bees, who currently has a collection of 118 vanity pets. I am also the creator of Hunter Loot.

Copyright © 2010 Cal Henderson.

The text of this article is all rights reserved. No part of these publications shall be reproduced, stored in a retrieval system, or transmitted by any means - electronic, mechanical, photocopying, recording or otherwise - without written permission from the publisher, except for the inclusion of brief quotations in a review or academic work.

All source code in this article is licensed under a Creative Commons Attribution-ShareAlike 3.0 License. That means you can copy it and use it (even commerically), but you can't sell it and you must use attribution.

18 people have commented

AF
# March 5, 2010 - 12:23 am PST
Well, you've missed some cases in your first little example, the two that begin drop / no drop. (2^3 is 8, not 6.) Rest looks okay.
Cal
# March 5, 2010 - 12:34 am PST
Wow, not sure how I missed that. I'm blind to it after reading it so many times. Thanks :)
Mike D
# March 5, 2010 - 6:54 pm PST
Silly Cal. If it can be equipped, its hunter loot.
Jeff
# March 5, 2010 - 11:27 pm PST
So, essentially it's like asking: what's the probability of getting "heads" on the next coin flip in a series, versus the probability of generating a "heads" after 20 coin flips, then 21, then 22, etc? And BunnyHunter continually recalculates this probability with each loot.

Very impressive stuff, I'd never considered game drop rates like this (if I did indeed grasp it haha). Thanks for this little brain stretch, I don't even play WoW I just saw this on Reddit
Jason
# March 6, 2010 - 1:02 am PST
If you could sell it for 30k you would have made 2500g/hour (which is pretty darn high) non-auction house arbitrage methods max out around 500g/hour from what I've seen. If it took you the mean time, every time, you'd make 1000g/hour. If you sold your gold you could earn a nice salary of $4-$10 / hour!

But farming is fun...right?
Cal
# March 6, 2010 - 1:07 am PST
Jason: You could do that in theory, yes. However, if you do it too much, the price will come down. Demand isn't *that* high at the 30k price point. If you don't do it too much, then you face the risk of hitting the long tail too often and wasting your time.

If you're pet farming for money, the raptor in Northrend probably makes more sense because you get a *lot* more gold from the farming aspect, especially if you have skinning. And since each cycle is shorter, you should converge to the average a lot quicker.
Dylan
# March 6, 2010 - 4:12 am PST
Geometric probability! If you're bored and have a TI-84 or some similar graphing calculator you can do this as well.

2nd Vars (Distribution), GeometCDF, and then enter in P(probability), X(number of trials) and hit enter

Ex. The 1/10000 epic companion pet, say you kill 500 pirates.

GeometCDF(.0001,500) = .0488 or 4.88%

You can use Geometic models to find the probability of something occuring on an exact trial. You can add the probabilities of geometric sequences to find the probability of something occuring either on or before a certain trial.
Graeme Foster
# March 6, 2010 - 9:53 am PST
So the best way is to get someone who is lucky to farm for you.

Or failing that, someone who is gullible. ;)
Subu
# March 10, 2010 - 10:12 pm PST
Good article - just a note to readers: Look up something called Gambler's Fallacy and the Perch strategy in Roulette. In short, trying to assign a current trial probability using this doesn't work. (current trials will always have 1/10000 probability for the macaw, irrespective of the number of trials before that. Think of it this way. In three tosses, HHH is as Probable as HHT. So you can't really bet after the first two H that you will get a tail - because the first two instances has already happened.)

IOW, all that is predicted here is how lucky/unlucky you are - it doesn't influence the outcome of a given trial.
Joe
# March 12, 2010 - 7:06 am PST
Subu, the author devoted quite a bit of time to explaining what you just did — he called it probabilistic independence.

"What's predicted here" is not how likely you are to get certain loot on the next drop, but about how much time you'll need to farm before you find the loot you want. The author was very clear about that.

Interesting article, I enjoyed. Gaming + math fascinates. Thanks!
Melissa
# May 4, 2011 - 8:26 am PST
Now that cata is out and all will u be updating the addon?
Cal
# May 7, 2011 - 12:49 pm PST
It was updated for cata in January - you'll see the Fox Kit is now tracked.
Jeff
# May 10, 2011 - 4:24 am PST
Nice explanation and add-on.. Just a quick question. Where did you get the drop rate for the Kit? It looks closer to 1/1000 0.09% based on the wowhead client.
Besides that, thanks for creating this lovely little add on that shows just how much of my life I am wasting trying to get a stupid little fox as a virtual pet :)
jdmaddison
# June 3, 2011 - 10:17 am PST
I commented on Curse under BH, but I'm not sure if you've seen that. I'm wondering how would I add a new "pet"? It's not really a pet, it's an enchanting formula, Formula: Enchant Weapon - Crusader (http://www.wowhead.com/item=16252) and it only drops from Scarlet Archmage's (http://www.wowhead.com/npc=9451) and only about 1 in 200 loots. It would seem pretty easy to extend this Addon to do this, if only I had a little more of an idea on just how to do so! Thanks!
Eric
# December 29, 2011 - 1:22 am PST
Are you going to include mounts from vortex pinnacle, stonecore, tempest keep, u. pinnacle ???
Eric
# December 29, 2011 - 1:26 am PST
Oops, I see Ashes of Alar and Blue Proto-Drake ... so just missing Vortex Pinnacle and Stonecore and Throne of the Four Winds and Alysrazor and the 3 in Dragon Soul
Cari
# January 4, 2012 - 4:16 pm PST
@ An Odd Side-effect

One thing that is important to note here, is that this shows the chance that you get your FIRST drop is higher on the first kill than on any other. Independently, you are as likely to get a drop on your millionth kill as on your first kill. It could just be your 400th bird :)

(Wanted to post this originally but thought of something better to write)
It's not that odd if you think of it with a crazy example. Let's compare the chance you get it on the first drop vs. the chance that you get it on the millionth drop. It is now easy to see why the first drop is more likely to be
Harvey
# August 25, 2014 - 7:36 pm PST
Very informative!

But I think I will stick to the very WRONG MIS-conception of 50% rate for farming all my vanity collections. (Will I see the *pet* in the next corpse I loot? Yes/No.) It makes for better farming experience and puts a lower strain on my poor little brain. Haha. Still, thank you for the analysis. Brilliant stuff~

Leave your own comment

Your name: Required
Email address: Optional, will be hidden
URL: Optional
Prove you're human: Enter the answer to 3 + 4