> 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).
(Note this is roughly what slay the spire did, but if they were to use a 'master' RNG output as the source of these sub-seeds then these correlations would also not be a problem. With a custom implementation they could save the RNG state directly as opposed to hacking around calling the RNG X times on loading a save)
What's burned me before is iterating over hash maps. B-tree maps (or hash maps that are guaranteed to iterate in insertion order, or any fixed order) are your friend.
I've been burned by this outside games as well. Computation heavy process, in production it writes the inputs into the output as well for reproducibility, but some of them used unordered maps so it would slightly differ when you loaded it back up. Long term solution was to stop using unordered maps in general, but short term we had to make sure the inputs got sorted before being inserted so they would have the same insertion order every time...
> 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.
Be glad you work on top of a relatively standardised platform! The C standard doesn't specify any details of the implementation backing rand(), so a bunch of platforms have wildly different implementations, and they change over time (FreeBSD swapped theirs out in 202, for example)
IIRC in the modern .NET runtime, System.Random should come from here, which is updated somewhat regularly: https://github.com/dotnet/runtime/commits/main/src/libraries.... Although, whether any of these is a behavioral breaking change isn't immediately clear; most are just API additions.
For what it’s worth, Claude did this without even being asked when I had it implement /dev/urandom in my deterministic dotnet runtime. (Fun fact: if the runtime only ever receives zero bytes from /dev/urandom then it will hang on attempting to initialise System.Random! That was the first way I asked for it to be implemented.)
Sometimes it is useful to deal with a platform where such things are not even available, never mind platform dependent. Then see how quickly your code breaks.
Standard library invocations - including random number generation - often break entirely when targeting wasm freestanding for instance, as in that case there is really very little "platform" to speak of.
Combining this article and discovery of an unwinnable seed in the original Slay the Spire [0] — I've always pondered the existence of some kind of "RNG hell", where a game uses the time as its random seed and, due to some quirk of the hashing function and the game mechanics, the game is rendered completely unwinnable for (say) four days straight. (Sometimes it feels like I'm in it!)
Putting this into my rotation of excuses. "It wasn't my fault! They were hacking, also my fingers were slippery and the deterministic behavior of psuedorandom number generators guaranteed we would lose anyway."
I haven't had time to read the whole article, but I really appreciate the cross section of the world that reads HackerNews and plays STS2. STS1 and STS2 are my favorite games and to see this pop up here brought a big smile on my face. Thanks for sharing.
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.
I don't understand the motivation for using multiple RNGs in the first place. If the game had one global, seed-able source of randomness, would this problem just disappear?
The motivation boils down to trying to make runs with the same starting seed feel "similar" in meaningful ways. It's "better" in a vibes way if both you and I were offered the same card choices in runs with the same seed, even if we took different amounts of turns on the first battle.
The main reason to allow users to set seeds manually is to allow players to share seeds among themselves. And the reason that players want to share seeds is because players will find exceptionally rare seeds that other players might want to try out. This sort of exceptional rarity might take the form "the first shop in act 1 sells a relic that gives you 2 potion slots, then the act 2 ancient offers a relic that gives you 4 potion slots, then the act 3 ancient offers a relic that fills all your potions slots at the start of every combat". However, when players share seeds, they aren't sharing the exact series of inputs they performed in that game. This means that the relics that have been "randomly" offered like the ones above need to be offered on the same seed regardless of any prior player decision. And player decisions can generally cause the RNG to advance an arbitrary number of times. So this means that you want to have entirely separate RNGs for every thing that the player has any power to influence, because this makes the randomness of a single seed more usefully reproducible in practice.
I wonder if this can explain something happening to me. If I select "random" at character select, I had a run of 30 or 40 where I never received the Silent. Defect seem to come up more often than it should, and Ironclad less often.
> 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.
That's assuming the game initialization order is deterministic. Using the hash of the combined state of seed and string avoids that assumption without giving up determinism.
Point being, the current problematic state of the game is trivially fixable in multiple ways that require half a second's thought (once being aware of the problem).
> 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 think you're overlooking the distinction between seeded and unseeded runs. An unseeded run is a run in which the player enters the game not knowing what the seed of the RNG is and not being able to pick it (this is the default mode). A seeded run is where the player provides the RNG seed. Generally, things like unlocks and steam achievements can only be earned on unseeded runs, but players want to be able to play seeded runs anyway. Of course all runs have an RNG seed: an unseeded run is when the seed is itself chosen at random, a seeded run is when the player specifies the seed.
Imagine a game with a standard deck of cards played over several rounds, where your opponent performs actions in response to your actions. The deck of cards is shuffled pseudo-randomly between every round. Every time you make a move, your opponent has N valid moves, and picks between them pseudo-randomly.
Players play a seeded run because they want to retry the same set of challenges, because they are asking themselves "if I had done this, would I have won" or "if I had done this, what would have happened".
So in this example, given a known seed: in round 1, my cards are shuffled this way, and in round 2, my cards a shuffled this other way, regardless of which moves I make in round 1.
If the opponent picks its response using the same RNG that shuffles the deck, the players actions in round 1 would change the shuffling of the deck in round 2. This would change the design parameters of what a seeded run means: it's no longer giving the guarantee "the deck is shuffled in the same way in round 2 regardless of what you do in round 1", which is the experience the designer wants to create and what the players want to play. Players might, e.g., say "who can get the highest score on this seed", they might search for the easiest or most difficult seeds, or they might search for seeds where particularly unlikely sequences of events are guaranteed to occur, because perhaps this sequence of events is so unlikely that a human would have to play a hundred million games to witness that sequence organically, and people want to see that sequence of events because it's interesting in some way. It's designed this way so that if you play the same seed, certain random events play out the same way, i.e., non-randomly.
Some degree of stability in seeds is desirable, partly because of the compatitive elements (multiple players playing the same seed should have roughly the same game), but also when updating the game is means that if they tweak one area the rest of the seed will stay roughly the same. (Maybe less important for games with short runs compared to sandbox games like Minecraft where the world might be generated by very different versions if the game and you don't want blatent seams when it happens)
You're confusing RNG manipulation (really clearly bad, basically cheating by removing the randomness from the game) from RNG prediction (less bad but still unfun, being able to predict future random states).
You can be safe from RNG manipulation while still suffering from RNG prediction. Players can't modify the events that are going to happen, but if they can predict them, it's still a problem.
The situation is like there's a bug in the blackjack table where, instead of shuffling the whole shoe together, each deck in it was shuffled on its own in the same way and then the identical decks are stacked together. Once you've seen 52 cards, you know the repeating pattern and can play with perfect or near-perfect knowledge of what's about to be dealt.
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.
That's just to restore the internal state when you reload your save file, so that, for instnace, if you save and quit while looking at a set of card rewards, but haven't made your choice yet, when you reload, you will see the same set of rewards (you can't just reload your save to reroll).
This doesn't really have any impact on the gameplay, and isn't related to the correlation problem, it's just a constraint on the class of RNG algorithms in use, they need to be deterministic with recoverable state.
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.
It's in fact the opposite: an intentional design choice to make save scumming (edit: and by extension, sharing specific rng seeds) more effective for people who like doing it. They made a similar design choice with how save/restore works, in that it resets the current encounter, which allows players a limited ability to undo/backtrack if they make a mistake.
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.
Can you describe what you mean by "oracle attack" here? CSPRNG APIs (at least the ones I've used) usually expose ways to set a specific seed and serialize the RNG state. In fact, arguably the simplest possible CSPRNG, where you just run a (suitably strong) block cipher in counter mode, would seem to meet the requirements for game dev in a straightforward manner.
CSPRNGs are absolutely seedable deterministic functions that will result in entirety reprodible runs.
The only difference is that if you don't know the seed it is computationally difficult to predict the next value given the previous ones. But that's not something any game dev is ever going to want to do (or waste time trying to do)
I would expect all RNG algorithms to be deterministic and stable with their seed,
but the cryptographically secure ones to have some additional properties like making it unfeasible to reverse the seed from the output, having a very long period or strong guarantees on the distribution of the output.
It's just that using a 'secure' algorithm is often overkill for a game when you don't really need those extra guarantees.
If the slay the spire 2 devs could compile all their ELF64 binaries with "-static-libgcc -static-libstdc++", statically link their libcurl4 (with its deps) and their libz, I'll be pleased to play their game.
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.
That's a bad example to use because it has very few repetitions (only the spaces I think?) and the key doesn't have different equivalent values so you can't test that you're order-preserving (or not).
But ideally sort is something you want to test with something like quickcheck/hypothesis, not gold tests (and I say that as probably the world's number 1 proponent of gold tests).
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.
They can certainly be part of the standard library, it's just that you have to make the programmer be specific: it's a bad idea `new Random(seed)`, because you can then never update the `Random` class, and you might get stuck with a terrible default forever. But having a `new Xoshiro256(seed)` is a fine thing to have in your standard lib, given that quality PRNGs are such a common need.
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.
>> However, I am confident that Mega Crit will address this issue.
They did not address it in StS1, exactly the same bugs were reported there.
I would not be very hopeful. They did not even change their RNG to something better, like MT.
This time it has a major impact on the possible RNG outcomes even for a player who doesn't know about the bug, and it was caught much earlier in development before the permanent stability of existing seeds was guaranteed.
"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.
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.
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 post suggests replacing the linear congruential generator (LCG) with a permuted congruential generator (PCG). The latter has more random-looking output.
Another solution is to switch to a cryptographic hash function. For example, using sha256(seed || event type || counter) only requires storing seeds and counters in the save game.
This has several benefits:
- You can find efficient implementations on all platforms without having to roll your own.
- Gives the same output on all platforms by design.
- Output is practically indistinguishable from randomness by design.
The main downside is that sha256 is significantly slower than any non-cryptographic PRNG, but considering how few random numbers you need during a typical game, this doesn't really matter.
It seems really the problem is twofold: the reference is from 1992 and cites a 1981 publication's reference to an unpublished 1958 generator. Not to say that being old makes the algorithm bad, but it's a bad implementation of an algorithm that already is questionable given more recent research.
I'll go section by section:
> //Apparently the range [1..55] is special (Knuth) and so we're wasting the 0'th position.
This is a silly comment. Knuth explicitly states that "24 and 55 in this definition were not chosen at random; they are special values that happen to define a sequence whose least significant bits, {Xn mod 2), will have a period of length 2^55 - 1. Therefore the sequence (Xn) must have a period at least this long."
Then you have the initial seeding of the LCG with with a = 21 and m = 55, which is interesting. Numerical Recipes uses those values, but Knuth whom they got the algorithm from does not suggest them. The closest Knuth suggests is 24 and 55. This suggestion is from 1981, so the viability is questionable (and Knuth clearly states that this is an unpublished algorithm from 1958 - Numerical Recipes itself questions the quality).
Then they use 21 for inextp - this is wrong. Numerical Recipes uses 31, and that is significant per the period length quote above. The use of 21 should measurable lower the period.
So the implementation is a questionable algorithm from 1958, and it's done incorrectly. Numerical Recipes opens the chapter on randomness almost immediately with: "Now our first ... lesson in this chapter is: be very, very suspicious of a system-supplied rand()," and then the authors of the .NET random package show exactly why that is.
Maybe turn-based roguelike deckbuilders aren't the best for this, but I actually like some correlated randomness in some games, as it adds a new hidden mechanic to explore. In Hades 1 there are some (presumably unintentional) RNG manipulations that open up high-level techs for seeded speedruns:
- Hades 1 is a series of "chambers", or enemy encounters, where some layouts are faster than others [0]
- chambers (and other things like enemy spawns, boons, etc.) are "randomly" picked by an RNG with its seed normally unknown to the player (well that, and other factors [1])
- you can see the per-chamber RNG seed using mods [2], and manipulate it with seemingly meaningless actions [3] — e.g. breaking a pot (a mundane, cosmetic environmental item) increments the RNG seed by 1
- this leads to the existence of "routed runs" [4] — very fast speedruns enabled by very deliberate actions that can be replicated by a skilled player [5].
- anecdotally, with enough practice, skilled players can also recognize chamber patterns in unseeded speedruns and give themselves better odds at more favorable chambers by manipulating the RNG (although tbh the ability to recognize this on the fly is a little dubious)
So the invisible correlated RNG seeding adds in a higher skill ceiling for experienced players, while not really taking anything away from casual players.
Another game with this kind of RNG mechanic is Super Mario Bros. 3 — there's an excellent (86-minute, fyi) Summoning Salt video about the history of speedrunning this game and dealing with the "random" Hammer Bros movement (@27:15 to skip to that part).
> 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).
(Note this is roughly what slay the spire did, but if they were to use a 'master' RNG output as the source of these sub-seeds then these correlations would also not be a problem. With a custom implementation they could save the RNG state directly as opposed to hacking around calling the RNG X times on loading a save)
What's burned me before is iterating over hash maps. B-tree maps (or hash maps that are guaranteed to iterate in insertion order, or any fixed order) are your friend.
I'm so happy most modern language stdlibs decided having a guaranteed order for maps and other collections is a good idea.
Although I can definitely respect Go's decision to always iterate over maps in a random order.
I've been burned by this outside games as well. Computation heavy process, in production it writes the inputs into the output as well for reproducibility, but some of them used unordered maps so it would slightly differ when you loaded it back up. Long term solution was to stop using unordered maps in general, but short term we had to make sure the inputs got sorted before being inserted so they would have the same insertion order every time...
> 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...
Be glad you work on top of a relatively standardised platform! The C standard doesn't specify any details of the implementation backing rand(), so a bunch of platforms have wildly different implementations, and they change over time (FreeBSD swapped theirs out in 202, for example)
IIRC in the modern .NET runtime, System.Random should come from here, which is updated somewhat regularly: https://github.com/dotnet/runtime/commits/main/src/libraries.... Although, whether any of these is a behavioral breaking change isn't immediately clear; most are just API additions.
For what it’s worth, Claude did this without even being asked when I had it implement /dev/urandom in my deterministic dotnet runtime. (Fun fact: if the runtime only ever receives zero bytes from /dev/urandom then it will hang on attempting to initialise System.Random! That was the first way I asked for it to be implemented.)
It also gives you the option of serialising the RNG states directly instead of using the counter hack.
Sometimes it is useful to deal with a platform where such things are not even available, never mind platform dependent. Then see how quickly your code breaks.
Standard library invocations - including random number generation - often break entirely when targeting wasm freestanding for instance, as in that case there is really very little "platform" to speak of.
Combining this article and discovery of an unwinnable seed in the original Slay the Spire [0] — I've always pondered the existence of some kind of "RNG hell", where a game uses the time as its random seed and, due to some quirk of the hashing function and the game mechanics, the game is rendered completely unwinnable for (say) four days straight. (Sometimes it feels like I'm in it!)
[0] https://oohbleh.github.io/losing-seed/
Putting this into my rotation of excuses. "It wasn't my fault! They were hacking, also my fingers were slippery and the deterministic behavior of psuedorandom number generators guaranteed we would lose anyway."
I haven't had time to read the whole article, but I really appreciate the cross section of the world that reads HackerNews and plays STS2. STS1 and STS2 are my favorite games and to see this pop up here brought a big smile on my face. Thanks for sharing.
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.
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.
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!
> (By the way, floor 2 Corpse Slugs will both be attacking on turn 1 less than 3% of the time. How nice of them!)
I assumed that was just deterministic. Didn't realize the game permitted such a challenge on floor 2 :(
I don't understand the motivation for using multiple RNGs in the first place. If the game had one global, seed-able source of randomness, would this problem just disappear?
The motivation boils down to trying to make runs with the same starting seed feel "similar" in meaningful ways. It's "better" in a vibes way if both you and I were offered the same card choices in runs with the same seed, even if we took different amounts of turns on the first battle.
The main reason to allow users to set seeds manually is to allow players to share seeds among themselves. And the reason that players want to share seeds is because players will find exceptionally rare seeds that other players might want to try out. This sort of exceptional rarity might take the form "the first shop in act 1 sells a relic that gives you 2 potion slots, then the act 2 ancient offers a relic that gives you 4 potion slots, then the act 3 ancient offers a relic that fills all your potions slots at the start of every combat". However, when players share seeds, they aren't sharing the exact series of inputs they performed in that game. This means that the relics that have been "randomly" offered like the ones above need to be offered on the same seed regardless of any prior player decision. And player decisions can generally cause the RNG to advance an arbitrary number of times. So this means that you want to have entirely separate RNGs for every thing that the player has any power to influence, because this makes the randomness of a single seed more usefully reproducible in practice.
I wonder if this can explain something happening to me. If I select "random" at character select, I had a run of 30 or 40 where I never received the Silent. Defect seem to come up more often than it should, and Ironclad less often.
> 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.
That's assuming the game initialization order is deterministic. Using the hash of the combined state of seed and string avoids that assumption without giving up determinism.
Yeah true. That's even better.
Point being, the current problematic state of the game is trivially fixable in multiple ways that require half a second's thought (once being aware of the problem).
> 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 think you're overlooking the distinction between seeded and unseeded runs. An unseeded run is a run in which the player enters the game not knowing what the seed of the RNG is and not being able to pick it (this is the default mode). A seeded run is where the player provides the RNG seed. Generally, things like unlocks and steam achievements can only be earned on unseeded runs, but players want to be able to play seeded runs anyway. Of course all runs have an RNG seed: an unseeded run is when the seed is itself chosen at random, a seeded run is when the player specifies the seed.
Imagine a game with a standard deck of cards played over several rounds, where your opponent performs actions in response to your actions. The deck of cards is shuffled pseudo-randomly between every round. Every time you make a move, your opponent has N valid moves, and picks between them pseudo-randomly.
Players play a seeded run because they want to retry the same set of challenges, because they are asking themselves "if I had done this, would I have won" or "if I had done this, what would have happened".
So in this example, given a known seed: in round 1, my cards are shuffled this way, and in round 2, my cards a shuffled this other way, regardless of which moves I make in round 1.
If the opponent picks its response using the same RNG that shuffles the deck, the players actions in round 1 would change the shuffling of the deck in round 2. This would change the design parameters of what a seeded run means: it's no longer giving the guarantee "the deck is shuffled in the same way in round 2 regardless of what you do in round 1", which is the experience the designer wants to create and what the players want to play. Players might, e.g., say "who can get the highest score on this seed", they might search for the easiest or most difficult seeds, or they might search for seeds where particularly unlikely sequences of events are guaranteed to occur, because perhaps this sequence of events is so unlikely that a human would have to play a hundred million games to witness that sequence organically, and people want to see that sequence of events because it's interesting in some way. It's designed this way so that if you play the same seed, certain random events play out the same way, i.e., non-randomly.
Some degree of stability in seeds is desirable, partly because of the compatitive elements (multiple players playing the same seed should have roughly the same game), but also when updating the game is means that if they tweak one area the rest of the seed will stay roughly the same. (Maybe less important for games with short runs compared to sandbox games like Minecraft where the world might be generated by very different versions if the game and you don't want blatent seams when it happens)
You're confusing RNG manipulation (really clearly bad, basically cheating by removing the randomness from the game) from RNG prediction (less bad but still unfun, being able to predict future random states).
You can be safe from RNG manipulation while still suffering from RNG prediction. Players can't modify the events that are going to happen, but if they can predict them, it's still a problem.
The situation is like there's a bug in the blackjack table where, instead of shuffling the whole shoe together, each deck in it was shuffled on its own in the same way and then the identical decks are stacked together. Once you've seen 52 cards, you know the repeating pattern and can play with perfect or near-perfect knowledge of what's about to be dealt.
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.
That's just to restore the internal state when you reload your save file, so that, for instnace, if you save and quit while looking at a set of card rewards, but haven't made your choice yet, when you reload, you will see the same set of rewards (you can't just reload your save to reroll).
This doesn't really have any impact on the gameplay, and isn't related to the correlation problem, it's just a constraint on the class of RNG algorithms in use, they need to be deterministic with recoverable state.
> With a good RNG it should not be possible to predict future numbers based on past numbers
Since they are using the built-in RNG, it is trivial to predict if you know (or can guess) the seed: just run the same RNG a few steps ahead.
For something like a tool-assisted speed run, this is very exploitable to setup optimal runs
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.
For things like daily runs / seeded runs part of the fun is getting the same card rewards.
I guess it's mainly a limit to savescumming.
It's in fact the opposite: an intentional design choice to make save scumming (edit: and by extension, sharing specific rng seeds) more effective for people who like doing it. They made a similar design choice with how save/restore works, in that it resets the current encounter, which allows players a limited ability to undo/backtrack if they make a mistake.
> 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.
The criteria for calling a RNG "cryptographically secure" are incompatible with the game design goals here.
The game needs a RNG that's stable when seeded, for reproducible runs. I look for the same kind of qualities when doing generative art.
In comparison, a CSPRNG should be safe from oracle attacks, which is essentially the opposite goal.
Can you describe what you mean by "oracle attack" here? CSPRNG APIs (at least the ones I've used) usually expose ways to set a specific seed and serialize the RNG state. In fact, arguably the simplest possible CSPRNG, where you just run a (suitably strong) block cipher in counter mode, would seem to meet the requirements for game dev in a straightforward manner.
CSPRNGs are absolutely seedable deterministic functions that will result in entirety reprodible runs.
The only difference is that if you don't know the seed it is computationally difficult to predict the next value given the previous ones. But that's not something any game dev is ever going to want to do (or waste time trying to do)
I would expect all RNG algorithms to be deterministic and stable with their seed, but the cryptographically secure ones to have some additional properties like making it unfeasible to reverse the seed from the output, having a very long period or strong guarantees on the distribution of the output. It's just that using a 'secure' algorithm is often overkill for a game when you don't really need those extra guarantees.
If the slay the spire 2 devs could compile all their ELF64 binaries with "-static-libgcc -static-libstdc++", statically link their libcurl4 (with its deps) and their libz, I'll be pleased to play their game.
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.
That's a bad example to use because it has very few repetitions (only the spaces I think?) and the key doesn't have different equivalent values so you can't test that you're order-preserving (or not).
But ideally sort is something you want to test with something like quickcheck/hypothesis, not gold tests (and I say that as probably the world's number 1 proponent of gold tests).
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.
They can certainly be part of the standard library, it's just that you have to make the programmer be specific: it's a bad idea `new Random(seed)`, because you can then never update the `Random` class, and you might get stuck with a terrible default forever. But having a `new Xoshiro256(seed)` is a fine thing to have in your standard lib, given that quality PRNGs are such a common need.
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.
>> However, I am confident that Mega Crit will address this issue.
They did not address it in StS1, exactly the same bugs were reported there. I would not be very hopeful. They did not even change their RNG to something better, like MT.
MT is actually quite a poor (and slow) RNG! PCG32 suggested in the article has much better randomness, state size, and speed.
This time it has a major impact on the possible RNG outcomes even for a player who doesn't know about the bug, and it was caught much earlier in development before the permanent stability of existing seeds was guaranteed.
Spectacular write up. Gonna have to re-read this one a few times to fully internalize it.
"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.
Really interesting read. The fact that Rebound is literally impossible to get is hilarious and completely unexpected.
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 :(
I need to play this game as a case study.
Why don't they just pass the time into the RNG in order to randomize it instead of using fixed seeds?
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.
It's a big 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.
(Generally, when you just press 'start game', you'll get a truly random seed, but then you can also put that seed in again to get the same RNG).
Being able to share and replay seeds is a big part of the StS community.
The post suggests replacing the linear congruential generator (LCG) with a permuted congruential generator (PCG). The latter has more random-looking output.
Another solution is to switch to a cryptographic hash function. For example, using sha256(seed || event type || counter) only requires storing seeds and counters in the save game.
This has several benefits:
The main downside is that sha256 is significantly slower than any non-cryptographic PRNG, but considering how few random numbers you need during a typical game, this doesn't really matter.Well the .NET random is bad.
It seems really the problem is twofold: the reference is from 1992 and cites a 1981 publication's reference to an unpublished 1958 generator. Not to say that being old makes the algorithm bad, but it's a bad implementation of an algorithm that already is questionable given more recent research.
I'll go section by section: > //Apparently the range [1..55] is special (Knuth) and so we're wasting the 0'th position.
This is a silly comment. Knuth explicitly states that "24 and 55 in this definition were not chosen at random; they are special values that happen to define a sequence whose least significant bits, {Xn mod 2), will have a period of length 2^55 - 1. Therefore the sequence (Xn) must have a period at least this long."
Then you have the initial seeding of the LCG with with a = 21 and m = 55, which is interesting. Numerical Recipes uses those values, but Knuth whom they got the algorithm from does not suggest them. The closest Knuth suggests is 24 and 55. This suggestion is from 1981, so the viability is questionable (and Knuth clearly states that this is an unpublished algorithm from 1958 - Numerical Recipes itself questions the quality).
Then they use 21 for inextp - this is wrong. Numerical Recipes uses 31, and that is significant per the period length quote above. The use of 21 should measurable lower the period.
Instead if it were a simple LCG using values found in L'Ecuyer's 1999 publication on the topic (https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-...) I assume it would have a better distribution.
So the implementation is a questionable algorithm from 1958, and it's done incorrectly. Numerical Recipes opens the chapter on randomness almost immediately with: "Now our first ... lesson in this chapter is: be very, very suspicious of a system-supplied rand()," and then the authors of the .NET random package show exactly why that is.
Maybe turn-based roguelike deckbuilders aren't the best for this, but I actually like some correlated randomness in some games, as it adds a new hidden mechanic to explore. In Hades 1 there are some (presumably unintentional) RNG manipulations that open up high-level techs for seeded speedruns:
- Hades 1 is a series of "chambers", or enemy encounters, where some layouts are faster than others [0]
- chambers (and other things like enemy spawns, boons, etc.) are "randomly" picked by an RNG with its seed normally unknown to the player (well that, and other factors [1])
- you can see the per-chamber RNG seed using mods [2], and manipulate it with seemingly meaningless actions [3] — e.g. breaking a pot (a mundane, cosmetic environmental item) increments the RNG seed by 1
- this leads to the existence of "routed runs" [4] — very fast speedruns enabled by very deliberate actions that can be replicated by a skilled player [5].
- anecdotally, with enough practice, skilled players can also recognize chamber patterns in unseeded speedruns and give themselves better odds at more favorable chambers by manipulating the RNG (although tbh the ability to recognize this on the fly is a little dubious)
So the invisible correlated RNG seeding adds in a higher skill ceiling for experienced players, while not really taking anything away from casual players.
Another game with this kind of RNG mechanic is Super Mario Bros. 3 — there's an excellent (86-minute, fyi) Summoning Salt video about the history of speedrunning this game and dealing with the "random" Hammer Bros movement (@27:15 to skip to that part).
[0] https://docs.google.com/document/d/e/2PACX-1vR6NaU9v1-raeibk...
[1] https://docs.google.com/document/d/e/2PACX-1vSl9RGGyPbNqCnTL...
[2] https://www.youtube.com/watch?v=AHdt35TDvNY
[3] https://www.speedrun.com/hades/guides/jxpkj
[4] https://www.youtube.com/watch?v=CBRTQkoOZ4k
[5] https://docs.google.com/spreadsheets/d/1fNlBhBOsCz6092GUnsIt...
[6] https://www.youtube.com/watch?v=_EsFyogVvkw
I feel vindicated. I knew this game was bullshit and it couldn't possibly have been a skill issue.
I got the joke.