Understanding “randomness” in video games and related apps

Many of the events that occur in your program - whether it's a rare loot drop from an enemy, the shape of an upcoming Tetromino (Tetris block), the color of a cascading jewel, or the location/direction of a screen saver sprite - are the result of random factoring. This factoring, or programming, allows a deterministic machine - a machine that follows instructions to produce predictable outputs - to make seemingly unpredictable decisions. Surprisingly despite what we're told this randomness is seldom truly random and deviates from its predicted ratio (in other words random occurrences may be more, or less regular than they should be). I think pretty much everyone who uses computers, or mobile devices by this time already suspects this. Have you ever wondered why, if there's supposed to be an equal chance that a specific colored block will drop from the top of the screen after a match is made (without modifiers), mostly x and y colors seems to fall, or why you spend an hour trying to farm a piece of rare loot despite it having a 20% drop rate? As a result mid-session you may find yourself wondering why you still play this game, or accusing the AI of cheating during it's turn, or robbing you of your rightly deserved spoils and at times it may seem worse than others. You might be under the misconception "well that's just how a random number generator (RNG) works." No, no it's not. That's how an improperly implemented RNG, or one that hasn't been adequately field tested works. Excusing faulty implementation like it's just supposed to be that way is why we have games like Final Fantasy 14 which, despite being a really fun game, has the worst random drop rate of any game I've ever played bar none (if you've actually played the game for yourself and proceeded through the Crystal Tower, or Bahamut Coils in search of a particular piece of gear then you know exactly what I'm talking about), or the spawn rate of certain legendary gear in Borderlands 2 on Ultimate Vault Hunter mode in a multiplayer session (I despise you, Bee shield).

So let's take a quick look at how an RNG typically works before we explore the actual impact it has on your app.

There are two distinct types of random numbers as they relate to home computing and related devices: true random numbers and pseudo-random numbers. The primary feature which distinguishes the two is predictability - that is to say the ability to generate a number sequence that is impossible for someone to predict (the number could be guessed, but that would be the product of luck rather than of predictive science). "True random numbers are unfortunately not feasible to use in most app designs due to the unpredictable nature of the end user's hardware environment." True random numbers cannot be predicted, so in order for a computer to generate one it has to accept input from an external random/unpredictable source since any number generated internally could be predicted based on its programming. For example, you could use a USB sensor that listens to traffic noise coming through the window and creates a long numerical string, or bit sample, from those random fluctuating noise levels, or you could listen to the noise produced from other things like a resistor inside your computer, or the subtle sound variation of a nearby stream/creek. The computer would accept that random string and use it throughout the life of the program. Now let's look at the answer to how we would generate a random sequence in lieu of an external true random generator.

