Is-Every-Seed-Winnable-Comments

[ForgottenArbiter]

No description provided.

[kerrickstaley]

1. “Can a perfect player win every game of Slay the Spire?” (alternatively, “Is there a strategy that achieves a 100% win rate in Slay the Spire?”)
2. “For every seed of Slay the Spire, is there a sequence of decisions that results in a win?”

Given that there are only 2^64 seeds, the answer to these questions may actually be the same. The optimal strategy for a perfect player would likely involve determining the state of the RNG (which only requires witnessing about 64 bits of RNG output) at which point you know exactly what will happen for the rest of the game.

I'm not very familiar with Slay the Spire so maybe I'm misunderstanding though.

Cross-post from HN: https://news.ycombinator.com/item?id=23919305

[JPK314]

Is randomness done with a linear congruential generator? If so, we could count the amount of times it has been applied at each step and see if the set of congruences has a solution.

[ForgottenArbiter]

@kerrickstaley Sure, that is definitely a way of interpreting the question that makes both questions equivalent. However, I am assuming that the "perfect player" is playing optimally with respect to a theoretical version of Slay the Spire where everything is truly random.

@JPK314 The pseudo-random number generator used is xorshift128+, as implemented by libgdx. There are apparently ways to "crack" seeds for this random number generator, according to a quick search online. Furthermore, the initial prng state is set using MurmurHash3, which can also be reversed to get a 64-bit seed. I have not pursued this line of search yet, but it is an idea. Maybe I'll take a quick look when I get some time and see what I can do.

[JPK314]

If you ever get the details of the prng function calls, feel free to contact me if you have trouble with the math

[justinleona]

At first glance, it would appear question (1) is the contrapositive of question (2) - e.g., if there is an unwinnable seed, then clearly even a perfect player can't win every seed. Alternately, if there is no unwinnable seed, then clearly some strategy must exist allowing a perfect player to win all seeds.

[JPK314]

At first glance, it would appear question (1) is the contrapositive of question (2) - e.g., if there is an unwinnable seed, then clearly even a perfect player can't win every seed. Alternately, if there is no unwinnable seed, then clearly some strategy must exist allowing a perfect player to win all seeds.

The question in (1) requires a universal strategy, i.e. one that works independent of the seed. The question in (2) is a weaker condition: a strategy exists that is a function of the seed. Trivially, (1) implies (2) and not (2) implies not (1) by contrapositive, but we certainly don't have (2) implies (1) without a real proof.

[rosswlbrown]

Hi there, I was reading through the code for the seed search mod you have created. I am wondering how it handles the combat as it just appears to skip to the rewards. Does one of the packages imported handle it?

[ForgottenArbiter]

The seed search mod does indeed skip the combats. It has no way to play or simulate combats or even know your deck in-combat, and for most applications, that would just slow down the search dramatically for no benefit. These days, a lot of seed search applications that require filtering billions of seeds or more tend to use optimized GPU searches with absolutely everything unnecessary stripped out. The seed search mod is still useful though as a last step or a tool that implements much more functionality.