Rendered at 15:32:15 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
PennRobotics 18 hours ago [-]
Stardew Valley has two random number seeds. One is the normal character seed. The other, your multiplayer ID, can be determined by analyzing the save file.
Except! On the Switch, you can't easily access the save file AND the random number generator is different than on PC. There is a seed cracker that looks at your traveling cart listing and calculates the character seed. Maybe because it's less important and harder to observe, I haven't found any tool to crack the other seed and don't have time to attempt writing it myself.
By inspecting cracked geode contents, you should be able to isolate your multiplayer ID and then predict random events on Nintendo just as PC players have done for the last decade with access to the save file.
The C# code for the game is online and the Switch RNG is known, so you never have to work in the dark. It's three steps: ensure your Switch RNG implementation works by testing against the normal seed, ensure your geode RNG implementation works by testing against the PC RNG, and then apply the Switch RNG to the geode function enough times that only one seed could create your observed sequence.
-----
Two semi-related open questions: Are you able to solve as quickly while starting at ANY geode as you'd be solving from the first geode? Does the RNG eventually repeat, so it actually doesn't matter what your multiplayer ID is as long as you observe a unique sequence, since there will only be one continuation of that sequence?
bombcar 14 hours ago [-]
My favorite is the Doom random number generator, which is just a list of “random” numbers that it cycles through and if you know how to use it, you can do things like concentrate BFG attacks.
vladde 5 hours ago [-]
decino made a video about that, and at 13 minutes in the video they show what happens in-game if you set all values to 0 :)
EverQuest also used pre-generated numbers. The randomness was derived from the large number of players using the same list.
thaumasiotes 8 hours ago [-]
That sounds like a pretty strong source of true randomness, frankly.
(It's then filtered through the list, so the list needs to have good pseudorandomness properties anyway, but still.)
eru 4 hours ago [-]
> (It's then filtered through the list, so the list needs to have good pseudorandomness properties anyway, but still.)
Not sure? Suppose your list only had two number 0 and 1, and you build your random numbers one bit at a time.
Or more realistically, you have 256 numbers on the list 0, 1, 2, ..., 255 in order. If the 'large numbers of players drawing from the same list' assumption holds, it doesn't matter much that the list is in order.
What's just a bit weird is why anyone would want to turn an embarrassingly parallel problem into something with a sequential bottleneck?
thaumasiotes 4 hours ago [-]
> Or more realistically, you have 256 numbers on the list 0, 1, 2, ..., 255 in order. If the 'large numbers of players drawing from the same list' assumption holds, it doesn't matter much that the list is in order.
Why not? That should convert your random number generation into draws from a Poisson process. If you were looking to simulate a Poisson distribution, you're set. If not, you probably just ruined your RNG.
(If the idea is that the interval between any two samples is so large that the list will inevitably be cycled several times before any one person can sample a second byte, there's something to that. It's going to make asking for random numbers more than 8 bits long challenging though.)
eru 2 hours ago [-]
> It's going to make asking for random numbers more than 8 bits long challenging though.
'Yield' to other players' threads or processes after each byte you draw.
nomel 13 hours ago [-]
Reminds me of a "Dice" electronics kit I assembled when I was a kid. It just used some standard sequential counter ICs run at very high rate. Pressing the "roll" button would just stop the counter!
The coolest part of this for me is that it's not only reverse engineering the RNG and being able to predict random rolls, which is relatively simple for that PRNG algorithm, but then being able to implement that algorithm in-game using combinator networks. There are already a lot of amazing things that you can do with combinators and this is a great example to add to the list.
Aardwolf 17 hours ago [-]
> We chose taus88 mainly because it is the fastest from boost’s generators.
That's an RNG from 1996. It seems neither recent C++ standards, nor boost, know anything about the modern PRNGs that are much faster yet better at passing test suites
One of the reasons I dislike boost is in the first code sample. What’s the point of implementing what boils down to a 10 line function (as shown in the decompiled output) like this
This is called template-based compile-time programming.
By making 3 instances of linear_feedback_shift_engine class template ( and 2 of xor_combine_engine ), you are forcing the compiler to expand the code exactly as-is 3 times, each with different parameters.
The parameters to the template are constant, therefore the compiler can easily look at how they are used and you are guaranteed ( even in a 1999 c++ compiler ) that the compiler will look at the copies of the code and merge them as much as possible into a single piece of code... which is the one that you see when you decompile the code.
So in summary, it means that you get to write fairly readable code while the final binary is fully optimized as-if you had spent the time merging all the variants as needed for the specific constants.
eru 4 hours ago [-]
You could get something similar from CPP macros. But the compiler wouldn't be able to help you as much.
ainiriand 5 hours ago [-]
C++ is uglier than punching one's dad.
windenntw 5 hours ago [-]
Correct, but also beside the point.
To do it in almost-plain C, you'd need fairly complex macros that are more difficult to write correctly.
To do it in plain C without macros, or plain C++ without templates... you'd need to work out the combination of the template expansion yourself and write down a piece of code that is more likely to have bugs and more difficult to understand.
eru 4 hours ago [-]
I'm not quite sure: you could probably use plain C functions, and a reasonably smart compiler could see through it all and inline and duplicate and merge the code as necessary.
EDIT: I just had an AI agent run the experiment. At least for my version of clang, they produce the same assembly for x86_64 (modulo using slightly different registers).
mitxela 9 hours ago [-]
Boost predates C++11
torvin92 15 hours ago [-]
As if Factorio wasn't addictive enough, now we can predict ore patches! My sleep schedule is already ruined.
jtrn 5 hours ago [-]
This is so awesome! Thank you so much for this extremely fascinating read/work! I love combining gaming and learning!!
TL;DR: Wired up an in-game predictor of RNG output and used it to only craft legendary items when RNG would line up to roll legendary.
From base to legendary at a suprisingly high rate. Look very closely at the video at the top of the post - what I was seeing didn't sink in until I had finished the article. Amazing.
strstr 19 hours ago [-]
I did an easier version of this in my college intro class. There was a class competition that involved rock paper scissors as a subcomponent, and ties were broken with randomness. You could rig Java’s prng so you would win all ties.
The prng was seeded with usec time at first call. I called the rng a bunch of times to harvest entropy, and scanned the plausible usec times to find the seed. Then I primed the prng so I would win ties.
Frankly, I assume I implemented this wrong, but the theory was there lol.
3eb7988a1663 15 hours ago [-]
I am failing to find the article, but some early online poker systems used the server time as the seed coupled with a weak PRNG. With the information of the hole cards + community cards, after a few hands, could quickly determine exactly what seed was being used and perfectly predict everyone's cards.
It's a bad shuffle implementation + using time of day as seed (reducing search space). Using the player's 2 cards and the 3 flop cards, it finds the RNG seed in real time, and then future hands (on the same server) are solved in "under one second!"
rogueaine 18 hours ago [-]
That’s not at all what the article proposed. The author constructed and transpose to the linear shift register coefficients and built a circuit network based on this to predict the next state (in the sandbox) and direct recipes.
strstr 18 hours ago [-]
From the article:
> Sampling the current RNG through observations,
> Computing the current internal RNG state,
> Predicting the future internal states,
> Calculating corresponding quality levels for each future call, and finally
> Making use of the predicted levels with some adapters.
The entropy->seeds (internal RNG state) step took more math of course. Frankly, I wouldn’t be surprised if they could have extracted the seeds without the math with a bit of RE and memory inspection.
The version I did wasn’t predicting quality of course, it was predicting tie breakers
hbroom 15 hours ago [-]
Dedication like this is awesome. Finally, we can optimize those starting resource patches without endless map restarts!
3eb7988a1663 15 hours ago [-]
At the conclusion, he said he spent two years on this! That's a thesis.
throooooo 12 hours ago [-]
If you're playing/hosting locally you get a preview of the world and can reroll for a different seed if you'd like.
Founderarcstone 17 hours ago [-]
Really cool example of how something that looks random can become predictable once you understand the underlying system.
It mentions how they had to use a custom math library to differences in results on different platforms causing multiplayer sync issues.
vlyan 17 hours ago [-]
by far the blackest magic I ever saw for that game.
I'm an upper intermediate at Factorio, resorting to someone else's blueprints only for belt balancers and rail intersections, and I can't even begin to figure out how it's done.
harlan_pdx 14 hours ago [-]
Factorio players reverse-engineering an RNG? Peak Factorio. The dedication to optimize everything, even randomness, is truly something.
jatins 8 hours ago [-]
What’s the goal here with posting AI comments on every post? Does it help you get a job, do you sell this account?
redbear2026 7 hours ago [-]
It's probably just a test for their bot. We will see them everywhere.
jatins 4 hours ago [-]
it works! others can stop the test now
myhf 18 hours ago [-]
Impressive work!
lowbloodsugar 19 hours ago [-]
Madman. Brilliant.
FrustratedMonky 5 hours ago [-]
It gives me hope, that out there in the internet, there are still people just doing purely geeky deep dives. I wish you good luck in life.
Except! On the Switch, you can't easily access the save file AND the random number generator is different than on PC. There is a seed cracker that looks at your traveling cart listing and calculates the character seed. Maybe because it's less important and harder to observe, I haven't found any tool to crack the other seed and don't have time to attempt writing it myself.
By inspecting cracked geode contents, you should be able to isolate your multiplayer ID and then predict random events on Nintendo just as PC players have done for the last decade with access to the save file.
The C# code for the game is online and the Switch RNG is known, so you never have to work in the dark. It's three steps: ensure your Switch RNG implementation works by testing against the normal seed, ensure your geode RNG implementation works by testing against the PC RNG, and then apply the Switch RNG to the geode function enough times that only one seed could create your observed sequence.
-----
Two semi-related open questions: Are you able to solve as quickly while starting at ANY geode as you'd be solving from the first geode? Does the RNG eventually repeat, so it actually doesn't matter what your multiplayer ID is as long as you observe a unique sequence, since there will only be one continuation of that sequence?
https://www.youtube.com/watch?v=pq3x1Jy8pYM
(It's then filtered through the list, so the list needs to have good pseudorandomness properties anyway, but still.)
Not sure? Suppose your list only had two number 0 and 1, and you build your random numbers one bit at a time.
Or more realistically, you have 256 numbers on the list 0, 1, 2, ..., 255 in order. If the 'large numbers of players drawing from the same list' assumption holds, it doesn't matter much that the list is in order.
What's just a bit weird is why anyone would want to turn an embarrassingly parallel problem into something with a sequential bottleneck?
Why not? That should convert your random number generation into draws from a Poisson process. If you were looking to simulate a Poisson distribution, you're set. If not, you probably just ruined your RNG.
(If the idea is that the interval between any two samples is so large that the list will inevitably be cycled several times before any one person can sample a second byte, there's something to that. It's going to make asking for random numbers more than 8 bits long challenging though.)
'Yield' to other players' threads or processes after each byte you draw.
the closely related not-at-all-random fizzlefade from Wolfenstein: https://fabiensanglard.net/fizzlefade/
That's an RNG from 1996. It seems neither recent C++ standards, nor boost, know anything about the modern PRNGs that are much faster yet better at passing test suites
EDIT: Ok the above quote was from 2014, and boost seems to know some now! https://www.boost.org/doc/libs/latest/doc/html/boost_random/...
By making 3 instances of linear_feedback_shift_engine class template ( and 2 of xor_combine_engine ), you are forcing the compiler to expand the code exactly as-is 3 times, each with different parameters.
The parameters to the template are constant, therefore the compiler can easily look at how they are used and you are guaranteed ( even in a 1999 c++ compiler ) that the compiler will look at the copies of the code and merge them as much as possible into a single piece of code... which is the one that you see when you decompile the code.
So in summary, it means that you get to write fairly readable code while the final binary is fully optimized as-if you had spent the time merging all the variants as needed for the specific constants.
To do it in almost-plain C, you'd need fairly complex macros that are more difficult to write correctly.
To do it in plain C without macros, or plain C++ without templates... you'd need to work out the combination of the template expansion yourself and write down a piece of code that is more likely to have bugs and more difficult to understand.
EDIT: I just had an AI agent run the experiment. At least for my version of clang, they produce the same assembly for x86_64 (modulo using slightly different registers).
TL;DR: Wired up an in-game predictor of RNG output and used it to only craft legendary items when RNG would line up to roll legendary.
From base to legendary at a suprisingly high rate. Look very closely at the video at the top of the post - what I was seeing didn't sink in until I had finished the article. Amazing.
The prng was seeded with usec time at first call. I called the rng a bunch of times to harvest entropy, and scanned the plausible usec times to find the seed. Then I primed the prng so I would win ties.
Frankly, I assume I implemented this wrong, but the theory was there lol.
google surfaces a couple of HN posts, but the source (cigital.com) seems to be a dead domain at this point:
https://news.ycombinator.com/item?id=288138
https://news.ycombinator.com/item?id=9914607
It's a bad shuffle implementation + using time of day as seed (reducing search space). Using the player's 2 cards and the 3 flop cards, it finds the RNG seed in real time, and then future hands (on the same server) are solved in "under one second!"
> Sampling the current RNG through observations,
> Computing the current internal RNG state,
> Predicting the future internal states,
> Calculating corresponding quality levels for each future call, and finally
> Making use of the predicted levels with some adapters.
The entropy->seeds (internal RNG state) step took more math of course. Frankly, I wouldn’t be surprised if they could have extracted the seeds without the math with a bit of RE and memory inspection.
The version I did wasn’t predicting quality of course, it was predicting tie breakers
https://devblogs.microsoft.com/cppblog/bringing-correctly-ro...
It mentions how they had to use a custom math library to differences in results on different platforms causing multiplayer sync issues.
I'm an upper intermediate at Factorio, resorting to someone else's blueprints only for belt balancers and rail intersections, and I can't even begin to figure out how it's done.