Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Edit: Official Competition Website: here In the thread on Rock Paper Scissors, a person linked to The International RoShamBo Programming Competition, which I thought sounded like a really nice competition because the game itself is very simple but the possible strategies in a programmed version are numerous and range from the impressively simple to the astoundingly complex. I was saddened to see that the page had last been updated in 2001, and the last competition was in 2000. How about we have our own competition here on gamedev? I've already created a simplified C++ framework, which you can download here. The files are: roshambo.h - includes the definition of some helper functions and the abstract bot class randgen.h/cpp - a random number generator to help standardize the framework across platforms sampbots.h - 3 sample bot implementations that are very simple main.cpp - the actual tournament code It's still very simple right now. I plan to add timing around each NextThrow call because timing will be a rule (can't have the competition last years =-). I also plan to do some further fixups later, but I've been up to long so I don't want to touch it anymore right now. The idea is that you create a concrete child class of RoShamBo::Bot using standard C++, with the RandGen:: functions for random numbers (no rand/random calls please) and it will have to compete against all other entries. The bot should be self-contained, exposing no symbols outside it's class' namespace so that it can easily be plugged in without worrying about name conflicts. Naming the file and class the same thing would probably be a good idea as well. For 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 2. The winning player scores one point, and the losing player scores minus one point. After several throws, the person with the highest score wins. As far as contest rules: No entries larger than 30720 8-bit bytes (30KB) total and no more than 3000 lines total in the source code. Comments are required to explain at LEAST the basic strategy of the bot. The code must be licensed in such a way that I can freely distribute it. No calling ResetRandom or otherwise interfering with other bot's functionality. Reading/writing from files and other 'system access' is strongly discouraged, and may be a cause for disqualification. The bot's behavior must be deterministic so that multiple executions of the tournament program will result in the same outcomes if the same random seed is used (and it always is in the current setup). The code should compile with Visual Studio .Net 2003 and run in a windows console program. The bot can take no longer than an average of 5 milliseconds to process one entire turn (a single call to RegisterResult and a single call to NextThrow) such that a call to 'DoThrow' should, on average, take no more than 10 milliseconds. I reserve the right to modify the rules whenever and however I choose to do so. I'd like to have the code purely standard C++ (with a few assumptions like a 32-bit integer for sake of convenience, and that multiplication overflow causes no problems). If you notice anything not at all standard or portable, please help me make the corrections so everybody can see the bots in action =-) What is there to win? Well, nothing unless somebody wants to sponsor us and donate something. For now, its for fun and the challenge only. [Edited by - Extrarius on March 25, 2005 6:59:42 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
For 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by furby100
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.

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 this post


Link to post
Share on other sites
Quote:
Original post by furby100
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.
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Nietsnie
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.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
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:[...]
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 this post


Link to post
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 this post


Link to post
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.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this