Correlated randomness in Slay the Spire 2

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

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.

It also gives you the option of serialising the RNG states directly instead of using the counter hack.

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.

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

Another cross-section is space enthusiasts. I really have to rewire my brain every time someone says sts-n and doesn't mean a mission number of https://en.wikipedia.org/wiki/Space_Transportation_System

You may like a game my younger brother developed. Same genre as slay the spire.

He and one other guy coded this together for a few years. Really good reviews on Steam.

https://store.steampowered.com/app/3057670/Pluto/

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.

Sincerely blows my mind to see someone recommend cryptography to generate pseudorandom numbers. It speaks volumes of how fast computers are now, and how used we are to waste that power.

Slay the Spyre is a rogue deck builder, the PRNG of Windows Freecell (3.11) would be good enough for it.

Edit: From https://github.com/joshuamkite/freecell

> Microsoft FreeCell RNG Algorithm: Uses seeded random number generator (seed = (seed * 214013 + 2531011) & 0x7FFFFFFF) for reproducible deals (games numbered 1-1,000,000)

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.

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.

https://www.youtube.com/watch?v=MiuLeTE2MeQ&t=476

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.

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.

I guess it's mainly a limit to savescumming.

For things like daily runs / seeded runs part of the fun is getting the same card rewards.

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.

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.

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.

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.

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.

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)

> 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

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

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

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.

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!

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.

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

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.

MT is actually quite a poor (and slow) RNG! PCG32 suggested in the article has much better randomness, state size, and speed.

It always gives me Clash :(

Being able to share and replay seeds is a big part of the StS community.

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

I got the joke.