4 ms·

> 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

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

TylerE 6y ago
Couldn't that be more or less trivially defeated by taking wallclock time as an input to the RNG?
- b1ur 6y ago
  It could be, but considering the developers made the conscious decision to use a static seed and show that seed to the player they are probably okay with that.
- tarboreus 6y ago
  But that's not the game as constituted. Obviously it could incorporate more non-pseudorandom randomness, but it didn't and doesn't.
- Spivak 6y ago
  Yes but lots of games like this use static seeds that are shown to the player so that you can replay and share games. In particular so that viewers can play along with streamers.
NineStarPoint 6y ago
I'd think that assuming knowledge of the seeds isn't an interesting question from the perspective of the player. To me the much more interesting question, and what I presume 1 is asking, would be "Assuming true randomness, is there are strategy that achieves 100% win rate in slay the spire." (True randomness meaning ignore pseudorandomness and assume that if the game makes something happens 5% of the time, it could do so from any valid starting state.) Really what the question is asking is is there a strategy that for any theoretically valid game of slay the spire would, if followed, result in a win. Given that the article did prove that there are theoretically unwinnable seeds with A20 silent, the answer is definitely not that am optimal player could win 100% of the time on all rule sets. Does change the question to "For a given StS rule set, what is the winrate the maximally efficient strategy would achieve."
agag 6y ago
It seems like you didn't read the actual article all the way through. They are specifically explaining a series of theoretically possible events that would make it so that it is literally impossible to win even if you have perfect knowledge of what the seed is going to give you. And then they look for a seed where this series of events happens, making it impossible to win.
BorisTheBrave 6y ago
Good point. That approach was in fact used for "Sploosh Kaboom", a RNG minigame in the Windwaker: https://www.youtube.com/watch?v=1hs451PfFzQ https://www.youtube.com/watch?v=1hs451PfFzQ
- chaorace 6y ago
  See also: Rainbow Tables https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table The thing about "Sploosh Kaboom" is that the end state of the board, essentially a hash, is all you need to know to figure out the seed. That's thanks to the precomputed table embedded in the helper program. Unlike reversing a hash, however, you actually want to crack the code using as little information as possible! Nobody wants to solve for the seed after they've already revealed the whole board, after all. The truly novel part of this particular tool is in how it leverages calculus to narrow down the seed pool by exploiting the RNG that produced the board seed. Each entry in the precomputed table is also time-indexed, since the RNG step count can be loosely approximated based upon the game's runtime. As the tool eliminates seeds from the pool, it's also gaining confidence in the exact cycle count the RNG was at when it produced the seed value for the board, which, in turn, tightens up the distribution curve of the remaining seeds.
tialaramex 6y ago
Mario Maker 2 deliberately mimics early Mario in not having actual randomness. Anything that seems "random" is a result of fine player behaviour e.g. maybe you tapped that button for a frame longer or you stepped one pixel closer, the "random" result is different. Nintendo doesn't want people to upload courses that are impossible, so it requires you to prove any course you want to upload is possible by beating it yourself first. Of course it can't check the course is fun this way, resulting in courses that are "garbage" in the parlance of popular streamers. It also can't prevent the course design depending upon knowledge the designer has but which is concealed from players, such as so-called "pick a pipe" where there are clearly apparently plausible routes forward, all but one of which leads to death, and the use of "dev exits"† where the creator hid some simple way to beat the level while an innocent player will try to do what may actually be impossible. If there was true randomness then even a course intended just to be quite difficult might randomly sometimes be impossible due to unpredictable behaviour. †Unlike "pick a pipe" a "dev exit" could be a necessary part of some very sophisticated courses where there intentionally is no ordinary way to win from specific situations without dying, real players are expected to die and continue playing successfully but the upload test does not allow this.
- zimpenfish 6y ago
  > it requires you to prove any course you want to upload is possible by beating it yourself first. Relevant from yesterday: https://robertheaton.com/preventing-impossible-game-levels-using-cryptography/ https://robertheaton.com/preventing-impossible-game-levels-u...
mbrubeck 6y ago
The author’s latest blog post explores some related territory: https://forgottenarbiter.github.io/Correlated-Randomness/ https://forgottenarbiter.github.io/Correlated-Randomness/

