Correlated randomness in Slay the Spire 2 - Andy Tockman Open Original Page Correlated randomness in Slay the Spire 2 - Andy Tockman
portfolio
music
conlangs
video games
board games
puzzles
square dancing
food
Correlated randomness in Slay the Spire 2 very long (6880 words) gamesvideo gamesslay the spiremath Here are three true statements about the game of Slay the Spire 2
(in single player): If you pick Neow's Bones in the Underdocks,
the random curse is ~54% likely to be Debt.* It is impossible to receive Rebound from the Trash Heap event. Your first fight is 76% likely to drop a potion in Underdocks,
and 4% likely to drop a potion in Overgrowth.** (* assuming neither of the relics from Neow's Bones is New Leaf or Kaleidoscope) (** assuming your Neow relic doesn't give cards or other relics) (*** all on the current beta patch, v0.107.0) Why? The culprit is unexpected correlation between different random number generators --
knowing the first output of one of the game's RNGs
gives information that helps predict the first output of all of the others. The random number generators of Slay the Spire 2 For now,
I will give an extremely simplified explanation of this correlation.
If you want more details,
I will go into much greater depth at the end of this post.
If you don't care,
you can skip this section to see all the funny examples below. The phenomenon of "correlated RNG" (or "CRNG")
is already known in the Slay the Spire community,
because Slay the Spire 1 had a similar issue,
described in detail in Forgotten Arbiter's blog post.[1] Briefly,
in Spire 1,
the game used several distinct pseudorandom number generators,
to prevent e.g. randomness within a combat
from influencing future card rewards.
However,
they were all initialized to the same starting state,
which meant they produced the same sequence of numbers.
A crafty player could therefore pay attention to the results of past random events
and gain information about future random events. In an attempt to avoid the same problem,
Spire 2 initializes its pseudorandom number generators
to different states.
The code looks something like this
(highly simplified for didactic purposes): Rng UpFront = new Rng(seed + hash("up_front"));
Rng Shuffle = new Rng(seed + hash("shuffle"));
Rng UnknownMapPoint = new Rng(seed + hash("unknown_map_point"));
Rng CombatCardGeneration = new Rng(seed + hash("combat_card_generation"));
Rng CombatPotionGeneration = new Rng(seed + hash("combat_potion_generation"));
Rng CombatCardSelection = new Rng(seed + hash("combat_card_selection"));
Rng CombatEnergyCosts = new Rng(seed + hash("combat_energy_costs"));
Rng CombatTargets = new Rng(seed + hash("combat_targets"));
Rng MonsterAi = new Rng(seed + hash("monster_ai"));
Rng Niche = new Rng(seed + hash("niche"));
Rng CombatOrbGeneration = new Rng(seed + hash("combat_orbs"));
Rng TreasureRoomRelics = new Rng(seed + hash("treasure_room_relics"));
// ... There are many more random number generators in the game
that I have not listed for brevity;
notably,
every event has its own RNG. The hash function essentially produces a "random-looking" number
from the input string,
but the number is always the same for the same input.
So the idea is that the RNG states are shuffled around,
but the same seed still always results in the same run. The problem comes when these seeds are passed
to the stock System.Random class in C#.
Unfortunately,
the pseudorandom number generation algorithm
used in C#
is almost entirely "linear" in the starting seed. What this means exactly is a bit complicated --
again, I will go into greater detail later in this post.
But the consequence is that two RNGs
whose seeds differ by a known fixed amount
have their outputs differ by a fuzzier but still-exploitable amount. How exploitable,
you might ask?
Well... Here is a big pile of consequences of CRNG,
ranging from amusing-but-unimportant
to legitimately impactful on gameplay
(some of them even to casual players unaware of it!). I'll start with the first example from the intro.
If you pick Neow's Bones in Underdocks,
the "random" curse you receive
actually has the following approximate distribution: However,
in Overgrowth,
you instead get a curse from this distribution: This one is quite funny to me --
people all over Reddit and Discord have been lamenting their terrible luck
that they keep rolling Debt from Neow's Bones.[2]
Even before discovering CRNG,
I saw some of these posts insisting it seemed more frequent than random.
It is hard to express how instantaneously my brain automatically dismissed them
as textbook confirmation bias.
And yet... To understand this one,
we need to correlate three sources of randomness: The "curse relic" available from Neow
comes from a call to Neow's event-specific RNG,
which is seeded with seed + 1 + hash("NEOW"). The Neow options always have exactly one relic from the "curse pool",
as described on the wiki.
The choice of which of the 8 curse relics to offer
is the first call to Neow's RNG. The random curse from Neow's Bones
comes from a call to RunState.Rng.Niche,
which is seeded with seed + hash("niche"). Since New Leaf and Kaleidoscope also call Niche for their randomness,
rolling either of these relics from Neow's Bones will destroy the correlation.
But otherwise,
this will be the first call to Niche. The Act 1 variant
(Underdocks or Overgrowth)
comes from a call to an unnamed RNG created in StartRunLobby#BeginRunLocally,
which is seeded with the base seed. Since Neow's Bones comes from Neow's "curse pool",
you will only ever see it when the first call to the Neow RNG
rolls in a particular range,
which imposes a strong constraint on the possible range for the first call to Niche
(stronger when combined with which Act 1 you are in). It is clear that this correlation is very impactful on gameplay,
even for players unaware of it.
It makes Neow's Bones a much worse relic,
giving less harmful curses like Clumsy, Guilty, and Injury extremely rarely
and more crippling ones like Debt much more often. At this point,
you might be thinking
"wait,
doesn't that mean we can predict the randomness
of every Neow relic?"
Indeed we can!
Let's do some more of them. The first relic from Large Capsule is never common. More specifically,
in Overgrowth,
it's about 70% to be uncommon and 30% to be rare.
In Underdocks,
it's about 37% to be uncommon and 63% to be rare --
but there's a caveat: Large Capsule will only appear about 1.65% of the time
in an Underdocks act,
because everything is correlated with everything.
(Nobody seems to have noticed this one;
here was someone's very funny reaction to this information
as I was first investigating all of this.) Here is the specific distribution of the "curse pool" option at Neow in Underdocks: Getting back to Large Capsule in particular,
much like Neow's Bones,
the correlation has a legitimate gameplay impact.
The relic is better than it "should be" on average. What about Small Capsule? Since Small Capsule is not a curse pool relic,
it does not have an intrinsic bias the way Neow's Bones and Large Capsule do. However,
this means we can use the presence of another curse pool relic
to predict the rarity of the Small Capsule relic: (Here,
[U] means Underdocks and [O] means Overgrowth.
Large Capsule is never present because there is a hardcoded restriction
that both Capsules can't appear simultaneously.) I've kept the scaling on the bars the same as the two charts in the previous section --
the total width of each row is proportional to how often that curse pool relic actually appears in the act.
This is to demonstrate a concise heuristic:
Small Capsule will usually give a common relic in Underdocks,
and usually give an uncommon or rare relic in Overgrowth. Okay,
there's a lot more Neows with randomness,
so I'll sort of speed through a few more
and then get to some different stuff. Leafy Poultice and Hefty Tablet (These are "transform 2" and "choose a rare".) Since these are both curse pool relics,
they have an intrinsic bias.
But they both generate multiple cards,
so we can only predict the first one. It turns out that
the first transform from Leafy Poultice only has 22 possibilities
(out of each character's 80-card pool),
with some significantly more likely than others. (These charts are pretty big,
so I've hidden them away here.
You can click through each character
to see the available options,
and have fun deciding which act is better.) Leafy Poultice
Underdocks: cladsilentregentnecrodefect cladsilentregentnecrodefect Similarly,
the first option from Hefty Tablet only has 11 possibilities in Overgrowth,
and 3 possibilities in Underdocks!
This is because as shown above,
Hefty Tablet only appears in about 1.3% of Underdocks in the first place,
so seeing it is very strong information. cladsilentregentnecrodefect cladsilentregentnecrodefect New Leaf and Arcane Scroll (These are "transform 1" and "random rare".) Links
Browse another page: |