Pseudo-random numbers differ from true random numbers because they are created from a seed. A seed is a string of numbers/characters that a program uses to create a random number sequence via mathematical formulation rather than from real-world random occurrences (as we examined a moment ago). "Pseudo-random numbers are most common since they do not require the end user to have additional hardware installed in order to be generated." A common method for generating a pseudo-random number is to take the system time in milliseconds (since January 1, 1970) and run a mathematical algorithm to extrapolate that number into a larger sequence of semi-random numbers. Each algorithm has pros and cons - each produces an observable pattern at various scales (its distribution type), and each has a limited number of calculations it can make before repeating the sequence (the seed's period). The more entropy (randomness/chaos) of the seed, the less predictable the results, or at least the greater potential for less predictable results (which is why many use milliseconds since that value will change with each passing second and can be collected on any computer/mobile device).

To sum up, a TRNG's randomness depends upon the source used (be it atmospheric noise, radioactive emissions, etc.) and does not use mathematical formulation to generate its sequence. Every PRNG uses mathematical formulation on a number - its seed - to produce a pseudo-random sequence of numbers. This seed has a finite amount of times it can be used - its period - before repeating. Each generator produces a repeatable sequence/pattern of numbers from a given seed - its distribution type - that represents the statistical probability of a given number appearing during the period. "The Uniform and Normal distributions are among the most common types found in both natural and virtual environments." An example of a distribution type is uniform distribution, where each number in the sequence has the same probability of occurring as any other number in the same sequence (e.g. for the range of 1 to 4, the number 1 has an equal chance of being generated as the number 2, which has an equal chance of being generated as the number 3, etc., the end result being that each number has been generated approximately the same number of times by the end of the period).

Now let's see how these random number sequences impact our apps.

Technically speaking...

You might be wondering right about now how exactly the computer uses a random character sequence to calculate decisions. I mean it seems like something's missing, right? How does a bit sequence like 11101100, an integer sequence like the time in milliseconds as 1457114591, or a character string like J@yI$Aw3$0m equate to determining the stats on a rare weapon drop, or which direction the pipes travel on a screen saver (the random walk)? Well, let's talk technical. With the exception of a TRNG, each type of RNG produces different types of pseudo-random sequences using complex algebraic formulas such as the middle squares method, linear congruential method, or mersenne twister method to expand the seed and then calculate numbers that a program uses to make decisions with. Each programming language uses its own libraries to facilitate the generator, each compiler that builds the app inputs its own values specifying the min/low, max/high, and increment values of the generator, and each programmer can modify the generator's implementation to custom tailor the output (or make their own from scratch). With that in mind here's a specific example of how the process works (keep in mind there are many variations to the one I'm using here). For this example let's say there is a 1-in-4 chance (.25 in decimal notation, 25% as a rounded percentage, 00011001 - 1 in binary) that an enemy will drop loot upon death, and a 1-in-12 chance (.08333333 in decimal notation, 8% as a rounded percentage, 00001000 - 1 in binary) that it will drop a 4th tier (very rare) piece of loot.

1. The game makes a call to the RNG upon the enemy's death and passes in a range that represents the ratio 1-in-4 as either a rounded percentage (1, 100), or as a floating point (0, .25);
2. Depending upon the type of number generator used,
   • If the random number is a bit sequence, say 11101100 00100000, the generator takes the shortest sequence of bits required to represent the highest value in the range (the highest value in our range is 100) - after adding 1 to the total since we're counting the value of 00000000 to be equal to 1 rather than equal to 0 - which would be 7 bits (1 bit represents the values of 1 to 2, 2 bits represents 1 to 4, three bits represents 1 to 8... and 7 bits represents 1 to 128 after the + 1 is added), converts it to decimal, and discards it if it exceeds the range (the first 7 bits are greater than 100, since 1110110 = 118 + 1, thus it would be discarded). The next sequence of 7 bits is evaluated (since 0001000 = 8 + 1, it would be kept since it it's within the range) and returned to the game;
   • If the random number is an integer sequence, say 1457474945, we'll compute a pseudo-random number using a multiplicative generator with the formula X_n = aX_n-1 mod m. Using 2147483647 as the high/max value (H), 48,271 as the low/min value (L), and the system time as the initial seed that is slightly different each time the program runs (S), the generator will compute L * (S % (H / L)) - (H % L) * (S / (H / L)), which is then scaled to the range (0, 1) by multiplying it with the quotient of (1.0 / H) to produce a pseudo-random decimal value between 0 and 1. The first value generated is .028550 which is returned to the game. The original seed value is then updated in order to produce a different pseudo-random number(s) next time a call is made to the generator (X_n in the previous formula represents the updated seed, in case you were wondering);
   • If the random number is a character string, say J@yI$Aw3$0m3, the generator converts each character into its ASCII decimal index number thus turning the seed into an integer sequence as 74 64 121 73 36 65 119 51 36 48 109 51. The seed is then shortened first to prevent overflow when calculated with the formula X_n = aX_n-1 mod m by adding the product of each set of four digits as ((74*64)(121*73))+((36*65)(119*51))+((36*48)(109*51)) = 65640500 (this is preferable to truncating the seed as each character/digit in the original sequence is used to create a shorter, unique seed rather than just having the last x amount of characters/digits simply cut off from the result). The generator accepts the shorter seed and produces its first value of .462959 which is returned to the game. The seed is likewise updated to produce a new pseudo-random number on the next call to the generator.
3. The game evaluates the number returned by the generator to see if it's <= 25, or .25 respectively. Since 9 and .028550 are both below this range they are kept for further evaluation; since .462959 is above the .25 range, it is discarded and replaced with a sigh of frustration as the realization that you got robbed of yet another loot drop sets in. The two passing values are reevaluated to see if they are <= 8, or .0833333 respectively. Since the first value of 9 is just above the range, it only qualifies for a common loot drop; since the second value is .028550, it qualifies for a rare loot drop... you lucky bastard. NOTE: this step can also be performed by the generator itself - instead of returning the actual random value, like .028550, it can return a simple index number, like 1 or 4, to indicate what level loot, if any, should be dropped.

At the beginning of this blog I claimed that randomness in computing deviates from its predicted ratio. Perhaps it's because of the way the generator is seeded (which I'll cover in a moment), or because most programmers simply don't seem to grasp how an RNG actually works ("you simply seed the generator with the system time, input the desired range, and presto! Out pops a random number like magic!"), or a combination of the two. In any case I believe there is also a shared disconnect in the realm of software development between the engineering and testing departments relating to the implementation of random events because this trait seems to be shared among the lot of 'em judging by the finished products hitting store shelves. "Well written documentation is a valuable tool for learning how something works and should be used in conjunction with, but not in place of, personal experience." I suspect this is due in part to developers blindly relying upon the documentation for the generator they choose to use without thoroughly vetting it for themselves in their near-finished product (I don't blame them for trusting the documentation - some of the math formulas for methods like the mersenne twister are so complex that even some of us with engineering degrees get lost trying to follow along). But hey, if the generator claims to follow a uniform distribution type, and if this other guy used it and said it worked, then that's all that matters. User results be damned. So if your daily challenge app ends up repeating the same challenge two days in a row, or three times in the same week, that's just the uniform randomness in action, right? Right?! o_O

OK, let's talk seeding. Even the most dependable number generator is at the mercy of relying on a good seed in order to produce acceptable pseudo-random sequences. "Just as a real seed dictates the characteristics of the plant that sprouts from it, a digital seed encapsulates all the characteristics of the random sequence that will be extrapolated from it." A single seed can produce a different sequence of numbers for each type of generator that uses it (e.g. a linear congruential generator can use the same seed as a Xorshift generator, but will produce a different number sequence). If the same seed is used multiple times by the same generator then the random sequences produced will be identical. The generator's distribution type tends to produce low, high, or mixed patterns of numbers from the seeds it uses (e.g. in a range of 1 to 10, the generator may pick predominately low values like 1 to 5, or high values like 6 to 10). If the seed happens to fall into what I call a generator's barren patch (every generator that I've seen has at least one, usually more, and can be unpredictable), it's period will be stunted and it's pattern easier to recognize. Now when I was in school it was common practice to only seed a generator once for the lifetime of the program. In fact if you Google a phrase like "when should I seed a random number generator?" you'll still find that this belief is commonly upheld, even in instances where multi-threading requires simultaneous seeds to be maintained - the generators are still only seeded once. The reasoning here is that if the generator is reseeded it will prohibit the original seed from finishing its cycle/period thus skewing its distribution type. In other words most of the time reseeding is considered a bad idea because it stops the generator from doing its job of getting the best sequence of random numbers possible from each seed (similar to discarding an annual plant before it's bloomed). I contend, however, that the average seed isn't given the chance to finish its period in the first place due to the user ending the session before its cycle is finished. Keep in mind also that the only way to verify a generator's distribution type is by testing it at various scales, but what happens if the generator doesn't make it to its tested benchmark? For instance if you run a generator with a uniform distribution 1000 times and it confirms that each number between 1 and 10 was chosen approximately 100 times, can you be sure it will maintain that uniform output after being run only 500 times, or 1235 times? Does it produce uniform numbers for small ranges like 1 to 4 and larger ranges like 1 to 20 alike? Important things to consider.

