Source: https://www.bungie.net/7/en/News/Article/dev_insights_perk_rng_issue
Hi everyone. I am Andrew Friedland, the Technical Owner for the Engineering team that, among other things, owns the Destiny 2 rewards system. I ended up leading the programming work around the perk weighting issue investigation and will be walking you through some of what happened on our end.
The timing of our community team escalating this issue to us was actually quite serendipitous. When this first popped up on my team’s radar Vincent Davies, one of the engineers on my team, was just wrapping up work on a script to help us validate the stat distributions on next gen armor for Frontiers. With a few minor tweaks we were able to use this script to also help us validate weapon perks, simulating thousands of drops per minute and logging the data for us to chew through. Using this tool, we were also able to quickly verify the community’s findings.
Our finding? While the probability of any single perk was even, the probability of pairs of perks was anything but.
Here are the results of dropping almost 100,000 vs. Chill Inhibitors. As the community had discovered, some perk combinations are more common, some are less common, and some are almost impossible to get.
To understand what is happening here we will first need to take a deep dive into some math and computer science to define what random means to us.
What is Random
True random events are things that we can often assign probabilities for but can’t predict. This includes things like a coin flip or a die roll, as well as broader physical phenomena like where lightning will strike or when a radioactive atom will decay. For all of these we can make general predictions about how likely something will be, but we can’t forecast exactly what will happen. We are also unable to make a given result repeat when we want it to. Computers can’t do true random on their own, and when true random is required, people have turned to things like atmospheric noise (i.e. static on the radio or TV), recordings of the cosmic background radiation, or even walls of lava lamps. However, most things do not need truly random numbers, and for games we generally don’t want true random since we can’t control it.
Many years ago, some smart people came up with the idea of pseudorandom number generators (PRNG). The general idea behind a PRNG is that, given a seed number (often the current system time) we can run a series of mathematical operations to end up with a fairly random number. You can then use that new number as the seed for your next random number, ultimately giving you a sequence of numbers that is random enough.
One big advantage of PRNGs over true random for games is that they are repeatable. When using a given starting seed, you are guaranteed to always get the same sequence of numbers, which means that if you have the same starting seed and the same inputs then the game will turn out the same way. Games use this for many different uses, from saved films to fair tournaments and many more.
One big disadvantage for PRNGS, as called out in the name, is that they are pseudorandom. There can be patterns that appear in the output of PRNGs and depending on how you use them you may end up amplifying those patterns instead of getting something that appears random.
To help visualize various algorithms I will be using example data generated with help from Joe Venzon, our Engineering Director. We will start with the base use case of a PRNG, using 1 as the first seed and then using the last result as the seed for the next value. This results in a nice cloud of points with no clearly identifiable patterns, similar to static on an old TV screen. This is exactly what we want, as it means that our random numbers are fairly evenly distributed across the possibility space and that there shouldn’t be any clear patterns when looking at our sequence of numbers.
Unfortunately, on Destiny we can’t always feed the previous result back in as the next seed. We have many places where we require stable predictable seeds when generating new random numbers, and this new seed selection was ultimately what was causing our problems.
The Bug
In Destiny 2 we created a new system for items called the socket and plug system. This system handles a large percentage of what players see as gear, including weapon perks, mods, shaders, Masterworking, and even armor stats. Randomized items were added in Forsaken, and the main way they work is through the socket and plug system. In Destiny 2 a weapon will have sockets for its barrel, magazine, and other perks. When we drop that weapon, we will select plugs to insert into those sockets from the list of legal plugs, and those plugs each represent the perks you are familiar with. You can thank the flexibility of this system for all the mayhem of The Craftening last year.
Players can have different sockets enabled on the same item depending on what they have done or how they got it, as seen in the original implementation of artifice armor. This means that when initializing a new drop, we can’t assume that we will always initialize sockets in the same order. To make sure that vendors offer the same perks to all players even if some players have more sockets, we use a different seed for every socket being initialized. Unfortunately, this extra work to add stability ended up causing our bug.
To select a stable seed for each socket on an item we end up combining a number of different pieces of information together using a hash function, a mathematical way of taking some large chunk of data and turning it into a single number. While this new hash number was guaranteed to be stable, as we originally intended, because the socket index was the last piece being added into the hash we often ended up in a case where the hashes were sequential, and these sequential seeds are ultimately what caused the bad behavior.
Going back to our tables, let’s start by looking at hashes of sequential numbers. While the hashes themselves are not sequential, we can see some fairly clear patterns in how the numbers are coming out. This means that when we look at hashes of sequential numbers, we are likely to be able to find patterns in the output hashes. While this isn’t on its own a bad thing, it does mean that there are some interesting patterns in the data we are feeding into the PRNG.
If we then drop those numbers into the random number generator, we can see that those patterns in the input data have corrupted our outputs, resulting in some patterning in the data. These patterns are specifically what resulted in some perk pairs being easy to get while others were almost impossible to find.
Early Sandbox Investigations
The ultimate question: Why didn’t you investigate RNG earlier?
Each time we see player feedback about difficulties in obtaining specific rolls, our sandbox team has taken a look at weapon data first. Weapon perks have never had any intentional weighting, and in the absence of strong evidence that something more was going on, we left it at that.
Random number generation is so low level and foundational to the game (to all games, really) that in the absence of clear or abundant evidence that something's off, it doesn't always make sense to task an engineer with an investigation. Surely if something like this had been a frequent and obvious issue, we'd have noticed long ago, right?
Like all of game development, it's a question of priorities and tradeoffs. Many in Engineering and QA are focused on building the future of Destiny. Shifting their priorities to focus on something that potentially isn't an issue comes at a cost and a potential risk for those features and content.
In this case the community organizing around a data-gathering effort was what made a strong case that there was an issue to be found, and we'd need to start a deeper investigation into the RNG code.
From investigation, we found that the issue had been in the game for some time, but it's only recently received substantial community focus and traction. Players began focusing primarily on the Multimach CCX Submachinegun from Iron Banner, and the VS Chill Inhibitor Heavy Grenade Launcher from the Vesper's Host dungeon.
Even though the bug impacted all weapons, it could sometimes lead to desirable perks being easier to earn – and thus went unnoticed for some time.
Several overlapping issues are responsible for this:
-
The issue is most egregious on weapons with six perks per column.
- Some other similarly desirable weapons over the years have more or fewer perks than this, masking the impact of the issue to a degree.
-
The bug is heavily mitigated by perk columns with multiple choices.
- Adept weapons and playlist weapons have access to multiple perks per column.
- Most endgame weapon sources such as Raids, Trials and Nightfall Strikes have Adept weapons.
- Players could earn more perks per column on Vanguard, Crucible, and Gambit weapons via Reputation resets.
- Adept weapons and playlist weapons have access to multiple perks per column.
The bug is largely irrelevant on craftable weapons, which have applied to raids and most non-endgame weapon sources since the introduction of crafting in The Witch Queen
Ultimately, our community was able to compile enough evidence over time to prove that even with the appropriate content setup of equally weighted perks, there was a deeper issue to solve.
The Fix
Ben Thompsom, one of our more tenured engineers, recognized this issue almost immediately. For anyone who was around when the original Whisper of the Worm mission launched, you may remember having issues getting the Taken Blight Public Event to actually appear (Cabal, Again?!). It turns out that the underlying problem here is similar, where we were using sequential inputs to feed the seed for the random number generator. The fix in that case, and here as well, was to multiply our hash inputs by large prime numbers to better distribute them, also known as salting) the data. While there will still be a regular step between sequential inputs, the actual value is now significantly different between two sequential inputs and thus we are avoiding some of the patterning issues. When we hash these salted inputs, we end up with a much better distributed series of hash values.
And when we feed the salted hashes into random number generator, we once again end up with a nice point cloud with no clearly discernable patterns.
Going back to our original test case with VS Chill Inhibitor, what do our perk rolls look like with the fix? All the perk pairs show up relatively evenly, with some minor variations around the average as would be expected from a sampling or random events. The probability of getting any specific perk pair should now be close to true random, as originally intended.
The fix for perk selections went live in update 8.1.0.4, and we plan to do audits over multiple areas of the code base soon to watch for any similar issues. All in all, these learnings will empower us to prevent this from happening again, or at the very least will help us do better spot-checking from time to time to ensure the bug doesn't resurface. I would like to thank the community for their impressive data gathering, which helped us identify this rather insidious issue lurking in what is now fairly old and proven code.
External link →