TylerE 6y ago

Couldn't that be more or less trivially defeated by taking wallclock time as an input to the RNG?

b1ur 6y ago
It could be, but considering the developers made the conscious decision to use a static seed and show that seed to the player they are probably okay with that.
tarboreus 6y ago
But that's not the game as constituted. Obviously it could incorporate more non-pseudorandom randomness, but it didn't and doesn't.
Spivak 6y ago
Yes but lots of games like this use static seeds that are shown to the player so that you can replay and share games. In particular so that viewers can play along with streamers.

NineStarPoint 6y ago

I'd think that assuming knowledge of the seeds isn't an interesting question from the perspective of the player. To me the much more interesting question, and what I presume 1 is asking, would be "Assuming true randomness, is there are strategy that achieves 100% win rate in slay the spire." (True randomness meaning ignore pseudorandomness and assume that if the game makes something happens 5% of the time, it could do so from any valid starting state.) Really what the question is asking is is there a strategy that for any theoretically valid game of slay the spire would, if followed, result in a win. Given that the article did prove that there are theoretically unwinnable seeds with A20 silent, the answer is definitely not that am optimal player could win 100% of the time on all rule sets. Does change the question to "For a given StS rule set, what is the winrate the maximally efficient strategy would achieve."

agag 6y ago

It seems like you didn't read the actual article all the way through. They are specifically explaining a series of theoretically possible events that would make it so that it is literally impossible to win even if you have perfect knowledge of what the seed is going to give you. And then they look for a seed where this series of events happens, making it impossible to win.

BorisTheBrave 6y ago

Good point. That approach was in fact used for "Sploosh Kaboom", a RNG minigame in the Windwaker: https://www.youtube.com/watch?v=1hs451PfFzQ https://www.youtube.com/watch?v=1hs451PfFzQ

chaorace 6y ago
See also: Rainbow Tables https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table The thing about "Sploosh Kaboom" is that the end state of the board, essentially a hash, is all you need to know to figure out the seed. That's thanks to the precomputed table embedded in the helper program. Unlike reversing a hash, however, you actually want to crack the code using as little information as possible! Nobody wants to solve for the seed after they've already revealed the whole board, after all. The truly novel part of this particular tool is in how it leverages calculus to narrow down the seed pool by exploiting the RNG that produced the board seed. Each entry in the precomputed table is also time-indexed, since the RNG step count can be loosely approximated based upon the game's runtime. As the tool eliminates seeds from the pool, it's also gaining confidence in the exact cycle count the RNG was at when it produced the seed value for the board, which, in turn, tightens up the distribution curve of the remaining seeds.

tialaramex 6y ago

Mario Maker 2 deliberately mimics early Mario in not having actual randomness. Anything that seems "random" is a result of fine player behaviour e.g. maybe you tapped that button for a frame longer or you stepped one pixel closer, the "random" result is different. Nintendo doesn't want people to upload courses that are impossible, so it requires you to prove any course you want to upload is possible by beating it yourself first. Of course it can't check the course is fun this way, resulting in courses that are "garbage" in the parlance of popular streamers. It also can't prevent the course design depending upon knowledge the designer has but which is concealed from players, such as so-called "pick a pipe" where there are clearly apparently plausible routes forward, all but one of which leads to death, and the use of "dev exits"† where the creator hid some simple way to beat the level while an innocent player will try to do what may actually be impossible. If there was true randomness then even a course intended just to be quite difficult might randomly sometimes be impossible due to unpredictable behaviour. †Unlike "pick a pipe" a "dev exit" could be a necessary part of some very sophisticated courses where there intentionally is no ordinary way to win from specific situations without dying, real players are expected to die and continue playing successfully but the upload test does not allow this.

zimpenfish 6y ago
> it requires you to prove any course you want to upload is possible by beating it yourself first. Relevant from yesterday: https://robertheaton.com/preventing-impossible-game-levels-using-cryptography/ https://robertheaton.com/preventing-impossible-game-levels-u...

mbrubeck 6y ago

The author’s latest blog post explores some related territory: https://forgottenarbiter.github.io/Correlated-Randomness/ https://forgottenarbiter.github.io/Correlated-Randomness/