The problem here is threefold: first there is no guarantee that each seed's period will be long enough to last the entire length of the app's session without repeating; second there is no guarantee that every seed will appear to follow the generator's distribution type, especially if the sessions are shorter than the seed's period; third if the generator is only seeded once, any shortfalls apparent with a given seed will persist through the duration of the user's session (in other words the user will be screwed until he/she restarts the app and the generator gets reinitialized/reseeded). This should answer the question that may be in the back of your mind "why does it seem like some days I get better loot drops than on other days?" "The concept of only seeding a generator once is an archaic sentiment that completely ignores the dynamic length of a user's session when evaluating the statistical properties (distribution type) of a PRNG." Once you start your app you essentially get locked into using a seed that may give you better or worse random statistical properties. MMOs are notorious for this because you, the client, do not control seeding the generator (which is why client-side cheat programs can't influence your loot drop's rarity, critical rolls, etc.). That is done on the server side to ensure rare loot gets "evenly" distributed among the participants of a given raid/quest, and to ensure that you can't hack the system to gain an unfair advantage. This also means that a bad seed will be perpetuated until the server(s) gets rebooted (and vice versa for a good seed). Some developers try to counter this effect by giving participants tokens for each event they participate in that can be cashed in later on for the rare item they keep failing rolls to acquire, but that doesn't help when it comes to spending hours farming resources for a single attempt at socketing a rare gem into a piece of legendary gear. Of course don't be fooled - some developers do this on purpose as a means of controlling replay value (they get you, the user, to keep spending more money on subscriptions/market purchases as opposed to hours grinding until you get what you want), but that's a rant for a whole different blog. ;o)

