account42
> 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.
|
> fc417fc802
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.
|
> > rcxdude
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).
|
> > maxbond
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.
|
> bilekas
> 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/comm
its/main/ms...
|
jszymborski
> 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.
|
FromTheFirstIn
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!
|
stdc105
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.
|
iliveinberlin
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.
|
handoflixue
"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.
|
xdertz
> 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?
|
> vintermann
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.
|
> hannasanarion
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.
|
> bulbar
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.
|
> > myrmidon
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.
|
> eig
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.
|
> > margalabargala
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.
|
> > > Arcorann
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.
|
> torgoguys
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.
|
> > hannasanarion
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.
|
> iNic
For things like daily runs / seeded runs part of the
fun is getting the same card rewards.
|
> bzax
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.
|
> yccs27
I guess it's mainly a limit to savescumming.
|
OskarS
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.
|
> stevekemp
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.
|
> FromTheFirstIn
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!
|
> > account42
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.
|
> haeseong
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.
|
0xdecrypt
Really interesting read. The fact that Rebound is
literally impossible to get is hilarious and completely
unexpected.
|
abstractcontrol
Why don't they just pass the time into the RNG in order to
randomize it instead of using fixed seeds?
|
> rcxdude
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).
|
> ixwt
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.
|
> wbobeirne
Being able to share and replay seeds is a big part of
the StS community.
|
d357r0y3r
I feel vindicated. I knew this game was bullshit and it
couldn't possibly have been a skill issue.
|
cbondurant
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.
|
> FromTheFirstIn
It always gives me Clash :(
|