Correlated randomness in Slay the Spire 2

Posted by rdmuser 11 hours ago

234 points | 75 commentspage 3

sylware 2 hours ago|

If the slay the spire 2 devs could compile all their ELF64 binaries with "-static-libgcc -static-libstdc++", statically link their libcurl4 (with its deps) and their libz, I'll be pleased to play their game.

sltkr 6 hours ago||

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.

ASalazarMX 1 hour ago||

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)

j_w 3 hours ago||

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.

d357r0y3r 7 hours ago||

I feel vindicated. I knew this game was bullshit and it couldn't possibly have been a skill issue.

throw4847285 3 hours ago|

I got the joke.

jcalx 6 hours ago||

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

ahmdnassir1 8 hours ago|

[dead]