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

61–70 of 92 posts

Re: Correlated randomness in Slay the Spire 2

#61

Post by margalabargala »

AlotOfReading wrote: post #46
margalabargala wrote: post #18

Earlier quoted context omitted.

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.

That's assuming the game initialization order is deterministic. Using the hash of the combined state of seed and string avoids that assumption without giving up determinism.

Yeah true. That's even better.

Point being, the current problematic state of the game is trivially fixable in multiple ways that require half a second's thought (once being aware of the problem).

Re: Correlated randomness in Slay the Spire 2

#62

Post by mellinoe »

bilekas wrote: post #30
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…

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

IIRC in the modern .NET runtime, System.Random should come from here, which is updated somewhat regularly: https://github.com/dotnet/runtime/commits/main/src/libraries.... Although, whether any of these is a behavioral breaking change isn't immediately clear; most are just API additions.

Re: Correlated randomness in Slay the Spire 2

#64

Post by cptroot »

antitoi wrote: post #63

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?

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.

Re: Correlated randomness in Slay the Spire 2

#65

Post by OskarS »

account42 wrote: post #31
FromTheFirstIn wrote: post #14

Earlier quoted context omitted.

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.

They can certainly be part of the standard library, it's just that you have to make the programmer be specific: it's a bad idea `new Random(seed)`, because you can then never update the `Random` class, and you might get stuck with a terrible default forever. But having a `new Xoshiro256(seed)` is a fine thing to have in your standard lib, given that quality PRNGs are such a common need.

Re: Correlated randomness in Slay the Spire 2

#66

Post by j_w »

sltkr wrote: post #51

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

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.

Re: Correlated randomness in Slay the Spire 2

#67

Post by kibwen »

antitoi wrote: post #63

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?

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.

Re: Correlated randomness in Slay the Spire 2

#69

Post by tveita »

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…

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

Re: Correlated randomness in Slay the Spire 2

#70

Post by Straw »

shmoil wrote: post #49

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

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