Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Correlated randomness in Slay the Spire 2

tck.mn

Post reply on HN
Print view View original

31–40 of 92 posts

Re: Correlated randomness in Slay the Spire 2

#31

Post by account42 »

FromTheFirstIn wrote: post #14
OskarS wrote: post #8

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 c…

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.

Re: Correlated randomness in Slay the Spire 2

#34

Post by rcxdude »

fc417fc802 wrote: post #29
account42 wrote: post #27

> 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 impl…

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)

Re: Correlated randomness in Slay the Spire 2

#35

Post by stevekemp »

OskarS wrote: post #8

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 c…

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.

Re: Correlated randomness in Slay the Spire 2

#36

Post by rcxdude »

abstractcontrol wrote: post #21

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

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

Re: Correlated randomness in Slay the Spire 2

#37

Post by hannasanarion »

xdertz wrote: post #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,…

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.

Re: Correlated randomness in Slay the Spire 2

#38

Post by maxbond »

fc417fc802 wrote: post #29
account42 wrote: post #27

> 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 impl…

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.

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.

Re: Correlated randomness in Slay the Spire 2

#39

Post by hannasanarion »

torgoguys wrote: post #6
xdertz wrote: post #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,…

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.

Re: Correlated randomness in Slay the Spire 2

#40

Post by Lalabadie »

jszymborski wrote: post #33

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

Post reply on HN