Intro | Rules | Enter | FAQ | Links |

Introduction

last updated: June 25, 2000.     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. 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

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 darse@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: How do I benchmark my submission to ensure it plays in under 1 second? A: If it runs at least as fast as the slowest programs in the test suite (probably Boom or Iocaine Powder), then you should be fine. Q: Can I get more in-depth instructions on testing my program in the test code provided? A: The easiest thing to do is to replace one of the existing programs with your program, and then change the name in the procedure Init_Player_Table(). If you want to add a new player, just add an appropriate block to this roster, and increase the #define players constant. Q: Will in-line assembly be allowed? A: No, the code must be easily readable. ANSI C only. 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, or play the new RoShamBot at Pick'em Sports.

Related Links

The First International RoShamBo Programming Competition (Sept 1999)   Announcement and Rules   Results (Part 1)   (Part 2) the test suite includes almost all of the top programs from the 1999 contest!         (compile with:   gcc rsb-ts1.c -lm  ) the sample program is a smaller version (only "dummy bots" from the previous competition). Check out the World RPS Society, home of an article and a tournament report on the first competition were published in:         The International Computer Games Association (ICGA) Journal (Vol. 23, No. 1, March 2000) an article also appeared in The Mind Sport Olympiad's "Mindzine" Michael Gherrity has computed ratings for all players in the test suite, using the new         Glicko rating system used for chess. (Click on Michael's link for all the gory details). here are some recent results, with strong new programs by Don Beal and Neil Burch.

Intro | Rules | Enter | FAQ | Links |

U of A GAMES group

You are visitor to this page since June, 2000.