6 ms·

Rock Paper Scissors Programming Competition

30 points by bvaldivielso 12y ago

twiceaday 12y ago
I participated in a Google hosted one a while back and it was great fun. There is a great push and pull between trying to be as random as possible while attempting to exploit non-randomness in your opponents. I ended up going with a 'many demons' solution whereby I had many strategies voting on what the guess should be and I modulated the weight of their votes based on their success. I also used 'sicillian logic' to make meta-strategies that simply voted on a move that would win/lose to the guesses of my other strategies. One thing I always wanted to try was to cheat. Flood the submissions with bots that would attempt a pseudo-random-looking handshake. If it failed the bots would act randomly. But if it succeeded they would perform a pre-determined pseudo-random pattern that my one true bot would exploit to boost its rating.
- mdonahoe 12y ago
  Reminds me of the clever strategy that won a prisoner's dilemma contest. http://archive.wired.com/culture/lifestyle/news/2004/10/65317 http://archive.wired.com/culture/lifestyle/news/2004/10/6531...
  - richdougherty 12y ago
    Or The Alliance of Pacifist Scum from RoboWar, a game I played back in the 90s. http://robowar.sourceforge.net/RoboWar5/Theory/theory.html#Alliance http://robowar.sourceforge.net/RoboWar5/Theory/theory.html#A... "Essentially, the idea behind the Alliance was a simple recognition that the scoring system for tournaments up to that point made no award at the time for killing one's enemy, only for surviving the battle. It mattered not even if the enemy was still alive, so long as you were alive at the conclusion. So in the Eighth Tournament, someone came up with the screwball idea that maybe they shouldn't bother even fighting at all unless they came under attack from their enemy. Either it was amazing coincidence or there was an active conspiracy of communication going on that I was unaware of to build these horrible things, because a few more of these guys showed up at once than coincidence would seem to warrant in the Eighth Tournament. "I refer to this bunch as the Alliance because that's essentially what it is. The robots agree not to fight each other so that each gets full credit for all of their battles. When Allied Pacifist Scum are in battle with each other, both get 100% points for their battles. If they fought it out, each would get 50% if they were equally matched, and both might well get less than that, since a double kill doesn't benefit either one of them."
  - surreal 12y ago
    This is the most clever I've seen: http://www.youtube.com/watch?v=S0qjK3TWZE8 http://www.youtube.com/watch?v=S0qjK3TWZE8 He ensures his opponent has nothing to gain from defecting... (Rules etc until 2m 30s, then the game)
    - twiceaday 12y ago
      That's awesome. My favorite part is when the clever guy who kept his cool during the entire episode drops his jaw when he hears the other guy is going to use his winnings to re-spray his yacht.
deleted 12y ago
[deleted]
ngokevin 12y ago
This reminds me poker push-fold strategy. Push-fold is the late stages of poker tournaments where the chip stacks in relations to the blinds are so small, that your only options are to go all-in or fold. You can either play the "equilibrium" where your play is non-exploitable and yields neutral expectation (this is done by using a push-fold chart). Or you can play "exploitably" where your play tries to predict patterns in the opponent to gain a positive expectation. The difference between this and rock-paper-scissors though is it involves more factors (3 choices vs 169 starting hands + push-or-fold), and a little bit of short-term chance. Though of course if you run bot vs bot 1,000,000 times, it'll be pretty clear which is superior.
deleted 12y ago
[deleted]
vorg 12y ago
The five-option "Rock-paper-scissors-Sheldon-Spock" version would be more fun.
- ryan-c 12y ago
  Isn't it rock paper scissors spock lizard?
  - vorg 12y ago
    Scissors cuts Paper, and Paper covers Rock as they always have, Rock crushes Sheldon, Sheldon poisons Spock, Spock smashes Scissors, Scissors decapitates Sheldon, Sheldon eats Paper, Paper disproves Spock, Spock vaporizes Rock, and Rock crushes Scissors as it always has.
    - p3lim 12y ago
      Yeah, that is incorrect, it's rock, paper, scissors, lizard, spock. https://www.youtube.com/watch?v=x5Q6-wMx-K8 https://www.youtube.com/watch?v=x5Q6-wMx-K8
