A New Algorithm for Controlled Randomness

 A New Algorithm for Controlled Randomness

by Malte Skarupke

I don’t know if this problem has a proper name, but in game development you usually don’t want truly random numbers. I’ve seen the solution named a “pseudo random distribution” but “pseudo random” already has a different meaning outside of game design, so I will just call it controlled randomness for this blog post.

The description of the problem is this: An enemy is supposed to drop a crucial item 50% of the time. Players fight this enemy over and over again, and after fighting the enemy ten times the item still hasn’t dropped. They think the game is broken. Or an attack is supposed to succeed 90% of the time but misses three times in a row. Players will think the game is broken.

In this blog post I want to expand that problem to the situation where you not only have two choices (success or fail) but many choices. For example you want to create traffic on a road and spawn a bunch of random cars without having the same car too many times. The problem was already partially solved for the success/fail case, and in this blog post I will improve on that solution and present the solution for the case where there are many choices.

I will also allow you to control exactly how random or non-random you want the result to be. If you’re fine with a 90% success chance to fail three times in a row in certain situations, but want it to be more reliable in other situations, you will be able to tweak that with a number.

First of all I need to clarify that in the above examples, it is certainly the game that is broken. If something has a 90% chance of succeeding and it fails three times in a row, the player is completely justified in thinking that the game is broken. Three failures in a row are a 1 in 1000 chance, so if you have enough players, or players play your game for long enough, this will happen a lot. And you might think that players are just bad at statistics and are wrong for complaining, but the problem is deeper than that.

Most of the time when you use randomness, you don’t actually want randomness. One use case for randomness is to generate variety. For example when you don’t want the same items to drop every time. But true randomness doesn’t guarantee variety, so you shouldn’t use true randomness.

Another use case for randomness is to emulate systems that are too complex to fully simulate. For example when you just give an attack a 90% chance to hit instead of simulating the movement of the sword and the dodging or parrying of enemies and all that. But true random numbers are rarely the correct approach to simulating a system like that: If you have a 90% hit chance (like when stabbing an enemy from behind) and you miss twice, in reality you would play it safe the third time and definitely hit. You didn’t want to simulate the complexity of the underlying system, but you need to at least be somewhat close to it, and true randomness is the wrong choice as soon as a system is even slightly complex and includes a feedback loop that would react to the first two failures.

SOLUTION FOR SUCCESS/FAIL

For a simple success/fail case, the best solution I am aware of is the solution that Blizzard used for Warcraft 3. It is explained here, but let me also explain it with an example:

The idea is that you keep on increasing the chance every time that something fails to happen. Let’s say you have a 19% chance to get a critical hit. Then the first time you attack, and you want to calculate if it was a critical hit or not, you use true randomness with a 5% chance of succeeding. If you don’t land a critical hit, the next time you will get a 10% chance. If you fail again your chance goes up to 15%, then 20%, 25% etc. If you keep on failing, at some point you will have a 100% chance of landing a critical attack. But if you succeed at any point, your chance goes back down to 5%.

This approach does two things: 1. It prevents long dry stretches where you never seem to get a critical hit. 2. It makes it less likely that you get a critical hit twice in a row. If you do increments of 5% like this, you will on average succeed roughly 19% of the time. How do you arrive at that 5% base chance? I actually don’t know an analytic way of arriving there, but you can get there experimentally pretty easily by just writing a loop that runs through this a million times and then tells you how often it succeeded or failed. Then you build a lookup table that contains the percentages.

All that being said this algorithm breaks somewhere between 60% and 70%. From the above link it sounds like Blizzard fixed the problem by just messing with the percentages. For example in their case, when a designer puts in a 70% chance of something happening, they actually only get a 60% chance. How does the algorithm break? In order to get a 70% chance, you need to have a 57% chance on the first try, and a 100% chance on the second try. The obvious problem with that is that it can make the game predictable. Once players notice that an ability will always succeed if it has failed before, they can exploit that behavior. So I actually prefer a different approach: Instead of adding the percentages, multiply them instead.

Going through the multiplication example with the 19% chance, it works like this: On your first try, you have a 94.4% chance of failing. (this time we use the chance of failing, not the chance of succeeding) On your second try you get a (94.4%)^2 = 89% chance of failing. On your third try you get a (94.4%)^3 = 84% chance of failing. The chance of failing goes down the more often you fail until it eventually approaches (but never reaches) zero. So you always have a small chance of failing and it never gets completely predictable, but the chance of failing over and over again at some point becomes vanishingly small.

So without further ado here is the code:

https://probablydance.com/2019/08/28/a-new-algorithm-for-controlled-randomness/