[dzdt]

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

[timdierks]

That's me! Thanks for pulling up the quote from long ago:

> "With his obvious technical skill, and his "cheat early and often" attitude, Tim could have a promising career as an AI programmer in the computer games industry. :)"

Instead took a path of security, authoring the TLS RFC and principal engineer in Google security. Thanks for the flashback.

[teekert]

You pulled a Kobayashi Maru when you got the chance. I bow to thee.

[tomrod]

This makes me happy to see.

[shthed]

Can you share the source to Nostradamus?

[le-mark]

Or a write up on the algorithm used? How did knowledge of the prngs of the impact the impl?

[spacebacon]

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.

[romanows]

DJs have timecoded vinyl records that do something like this, even allowing the DJ to scratch the mp3 that is being played.

[1letterunixname]

Serato is digital pretend scratching. Might as well use a DJ controller. Real scratching requires a proper tt and skill like Mix Master Mike. Hell, I have 2 Pioneer DL-5 and a Pioneer DJM-600, but these tts aren't good for scratching because of their straight arms, they're good for gapless playback. https://youtu.be/58Y--XTIRZ8

[timvdalen]

Only on Hacker News!

[sleepingreset]

you're a wizard bro. hell yea

[reactordev]

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.

[joshu]

I submitted the optimally bad entrant the first year, cheesebot.

https://web.archive.org/web/20180719050236/http://webdocs.cs...

[BarryMilo]

I can't believe they didn't say anything about your solution! How did it work?

[rhaps0dy]

Nice! How does Cheesebot work and why did it lose?

[dzdt]

The whole commentary about the "supermodified" class of competition entrants is making my laugh:

> Nostradamus was written by Tim Dierks, a VP of Engineering at Certicom, who has a lot of expertise in cryptography. The program defeats the optimal player by reverse-engineering the internal state of the random() generator, which he states "was both easier and harder than I thought it would be". To be sporting, it then plays optimally against all other opponents.

> Fork Bot was based on an idea that Dan Egnor came up with a few minutes after hearing about the contest. Since "library routines are allowed", his elegant solution was to spawn three processes with fork(), have each one make a different move, and then kill off the two that did not win. This was implemented by Andreas Junghanns in about 10 lines of code. Unfortunately, since all three moves lost to the Psychic Friends Network after the first turn, the program exited and the remainder of that match was declared forfeited.

> The Psychic Friends Network is a truly hilarious piece of obfuscated C, written by Michael Schatz and company at RST Corporation. Among other things, it uses an auxiliary function to find good karma, consults horoscopes, cooks spaghetti and (mystic) pizza to go with various kinds of fruit, #defines democrats as communists, and undefines god. We're still trying to figure out exactly what it is doing with the stack frame, but we do know that it never scores less than +998 in a match, unless it is playing against a meta-meta-cheater.

> The Matrix was written by Darse Billings, who holds the prestigious title of "Student for Life", and recently started the PhD programme at the University of Alberta. The RoShamBo program defeated every opponent with a perfect score, based on the simple principle "There is no spoon".

> Since The Matrix is also the tournament program, it has complete access to all other algorithms, data structures, and output routines, and is therefore unlikely to ever be overtaken. As a result, this category is hereby declared to be solved, and thus retired from future competitions.

[rhaps0dy]

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 :)

[konstantinua00]

so parallel universes lost to rewriting history

amazing

[dzdt]

Thanks for the deep dive. Yes fun to follow.

[handojin]

The whole is better than the sum of the parts. You have nostradamus which predicts the future, fork bot which plays all playable presents, and the psychic friends network which rewrites the past. All under the watchful eye of the matrix.

There's something beautiful here and you honestly couldn't make it up.

[eru]

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

[alickz]

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

[eru]

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.

[thenewnewguy]

Wouldn't the most obvious method of cheating be the site owner peeking at other player's hands and/or the deck? Which this doesn't (and cannot) prevent?

I guess I'm not sure what publicizing their PRNG is meant to prove. It shows they didn't cheat via a very specific type of cheating but there are several other potential cheating vectors.

[eru]

> It shows they didn't cheat via a very specific type of cheating but there are several other potential cheating vectors.

Yes, and this is not the only anti-cheat method they had.

[eru]

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

[Elucalidavah]

> don't use some form of hardware based RNG

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?

[eru]

If you just want any old entropy, and don't care about proving to someone else that your entropy is good, these are acceptable. But it's honestly really easy to get entropy on that grate, and thanks to modern cryptographically secure PRNG, you don't need a lot of 'real' entropy. You can stretch it out forever.

If you want/need to be able to argue to a third party that your entropy was good, you can spend a bit more.

How do you convince anyone that your mic input was actual real mic input, and not just a sequence of bits you made up to be convenient for you?

[logtempo]

https://www.random.org/

[mikegreenberg]

Or, if you don't want to trust the source, https://drand.love/

[bagels]

So, it was using a pseudorandom generator?