> Implementing a PRNG within the codebase instead of calling the C# standard library has an additional advantage: seeds are guaranteed to be the same on all platforms. In Spire 1, seeds on the desktop version of the game were different from seeds on the mobile version of the game, because the standard library implementation of PRNG differed between platforms. It is also worth mentioning that the standard library implementation might change over time, which would break all past seeds.
This is the correct conclusion - game developers should consider gameplay-relevant random generators part of their gameplay code rather than platform code.
More than just that, procgen as a whole requires an entirely different level of vigilance to avoid nondeterminism creeping in if the game requires it to be reproducible. None of the inputs to the procgen algorithm can be allowed to even so much as brush up against code you aren't actively exerting complete control over, and care is required to avoid inadvertently encountering any platform specific hardware quirks.
It can also be a good idea to split the RNG into a tree for different areas (i.e. seed multiple RNGs from the main one), so that adjusting the generation for one aspect doesn't shift around everything else in a seed (especially in something like Minecraft where different parts of the world might be generated on different versions of the game).
> It is also worth mentioning that the standard library implementation might change over time, which would break all past seeds.
If the stdLib changes and you need to use the same, then you're unfortunately going to be suck with porting the previous version into your own library. It's pretty forward thinking from the devs here, I would love to see my boss' face if I told him we need time to port some of the stdLib incase they update it in the future.
I had to check for my own curiosity, but it looks like the Random class has not been updated in 12 or so years. At least in the inital subset of framework to core.
This is a pretty funny abbreviation since CRNG is sometimes "cryptographic random number generator", which would not be susceptible to this correlation. Albeit I think CSRNG is more common.
Interestingly, StS2 got this problem because it was using C# System.Random in Godot, while the RNG class in GDScript (Godot Engine's own scripting language) is using PCG32 which should be free of this particular problem.
"Appendix: How?" is a neat walkthrough of discovering this by trying to find a specific seed, and learning that the correlated randomness made the outcome he was searching for vanishingly rare.
I've always thought that random number generators are one of the best examples of Hyrum's law ("all observable behaviours are part of your API"): once you release a random number generators that either uses a default seed or allows you to seed it, you can't ever change it, it's a huge breach of backwards compatibility. Imagine if you did a Minecraft style game that relied on the behaviour of some PRNG, and then you changed the implementation? The entire game will break. That's why GNU libc still uses a terrible LCG for rand() despite the fact that much better generators exist: they can't ever fix it, because srand() exists and people rely on it.
On the other hand, it's STUPENDOUSLY useful to have "default" random functionality in your core library, for the "just give me a random number" or "shuffle this array, I don't care how" users, who don't really care about the details. But if you do that: always seed it with some external entropy (current time or /dev/random or whatever), don't even allow users to seed it. That means you can improve it in the future, because users already can't ever rely on the sequence. If the users do want to rely on the sequence, they should have to specify the exact engine they want.
TL;DR: System.Random in C# should not ever have been seedable, big mistake.
I had a similar realization recently; I was writing a compiler so I implemented a "random" function as part of the runtime.
To avoid regression I have some simple code examples I compile and execute, and I compare their output to "known good" versions.
I reached a point where I wanted to write a "sort array" routine and my immediate thought was to generate an array of 50 random numbers, sort them, and print them. But of course that wouldn't give me predictable output for my test-driver.
In the end I decided I'd do that when run interactively, but for testing purposes I'd just sort the characters in a string "The quick brown fox .." and while it isn't super-convincing it's enough to let me see regressions in my sorting function and/or array indexing runtime code.
If you’ve played the game it makes sense to have the seed be settable and shareable. In Slay the Spire it can be exciting to have an outrageously unlikely starting state or early option, and in order for players to share this with each other the seed has to be user controlled. It’s a big part of what gives the game its community!
GP isn't saying you should never have seedable random generators, just that they should not be part of the standard library because then the API promise is no longer that you get random numbers but that you get a very specific sequence of numbers which fixes the implementation as part of the API contract.
That split is exactly what .NET 6 did. The parameterless Random switched to xoshiro256*, but new Random(seed) stays pinned to the old Numerical Recipes subtractive generator so historical seeds still reproduce, and that legacy generator is the affine one whose first output is linear in abs(seed), which is the whole root cause of this bug.
> the game used several distinct pseudorandom number generators, to prevent e.g. randomness within a combat from influencing future card rewards.
Why is this important? Feels like fixing what seems to be a non-issue lead to a bunch of real issues.
With a good RNG it should not be possible to predict future numbers based on past numbers so players cannot manipulate card rewards in their favour based on combat actions, right?
I don't think it's deliberate RNG manipulation they worry about. It's a single player (or coop) game after all.
However, one of their design goals is that people playing on the same seed should have roughly the same game, it should feel "fair". Some things you probably want to be fairly random, for instance your card choices can depend on what cards you chose before. But it's also important that people choosing the exact same cards (and taking the same path, maybe?) should be offered the same options.
In STS1, the order of relics was fixed from the start as I recall. So if you skipped a shop, you'd get exactly the same relics in the next shop as you would have in the one you skipped. Good for seed fairness, but a little odd.
For a singular seed, they wanted the resulting run to be stable in the sense that small deviations in decision making does not result in a vastly different result (as far as random events are concerned)
Imagine the game of two players having the same state X. While combat, one player would trigger a random action, the other doesn't. After the combat, both should still get the same randomized reward options. This wouldn't work with just a singular RNG.
This way, you can see how e.g. players of different skill level navigate the "same" run (same seed), without everything diverging completely on the very first (meaninglessly small) combat choice.
The game stores and allows you to see the RNG seed that controls the run's events and layout. The developers want players to be able to share seeds that produce interesting runs.
That requirement is what made this problem difficult for the devs to solve.
This shouldn't actually be difficult to solve though.
The issue is that knowing the offset of seeds helps predict outputs.
Instead of calling RNG(seed+hash(string)) 10x, make one RNG(seed) and call that 10 times to get random seeds for your 10 rngs. Now you have perfect determinism and no correlation.
My first solution was RNG(hash(seed.toString() + string)), which would get rid of the correlation while still being deterministic based on the seed.
It's also more robust than calling RNG 10 times since if you use the same algorithm to seed as for the RNG proper then you will get the same sequences in each instance, just offset.
Because they appear to have a curious way of doing their saves. From the article:
>The way Slay the Spire allows you to save and resume runs is by storing the total number of times each RNG has been called, and then calling each RNG that many times (throwing away the result) whenever a save file is loaded.
Depending on what the game is like (I know nothing about it), that could make sense, even if it is inelegant.
You could observe future random numbers by taking combat actions, and then reset to the start of the fight and play a line which consumes fewer random numbers in order to manipulate your card rewards. Maybe you could generate the card reward at the start of the fight, but what if they play a card which impacts the card reward, e.g. by creating an extra card reward.
People often want to share their seeds so that players can play the same game they did. If there was an interesting series of results for example, which gave you a good set of cards.
Minecraft does this too with world generation for example.
The trash heap event gave me the same relic the first 3 times in a row that I got it before it gave me anything else. I wonder that's another example of this correlation?
I hope the StS team is made aware of this and is able to make the earlier outcomes a bit more evenly spread, so that the distribution matches more closely with what people would intuit them to be.
> Implementing a PRNG within the codebase instead of calling the C# standard library has an additional advantage: seeds are guaranteed to be the same on all platforms. In Spire 1, seeds on the desktop version of the game were different from seeds on the mobile version of the game, because the standard library implementation of PRNG differed between platforms. It is also worth mentioning that the standard library implementation might change over time, which would break all past seeds.
This is the correct conclusion - game developers should consider gameplay-relevant random generators part of their gameplay code rather than platform code.
More than just that, procgen as a whole requires an entirely different level of vigilance to avoid nondeterminism creeping in if the game requires it to be reproducible. None of the inputs to the procgen algorithm can be allowed to even so much as brush up against code you aren't actively exerting complete control over, and care is required to avoid inadvertently encountering any platform specific hardware quirks.
It can also be a good idea to split the RNG into a tree for different areas (i.e. seed multiple RNGs from the main one), so that adjusting the generation for one aspect doesn't shift around everything else in a seed (especially in something like Minecraft where different parts of the world might be generated on different versions of the game).
> It is also worth mentioning that the standard library implementation might change over time, which would break all past seeds.
If the stdLib changes and you need to use the same, then you're unfortunately going to be suck with porting the previous version into your own library. It's pretty forward thinking from the devs here, I would love to see my boss' face if I told him we need time to port some of the stdLib incase they update it in the future.
I had to check for my own curiosity, but it looks like the Random class has not been updated in 12 or so years. At least in the inital subset of framework to core.
https://github.com/microsoft/referencesource/commits/main/ms...
> The phenomenon of "correlated RNG" (or "CRNG")
This is a pretty funny abbreviation since CRNG is sometimes "cryptographic random number generator", which would not be susceptible to this correlation. Albeit I think CSRNG is more common.
This is such a great article- I’ve had so many runs where it’s felt like “why am I always getting this random card?” And now I’ll know! Thank you!
Interestingly, StS2 got this problem because it was using C# System.Random in Godot, while the RNG class in GDScript (Godot Engine's own scripting language) is using PCG32 which should be free of this particular problem.
"Appendix: How?" is a neat walkthrough of discovering this by trying to find a specific seed, and learning that the correlated randomness made the outcome he was searching for vanishingly rare.
This is also the cause of the thing in Minecraft where you find surface clay, move X blocks over, and dig straight down into diamonds.
I've always thought that random number generators are one of the best examples of Hyrum's law ("all observable behaviours are part of your API"): once you release a random number generators that either uses a default seed or allows you to seed it, you can't ever change it, it's a huge breach of backwards compatibility. Imagine if you did a Minecraft style game that relied on the behaviour of some PRNG, and then you changed the implementation? The entire game will break. That's why GNU libc still uses a terrible LCG for rand() despite the fact that much better generators exist: they can't ever fix it, because srand() exists and people rely on it.
On the other hand, it's STUPENDOUSLY useful to have "default" random functionality in your core library, for the "just give me a random number" or "shuffle this array, I don't care how" users, who don't really care about the details. But if you do that: always seed it with some external entropy (current time or /dev/random or whatever), don't even allow users to seed it. That means you can improve it in the future, because users already can't ever rely on the sequence. If the users do want to rely on the sequence, they should have to specify the exact engine they want.
TL;DR: System.Random in C# should not ever have been seedable, big mistake.
I had a similar realization recently; I was writing a compiler so I implemented a "random" function as part of the runtime.
To avoid regression I have some simple code examples I compile and execute, and I compare their output to "known good" versions.
I reached a point where I wanted to write a "sort array" routine and my immediate thought was to generate an array of 50 random numbers, sort them, and print them. But of course that wouldn't give me predictable output for my test-driver.
In the end I decided I'd do that when run interactively, but for testing purposes I'd just sort the characters in a string "The quick brown fox .." and while it isn't super-convincing it's enough to let me see regressions in my sorting function and/or array indexing runtime code.
If you’ve played the game it makes sense to have the seed be settable and shareable. In Slay the Spire it can be exciting to have an outrageously unlikely starting state or early option, and in order for players to share this with each other the seed has to be user controlled. It’s a big part of what gives the game its community!
GP isn't saying you should never have seedable random generators, just that they should not be part of the standard library because then the API promise is no longer that you get random numbers but that you get a very specific sequence of numbers which fixes the implementation as part of the API contract.
That split is exactly what .NET 6 did. The parameterless Random switched to xoshiro256*, but new Random(seed) stays pinned to the old Numerical Recipes subtractive generator so historical seeds still reproduce, and that legacy generator is the affine one whose first output is linear in abs(seed), which is the whole root cause of this bug.
Really interesting read. The fact that Rebound is literally impossible to get is hilarious and completely unexpected.
> the game used several distinct pseudorandom number generators, to prevent e.g. randomness within a combat from influencing future card rewards.
Why is this important? Feels like fixing what seems to be a non-issue lead to a bunch of real issues.
With a good RNG it should not be possible to predict future numbers based on past numbers so players cannot manipulate card rewards in their favour based on combat actions, right?
I don't think it's deliberate RNG manipulation they worry about. It's a single player (or coop) game after all.
However, one of their design goals is that people playing on the same seed should have roughly the same game, it should feel "fair". Some things you probably want to be fairly random, for instance your card choices can depend on what cards you chose before. But it's also important that people choosing the exact same cards (and taking the same path, maybe?) should be offered the same options.
In STS1, the order of relics was fixed from the start as I recall. So if you skipped a shop, you'd get exactly the same relics in the next shop as you would have in the one you skipped. Good for seed fairness, but a little odd.
For a singular seed, they wanted the resulting run to be stable in the sense that small deviations in decision making does not result in a vastly different result (as far as random events are concerned)
Imagine the game of two players having the same state X. While combat, one player would trigger a random action, the other doesn't. After the combat, both should still get the same randomized reward options. This wouldn't work with just a singular RNG.
This is exactly it.
This way, you can see how e.g. players of different skill level navigate the "same" run (same seed), without everything diverging completely on the very first (meaninglessly small) combat choice.
The game stores and allows you to see the RNG seed that controls the run's events and layout. The developers want players to be able to share seeds that produce interesting runs.
That requirement is what made this problem difficult for the devs to solve.
This shouldn't actually be difficult to solve though.
The issue is that knowing the offset of seeds helps predict outputs.
Instead of calling RNG(seed+hash(string)) 10x, make one RNG(seed) and call that 10 times to get random seeds for your 10 rngs. Now you have perfect determinism and no correlation.
My first solution was RNG(hash(seed.toString() + string)), which would get rid of the correlation while still being deterministic based on the seed.
It's also more robust than calling RNG 10 times since if you use the same algorithm to seed as for the RNG proper then you will get the same sequences in each instance, just offset.
Because they appear to have a curious way of doing their saves. From the article:
>The way Slay the Spire allows you to save and resume runs is by storing the total number of times each RNG has been called, and then calling each RNG that many times (throwing away the result) whenever a save file is loaded.
Depending on what the game is like (I know nothing about it), that could make sense, even if it is inelegant.
For things like daily runs / seeded runs part of the fun is getting the same card rewards.
You could observe future random numbers by taking combat actions, and then reset to the start of the fight and play a line which consumes fewer random numbers in order to manipulate your card rewards. Maybe you could generate the card reward at the start of the fight, but what if they play a card which impacts the card reward, e.g. by creating an extra card reward.
I guess it's mainly a limit to savescumming.
Why don't they just pass the time into the RNG in order to randomize it instead of using fixed seeds?
It's a bug thing for competition. In a procedural game there's a lot of variation between seeds so the only 'fair' way is to start with the same seed.
People often want to share their seeds so that players can play the same game they did. If there was an interesting series of results for example, which gave you a good set of cards.
Minecraft does this too with world generation for example.
Being able to share and replay seeds is a big part of the StS community.
I feel vindicated. I knew this game was bullshit and it couldn't possibly have been a skill issue.
The trash heap event gave me the same relic the first 3 times in a row that I got it before it gave me anything else. I wonder that's another example of this correlation?
I hope the StS team is made aware of this and is able to make the earlier outcomes a bit more evenly spread, so that the distribution matches more closely with what people would intuit them to be.
It always gives me Clash :(