21 ms·

Back in 1999-2000 there was an "International RoShamBo Programming Competition" [1] where computer bots competed in the game of rock-paper-scissors. The baselin

by dzdt 2y ago

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.ualberta.ca/~darse/rsbpc2.html https://web.archive.org/web/20180719050311/http://webdocs.cs... [2] https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc

dzdt 2y ago
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 2y ago
  I was very curious about the Psychic Friends Network. One can find the code here (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine.c#L5464-L5564 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.c#L5520 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.c#L5624 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.c#L5527-L5532 https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...) never get executed, then these lines (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine.c#L5527-L5532 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.c#L5540 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.c#L5551-L5560 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 :)
  - dzdt 2y ago
    Thanks for the deep dive. Yes fun to follow.
timdierks 2y ago
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.
- timvdalen 2y ago
  Only on Hacker News!
- reactordev 2y ago
  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.
- tomrod 2y ago
  This makes me happy to see.
- sleepingreset 2y ago
  you're a wizard bro. hell yea
- shthed 2y ago
  Can you share the source to Nostradamus?
  - le-mark 2y ago
    Or a write up on the algorithm used? How did knowledge of the prngs of the impact the impl?
- teekert 2y ago
  You pulled a Kobayashi Maru when you got the chance. I bow to thee.
- spacebacon 2y ago
joshu 2y ago
I submitted the optimally bad entrant the first year, cheesebot. https://web.archive.org/web/20180719050236/http://webdocs.cs.ualberta.ca/~darse/rsb-results1.html https://web.archive.org/web/20180719050236/http://webdocs.cs...
- BarryMilo 2y ago
  I can't believe they didn't say anything about your solution! How did it work?
- rhaps0dy 2y ago
  Nice! How does Cheesebot work and why did it lose?
eru 2y ago
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 2y ago
  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_generator https://en.wikipedia.org/wiki/Hardware_random_number_generat...
  - eru 2y ago
    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.
    - eru 2y ago
      (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.)
    - thenewnewguy 2y ago
      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 2y ago
        > 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.
bagels 2y ago
So, it was using a pseudorandom generator?

by dzdt 2y ago

dzdt 2y ago

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 2y ago
I was very curious about the Psychic Friends Network. One can find the code here (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine.c#L5464-L5564 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.c#L5520 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.c#L5624 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.c#L5527-L5532 https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine...) never get executed, then these lines (https://github.com/MrValdez/Roshambo/blob/master/rsb-iocaine.c#L5527-L5532 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.c#L5540 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.c#L5551-L5560 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 :)
- dzdt 2y ago
  Thanks for the deep dive. Yes fun to follow.

timdierks 2y ago

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.

timvdalen 2y ago
Only on Hacker News!
reactordev 2y ago
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.
tomrod 2y ago
This makes me happy to see.
sleepingreset 2y ago
you're a wizard bro. hell yea
shthed 2y ago
Can you share the source to Nostradamus?
- le-mark 2y ago
  Or a write up on the algorithm used? How did knowledge of the prngs of the impact the impl?
teekert 2y ago
You pulled a Kobayashi Maru when you got the chance. I bow to thee.
spacebacon 2y ago

joshu 2y ago

I submitted the optimally bad entrant the first year, cheesebot. https://web.archive.org/web/20180719050236/http://webdocs.cs.ualberta.ca/~darse/rsb-results1.html https://web.archive.org/web/20180719050236/http://webdocs.cs...

BarryMilo 2y ago
I can't believe they didn't say anything about your solution! How did it work?
rhaps0dy 2y ago
Nice! How does Cheesebot work and why did it lose?

eru 2y ago

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 2y ago
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_generator https://en.wikipedia.org/wiki/Hardware_random_number_generat...
- eru 2y ago
  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.
  - eru 2y ago
    (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.)
  - thenewnewguy 2y ago
    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 2y ago
      > 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.

bagels 2y ago

So, it was using a pseudorandom generator?