This assignment helps you learn about Linux processes, low-level input/output, interprocess communication, signals, and pipes. It also will give you opportunity to take modularity decisions; in that sense the assignment is a capstone for the course.
You may work with a teammate (from your precept) on Assignment 7, if you follow these rules:
Note: There will be a link posted on Piazza by Monday, December 10 that will allow you to access the partner form for Assignment 7.
When working on Part 3, you may use either or both teammates' chat programs as the basis for referee. This is an authorized source, and you may now discuss all parts of the assignment with your teammate.
The tournament manager program (as described in the Tournament Manager section of the assignment specifications) is the "extra challenge" part of the assignment. While doing the extra challenge part of the assignment, you are bound to observe the course policies regarding assignment conduct as given in the course Policies web page, plus one additional policy: you may not use any "human" sources of information. That is, you may not consult with the course's staff members, the lab teaching assistants, other current students via Piazza, or any other people while working on the extra challenge part of an assignment, except for clarification of requirements. (Of course you may consult with your teammate while working on the extra challenge.)
For this assignment, the extra challenge part is worth 8 percent of this assignment. So if you don't attempt the tournament manager program, and all the other parts of the assignment are perfect and submitted on time, then your grade for the assignment will be 100 percent. If, in addition to completing a perfect referee program and submitting it on time, you submit on time a perfect tournament manager program, your grade for the assignment will be 108 percent.
The game of Othello (or Reversi) is explained in detail here. Unlike at that web
site, you should number your rows from 0
to 7
.
You are given various Othello player programs in the form of executable files (see table below).
File | Description |
player_<name>
|
Different Othello players that take reasonable decisions during the game. Can act as first or second players. |
playermanual
|
Othello player that reads the moves from stdin . Can
act as first or second player. |
playermax1bad
|
An Othello player that always outputs "D4" as its first move and then hangs. Always plays as a second player. |
playermax2bad
|
An Othello player that always outputs "D2" as its first two moves and then hangs. Always plays as a second player. |
playermin1bad
|
An Othello player that always outputs "A9" as its first move and then hangs. Always plays as a first player. |
playermin2bad
|
An Othello player that always outputs "D4" as its first two moves and then hangs. Always plays as a second player. |
playertoolong
|
An Othello player that implements an infinite loop. Can play as first or second player. |
player3mins
|
An Othello player waits for 3 mins and terminates. Can play as first or second player. |
player20secs
|
An Othello player waits for 20 secs and terminates. Can play as first or second player. |
Your task has three parts. The first part of the assignment is to create a chat program. The chat program will launch two other programs: add1 and add2. The second part is to create a Othello referee program. The referee program can launch and monitor two Othello player programs, one representing the first player and the other representing the second player. You may use the provided player programs to test the functionality of your referee program. The third part is also the extra challenge part of the assignment. You are tasked with the creation of a tournament manager program. The program runs a round robin Othello tournament among specified players by (a) determining the matchup to be played, (b) launching the referee program to run the matchup and (c) keeping track of the results of all matchups played so far. At the end, the results of all the matchups are printed on standard output, followed by the final ranking of the players.
Disclaimer: The extra challenge part is comparable in difficulty to the main part (referee) of the assignment and is one-twelfth as many points. Therefore it may not be an efficient use of your time. We suggest you try the extra challenge part only if you have completed the referee program and you have time to work on it.
Develop on CourseLab. Use emacs
to create source code. Use make
to automate the build process. Use
gdb
to debug.
Read this entire assignment specification page. Review the lecture slides and precept material from the first half of the course on testing, building, debugging, style, and especially modularity. Study the lecture slides and precept material from the second half of the course on exceptions and processes, process management, I/O management, signals, alarms and pipes. Complete the pertinent required reading, especially Chapter 8 of Computer Systems: A Programmer's Perspective (Bryant & O'Hallaron).
The CourseLab /u/cos217/Assignment7
directory contains the player program files. They are described in this page. It
also contains a sample referee program named samplereferee
and a sample tournament program named
sampletournament
that exhibit perfect functionality. Furthermore, the directory contains the scripts
testrefereediff
and testtournamentdiff
that will help your testing process. Create a project directory and
copy all files from the /u/cos217/Assignment7
directory to your project directory.
Run a game of Othello between the players player_Beatrice
(first player) and playermanual
(second
player). You can do so by using the runmanualgame
script. To run the script type
./runmanualgame
in the terminal.The script runs the game between the player_Beatrice
and playermanual
, and allows you to
observe the contents of the game record file (see the Othello referee tracking mode later in this page for more information on game
records) in real time, as the file is updated. Please note that when it is the time for the second player to send the move, you will
be able to type a move on the terminal and register it in the game.
add1
that reads a number from its standard input (using
scanf), adds 1, and writes the result to the standard output, and repeats that process when
there is input.
Your add1
should check that no file descriptor
in the range 3-40 is open. If one of those file descriptors
is active, for example 5, print an error message
"File descriptor 5 was not closed!" to stderr.
Write a similar program add2
that adds 2.
add1
processes in the background
by writing ./add1&
at the shell prompt
(they'll sit there waiting for input that never comes).
Now run ps
and learn their process ids.
Then use the kill -9
command to kill those processes,
and run ps
again to make sure they're dead.
(The flag -9 means "with extreme prejudice.")
What's the point? When you're debugging your chat
and referee
programs,
you don't want to inadvertently fill up the process table with
zombie players. If the process table fills up, then courselab
becomes unusable by anyone! Using ps
and
kill
is one way to maintain hygiene.
chat
that forks two children, and sets up pipes to and from
each child. Send an initial 0 to add1, get the answer (through a pipe) and send that to add2,
send the result back to add1. Perform the process a total of 10 times. Print the sequence of results you
receive; it should be "1 3 4 6 7 9 10 12 13 15 16 18 19 21 22 24 25 27 28 30". Your chat program should be run from the command line as follows:
./chat add1 add2
Edit your copy of the given readme-1 file.
Submit chat.c
, add1.c
, add2.c
. Add appropriate building rules in the Makefile to create the
executables add1
, add2
and chat
but do not submit your Makefile with Part 1.
Submit your work for Part 1 on CourseLab using the following commands:
If you are punting, then you will submit only the completed readme-1 file.submit 7 readme-1 submit 7 chat.c add1.c add2.c
displaygame
that checks moves in an Othello game.
After printing the initial board to stdout, its input is a sequence of
moves, one per line, in
the standard input stream.
After each move, the program prints the board to stdout.
It may be helpful to indicate which player is to play next by printing a prompt to
stderr.
When the game is concluded (no more moves possible), output
It will be to your advantage to make the output of displaygame match as closely as possible the format of the file written by the samplereferee program in tracking mode. Any lines that samplereferee generates that include the name of the player will not match, but all other output lines should match. To help you with this task, we have supplied some input files for displaygame; draw.txt, earlyfinish.txt and illegalFirstMove.txt.
earlyfinish.txt is the input for a game that ends before all the spaces are covered because it gets to a state where neither player has a legal move. Its output should match the supplied text file earlyfinishFIRST_vs_earlyfinishSECOND (except for lines that include the player names).
illegalFirstMove.txt is a file with only two moves. The first move is illegal and should halt the game. The second move should never be read. Its output should match the file that is generated by running
That will output a file named playermin1bad_vs_player_Aaron. Once again, the lines that include player names will not match../samplereferee -tracking playermin1bad player_Aaron
If your displaygame prompts the user for input, write those prompt messages to stderr. Only write to stdout the lines that indicate the game state. If you want to diff the results of your displaygame with the results of samplereferee, you must redirect the output of displaygame to a file. For example:
$ ./samplereferee -tracking playermin1bad player_Aaron -64 $ ./displaygame < illegalFirstMove.txt > illegalmoveoutput Player x, it is your move. $ diff playermin1bad_vs_player_Aaron illegalmoveoutput 16,17c16,17 < FIRST (playermin1bad) vs SECOND (player_Aaron) < Winner SECOND player_Aaron --- > FIRST vs SECOND > Winner SECOND
Submit displaygame.c
(and any associated .c and .h files) and add appropriate building rules in the Makefile to create
the executable displaygame
.
Write displaygame
in a modular way:
some of the .c and .h files that you submit for the
Othello move checker should also be used by your Othello referee.
Compose the Othello referee program. Your Othello referee's
main
function should be in referee.c
,
and you may have other .c and .h files as necessary.
At a high level, the referee program should
Set the "current" Othello player to be the MIN player.
Read a move from the current Othello player.
Verify that the move is valid, and end the game gracefully if it is not.
Update its game state with the move.
Write the move to the other Othello player.
Determine which Othello player is now the current one.
Repeat steps 2-6 until the game is over, and then...
Write the score of the game to stdout.
where the score is a positive number if the MIN player wins or a negative number if the MAX player wins.
There are two different modes your referee program should support.
Silent mode : Your referee program should be run from the command line as follows
./referee [MINplayer] [MAXplayer]
where [MINplayer] is the player program that makes the first move in the game and [MAXplayer] is the player program that makes the second move in the game. For example
runs the referee program for the game./referee player_Aaron playermax1bad
player_Aaron
vs. playermax1bad
. From the order of
the player program names it is implied that player_Aaron
makes the first move.
When referee launches each player, it must include a command-line argument "FIRST" or "SECOND" which tells the player program whether it will be [MINplayer] or [MAXplayer].
If either of the players does not exist, or is not executable,
should output on stderr File playername does not exist or
is not executable
, where playername is the actual name
of the player provided in the command line.
Your referee program should make sure that no player runs more than 1 minute. In order to do that, each child referee process should
call setrlimit
to limit the amount of CPU time that the process may consume to 1 minute, before overlaying itself with a player.
Your referee program should detect when a player has crashed (or failed to exist, or ran out of time). In that case, it should award the maximum score 64
to the player that did not crash, and exit indicating success. (Hint: When you test your program, note that playermanual
is not an appropriate player to test this case against.)
You may create your own Othello players to test how the referee is supposed to handle "problematic" players, as necessary. In all cases, your referee program must mirror the behavior of the samplereferee executable we provide /u/cos217/Assignment7/samplereferee
. We suggest you use the playermanual
program to test the execution of your referee program against the execution of samplereferee
thoroughly (you may assume that player moves will always be written in three characters, the letter corresponding to the column, the number corresponding to the row and the newline character - unless the program crashes -).
Tracking mode: The purpose of the tracking mode is to mainly help with debugging and to provide a lasting record of the game. To run the referee program in tracking mode, one should type the command line as follows
./referee -tracking [MINplayer] [MAXplayer]
where [MINplayer] is the player program that makes the first move in the game and [MAXplayer] is the player program that makes the second move in the game.
With -tracking
, the referee stores a record of the game in a file named MINplayer_vs_MAXplayer
, where MINplayer
is the name of the player program having the first move and MAXplayer
is the name of the player program having the second move in the game. As an example of the type of data stored on the record file see the picture below; use samplereferee
to see exactly the expected format of the record of the game stored on the file.
Initial game state: FIRST = x, SECOND = o A B C D E F G H 0 . . . . . . . . 1 . . . . . . . . 2 . . . . . . . . 3 . . . o x . . . 4 . . . x o . . . 5 . . . . . . . . 6 . . . . . . . . 7 . . . . . . . . Move #0 (by FIRST player): D2 Current game state: FIRST = x, SECOND = o A B C D E F G H 0 . . . . . . . . 1 . . . . . . . . 2 . . . x . . . . 3 . . . x x . . . 4 . . . x o . . . 5 . . . . . . . . 6 . . . . . . . . 7 . . . . . . . . Move #1 (by SECOND player): C4 Current game state: FIRST = x, SECOND = o A B C D E F G H 0 . . . . . . . . 1 . . . . . . . . 2 . . . x . . . . 3 . . . x x . . . 4 . . o o o . . . 5 . . . . . . . . 6 . . . . . . . . 7 . . . . . . . .
Compose a tournament manager for a round robin tournament. The main code of the tournament organizer should be placed in the a file named tournament.c
even though it may use other modules you define as necessary. The program should be run from the command line as follows
./tournament [player1] [player2] [player3] ... [playerN]
where [player1] [player2] [player3] ... [playerN]
are the names of the N
players participating in the tournament.
(The same player might be listed more than once! Most likely
this won't cause any problems for your program.)
The program should
Determine the matchup to be played (from the list of matchups that have not taken place yet).
Launch your referee program in tracking mode to monitor the matchup and report the score.
Update the tournament score board with the score of the matchup.
Repeat steps 1-3 until all matchups have been played.
Write on stdout
the names of the tournament participants followed by
the matchups and their scores followed by
the ranking of the players in the tournament.
Run the matchups (games) in the following order:>
[player1] vs [player2] [player1] vs [player3] ... [player1] vs [playerN] [player2] vs [player1] [player2] vs [player3] ... [player2] vs [playerN] ... [playerN] vs [player1] [playerN] vs [player2] ... [playerN] vs [playerN-1]
The ranking of the players is based on the number of wins. The highest ranked player is the player with most wins, followed by the player with the next number of wins, etc.. In the case of two players having the same number of wins, the player with the highest total score gets higher ranking.
In all cases, your referee program must mirror the behavior of the tournament executable we provide /u/cos217/Assignment7/sampletournament
.
For instance, if the match between any pair of the players participating in the tournament is not concluded properly (indicated by the referee program for that match exiting with nonzero status), an appropriate message should be printed on the standard error stream
and the program should exit indicating failure. In the message above tournamentname is the name of the tournament program preceeded bytournamentname: Match between playerMIN and playerMAX was not concluded properly
./
(dot forward-slash), playerMIN denotes the name of the player playing first and playerMAX the name of the other player.
A sample run of the tournament program is demonstrated in the following picture
-------------------------- Tournament: ./tournament --------------- -------------------------- Players ------------------------ firstplayer secondplayer thirdplayer -------------------------- 6 Games Played ---------------------- firstplayer vs secondplayer , Score: -1 firstplayer vs thirdplayer , Score: 0 secondplayer vs firstplayer , Score: 1 secondplayer vs thirdplayer , Score: 1 thirdplayer vs firstplayer , Score: 0 thirdplayer vs secondplayer , Score: -1 -------------------------- Rankings -------------------------- secondplayer 4 Total Wins 4 Total Score firstplayer 0 Total Wins -2 Total Score thirdplayer 0 Total Wins -2 Total Score
In all cases, your tournament program must mirror the behavior of the sampletournament executable we provide /u/cos217/Assignment7/sampletournament
.
Critique your programs using the splint
tool. Each time splint
generates a warning on your code, you must either (1) edit your code to eliminate the warning, or (2) explain your disagreement with the warning in your readme
file.
Similarly, critique your programs using the critTer
tool. Each time critTer
generates a warning on your code, you must either (1) edit your code to eliminate the warning, or (2) explain your disagreement with the warning in your readme
file.
Make sure the first dependency rule in your Makefile is
all: add1 add2 chat displaygame referee tournament
if you did the Challenge, or just
all: add1 add2 chat displaygame referee
otherwise. As usual, your Makefile
must maintain object (.o) files to allow for partial builds, and use gcc217
to compile.
Edit your copy of the given readme
file by answering each question.
One of the sections of the readme
file requires you to list the authorized sources of information that you used to complete the assignment. Another section requires you to list the unauthorized sources of information that you used to complete the assignment. Your grader will not grade your submission unless you have completed those sections. To complete the "authorized sources" section of your readme
file, copy the list of authorized sources given in the "Policies" web page to that section, and edit it as appropriate.
Provide the instructors with your feedback on the assignment. To do that, issue this command:
FeedbackCOS217.py 7
and answer the questions that it asks. That command stores its questions and your answers in a file named feedback
in your working directory.
Submit your work electronically on CourseLab using these commands:
submit 7 readme feedback Makefile submit 7 displaygame.c submit 7 referee.c tournament.c submit 7 allOtherModuleFiles
Don't forget to submit both your .h
files and your .c
files.
Suggestion: To make sure that your submission is complete, use this approach... Create a temporary directory. Copy the files that comprise your submission to that directory. Build your programs in that directory to make sure that no files are missing. Delete from that directory all files that you do not wish to submit, for example, executable binary files and .o files. Finally submit all of the files in that directory by issuing the command submit 7 *
.
The error messages written by your programs must be identical to those written by samplereferee
and sampletournament
.
It must be impossible for the user's input to cause your programs to terminate abnormally — via a failed assert, heap corruption, a segmentation fault, etc.
Your programs must contain no memory leaks. For every call of malloc
or calloc
, eventually there must be a corresponding call of free
. More specifically, your programs must produce clean meminfo
reports.
In part, good program style is defined by the splint
and critTer
tools, and by the rules given in The Practice of Programming (Kernighan and Pike) as summarized by the Rules of Programming Style document.
The more course-specific style rules listed in the previous assignment specifications also apply, as do these: your code must have proper file-level and function-level modularity.
To receive any credit for your referee
, the program must build. To receive any credit for your tournament
, the program must build.
We will grade your work on two kinds of quality:
Quality from the user's point of view. From the user's point of view, your code has quality if it behaves as it must. The correct behavior of your programs is defined by the previous sections of this assignment specification and by the given samplereferee
and sampletournament
programs.
Quality from the programmer's point of view. From the programmer's point of view, your code has quality if it is well styled and thereby easy to maintain. Good program style is defined by the previous section of this assignment specification. The use of proper function-level and file-level modularity will be an important part of your grade.
To encourage good coding practices, we will deduct points if gcc217
generates warning messages.
This assignment was written by Iasonas Petras with contributions from Andrew Appel and Robert M. Dondero, Jr..