# RoShamBo Programming Competition

This topic is 4644 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
Quote:
 Original post by ExtrariusFor those that don't know, RoShamBo is essentially a game where on each turn two players select a move which is in this case represented by the number 0, 1, or 2. If both players select the same number, it is a tie and 0 points are awarded. Otherwise, a selection of 1 wins versus a selection of 0, a selection of 2 wins versus a selection of 1, and a selection of 0 wins versus a selection of 0. The winning player scores one point, and the losing player scores minus one point. After several throws, the person with the highest score wins.

I assume you mean that 0 wins versus 2.

Sounds fun. Spring Break just started, so maybe I'll participate. No promises.

*edit: At the very least, if anybody who does play doesnt have access to VS, I'm willing to help verify that the code compiles properly. Obviously you'll just have to trust that I won't cheat.

CM

##### Share on other sites
Quote:
 Original post by Conner McCloud[...]I assume you mean that 0 wins versus 2.Sounds fun. Spring Break just started, so maybe I'll participate. No promises.CM
Indeed. You'd think being too tired to program would be a hint to me that I'm too tired to post such a long post error free, but apparently not =-) Fixed

##### Share on other sites
How is it possible to devise a strategy? There doesn't appear to be one. This would essentially select the winner of the competition by an elaborate prize draw.

##### Share on other sites
Quote:
 Original post by furby100How is it possible to devise a strategy? There doesn't appear to be one. This would essentially select the winner of the competition by an elaborate prize draw.

You play a lot of rounds against a specific opponent, and the challenge is to learn its strategy. Initially, you are probably right. But after a few rounds a good bot should pull ahead.

Thinking about it, this may take me more than a week to do properly [sad].

CM

##### Share on other sites
Quote:
 Original post by furby100How is it possible to devise a strategy? There doesn't appear to be one. This would essentially select the winner of the competition by an elaborate prize draw.
If every bot played random, introducing one with some kind of strategy wouldn't make any different. The reason stragies are possible is that there will be some bots that don't play random (2 existing sample bots at the very least, and possibly more in the future). If you can find ways to take advantage of their strategies, you can get a greater than 1/3 win chance against those bots which will put you ahead of bots that don't take advantages of weaknesses.

Quote:
 Original post by Conner McCloud[...]Thinking about it, this may take me more than a week to do properly [sad].[...]
Well, there is a lot of source code on the international competition site with comments on the ideas behind it, so you could start by just rehashing what has already been done.
I don't have any deadline in mind, and perhaps it could even be an on ongoing 'competition' where there is just a webpage that ranks submissions that is updated every few weeks if new entries come up. I haven't really decided on the exact format I'd like to persue for the competition.

##### Share on other sites
I uploaded a new version of the framework. Changes include:
Bots no longer fight themselves or matches that have been fought with opposite sides.
The random number generate has become a class so it doesn't matter which bot's code is called first since they modify only their own generators now instead of the global one.
New sample bots added with more comments for each bot and a possible difficulty analysis on beating each one.

The link is the same: Extrarius's RoShamBo Competition Framework.

[Edited by - Extrarius on March 17, 2005 3:46:46 PM]

##### Share on other sites
That is awsome. A great idea.

I think having an ongoing tournament on some webiste is a great idea, as there is no time restrictions and authors can update their bots and such. Maybe all new entries are accepted by Sunday at midnight, the battles take place Monday, and that leaves the rest of the week to update code. Just an idea :)

But if it is going to be ongoing, definently count me in!

##### Share on other sites
damn, what a fun idea, im glad i thought of it :-D
er, seriously, thanks for taking my insane interest in the problem one step further and attempting to set this up. an ongoing tournament? has that been done before? count me in.

##### Share on other sites

Oh, and for the prizes, I'll donate an entry in my journal to the winner to explain their winning strategy...

##### Share on other sites
But, like the guy above me said, wouldn't your best strategy be to just make it completely random? I mean, I am a sucky programmer, but if I can just make a random robot and have an even chance of winning, what is going to stop me from killing off the toughest bot on the first round by unpredictable dumb luck?

##### Share on other sites
Well, a good bot would realize that your bot is completely random. So the good bot can then just output the exact same result every time, hence winning 66% of the time and beating the other bot.

##### Share on other sites
Quote:
 Original post by NietsnieSo the good bot can then just output the exact same result every time, hence winning 66% of the time and beating the other bot.

Its still a zero-sum game - even if one player is random, as long as the players choice is unknown, the odds will be fair, observe:

__| 1 | 2 | 3 |
1 |+0 |-2 |+2 | 0
2 |+2 |+0 |-2 | 0
3 |-2 |+2 |+0 | 0

____0___0___0

There is no saddle point, and the expected value of the game is 0. Assuming the player picks a random choice, and you always pick the same choice, the expected outcome is still 0.

You win by figuring out WHAT your opponent is going to choose, then choose the one that will make you win .
*hint: regressions, ANNs

EDIT: <TT> tags being a bitch

