## The Results Are In!Part 1Part 2

last updated: September 16, 1999.

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 become quite complicated when playing against fallible opponents (such as humans:).

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 paper covers rock, scissors cuts paper, or rock crushes scissors. 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 weaknesses 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 that player may be attempting to trap its opponent by anticipating the 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.

This competition is modeled on the "Prisoner's Dilemma" tournaments held by Axelrod in the early 1980s. An excellent account of those events can be found in Douglas Hofstadter's Scientific American articles, which are reprinted in his book "Metamagical Themas".

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. A sample program for conducting RoShamBo tournaments is given below (this may not be the exact version used in the official competition, but the protocol for computer players will be the same).

Please note that the computer players used in the sample program will not be playing in the official competition (except Random (Optimal)). The identifiable characteristics of the intentionally weak programs in the actual tournament will be more subtle, and may change over time.

Rules of the First International RoShamBo Programming Competition:

1. All programs must be written in standard C, using common libraries. All code must compile cleanly, using "gcc -Wall -lm". No attempt will be made to fix programming errors of any kind. Any program that does not function properly on the organizer's machine, for any reason, will be rejected.

2. Each player will be a single 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 some compute-intensive algorithms. (Hint: using static variables may allow you to avoid some unnecessary re-computation). Slower programs will be relegated to a side competition or rejected. Programs may be short, or several hundred lines long (more than that is probably excessive).

4. The length of each match will normally be at least 100 turns, and not more than 10000 turns. The numerical result of each match is used in the overall standings. For example, 30 wins, 40 losses, and 30 ties over 100 turns would net -10 points for that match.

5. Players may access the 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 (maximum of 18 characters), to appear on the tournament crosstable. Suggest a short name for the C function. (*) The names "RoShamBot" and "Deep Rock" have been taken.

2. 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 PLAIN TEXT only: no HTML, no attachments.

• Deadline: Monday, September 27, 1999.

Good luck!

(*) 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

(*) Patti Beadle's Deep Rock was the first program to compete in the RoShamBo World Championship (in Las Vegas, 1997).

Q: Can you tell me what kind of hardware/OS the competition will be run on?

A: That has not yet been decided. It may be a Sun Ultra-5 Workstation running Unix (Solaris), or it could be a fast PC running Linux. If the code compiles cleanly with gcc, it 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 produce my own random numbers, or must I use random and/or 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().

Q: Can I use the defined trials constant to know how many trials will be played (for defining array sizes, for example)?

A: Yup, that's what constants are for. :)

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 simultaneous) affects the strategy. Going first tends to be somewhat advantageous in Roshambeau.

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 (ie. break-even) 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: 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 round-robin format used in the sample program, 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 is "evolutionary", where the lowest finishers are systematically eliminated, until only the strongest of the strong algorithms are playing each other. The winner of this event will be the program that beats all other opponents, even if only by a small margin.

• freqbot2() has been added to demonstrate the use of static variables, to avoid scanning the entire history array each move. Now there is only one update each turn and it is remembered. This technique may be important to you for reducing execution time!

• Note: Some code may not appear in HTML. Use the page source for copying, to be sure you get it all.

-=-=- file: roshambo.c -=-=-