ryan-c 12y ago
I wrote an entry about two years ago: http://www.rpscontest.com/entry/614005 http://www.rpscontest.com/entry/614005 The comment in the program is, of course, a joke. What I actually did was download every other bot on the site, pick out all the ones that made no calls to `random` and let a brute force search for a good constant run for a few days. The trick is that random play wins about 50% of the time, and this hack, despite being totally deterministic, has play that is indistinguishable from random within the constraints of the contest unless specifically accounted for. For each other program that also has deterministic play, about half of all possible constants will win. Try enough constants and eventually you'll find one that wins against a moderate majority of the other entries.
nickgrosvenor 12y ago
https://www.youtube.com/watch?v=2u4xd1PNvMc https://www.youtube.com/watch?v=2u4xd1PNvMc
srean 12y ago
No one yet has mentioned an approach that I had a lot of fun with. It was a 15~20 liner one-off in Python that earned quite a few wins for one of these RPS competitions. I lost the code with the laptop to a disk crash. All it did was keep around compressed concatenation of the opponents plays, and a compressed concatenation of opponent and my plays interleaved. When it was my turn to play, I would extend the strings with the three possible one turn plays, i.e. extend by 'r', 'p', 's' and re-compress, whichever gave the shortest compression was my guess of what the opponent would play next. Then I would play whatever defeated opponent's guessed play. The whole thing was 15~20 lines but of course I was standing on shoulder of giants and the std library. The prediction part was entirely abstracted / co-opted out to the compressor. Better compressors would yield better results. Lempel-Ziv worked well enough as long as there were enough rounds. The theory for this can run quite deep. There are algorithms that will do the best possible if the opponent is using a finite state m/c, which computers are anyway. The performance of these are determined by the state space of the FSM. If one wants to go deeper then one would land in the territory of Kolomogorov complexity.
maurycy 12y ago
My first thought was Core Wars. :-)
Scribblenaut9 12y ago
I think this would be a good situation for a learning algorithm. Couldn't Markov chains be used in this situation? I'd enter this if I was better with Python.

30 points by bvaldivielso 12y ago

I participated in a Google hosted one a while back and it was great fun. There is a great push and pull between trying to be as random as possible while attempting to exploit non-randomness in your opponents. I ended up going with a 'many demons' solution whereby I had many strategies voting on what the guess should be and I modulated the weight of their votes based on their success. I also used 'sicillian logic' to make meta-strategies that simply voted on a move that would win/lose to the guesses of my other strategies. One thing I always wanted to try was to cheat. Flood the submissions with bots that would attempt a pseudo-random-looking handshake. If it failed the bots would act randomly. But if it succeeded they would perform a pre-determined pseudo-random pattern that my one true bot would exploit to boost its rating.

mdonahoe 12y ago
Reminds me of the clever strategy that won a prisoner's dilemma contest. http://archive.wired.com/culture/lifestyle/news/2004/10/65317 http://archive.wired.com/culture/lifestyle/news/2004/10/6531...
- richdougherty 12y ago
  Or The Alliance of Pacifist Scum from RoboWar, a game I played back in the 90s. http://robowar.sourceforge.net/RoboWar5/Theory/theory.html#Alliance http://robowar.sourceforge.net/RoboWar5/Theory/theory.html#A... "Essentially, the idea behind the Alliance was a simple recognition that the scoring system for tournaments up to that point made no award at the time for killing one's enemy, only for surviving the battle. It mattered not even if the enemy was still alive, so long as you were alive at the conclusion. So in the Eighth Tournament, someone came up with the screwball idea that maybe they shouldn't bother even fighting at all unless they came under attack from their enemy. Either it was amazing coincidence or there was an active conspiracy of communication going on that I was unaware of to build these horrible things, because a few more of these guys showed up at once than coincidence would seem to warrant in the Eighth Tournament. "I refer to this bunch as the Alliance because that's essentially what it is. The robots agree not to fight each other so that each gets full credit for all of their battles. When Allied Pacifist Scum are in battle with each other, both get 100% points for their battles. If they fought it out, each would get 50% if they were equally matched, and both might well get less than that, since a double kill doesn't benefit either one of them."