##### Share on other sites
Hmm... guess your right... I suck at probabilities/odds :)

Anyways, I think the points is you sumbit something that does more than output random numbers, because (as Mushu showed) it will finish around the middle of the pack.

##### Share on other sites
just playing around, trying to get an implementation of henny working (btw: it isnt so good except against rockbot) and nticed that you may want to add a cleanup function to the base bot, so that any dynamic memory can be freed. you can do it in the destructor, but its less elegant, imo.

##### Share on other sites
Bot->KickInNuts(Bot2, 50);
Bot2->KickInNuts(Bot, INT_MAX);

?

##### Share on other sites
To fix some warnings (I didn't even need -Wall to get these):

- "Reset()" should have a return type (I assume void)
- THROWS_PER_ROUND should have a type (I assume int)

Took me a while to get my first entry working properly (it seemed to work except it segfaulted at the end of the program run, some of the time - turns out I was calculating some bogus array indices because of putting the wrong variable somewhere ^^; ) but I have it done now. It beats all the easily beaten samples consistently, and is near a draw against the ones that aren't.

##### Share on other sites
If two bots both try and win by figuring out the opponent's stragegy, their own strategies will be modified... it sounds like you'd have to have a lot of rounds.
I still can't see that anything could beat a random-bot so why would you write anything else.
I'd say this is a weak contest compared to GDArena (what happened to that by the way - still going?)

Just my 2c though.

##### Share on other sites
http://www.cs.ualberta.ca/~darse/rsb-results1.html
Quote:
 Myth: Random (Optimal) can't be beat. The optimal strategy won't lose a match by a statistically significant margin, but it also won't win a match, regardless of how predictable the opponent is. Try winning a chess tournament by drawing every game! Moreover, the statement isn't even true in a more fundamental sense. Opportunistic strategies can be theoretically better, having positive expectation under more realistic assumptions. People interested in advanced game theory may enjoy the recent book "The Theory of Learning in Games" by Fudenberg and Levine.

##### Share on other sites
I've guaranteed there will be some bots that are not random (the sample bots) that can be beaten with a strategy. Thus, your bot can score better overall by taking advantage of those 'weak' bots. You might not be able to do well against RandomBot, but you don't really have to because there are many other bots to beat for good points. Perhaps I should also make a sample bot that does a very simple pattern analysis to take advantage of the bots so you HAVE to take advantage of something (or get lucky) to place above all the sample bots.

I plan on having at least 10000 rounds (as is currently in the framework), so you have quite a bit of time to adapt (ten times as much as in the international competition linked to in the OP). The number may be modified based on the speed of the bots (no more than 5 milliseconds per turn on average on my Athlon 2400+ w/ 640 MB PC2100 running Win XP Pro, but if all submissions take 5 milliseconds it might be a long while - an overnight run doesn't bother me tho)

N8dunn: Use the destructor. Adding a special cleanup function seems messy when there is already a standard way to do exactly that.

Zahlman: Fixed - Extrarius's RoShamBo Competition Framework v1.0.2. I set VS warings on highest as I should have done originally, and the only warnings I get are that the parameter isn't used in RegisterResult for some bots. If you'd like to do a -Wall compile and PM the warnings, I'd appreciate it. As I said, I'd like this to be platform independant aside from the few assumptions that are made for convenience.

I'm going on a small trip over the weekend, so I won't be here to make updates too long after this one until I get back late sunday.

As far as a deadline for the first matchup, how about all bots must be in before April 10th, 2005 1:00 AM Central Standard Time. EMail all entries to the address in the source (which has changed since the last version). You may make multiple unrelated entries, but if it is found that your bots cooperate, any or all of your submissions may be disqualified and future participation may be prohibited. If you send your bot and then decide you'd prefer a different version be used in the competition, send the different version before the deadline with text saying so.

I quite like the idea of an ongoing competition, but for the first few runs I think it probably needs to start off with a deadline to help give time to get a site up and running.

[Edited by - Extrarius on March 18, 2005 3:11:54 AM]

##### Share on other sites
Also, right now, you could beat the random bot perfectly because you can generate the exact same random numbers it does and then just play the better move. When I get back, I'll update the RNG to have some kind of 'reseed' function (maybe an arg to reset) that allows you to have multiple random number generators. It will be a rules requirement that you use a fixed seed so the game will run the same each time (and multiple matches versus the same bot must have exactly the same outcome as long as both bot's "reset" function is called between matches).

##### Share on other sites
GCC complains about a few minor things:

- No newline at the end of any of the files.
- [Rock|Random|Rotator]Bot::RegisterResult(): p_ThrowResult not used for anything.

A Makefile plus the above minor changes to compile it in Linux using GCC. Also the newline characters sequences have been mangled. Hope nobody tries to read it using Notepad.

##### Share on other sites
Well, I spent way more time on this than I should have, but I think it's an improvement.

Includes API reference and snazzy new results output:
+--------------------+--------------------+----------+|Contestant          |Challenger          |     Score|+--------------------+--------------------+----------+|RockBot             |RandomBot           |      -131||RockBot             |AntiRandomBot       |        69||RockBot             |UnityBot            |        62||RockBot             |RotatorBot          |        -1||RockBot             |CrazySpinBot        |         0||RockBot             |CopyBot             |         0||RockBot             |CounterBot          |    -10000||RockBot             |ThirdBot            |         0||RandomBot           |AntiRandomBot       |    -10000||RandomBot           |UnityBot            |     10000||RandomBot           |RotatorBot          |      -110||RandomBot           |CrazySpinBot        |       -59||RandomBot           |CopyBot             |       -52||RandomBot           |CounterBot          |       103||RandomBot           |ThirdBot            |       -49||AntiRandomBot       |UnityBot            |    -10000||AntiRandomBot       |RotatorBot          |        65||AntiRandomBot       |CrazySpinBot        |        67||AntiRandomBot       |CopyBot             |       -51||AntiRandomBot       |CounterBot          |       104||AntiRandomBot       |ThirdBot            |        75||UnityBot            |RotatorBot          |        45||UnityBot            |CrazySpinBot        |        -8||UnityBot            |CopyBot             |       -53||UnityBot            |CounterBot          |       105||UnityBot            |ThirdBot            |        14||RotatorBot          |CrazySpinBot        |      5000||RotatorBot          |CopyBot             |     10000||RotatorBot          |CounterBot          |         0||RotatorBot          |ThirdBot            |     -9999||CrazySpinBot        |CopyBot             |         0||CrazySpinBot        |CounterBot          |        -1||CrazySpinBot        |ThirdBot            |        37||CopyBot             |CounterBot          |     -5000||CopyBot             |ThirdBot            |    -10000||CounterBot          |ThirdBot            |     -3380|+--------------------+--------------------+----------++--------------------+---------------+|Bot                 |    Final Score|+--------------------+---------------+|ThirdBot            |          23302||CounterBot          |          11309||RotatorBot          |           5002||AntiRandomBot       |            191||UnityBot            |             41||RandomBot           |            -36||CrazySpinBot        |          -4964||RockBot             |         -10001||CopyBot             |         -24844|+--------------------+---------------+

It's asciilicious. Also includes AntiRandomBot, which will always win against RandomBot, and UnityBot to keep things fair between Random and AntiRandom.

Oh, and lastly a new random number generator class, based on the Mersenne Twister. The old one is gone. I killed it. *Evil Laugh*

##### Share on other sites
Quote:
 Original post by smart_idiotWell, I spent way more time on this than I should have, but I think it's an improvement.Includes API reference and snazzy new results output:[...]It's asciilicious. Also includes AntiRandomBot, which will always win against RandomBot, and UnityBot to keep things fair between Random and AntiRandom.Oh, and lastly a new random number generator class, based on the Mersenne Twister. The old one is gone. I killed it. *Evil Laugh*
I've been planning on turning the results into CVS format because its easy to plug in to anything (like the HTML results page that will be put up) whereas your format is nice to look at in text mode but takes more work to import into various places. Also, I'll never include MT in the my version because I don't like the license (I was never quite sure I understood the legalese part, and having to put the notice on the website {the only real documentation I was planning} wouldn't be nice). I'd implement my own version from the paper, but it isn't simple and I don't really feel it's worth the time. I was planning on tweaking the random number generator, but I had to leave so hadn't had the time yet.