```/*  RoShamBo Tournament Program           Darse Billings,  Sept 1999  */

#include          /* stdio.h */
#include         /* stdlib.h */
#include         /* string.h */
#include           /* math.h */
#include           /* time.h */

#define rock      0
#define paper     1
#define scissors  2

#define players   7          /* number of players in the tournament */
#define tourneys  1          /* number of round-robin tournaments */
#define trials    1000       /* number of turns per match */

#define fw        5          /* field width for printed numbers */
#define verbose1  0          /* print result of each trial */
#define verbose2  0          /* print match histories */
#define verbose3  1          /* print result of each match */

/*  Full History Structure (global variables, accessible to the
current player during each match)

- element 0 is the number of trials played so far
- element i is the action taken on turn i (1 <= i <= trials ) */

int my_history[trials+1], opp_history[trials+1];

/*  Tournament Crosstable Structure  */

#define nameleng  18
typedef struct {
char name[nameleng+1];   /* descriptive name (max 18 chars) */
int(*pname)();           /* function name for computer player */
int result[players+1];   /* list of player's match results */
} Player_Table;

#define maxrandom 2147483648.0   /* 2^31, ratio range is 0 <= r < 1 */

int flip_biased_coin (double prob)
{
/* flip an unfair coin (bit) with given probability of getting a 1 */

if ( (random() / maxrandom) >= prob )
return(0);
else return(1);
}

int biased_roshambo (double prob_rock, double prob_paper)
{
/* roshambo with given probabilities of rock, paper, or scissors */
double throw;

throw = random() / maxrandom;

if ( throw < prob_rock )                   { return(rock); }
else if ( throw < prob_rock + prob_paper ) { return(paper); }
else /* throw >= prob_rock + prob_paper */ { return(scissors); }
}

/*  RoShamBo Player Algorithms  */

int randbot ()
{
/* generate action uniformly at random (optimal strategy) */
return( random() % 3);
}

int rockbot ()
{
/* "Good ole rock.  Nuthin' beats rock." */
return(rock);
}

int r226bot ()
{
/* play 20% rock, 20% paper, 60% scissors */
return( biased_roshambo(0.2, 0.2));
}

int rotatebot ()
{
/* rotate choice each turn */
return( my_history[0] % 3);
}

int copybot ()
{
/* do whatever would have beat the opponent last turn */
return( (opp_history[opp_history[0]] + 1) % 3);
}

int switchbot ()
{
/* never repeat the previous pick */
if ( my_history[my_history[0]] == rock ) {
return( biased_roshambo(0.0, 0.5) ); }
else if ( my_history[my_history[0]] == paper ) {
return( biased_roshambo(0.5, 0.0) ); }
else return( biased_roshambo(0.5, 0.5) );
}

int freqbot ()
{
/* play whatever will beat the opponent's most frequent choice */

int i, rcount, pcount, scount;

rcount = 0;  pcount = 0;  scount = 0;
for (i = 1; i <= opp_history[0]; i++) {
if (opp_history[i] == rock)            { rcount++; }
else if (opp_history[i] == paper)      { pcount++; }
else /* opp_history[i] == scissors */  { scount++; }
}
if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
else if ( pcount > scount ) { return(scissors); }
else { return(rock); }
}

int freqbot2 ()  /* based on code by Don Beal */
{
/* maintain stats with static variables to avoid re-scanning the
history array */

static int rcount, pcount, scount;
int opp_last;

if( opp_history[0] == 0 ) {
rcount = 0;  pcount = 0;  scount = 0;  }
else {
opp_last = opp_history[opp_history[0]];
if ( opp_last == rock)          { rcount++; }
else if ( opp_last == paper)    { pcount++; }
else /* opp_last == scissors */ { scount++; }
}
if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
else if ( pcount > scount ) { return(scissors); }
else { return(rock); }
}
/*  End of RoShamBo Player Algorithms  */

void Init_Player_Table (Player_Table crosstable[players+1])
{
int i, j;

strcpy(crosstable[0].name, "Player Name");

strcpy(crosstable[1].name, "Random (Optimal)");
crosstable[1].pname = randbot;

strcpy(crosstable[2].name, "Good Ole Rock");
crosstable[2].pname = rockbot;

strcpy(crosstable[3].name, "R-P-S 20-20-60");
crosstable[3].pname = r226bot;

strcpy(crosstable[4].name, "Rotate R-P-S");
crosstable[4].pname = rotatebot;

strcpy(crosstable[5].name, "Beat The Last Move");
crosstable[5].pname = copybot;

strcpy(crosstable[6].name, "Always Switchin'");
crosstable[6].pname = switchbot;

strcpy(crosstable[7].name, "Beat Frequent Pick");
crosstable[7].pname = freqbot;

for (i = 0; i <= players; i++) {
for (j = 0; j <= players; j++) {
crosstable[i].result[j] = 0;
}
}
}

int Play_Match ( int(*player1)(), int(*player2)() )
{
/* play a match between two RoShamBo players */

int i, j, p1, p2, p1total, p2total, ties;
int p1hist[trials+1], p2hist[trials+1];

p1total = 0; p2total = 0; ties = 0;

for (i = 0; i <= trials; i++) {
p1hist[i] = 0; p2hist[i] = 0;
my_history[i] = 0; opp_history[i] = 0;
}

for (i = 1; i <= trials; i++) {

/* provide copies of history arrays for each player */
memcpy(my_history, p1hist, sizeof(int)*(trials+1));
memcpy(opp_history, p2hist, sizeof(int)*(trials+1));

p1 = player1 ();              /* get player1 action */
if ( (p1 < 0) || (p1 > 2) ) {
printf("Error: return value out of range.\n");
p1 = (p1 % 3 + 3) % 3;    /* note: -5 % 3 = -2, not 1 */
}

memcpy(opp_history, p1hist, sizeof(int)*(trials+1));
memcpy(my_history, p2hist, sizeof(int)*(trials+1));

p2 = player2 ();             /* get player2 action */
if ( (p2 < 0) || (p2 > 2) ) {
printf("Error: return value out of range.\n");
p2 = (p2 % 3 + 3) % 3;
}

p1hist[0]++; p1hist[p1hist[0]] = p1;
p2hist[0]++; p2hist[p2hist[0]] = p2;

if (verbose1) { printf(" p1 = %d, p2 = %d", p1, p2); }
if (p1 == p2) {
ties++;
if (verbose1) { printf(" tie!\n"); } }
else if ( (p1-p2 == 1) || (p1-p2 == -2) ) {
p1total++;
if (verbose1) { printf(" p1 wins!\n"); } }
else if ( (p2-p1 == 1) || (p2-p1 == -2) ) {
p2total++;
if (verbose1) { printf(" p2 wins!\n"); } }
else printf("Error: should not be reached.\n");
}
if (verbose2) {
printf(" Full history of p1 (%d trials):\n", p1hist[0]);
for (j = 1; j <= trials; j++) {
printf(" %d", p1hist[j]); }
printf("\n");
printf(" Full history of p2 (%d trials):\n", p1hist[0]);
for (j = 1; j <= trials; j++) {
printf(" %d", p2hist[j]); }
printf("\n");
}
if (verbose3) {
printf(" Match: %*d (%*d+ %*d- %*d=)\n", fw, p1total-p2total,
fw-1, p1total, fw-1, p2total, fw-1, ties);
}

return (p1total - p2total);
}

void Print_T_Results (Player_Table crosstable[players+1])
{
int i, j;

printf("\n Tournament results: \n\n");
printf("    ");
printf("%-*s ", nameleng, crosstable[0].name);
for (j = 1; j <= players; j++) {
printf(" %*d", fw, j);
}
printf("  total\n\n");
for (i = 1; i <= players; i++) {
printf(" %2d ", i);
printf("%-*s ", nameleng, crosstable[i].name);
for (j = 1; j <= players; j++) {
printf(" %*d", fw, crosstable[i].result[j]);
}
printf(" %*d \n", fw+1, crosstable[i].result[0]);
}
printf("\n");
}

void Print_Sorted_Results (Player_Table crosstable[players+1])
{
int i, j, max, swap;
char nameswap[nameleng+1];

Player_Table sorted[players+1];

for (i = 0; i <= players; i++) {
strcpy(sorted[i].name, crosstable[i].name);
for (j = 0; j <= players; j++) {
sorted[i].result[j] = crosstable[i].result[j];
}
}

for (i = 1; i <= players; i++) {
max = i;
for (j = i; j <= players; j++) {
if ( (sorted[j].result[0] > sorted[max].result[0]) ) {
max = j;
}
}
strcpy(nameswap, sorted[i].name);
strcpy(sorted[i].name, sorted[max].name);
strcpy(sorted[max].name, nameswap);
for (j = 0; j <= players; j++) {
swap = sorted[i].result[j];
sorted[i].result[j] = sorted[max].result[j];
sorted[max].result[j] = swap;
}
for (j = 1; j <= players; j++) {
swap = sorted[j].result[i];
sorted[j].result[i] = sorted[j].result[max];
sorted[j].result[max] = swap;
}
}
Print_T_Results (sorted);
}

void Play_Tournament (Player_Table crosstable[players+1])
{
int i, j, score;

for (i = 1; i <= players; i++) {
for (j = i+1; j <= players; j++) {
if (verbose3) { printf(" %-*s vs %-*s ", nameleng,
crosstable[i].name, nameleng, crosstable[j].name); }
score = Play_Match (crosstable[i].pname, crosstable[j].pname);
crosstable[i].result[j] += score;
crosstable[j].result[i] -= score;
}
}

for (i = 1; i <= players; i++) {
crosstable[i].result[0] = 0;
for (j = 1; j <= players; j++) {
crosstable[i].result[0] += crosstable[i].result[j];
}
}
if (verbose2) { Print_T_Results (crosstable); }
}

int main() {

int i;
Player_Table crosstable[players+1];

/* fixed or variable seed to the random() function */
/* srandom(0); */
srandom(time(0));

Init_Player_Table (crosstable);

printf(" Playing %d tournaments with %d trials per match...\n\n",
tourneys, trials);

for (i = 1; i <= tourneys; i++) {
Play_Tournament (crosstable);
}
Print_Sorted_Results (crosstable);
return(0);
}
```