> 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'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.
Yes this is a key insight, and fortunately something I realised very early on in my JavaScript game engine which had a custom PRNG - but effectively for part of my game engine (stateful replays) every time I change my codebase and release/publish I effectively have to freeze that version of my engine - and route players to that engine version silently.
It’s not elegant but I don’t see any better way to do it to maintain backwards and forwards compatibility.
My plan is to control engine versions via a manifest.json or similar that points to applicable engine versions as a compatibility layer
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.
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.
> 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.
i wonder how the StS developer could get this far without "ownership" of the behavior that this blog author called "linearity." in these kinds of games you simulate bajillions of random games and check metrics after every player action, including whether or not you observe sufficient randomness in shuffles and stuff, as a matter of debugging something this complicated.
"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 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.
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.
Were they at different ascensions? I believe up until the most recent beta patch random with an ascension selected would only pick from classes which had that ascension unlocked which might explain it?
Latest beta patch introduced
> Implemented preferred Ascension for random character option
>> 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.
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).
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.
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!)
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.
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?
They want two players with the same seed to have a similar gameplay experience in terms of challenges encountered.
For this reason they want to isolate the RNG that procedurally generates maps, card rewards, shop contents, from other RNG streams such as the RNG used by random enemy attacks in battles, random event outcomes, etc.
One example of the wonky things that are possible when there is a single RNG stream is speedrunners manipulate the RNG state. For example, in Super Mario 64 they can jump in place to produce dust clouds that advance the RNG state until it is in a favorable position.
Think of chaos theory, or at least the pop-science version of it. You brush aside a butterfly today, and the fated hurricane doesn't happen next week.
However if insect-wingbeats and weather-systems used two independent PRNGs, you could safely walk in the garden without changing the meteorological future.
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.
Would the problem go away by doing hash(seed + string) rather than (seed + hash(string)) ? It keeps the determinism when you want it, but destroys the linearity.
34 comments
[ 2.7 ms ] story [ 43.3 ms ] threadWhy 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?
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.
It’s not elegant but I don’t see any better way to do it to maintain backwards and forwards compatibility.
My plan is to control engine versions via a manifest.json or similar that points to applicable engine versions as a compatibility layer
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.
This is the correct conclusion - game developers should consider gameplay-relevant random generators part of their gameplay code rather than platform code.
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.
Latest beta patch introduced > Implemented preferred Ascension for random character option
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.
- 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
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.[0] https://oohbleh.github.io/losing-seed/
He and one other guy coded this together for a few years. Really good reviews on Steam.
https://store.steampowered.com/app/3057670/Pluto/
I assumed that was just deterministic. Didn't realize the game permitted such a challenge on floor 2 :(
For this reason they want to isolate the RNG that procedurally generates maps, card rewards, shop contents, from other RNG streams such as the RNG used by random enemy attacks in battles, random event outcomes, etc.
One example of the wonky things that are possible when there is a single RNG stream is speedrunners manipulate the RNG state. For example, in Super Mario 64 they can jump in place to produce dust clouds that advance the RNG state until it is in a favorable position.
https://www.youtube.com/watch?v=MiuLeTE2MeQ&t=476
However if insect-wingbeats and weather-systems used two independent PRNGs, you could safely walk in the garden without changing the meteorological future.