Back in 1999-2000 there was an "International RoShamBo Programming Competition" [1] where computer bots competed in the game of rock-paper-scissors. The baseline bot participant just selected its play randomly, which is a theoretically unbeatable strategy. One joke entry to the competition was carefully designed to beat the random baseline ... by reversing the state of the random number generator and then predicting with 100% accuracy what the random player would play.
Edit: the random-reversing bot was "Nostradamus" by Tim Dierks, which was declared the winner of the "supermodified" class of programs in the First International RoShamBo Programming Competition. [2]
[1] https://web.archive.org/web/20180719050311/http://webdocs.cs... [2] https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc
That's me! Thanks for pulling up the quote from long ago:
Instead took a path of security, authoring the TLS RFC and principal engineer in Google security. Thanks for the flashback.
I had to checkout your Git after this awesome reply. Gotta love Hacker News.
I had a cool vision for “tag play” … I visualize mini RFID records on a turn table that tell Roku what to play.
DJs have timecoded vinyl records that do something like this, even allowing the DJ to scratch the mp3 that is being played.
Can you share the source to Nostradamus?
Or a write up on the algorithm used? How did knowledge of the prngs of the impact the impl?
This makes me happy to see.
Only on Hacker News!
You pulled a Kobayashi Maru when you got the chance. I bow to thee.
you're a wizard bro. hell yea
So what you’re saying is, if you can’t beat em, join em? /s
I’m actually a bit relieved they have you on the team. Considering what they (Google) know about us all.
I remember someone doing the same to an online poker site that had helpfully documented its PRNG in a laudable attempt at transparency.
(And the transparency got them an improvement in their security in the end.)
I'm surprised they don't use some form of hardware based RNG. I assume there's many good reasons
https://en.wikipedia.org/wiki/Hardware_random_number_generat...
They wanted to show that they didn't cheat.
In general, you can pick a random seed at the start of the day, commit to it somewhere (eg publish a hash of it on the bitcoin blockchain, or just on your website), then use that seed in a cryptographically secure PRNG on your website all day, and at the end of the day you publish the seed you already committed to.
This way people can check that you didn't cheat, but can't guess their opponents cards either.
(The above was simplified. In a game of poker, you also want to make sure that when hands get folded, that no one learns what the cards were.)
https://www.random.org/
I've always wondered: why aren't ADCs (e.g. mic input) and temperature sensors considered a good source of entropy, particularly if the lower bits are taken?
The whole commentary about the "supermodified" class of competition entrants is making my laugh:
I was very curious about the Psychic Friends Network. One can find the code here (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...), and it's easy to deobfuscate substantially by running it through the C preprocessor.
I believe it works as follows: - It plays randomly for the first 998 turns (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...): this line is "if (*turn < trials - 2) return libra ? callback() : random() % 3;", and "libra" is initalized to (int) NULL, i.e. zero, on every invocation.
- In the last 2 turns, it uses `find_goodkarma` to comb through the stack to find where the variables that match its history and the opponents' history are stored. These the stack arrays p1hist and p2hist (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...)
They're easy to find because they contain 998 known values each in a ~random sequence of (0, 1, 2), and they're just upwards of the stack from the current invocation of the Psychic Friends Network.
`find_goodkarma` simply increments a pointer until the whole sequence of 998 values matches the known history.
- Then, it rewrites the history to make itself win. These lines (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...) never get executed, then these lines (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...) tally up draws so far (libra), wins (cancer) and losses (scorpio).
This line makes sure its move is the opponents' move +1 mod 3, which is the winning move: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...
Then, these lines repeat the same trick for the number of wins and losses. It checks whether it's p1 or p2 by comparing the addresses of the win/loss arrays, and then overwrites the wins/losses appropriately using `pizza` https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...
in the end it returns an arbitrary value (the address of `good_hand` mod 3).
It was fun to follow but the result is kind of boring :)
so parallel universes lost to rewriting history
amazing
Thanks for the deep dive. Yes fun to follow.
I submitted the optimally bad entrant the first year, cheesebot.
https://web.archive.org/web/20180719050236/http://webdocs.cs...
Nice! How does Cheesebot work and why did it lose?
I can't believe they didn't say anything about your solution! How did it work?
So, it was using a pseudorandom generator?