CSC 209H: Assignment 3

Weight: 10% of course grade.

Due date: 10:00 p.m. Thursday November 17 Saturday November 19, 2005.

Introduction

In this assignment, you will be writing programs that will play the age-old game of Roshambo, otherwise known as rock, paper, scissors or by a number of other names. Typically the game is played between human beings as an easy way to determine who sits in the front seat, who gets the big piece of pie, or who plays with the toys first.

The game itself is very simple. Two players make a fist with one hand, and count together "Ro... Sham... Bo!" or "One... Two... Three!" while bouncing their fist. On "Three", they simultaneously change their fist into one of three shapes: a rock (a fist), a piece of paper (an open hand), or a pair of scissors (two fingers making a V). Paper beats rock, scissors beats paper, and rock beats scissors. If both players choose the same shape, it's a tie, and they repeat.

The optimal strategy is to choose a shape at random, which wins 33% of the time and ties 33%. But humans are bad at randomness, so the secret to winning is to try to guess what shape your opponent will throw, and yourself throw the shape that wins. Do this well, and you'll win much more often than using the optimal strategy.

Roshambo is probably bigger than you thought. Every year since 2002, Toronto has been host to the WRPS International World Championship, where the winner receives a large cash prize. This event is even broadcast internationally on television. There is also an annual computer Roshambo competition, where programs compete, trying exploit each other's weaknesses.

Our goal here will be to write some simple Roshambo-playing programs, and write a program that will run and judge a Roshambo tournament.

Part 1 - Rock-Paper-Scissors players

In this part you are asked to write at least two different C programs that will play a series of rock, paper, scissors games.

Your programs will be named rps1, rps2, and so on. You may write and submit as many programs as you wish. You will also submit a README text file briefly describing how each of your programs work. Be sure to point out any interesting strategies you might be using!

For the purposes of this assignment, we will use the following representations for the possible throws:

• 0 means rock (it's round just like a stone)
• 1 means paper (it looks like a sheet of paper from the side)
• 2 means scissors (it's a "pair of scissors," and pair means two)

Your program will iteratively execute the following phases:

• waiting: waiting for the line "GO" to be read from stdin
• throwing: choosing a shape and printing one line with the decision to stdout
• decision: waiting for a line containing the other player's decision to be read from stdin, thereby learning whether it won, lost or tied

When EOF is encountered on stdin instead of "GO", your program should terminate normally.

Each program may assume it is playing a series of games against a single opponent. A particularly clever program may use past results to try to increase its odds of winning (for example, if its opponent always throws rock, your program might decide to always throw paper).

Warning: you will not be evaluated on how clever your program is, only that it follows the specification! Do not spend so much time on your players so that you do not complete the rest of the assignment!

Tip: To aid in debugging (particularly for part 2), you might want to send diagnostic or status information to standard error. Be sure to turn off this diagnostic output before handing in your assignment.

Examples

The following may be an execution of such a program.

stdin	stdout
GO	2
2		
GO	0
1		
GO	2
1		

When in debugging or diagnostic mode, your program might follow an execution like this.

stdin	stdout	stderr
GO	2
2		Tie
GO	0
1		Lose
GO	2
1		Win

Hints and Clarifications

• This should be an easy exercise. Don't spend too much time on this part, until you've completed part 2.
• Though it might seem strange that your program is printing its throw before learning its opponent's throw, note that we'll be playing against other programs instead of humans. This also makes sure your program isn't cheating.
• You will want to make sure that two programs (or two processes running the same program, particularly if started at the same time) will produce a different sequence of throws. You might want to use the random() function.
• Typically, pseudo-random number generators are seeded with a unique integer, such as the current time(). But, in this assignment we might start two processes at the same time, so we'll need a better seed. The process id is guaranteed to be unique. You may also read from /dev/random.
• You might want to prefix your diagnostic output with your process id (the getpid() function), particularly while doing the second part of this assignment.
• To ensure your output to stdout is being written immediately, you might want to use the fflush() function following a print call.

Part 2 - Roshambo umpire

In this part you will write a C program named roshambo that will act as the umpire in a Roshambo tournament. The competitors will be executions of your rps* programs.

Your program should support being run in the following manner:

$ roshambo [-r rounds_per_match] list-of-competitors

Following the -r option (if it exists) is an integer N, the number of rounds to be played per match. If -r does not appear, default to N=10.

The list of competitors will be a list of program names of rps programs, possibly (and probably) with duplicates. For example, a list might be rps1 rps2 rps3 rps1 rps1 for a tournament with 5 players. There must be at least 2 competitors specified. Your program must support tournaments of at least 16 competitors.

Your program will do the following:

• Create one child process per competitor. The child process will exec the specified program (once the standard input and standard output are set up appropriately to communicate with the umpire). Competitor names will be a combination of their number and the name of the program (i.e., "player 1 (rps1)").
• Choose two (remaining) competitors and referee a Roshambo match between them. The participants in the match are chosen by the following algorithm. Suppose a is the next highest numbered competitor after those involved in the previous match (a=1 if no matches yet). a's opponent is the next highest numbered competitor after a still in the tournament. (Of course, "next highest numbered competitor" is computed modulo the number of competitors.) For example, in a tournament with 5 players, 1 beats 2, 3 loses to 4, 5 loses to 1, then 4 plays 1.
• In each match, you will play a minimum of N rounds. Report to standard output the throws made in each round. If the two processes are tied after N rounds, play up to N additional sudden death rounds until a winner is decided. If no winner can be decided after 2N rounds (i.e., they always make the same throw), the umpire decides the winner arbitrarily. Report the result of the match to standard output.
• Terminate the losing competitor. The winner moves on to play another match. When only one competitor remains, declare that competitor the winner, and print a message to standard output declaring the winner.

Important: Be sure to clean up any processes that may be left behind before logging out of your machine. The ps and top commands can help you find any lingering processes.

Examples

This is a tournament played between two competitors.

$ ./roshambo -r 10 rps1 rps2
Match 1: player 1 (rps1) versus player 2 (rps2)
Round 1: 1 and 1
Round 2: 2 and 2
Round 3: 2 and 0
Round 4: 2 and 2
Round 5: 2 and 0
Round 6: 1 and 0
Round 7: 2 and 0
Round 8: 1 and 0
Round 9: 1 and 1
Round 10: 1 and 0
Round 11: 1 and 1
Round 12: 2 and 1
Score: 4 to 3 with 5 ties, player 1 (rps1) wins
The tournament winner is player 1 (rps1)

Hints and Clarifications

• Start now! Try to get something very simple working first, then get the pipes set up to communicate with one child process, then continue adding functionality step by step.
• You must use pipes to communicate between processes for this assignment. Do not use sockets or other advanced IPC methods.
• Since pipes are half-duplex (one-way) communication, you will need two pipes to communicate with each child process.
• The rps* programs only know about stdin and stdout. You will need to use dup2() to reassign the file descriptors associated with the pipes. The defined constants STDIN_FILENO and STDOUT_FILENO refer to these file descriptors.
• If you are having trouble reading over the pipe from a child process, the output might be getting buffered by your rps program. The fflush() function will make sure printf output is flushed to the pipe.
• You can throw away the diagnostic output from your children by redirecting stderr (file descriptor 2) to /dev/null under a Bourne shell.
• You should clean up any zombie children processes using one of the wait functions.
• You must check the return values from each library function call and take appropriate action based on these return values (such as printing an error message, exiting with error, or continuing normally).
• For full marks, your roshambo program C code must be well-documented, follow good programming style, and be easily understandable by the marker.

Learning Objectives

• Creating and controlling processes under UNIX (fork, wait, etc.).
• Executing programs using C (exec).
• Basic interprocess communication (pipes) in C.
• Understanding file descriptors in UNIX.

What to hand in

You will commit to the a3 directory of your CSC209 repository the following files:

• Your C source files for rps1, rps2, ....
• Your C source files for roshambo.
• Any additional files needed by your programs (header files, etc.)
• Makefile, containing commands to compile your rps* programs and roshambo simply by running make
• README, briefly describing each of your rps* programs.

You are strongly encouraged to take advantage of the version control system and commit your work frequently so that you can keep track of your progress. Please note that perfectly fine (and even recommended) that you keep any additional files related to this assignment (such as files and scripts used for testing) under version control. The markers will simply ignore such files.