I think your change to WrapThrow is invalid, because I don't think modding a negative number is guaranteed by the standard to work a certain way, but maybe it just doesn't work the way I expected it to..?

Also, I'm thinking about changing a lot of the interface for much of the program now that I've had some time to consider everything (after getting some sleep). It will probably break bots, but it shouldn't be more than a few lines that need modification.

Thanks for running it through GCC and fixing those warning, and I do like some of the changes you made (new types is a good thing). I'll have to go over your modifications in more detail when I have more time (just got in and I have to be up early tommorow).

[Edited by - Extrarius on March 20, 2005 11:51:51 PM]

##### Share on other sites
From the source code - "Who really cares about time anyway?"
Well, I do, but only because I don't want to dedicate my computer to judging for the next 10 years =-)

I chose 5ms because 10000(num trials per matchup) * 0.005sec (max length of one throw decision) * 2 (num opponents) = ~1.7 minutes per match
That seemed like a reasonable limit, especially with some changes I'm making in the match format (10 rounds of 10k throws with a different inital random seed for each of the 10 rounds).

I probably shouldn't have bothered with a date until I had finalized the foundation, but at the time I was really tired and these changes shouldn't make much difference to strategy or code except that you won't be able to always beat random any more. If anybody is actually working on this and feels the date should be changed after I decide to 'freeze' everything for this iteration, I'll probably change it.

##### Share on other sites

This topic is 4644 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628642
• Total Posts
2983993

• 9
• 10
• 21
• 20
• 13