Slashdot Mirror
Rock-Paper-Scissors
Andreas Junghanns writes: "Check out the Second
International RoShamBo Programming Competition for a completely
different experience!
If you think you know everything about Rock-Paper-Scissors -- here is your
chance to prove it against some stiff international competition. At the Web site
you can find rules, sample programs and a report of the first contest,
complete with results and program descriptions." This looks pretty cool, and it might make a neat first project for someone, too.
From what I gathered from a quick read overview, pretty much all of the strategies are dynamically programmable, whcih of course will cut down the time needed per turn dramatically.
Johan
These strategies all together easily beat the sample bots but get hammered by the competitive bots. They are no where near as powerful as the competitive bots. I was going to do a bit more extensive pattern matching routines to try and beat them, but just havent got around to doing it.
Vivek Mittal Telstra Research Labs
PS: I wonder how much my first post ever on /. will get moderated. :)
PPS: Can we add another way to get your account information back... enter email... I dont remember by user id and when I try to create a new account, /. complains of a duplicate email.
Somewhere on the web site they has a section of cheating bots and one of the bots did exactly that. It somehow re-engineered the RNG and won all 1000 times against the random bot. Vivek Mittal Telstra Research Labs
My submission, Iocaine Powder, won last year's competition. Follow the link to see a complete description of how it works. The competition results from last year describe some of the other strategies that did well (and some that did not-so-well).
This competition is more complex than it seems; not only are there deliberate "dumb robots", but many of the real entries are quite predictable. A random player wouldn't have made it close to winning, and stalemates were rare.
What does this year hold in store? We'll just have to see!
I'm really not suprised that all you gun-toting, neo-nazi Americans would try to glorify some excessively violent childhood game like Rock Paper Scissors. Have any of you stopped to consider what these sorts of values these pasttimes instill in our children?
I mean, let's start with the rock. And I'm not refering to that movie with Nicholas Cage & Sean Connery in it, either. Rocks == Violence! Ask any caveman! Were it not for Oog being silenced by the Lameness Filter, I assure you he would back me up on this.
As for the scissors, well why don't you just throw children off a cliff? How many times have we been told not to run with scissors, and here /. is urging people to use them as both toys and weapons!
And the paper... oh Lord, how irresponsible can you get? We do all we can to squash that horrible "Puff the Magic Dragon" degenerate druggy song and then you people come along and start handing out Zig Zag's to elementary school students!
While we're at it, let's review the "premise" of this whole "game":
Are any of you thinking about the children? I seriously doubt it!
1) AI class I took last year (well, TA'd) we went in to some detail on possible RPS strategies. Yes, you can have strategies, at least assuming that your opponent is not a pure RNG (in which case the only correct strategy is to be RNG yourself.)
2) Nothing that the tourney produces will be as cool as this. Unfortunately, the picture stinks, but on the left is my professor, and on the right is the kid (he'll hate me for that) who build the RPS-playing Lego Mindstorm. And that's the RPS bot in the kid's hand. It used some pattern learning software (written in legOS) to attempt to detect patterns in human RPS players. Didn't work great, but what the heck... it was still damn cool. Had fingers and the whole bit.
~luge
IAAL,BIANLY
... and for the sequel, a Tic-Tac-Toe robot competition!
Actually, I never realized there were so many levels of depth to Rock-Paper-Scissors. Neat.
--
No more e-mail address game - see my user info. Time for revenge.
Win dain a lotica, en vai tu ri silota
Is this a joke? I mean, if the "optimal" solution is a random distribution, then what possible good can using a heuristic to discover a "tendency" in the opponent be? The only thing you could possibly discover is flaws in the random number generator.
It's 10 PM. Do you know if you're un-American?
It's just like that game in the movie "Princess Bride", where a man reasons that to poison your drinking partner, you put the poison into your own glass. If he is suspicious he will switch with you when your back is turned, and will bring about his own doom. However, if he is a step cleverer than that, it becomes impossible to outsmart him - as the reverse-reverse psychologies pile up, the game boils down to random chance. Of course, the hero in the movie knew this and poisoned both glasses. After his opponent got thorougly lost in a maze of pseudo-logic, he took his poison and that was that.
That's the kind of visual image I get of someone trying to write a program that would win this contest - the "inconceivable!" guy from princess bride.
I wonder how a simple markov chain would do. That's where the probability of every move is based on the outcome of the previous game. For instance, "2 of the 3 times his rock beat my paper, his next move was scissors, so since his rock just beat my paper again, I'll anticipate scissors this time and go rock." I think this kind of reasoning would beat your typical human roshambo player in the long run, since a human would typically have a certain response based on what just happened.
Obviously, it's different with a computer. The program might anticipate this kind of thing, and has no general "feeling" that would you any reason to link a round to the one that came before. The more I think about this, the more I think it's just a matter of guessing right what other people will do.
--
grappler
Vidi, Vici, Veni
Hey, it could be fun. make a quake bot that aims for the crotch, and dodges crotch shots. now that would be great for the AI people. Wait, that would be a great mod. Someone make NutShot Quake.
"My head hurts, My feet stink, and I dont love Jesus." -Jimmy Buffett
Homer's brain: Rock. Nothing beats rock. Go rock!
Homer: ROCK!
Bart: Paper
Homer: DOH!
It's 10 PM. Do you know if you're un-American?
Bull. If enough people submit programs that use the 'random strategy', then one of them will win by sheer chance. If you've got thousands of Roshambots choosing at random, then the sequences of a few of them are going to coincidentally look a lot like the winning strategy of the smartest 'bots. It's the infinite-monkeys-on-typewriters problem, just simplified.
Stay up hacking each weekend. Sleep is for the week.
int roshambot(void) /* Good ol' rock. Nothing beats rock. */
{
return 0;
}
Stay up hacking each weekend. Sleep is for the week.
A smart program will use all kinds of techniques to figure out its opponent's prediction algorithm. I would imagine that such a program would start out with some carefully planned tricks to get the other program to reveal itself.
Of course, I don't know for sure, since I have not tried it. But, if you look at the results from the last tournament, you see that one program, called "Iocaine Powder", won every single round my a significant margine. The second-place program was based on an earlier version of Iocaine Powder, and was as far ahead of third place as it was behind first. Clearly, this is more complex than it sounds. :) Perfect name for the winner, too.
------
I have to admit, I was wondering about the name RoShamBo until I got to this:
* Q: RoShamBo? I thought that was the game where you and Cartman take turns kicking each other in the nuts as hard as
you can.
A: No, that's Roshambeau. Notice that alternating turns (rather than playing simultaneously) affects the strategy.
Going first tends to be somewhat advantageous in Roshambeau.
I notice that they limit you to a millisecond per turn. Is Iocaine Powder fast enough for that? I wouldn't have thought that any fairly sophisticated prediction system would be fast enough. I suppose, though, that a millisecond does give you a few hundred thousand cycles, but given a history of several hundred turns, that isn't a lot of cycles to spend per turn in the history.
Comment removed based on user account deletion
http://studio.tellme.c om/home/documentation/example-111.html
It's a company that produces a "VXML" platform that let's you program a phone voice system. Sample code #111 is a rock-paper-scissors game. Basically, you call up and play against a whiny, simulated kid voice. You can even "say" your commands...
In order to view the source, etc. you need to get a free login of their "developer studio" - but if you don't want to do that, here's how to play:
Enjoy!
Can your IM do this?
it wins
Trees can't go dancing
So do them a big favor
Pretend dancing stinks!
You've got a thousand moves. You could always spend the first few on a dumb pattern, hope the other player falls for it, and especially if the other player doesn't adapt strategy after its first decision -- then change strategy.
--
Infuriate left and right
Q: Can I enter Random (Optimal)?
A: No. You shouldn't want to anyway, because it is guaranteed to finish in the middle of the pack. It definitely will not finish in first place, because it cannot exploit the weaker programs.
This is a self-fulfilling prophecy isn't it? The more people believe the above statement, the more there is to gain or lose from a non (uniform) random strategy.
Having such a limited background in math, it's just this sort of walkthrough that hosers like myself need. The kicker, as is always the case, is that it's so fucking simple once you see what is being implemented and how successful it is.
Thanks for the information, egnor!
---
icq:2057699
seumas.com
A while back, a couple of math-geek friends came up with a variation of the traditional roshambo rules. I don't know if this new game got a name, but here's how it went.
Two new items are added: the angel (forming a circle with your thumb and another finger) and Satan (forming devil horns with your forefinger and pinky). Every item loses to two others, beats two others, and ties with itself. The traditional rock-scissors-paper patterns hold, so here are the new combos:
Angel loses to Paper (nasty paper cuts) and Scissors (clipped wings)
Angel beats Satan (because good always triumphs over evil) and Rock (because Angel can fly away from a rock-thrower)
Satan loses to Angel and to Rock (because Satan's malice gets turned against him)
Satan beats Paper (because it burns in Hell) and Scissors (I forget why, exactly, but it needs to be symmetric)
It was fun, but too hard to keep track of all the rules, so it was quickly discarded. (I might point out that other members of the same group staged a roshambo tournament, in which one player actually did quite well using the pi bot and the rockbot (Good ole rock. Nuthin' beats rock.) strategies.
I wonder: Would the extra items cause the roshambo writers to reevaluate their strategies? Would five items only make decision-making longer, or would it actually cause strategic differences?
--keith
A few people have told me they had some ideas that might beat The Matrix. I guess I should have had it score 1001 out of 1000, just to drive the point home. :)
char*p="char*p=%c%s%c;main(){printf(p,34,p,34);}"
Rock? Scissors? Paper? cf. Corewars, the original...
http://www.koth.org/
Advice: on VPS providers
Rock - bashes scissors, is covered by paper.
Paper - is cut by scissors, covers paper
Scissors - cuts paper, is smashed by rock
Contrary to popular belief, there is no "Nuclear Bomb" which destroys everything. And if there was, it would most certainly not consist of making a balled fist (as in "rock"), then "exploding" ones fingers by extending them, at which time an appopriate explosion noise is made.
There are three variables: Rock, Paper, Scissors.
Without considering the other person's moves, the initial best method of what to choose on each turn is obviously a completely random choice. Anything predictable will, of course, be predicted .
While you're playing your random moves, you could cache and analyze your opponent's plays and then alter your methods of attack based on that.
However, since he's probably going to be smart enough not to start with obvious attacks, he'll probably choose randomly, too -- and perhaps analyze your moves, which will wisely be random.
So it would seem analysis is useless -- because both players would do best to choose random, non-predictable plays. And since you can only predict random choices (with three variables) a third of the time, you'd likely maintain a close average.
Perhaps a decent strategy would be to choose obviously repetitive moves at first, so that the other player can analyze them and then begin to attack -- but by the time he starts attacking your repetitions, you switch to completely random choices (again, the wise move). But he'd likely do the same, and you're both averaging the same wins again.
Is it just me or does this seem like futile ThermoNuclear Global War, where the only way to win is to abstain from the game?
Of course, I'm not a mathematician and I'm a pretty lousy philosopher, so perhaps I'm way off here and it's more complex than I'm thinking. But anything other than random plays will be detected by a less-than-intelligent program and thoroughly exploited. And if everyone is completely random, statistics reign and come out the only 'winners'.
Hope I'm wrong, because on the face of it, this sounds cool. Just seems like the wrong choice of 'subject' for the competition.
---
icq:2057699
seumas.com
In a real tournament, you don't factor in just how badly you kick the asses of the worst players. This makes it a silly game of "guess who's playing". 2nd order roshambo: as silly as 1st order roshambo, and as painful as roshambeau.
For example, say there is one program that always uses rock (GOR), one with a sophisticated adaptive mechanism (IP), and 10,000 that always use scissors.
IP does very well, against these trivial opponents: on average missing the first 1, then recognising the pattern and getting every one after that.
GOR, however, wins every match, except against IP, against whom it loses every match after the first one (which is a toss-up).
At 1000 points per match, this gives GOR a score of 10 million and IP a score of around 9 thousand less than GOR. GOR wins over IP, despite the fact that IP beat every opponent GOR did, and beat GOR to boot.
It's all about the opponents. Remember that they're fluffing it up with enough ultra-stupid dummies that you don't have a hope in hell unless you beat these dummies soundly. Without the dummies, and in a real elimination tournament, a random-bot would have a fair crack at it, and there wouldn't be any point to it.
Of course, random(optimal) could still win, just as a monkey at a typewriter could recreate the complete works of Shakespeare, but it would take countless billions of tries for one to beat this system; there aren't enough people with computers to beat it that way. Of course, since the bots are the environment, if several dozen random bots were to enter for every non-random bot (including dummies), they would wash out the results in random noise (for every dummy you beat by 600 points, you'd face 50 random-bots that would randomly change your score up or down by, say, around 100 points), and all programs would be about equally likely to win (so a random-bot would probably take home the prize).
They have to restrict random-bots or strategy could become irrelevant and it would be 1st order silly, instead of 2nd order silly 8P
(and it is 2nd order silly; the basic way to win is simple to state, if complicated to implement: beat the trivial stupids, beat what you made to beat the trivial stupids, then beat what you have now, but the more levels of trickery you detect and beat, the more guesses you waste screwing around figuring out your opponent's strategy and the smaller the margin of victory, so you have to prioritize what level of trickery to try first, ending in the same sort of random guess that characterizes roshambo, except that you've spent a lot more effort...)
After a while of getting dynamited to hell, Mandy starts using dynamite. The small child in question then uses scissors, because sissors can cut the fuse.
Moral #1 of the story: Don't play with children.
Moral #2 of the story: As I said above, consistently beat small children <laugh>
Several cheater bots were entered in the last tournament. They were disqualified, of course, but here are the funniest ones:
For more info, see this page (near the bottom).
------
... is at http://www.worldrps.com
--
I suppose then the moderaters would over-use it because they don't seem to read the links either...
The catch is that they put in some deliberately dumb robots, so that if you just use the optimal mixed strategy (randomness), you've got a 50% chance of beating them, but you can clobber them if you've got an actual plan.
In their FAQ, they tell you not to submit the random strategy, because it'll be guaranteed to finish in the middle of the pack.
--
No more e-mail address game - see my user info. Time for revenge.
Win dain a lotica, en vai tu ri silota
It seems to me that since they've also told you that random() is to be used, someone very clever could try to predict the opponent's choices based on sequence random() is returning. You aren't allowed to reseed it of course, but if your code is getting a certain sequence of numbers, is it possible to write code to figure out the current seed, and thus the entire sequence of numbers? Based on where your code winds up picking up the sequence, you know how many random numbers the opponent generated each round. Using that, you can possibly draw a correlation between the numbers you know he's getting and the choices he makes.
Granted, this is a longshot, and I know I'm not that clever, but on the other hand, there are lots of random number generators out there free for the taking. I'd spend the few minutes to add one to my code just to guarantee an attack like this won't work.
Who can anticipate the greatest number of lousy implementations that will show up?
You really have to hard-code recognition of the basic categories, since you aren't allowed to take the time to do a thorough analysis.
So, forget clever coding. It's grinding through all the bad ideas that will win this one.
In case anyone is curious, the original game I wrote (five years ago) is here. Unfortunately, the game hasn't been modified since then either, so it's a bit outdated compared to, say, Quake III.
A choice of masters is not freedom
So, at one point, I knew this woman who thought rock, paper, scissors was sorta fun, and every so often, she'd insist on playing it. Her boyfriend got sick of this, and he would just point a single finger and say "Gun. Gun beats everything." So, once, she was playing me, and I was winning, and she tried this.
The next round, I did a sprawling-hand-spider. She said "gun." I said "space alien. Space alien is immune to gun", and I won the round.
Eventually, we also added dynamite and little bunny foo-foo, and rules for interactions between all the things. Everything beat three things, and lost to three things, so it was still balanced.
I don't remember all of the interactions, but the ones I do remember are funny.
"Townspeople throw rocks at alien" (rock beats alien)
"Little bunny foo-foo picks up alien and smacks it on the head". (lbff beats alien.)
The game has room for infinite complexity if your meal hasn't arrived yet.
My blog: http://www.seebs.net/log/ --- My iPhone/iPad app: http://www.seebs.net/seebsfrac/
Exactly.
Imagine how embarrassing that would be!
Stay up hacking each weekend. Sleep is for the week.