Rock Paper Scissors Programming Competition

http://www.rpscontest.com/

by bvaldivielso • 12 years ago

30 15 12 years ago

twiceaday2• 12 years 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• 12 years ago

Reminds me of the clever strategy that won a prisoner's dilemma contest.

http://archive.wired.com/culture/lifestyle/news/2004/10/6531...

richdougherty• 12 years 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#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• 12 years ago

This is the most clever I've seen: 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)

ngokevin• 12 years 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.

vorg2• 12 years ago

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

ryan-c2• 12 years ago

Isn't it rock paper scissors spock lizard?

vorg2• 12 years 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.

ryan-c2• 12 years ago

I wrote an entry about two years ago: 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• 12 years ago

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

srean• 12 years 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• 12 years ago

My first thought was Core Wars. :-)

Scribblenaut9• 12 years 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.

Rock Paper Scissors Programming Competition

Related Stories