COS 217: Introduction to Programming Systems
Assignment 4: A Kalah Referee
The purpose of this assignment is to help you learn about processes and
It will also give you more experience with advanced C programming and the GNU/UNIX programming tools.
This assignment is a follow-on to the previous one. Your task in this assignment is to create
a Kalah referee program that can launch and monitor the execution of two
competing Kalah player programs. More specifically, your job is to create code
which, when combined with portions of your team's Kalah player code from the
previous assignment, implements a Kalah referee
The Kalah Referee Functionality
Your Kalah referee should accept two command line arguments:
- The name of the executable file that contains the MIN player program.
- The name of the executable file that contains the MAX player program.
Your Kalah referee should keep track of the state of the game so it knows whose move
is next, when the game is over, and who won.
Informally, your Kalah referee should use this algorithm:
- Set the "current" player to be the MIN player.
- Read a move from the current player. If the read operation detects EOF,
then the current player must have crashed. In that case, write a
message to stdout indicating that the other player won, and end the game. If
the read operation takes too long (say, longer than 2 minutes), then the current player must not know
that it should write a move. In that case, write a message to stdout
indicating that the other player won, and end the game.
- Write the move to stdout.
- Verify that the move is valid. If it is invalid, write a message to stdout
indicating that the other player won, and end the game.
- Update the game state with the move.
- Write the game state to stdout.
- Write the move to the other player.
- Determine which player is now the current one.
- Repeat steps 2-8 until the game is over, and then...
- Write an indication of who won (MIN or MAX, and the name of the winning
executable file) to stdout. The referee
need not write the final score of the game.
Your Kalah referee should insure that neither player consumes more than 2 minutes of CPU time.
The Kalah Referee Design
Your Kalah referee should call:
- The pipe system call to create pipes through
which it communicates with the players.
- The fork system
call to create processes executing child referees.
- The execvp system call (or one of the other "exec" system
calls) to overlay each
child referee with a player.
- The close and dup (or dup2)
system calls to redirect stdin and stdout of each player so the player writes moves to
the referee through a pipe, and reads moves from the referee through a
- The setrlimit system call to set the CPU limit
for each player. More precisely, before overlaying itself with a player, each
child referee process should call setrlimit to limit the amount of CPU
time that the process may consume to 2 minutes.
- The kill system call to abort the player processes. Specifically,
before the referee exits it should kill its player processes to insure that
they do not become (in UNIX jargon) "orphans."
- The wait system call to wait for the player processes to
exit. Specifically, the referee should wait for its
player processes to exit to insure that they do not become (in UNIX jargon)
- The perror standard C function after a failed system call to print
a message to stderr indicating what went wrong. Your Kalah referee should
check the return value of every system call.
- The signal and alarm standard C functions to determine when
a player is taking too long to write a move.
- (Optionally) The atexit standard C function to simplify processing
immediately before the referee exits.
Your Kalah referee should be game-independent at the source code level. More
specifically, your referee's primary module should be able to play any deterministic two-player game of perfect
information, with no source code changes. It is fine for other modules to be
specific to the game of Kalah if they must be. (Of course, some of those other
modules indeed must be.)
This is not a team assignment; you should create your Kalah referee on your
own. However, you should feel free to use the Kalah player code that
your team created in the previous assignment. You may ask any of your teammates
for Kalah player code; if a teammate asks you for your Kalah player code, you should provide
it. You should only get Kalah player source code from other people after you have submitted your own
Kalah player program for a grade.
You should develop on arizona. Use Emacs to create
source code. Use the "make" tool to build. Use gdb to debug.
that a sample executable Kalah referee program is available in file
/u/cs217/Assignment3/samplereferee. You may
use it to answer questions about the desired functionality of your Kalah referee.
You should submit:
- A complete set of source code files for your Kalah referee. That set should
include your Kalah referee source code file(s), and will probably include some files that were created
by your team for the previous assignment.
- A makefile that uses those source code files to build an executable file
named referee. The first rule
in the makefile should build referee. You should compile using the "-Wall,"
"-ansi," and "-pedantic" options.
- A readme file.
Your readme file should contain:
- Your name.
- A description of whatever help (if any) you received from others while
doing the assignment, and the names of any individuals with whom you
collaborated, as prescribed by the course "Policies" web page.
- (Optionally) An indication of how much time you spent doing the
- (Optionally) Your assessment of the assignment.
- (Optionally) Any information that will help us to grade your work in the
most favorable light. In particular you should describe all known bugs.
If you can reuse some of the Kalah player files from the previous assignment completely unchanged,
so much the better. Please mention in your readme whether that was possible.
Submit your work electronically via the command
/u/cs217/bin/submit 4 sourcecodefiles makefile readme
As always, we will grade your work on functionality and design, and will consider
understandability to be an important aspect of good design. To encourage good coding practices, we will
take off points based on warning messages during compilation.
We will test your work by using your makefile and source code files to build
your referee. We will then use your referee to conduct games between various
players -- some of which play the game properly, some of which violate the rules
of the game, and some of which crash.