We've unraveled the mystery of the RNG and examined the impact it can have on games and other apps, so now let's explore ways to make the RNG play fairly with others.

• If you run a persistent world server for a game that has random events (an MMORPG like Final Fantasy XIV for example), only use a TRNG. Accept no substitutes... unless of course your goal is to continue screwing players out of random successes they've rightfully earned whilst claiming the game to be fair. Out of curiosity do you also keep cards up your sleeve when you play Poker, or use loaded dice when playing Craps? If you run a server then you probably have the extra $50 to purchase a small Geiger counter (or make one yourself), which you can use to begin recording radioactive emissions. Heck, purchase a half dozen of them to exponentially increase your yield so you can keep up with the constant demand of random calls from your players (it may take a while to get a hefty supply of bits in reserve, so plan accordingly). All you'll need to accompany the counter is a cheap Radio Shack circuit that reads and extracts bit samples, records them to a log file, and sends them to the server as needed to answer random calls. Boom! No more debating whether or not this game is unintentionally unfair - now if it's unfair, it's intentionally so. ;o)
• Periodically reseed the damn generator! You heard me right. Chances are a high value seed (especially greater than 32 bit) won't make it through its period to begin with (if it does then that can be just as bad), and the chances of the user getting stuck with a bad seed outweigh, in my mind, the detriments of starting over with a new seed. At least it adds to the random element by mixing things up a bit. You can easily make a subroutine that reseeds the generator, say, every 90 minutes of play time (pause screens excluded), or after every 2000 calls to the PRNG.
• If you scale down your random values make sure you don't scale the updated seed, or any values that the generator uses to update said seed (only scale the output). Doing so may very well stunt all future seeds, and cause the generator to begin producing skewed values.
• Create your own RNG rather than relying upon the pre-built libraries in languages like Java and C++ to ensure you have complete control over your output (the actual implementation in libraries belonging to functions such as <rand> may be unknown to the programmer).
• Do your research and use a thoroughly tested min, max, and increment value for your generator in order to produce better statistical results while minimizing the size of the barren patch.
• if you do use the time in milliseconds as your seed, like 1458625508, you might consider altering the value prior to using it in your generator. The reason is simple: the first two digits of that number will be the same for every programmer who uses it as a seed between the time of this writing and July 13, 2017. Additionally it takes three months for the third digit to change, and eleven days for the fourth. While a number that increments by more than 80,000 in less than 24 hours is certainly large enough to produce unique seeds each time, and given the fact that each passing second scratches out all previously used seeds from recurring, it may seem like a trivial detail; however given that you will most likely use the same min, max, and increment values for all of your seeds once you define them, changing this value provides your generator with a little more entropy from which to make the pseudo-random sequence. Just something to consider.
• For the app user I can only offer one piece of advice: if you feel like you've been getting screwed with respect to rare loot drops, or the colors cascading from the top of the screen are noticeably less-than-random (without modifiers), or some other random thing seems wrong, turn off the game/end your session, start a different game to clear the system cache, and then restart your previous game to begin with a new seed. I say start a different game because you need to ensure that the cached files from your previous game are cleared (just in case the seed is one such file that is kept for quicker loading on the next session), and I am not sure that simply shutting the game off and turning it on again will achieve this (by "different game" I mean start a different title than the one you just played). Ever since the original Xbox was released, various consoles have implemented cached gaming as a means of decreasing the load times of games the user plays consecutively, and even rebooting the console won't necessarily remove these files. May your next session bring you better luck...

Finally, a word to programmers everywhere...

As a developer if you want certain elements of your game to be truly random then design it to be so, but don't rely on the extra difficulty supplied from a faulty RNG to make up the difference, and don't assume that the generator you've chosen to use is adequate for the app your making before first testing it thoroughly for yourself - testing it like we inevitably will. The users who give their time and money supporting your product(s) deserve to be treated fairly, to know exactly what they're getting and how hard they have to work to get it, and you deserve to have the fruits of your labor rewarded in-kind. So don't cheap out, or blame ignorance as an excuse, and don't be a douche bag. I'm just saying.