The Second International RoShamBo Programming Competition
Darse Billings
The Second International RoShamBo Programming Competition
---------------------------------------------------------
Summary: Write a program to play Rock-Paper-Scissors, and enter it
to play in an open competition against other programs.
Purpose: To have fun, and maybe learn something.
URL: http://www.cs.ualberta.ca/~darse/rsbpc.html
Deadline for entries: Monday, July 10, 2000.
RoShamBo (also known as Rock-Paper-Scissors) is a simple game, but the
best strategy can be quite complicated when playing against fallible
opponents.
The game is played between two players. On each turn, the players
simultaneously choose one of "rock", "paper", or "scissors". If they
choose the same item, the result is a tie; otherwise rock crushes
scissors, paper covers rock, or scissors cuts paper. A match consists
of a series of turns between the two players.
The game is trivial from a game-theoretic point of view. The optimal
mixed strategy is to choose an action uniformly at random (one-third
probability of each). This will ensure a break-even result in the long
run, regardless of how strong (or how weak!) the opponent is.
However, against predictable opponents, a player can attempt to detect
patterns in the opponent's play, and exploit those tendencies with an
appropriate counter-strategy.
The RoShamBo Programming Competition is a tournament between computer
programs that play Rock-Paper-Scissors. Some of the programs in the
tournament will use sub-optimal strategies, and will be vulnerable to
a perceptive and adaptive opponent. Of course, there is always a risk
associated with such a prediction, as the opponent may be attempting
to trap you, by anticipating your reaction to previous plays.
The most successful programs will recognize a variety of patterns and
relationships, and use that information to gain an advantage over each
opponent, without being susceptible to similar attacks.
To enter the competition, participants will write a C procedure to play
Rock-Paper-Scissors, given only the complete history of the match
against the current opponent. The _test suite_ is an example program
for conducting RoShamBo tournaments (this may not be the exact version
used in the official competition, but the protocol for computer players
will be the same). The test suite contains many examples of RoShamBo
players, including almost all of the top contenders from the first
programming competition. A smaller _sample program_ is also available
(this includes only the dummy bots).
Please note that the computer players used in the sample programs will
not be playing in the official competition (except Random (Optimal)).
The exploitable characteristics of the intentionally weak programs in
the actual tournament will be quite subtle, and may change over time.
Rules of the Second International RoShamBo Programming Competition
------------------------------------------------------------------
1. All programs must be written in standard C, using common libraries.
All code must compile cleanly using:
"gcc -Wall -O5 progname.c -lm"
There must be no reported errors and no warnings of any kind. Note
that -O5 optimization does not ensure the initialization of certain
variables, so you must program carefully. No attempt will be made to
fix programming errors. Any program that does not function properly
on the organizer's machine, for any reason, will be rejected.
2. Each player will be a C function with no parameters, returning
a single integer value: 0 = rock, 1 = paper, or 2 = scissors.
3. Computer players must be fast! Each player must be able to finish
a 1000 turn match in one second on the tournament machine. This should
allow several passes through a full history array, but may preclude
certain compute-intensive algorithms. Slower programs will be rejected.
(Hint: using static variables may avoid some unnecessary re-computation).
Please use distinct names in the code, such as prefacing all variables
and procedures with your initials.
Limitations on memory usage may be added later, if necessary (but using
less than 50K should not pose a problem).
There is no limit on program length, but there will be a special side
competition for smaller programs (roughly 40 C statements or less).
Qualification for this category is at the discretion of the organizer,
and will be based on number of lines, keywords, size of the object file,
and other measures.
4. The length of each match will be 1000 turns. The numerical result
of each match will be used in the overall standings. For example, 200
wins, 300 losses, and 500 ties over 1000 turns would net -100 points for
that match. The match result (win, lose, or draw) is also important.
A draw is defined to be a range of outcomes statistically close to the
break-even result (0 points).
5. Players may access full history arrays for the match, as global
variables. These arrays will be called my_history[] and opp_history[].
Players may also use any provided routines, such as flip_biased_coin(),
and biased_roshambo(). Players must not access any memory or procedures
not intended for their use, and must not use srandom() to set the random
number seed. Any attempt to thwart the tournament system in any way, or
any behavior that is not in the spirit of the competition, will result
in disqualification.
6. There is no rule 6.
7. All submissions become public domain. However, appropriate credit
will be given to the original author(s) for any ideas or source code
that are used or published in the future.
8. The decisions of the organizer are final, and supercede all other
rules. No further discussion will be entertained.
To Enter
--------
1. Give your program a name to appear on the tournament crosstable
(maximum of 18 characters). The names of all programs in the first
competition are reserved for their original author.
2. Acknowledge any other programs you may have used as a model. Any
entry deemed to be too similar to an existing program will be rejected
without further consideration.
3. Submit your program by e-mail to da...@cs.ualberta.ca . Please put
"RoShamBo" in the subject. The e-mail must include the source code in
the body of the message, in PLAIN TEXT only: no HTML, no attachments.
If you believe you also qualify for the mini-program competition, please
indicate that in your message.
Deadline: Monday, July 10, 2000.
Good luck!
FAQ (frequently asked questions)
--------------------------------
Q: What kind of hardware and operating system will be used?
A: The competition will be run on a fast PC running Linux. If the code
compiles cleanly with a recent version of gcc, the development platform
shouldn't matter too much.
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.
Q: Are we allowed to have other functions, or must everything be done
in a single function?
A: You may have auxiliary functions, provided they can all be placed
together in the tournament program. There must, of course, be only one
player that is called for each move.
Q: Can I enter more than one program?
A: You may, provided they are completely independent (ie. one does not
lose to the other by a large margin, in order to stack the results).
If I have any doubts, I will take only the last entry, or I will assign
a zero result to that match-up.
Q: Do you want C source that compiles to an object file, or do you
want code you can cut and paste?
A: Cut and paste. You should be able to just plug it into the sample
tournament program.
Q: Can I produce my own random numbers, or must I use random(),
and the provided flip_biased_coin() and biased_roshambo()?
A: You may use your own random number generator, but it must use a fixed
seed, so that the tournament results are reproducible, given a fixed
seed to srandom(). However, there is little to be gained from using
your own RNG.
Q: Do you plan to use the same scoring system for the competition
that your example program has?
A: Yes and no. There will effectively be two divisions, and all
programs will participate in both. In the first format, the magnitude
of each match counts. The winner of this competition will be the
program that is most efficient at detecting and exploiting weaker
programs. The second format will be "evolutionary", based on match
results. This may be the "Best of the Best" format used in the 1999
competition, or may be an entirely new system. Regardless, the winner
of this event will be the program that defeats all other opponents,
even if only by a small margin.
Q: Can I use the "trials" constant to know how many trials will be
played (for defining array sizes, for example)?
A: Yup, that's what constants are for. :) The tournament matches will
be 1000 turns, but other sizes may be tried in certain experiments.
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.
Q: Where can I play RoShamBo on the World Wide Web?
A: You can play Perry Friedman's original RoShamBot at:
http://chappie.stanford.edu/cgi-bin/roshambot
Or play the new RoShamBot at Pick'em Sports:
http://contest1.pickem.com/cgi-bin/roshambo/roshambot.cgi
--
"There's no sense in searching for perfection
when you're making successful mistakes" -The Tragically Hip.
Eric Taylor
In rec.gambling.poker Craig Powers <eni...@hal-pc.org> wrote:
: number of "sample" opponents each of which implements a relatively
: straightforward pattern (some of which are more easily exploited than
: others). An RNG won't lose, but it can't win either because it won't
: beat the weak opponents. The good AIs do just as well as the RNG
: against the difficult opponents but beat it by demolishing the weak
: opponents.
even if the "sample" opponents weren't there, you will still be able to
do better than a random number generator, because there are enough real
program contestants that are entered that perform rather poorly. look
at the results. many of the dumb sample programs don't do that badly
compared to many of the "smart" programs.
all the good programs have a cutoff where if they start to lose too
much to a particular program, they switch over to a random number
generator so they cut their losses.
if roshambo ever becomes solved, then it would certainly make sense
that a random number generator could win the tournament, however, what
then would be the point of the tournament at all? the very fact that
there is a second (not just a first but a second) roshambo tournament
points pretty conclusively to the fact that a random number generator
is not yet the optimal way to play the game.
I don't know if it's just me, but this roshambo tournament at least to
me seems interesting and presents rather deep ideas about games in
general. superficially the game seems very simple.
--- edt
Mallor
"Eric Taylor" <e...@joust.gpcc.itd.umich.edu> wrote in message news:R_id5.2825
> the very fact that
> there is a second (not just a first but a second) roshambo tournament
> points pretty conclusively to the fact that a random number generator
> is not yet the optimal way to play the game.
How can you state that when http://www.cs.ualberta.ca/~darse/rsb-results2.html
says "Random (Optimal)" was tried once, and the heats of the contest have been
structured against randomness? Basically, Random (Optimal) is not being treated
as a control, it's being treated as something uninteresting. It's interesting
*because* it's a control, not whether it wins the competition or not.
--
Cheers, Infernal Troublemaker Troll
Mallor "By simple mistake, mortals themselves amuse."
Dan Mullen
have ever had to download on my computer. Go to rec.gambling.boring!!!
"Mallor" <mal...@3DProgrammer.com> wrote in message
news:ZQod5.4169$in.1...@newsread1.prod.itd.earthlink.net...
Jaeger T. Cat
Dan Mullen <dwmu...@yahoo.com> wrote:
>Is it me, or is this thread the most useless and uninteresting garbage I
>have ever had to download on my computer. Go to rec.gambling.boring!!!
>
Don't like it? Learn to use a killfile.
Dan Mullen
"Jaeger T. Cat" <jae...@pluto.njcc.com> wrote in message
news:8l5610$ocs$1...@pluto.njcc.com...
Jaeger T. Cat
Dan Mullen <dwmu...@yahoo.com> wrote:
>piss off
>
Don't like me? Learn to use a killfile.
Dan Mullen
"Jaeger T. Cat" <jae...@pluto.njcc.com> wrote in message
news:8l5dt2$5ll$1...@pluto.njcc.com...
Martin Moller Pedersen
>instead of a killfile, how bout i just kill YOU instead?
*PLOINK*