Correlated randomness in Slay the Spire 2

> 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.

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/

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.

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.

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 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!

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?

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 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.

> (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 :(

> 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.

>> 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.

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.

"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 need to play this game as a case study.

Really interesting read. The fact that Rebound is literally impossible to get is hilarious and completely unexpected.

Why don't they just pass the time into the RNG in order to randomize it instead of using fixed seeds?

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.

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.

[dead]