- surreal 12y ago
  This is the most clever I've seen: http://www.youtube.com/watch?v=S0qjK3TWZE8 http://www.youtube.com/watch?v=S0qjK3TWZE8 He ensures his opponent has nothing to gain from defecting... (Rules etc until 2m 30s, then the game)
  - twiceaday 12y ago
    That's awesome. My favorite part is when the clever guy who kept his cool during the entire episode drops his jaw when he hears the other guy is going to use his winnings to re-spray his yacht.

deleted 12y ago

[deleted]

ngokevin 12y ago

This reminds me poker push-fold strategy. Push-fold is the late stages of poker tournaments where the chip stacks in relations to the blinds are so small, that your only options are to go all-in or fold. You can either play the "equilibrium" where your play is non-exploitable and yields neutral expectation (this is done by using a push-fold chart). Or you can play "exploitably" where your play tries to predict patterns in the opponent to gain a positive expectation. The difference between this and rock-paper-scissors though is it involves more factors (3 choices vs 169 starting hands + push-or-fold), and a little bit of short-term chance. Though of course if you run bot vs bot 1,000,000 times, it'll be pretty clear which is superior.

deleted 12y ago

[deleted]

vorg 12y ago

The five-option "Rock-paper-scissors-Sheldon-Spock" version would be more fun.

ryan-c 12y ago
Isn't it rock paper scissors spock lizard?
- vorg 12y ago
  Scissors cuts Paper, and Paper covers Rock as they always have, Rock crushes Sheldon, Sheldon poisons Spock, Spock smashes Scissors, Scissors decapitates Sheldon, Sheldon eats Paper, Paper disproves Spock, Spock vaporizes Rock, and Rock crushes Scissors as it always has.
  - p3lim 12y ago
    Yeah, that is incorrect, it's rock, paper, scissors, lizard, spock. https://www.youtube.com/watch?v=x5Q6-wMx-K8 https://www.youtube.com/watch?v=x5Q6-wMx-K8

ryan-c 12y ago

I wrote an entry about two years ago: http://www.rpscontest.com/entry/614005 http://www.rpscontest.com/entry/614005 The comment in the program is, of course, a joke. What I actually did was download every other bot on the site, pick out all the ones that made no calls to `random` and let a brute force search for a good constant run for a few days. The trick is that random play wins about 50% of the time, and this hack, despite being totally deterministic, has play that is indistinguishable from random within the constraints of the contest unless specifically accounted for. For each other program that also has deterministic play, about half of all possible constants will win. Try enough constants and eventually you'll find one that wins against a moderate majority of the other entries.

nickgrosvenor 12y ago

https://www.youtube.com/watch?v=2u4xd1PNvMc https://www.youtube.com/watch?v=2u4xd1PNvMc

srean 12y ago

No one yet has mentioned an approach that I had a lot of fun with. It was a 15~20 liner one-off in Python that earned quite a few wins for one of these RPS competitions. I lost the code with the laptop to a disk crash. All it did was keep around compressed concatenation of the opponents plays, and a compressed concatenation of opponent and my plays interleaved. When it was my turn to play, I would extend the strings with the three possible one turn plays, i.e. extend by 'r', 'p', 's' and re-compress, whichever gave the shortest compression was my guess of what the opponent would play next. Then I would play whatever defeated opponent's guessed play. The whole thing was 15~20 lines but of course I was standing on shoulder of giants and the std library. The prediction part was entirely abstracted / co-opted out to the compressor. Better compressors would yield better results. Lempel-Ziv worked well enough as long as there were enough rounds. The theory for this can run quite deep. There are algorithms that will do the best possible if the opponent is using a finite state m/c, which computers are anyway. The performance of these are determined by the state space of the FSM. If one wants to go deeper then one would land in the territory of Kolomogorov complexity.

maurycy 12y ago

My first thought was Core Wars. :-)

Scribblenaut9 12y ago

I think this would be a good situation for a learning algorithm. Couldn't Markov chains be used in this situation? I'd enter this if I was better with Python.