Shell Assignment

Due: Wednesday, November 7, 11:59pm

For this assignment, you will write a program to run a tournament for automated players of a hot-or-cold game. You don’t have to implement the game itself or the players in the game; those are provided as C programs. Your task is to write a program that runs those programs, and that task will involve communicating messages between the game-maker program to the player programs. It’s not a “shell” in the usual sense, but your program will be shell-like in the way that it manages and controls processes.

Specifically, you will implement a run_tournament program that takes at least three arguments: a seed for a random generator (up to 8 digits), a number of rounds to run (up to 8 digits), and a path to the first player program. Any number of additional player-program paths can be provided as additional arguments. For example,

  ./run_tournament 42 100 scan_player step_player

will run a tournament with 100 rounds pitting scan_player against step_player. The seed 42 determines the “random” starting positions that are given to each player in each round. As long as the players always behave the same way for a given starting position, then running a tournament with a given seed number will produce the same results. In this case, the output ends with the three lines

which means that the first player, scan_player, won 1 round, lost 99 rounds, and failed in 0 rounds; the second player, step_player, won 99 rounds, lost 1 round, and failed in 0 rounds.

The Hot-or-Cold Game

Your task is not to implement the hot-or-cold game. Since your tournament program must manage the communication between the game maker and players, however, it’s helpful to understand how the game works.

The hot-or-cold game involves a grid of positions that are addressed by pairs (x,y) where x and y range from 0 to 99 inclusive. The game maker chooses a “random” position on the grid as the target position. It then places each player at a “random” position that is between 40 and 45 steps away from the target position. A distance in steps is a Manhattan distance (i.e., the sum of the magnitude of differences between the respective x and y components of a player’s position and the target position).

On each turn, a player picks a new position by moving any number of steps in either the x or y direction (but not both). That is, the new position must have either the same x or y component as its old position, and it cannot be the same as the old position. The game maker responds with “winner” if the new position is the target position, “colder” if the new position is further in steps from the target position, “hotter” if the new position is closer but not yet the target position, and “steady” if the new position is the same distance in steps as the old position (which is possible if the new position is an even number of steps from the old position). The game maker gives each player a turn, and it iterates through multiple turns until some player wins.

If a player makes an invalid move (e.g., by picking a new position where both the x and y components are different from the old position), the game maker responds with “wrong!” and does not give the player any further moves in the round. If all players go wrong in this way, a round can end without winner. Otherwise, there is no limit on the number of turns that are allowed in a round to find a winner.

Game Protocol

The game maker and the players communicate by reading from standard input and writing to standard output. The game maker does not know how to run players or how to communicate to multiple programs; it will be the job of your run_tournament program to run the game maker and players and to relay messages between them.

All communication with the game maker and players is based on a line that is exactly 7 bytes, where the seventh byte is always a newline character. A position line is exactly two decimal digits for the x component, one comma, one space, exactly two decimal digits for the y component, and a newline. A guidance response from the game maker is exactly either winner, colder, hotter, steady, or wrong! followed by a newline.

The game_maker program takes four command-line arguments: a seed number, a player count (which must be at least 1), a minimum starting distance, and a maximum starting distance. If the second argument is n, then game_maker responds immediately with one position line for the target (which is not meant to be seen by players, of course) and n position lines that are the starting positions of the players, in order. For example,

  ./game_maker 42 2 3 3

starts a two-player round where both are initially 3 steps away from the target, since both the maximum and minimum distance are 3. Starting game_maker that way produces the output

which says that the target is at (66, 40), the first player starts at (64, 41), and the second player starts at (65, 42).

The game maker program then waits for an input line that is the first player’s new position. For example, given the input

the server responds with

since (63, 41) is farther from (66, 40) than the player’s previous position (64, 41).

If the input were instead

then the server would respond with

since (65, 41) is closer to (66, 40) than the player’s previous position (64, 41).

If the input were

then the server would respond with

because (65, 42) is not a valid move from the previous position (64, 41).

After replying for the first player’s move, game_maker waits for the second player’s move as an input line, and so on. If game_maker responds to a move with wrong!, then it does not wait for a move from the player for future turns; that is, it skips the player for the rest of the round.

The game_maker program exits with status 0 as soon as it responds winner to any move. The game_maker program exits with status 1 if all players have gone wrong.

Here’s a complete transcript of a potential run of game_maker, where lines with a blue background correspond to input lines for game_maker and other lines are game_maker’s output.

In this transcript, the second player goes wrong on its third turn by making an invalid move, so it is skipped for the rest of the round, and the last two moves are both by the first player (which wins).

A player program, such as scan_player or step_player, expects an initial input line that is a position line. It responds with position line for the new location, and then it waits for a guidance-response line as input—iterating position output and guidance input until the guidance input line is winner.

Here’s a transcript of a potential run of step_player, where lines with a blue background correspond to input lines for step_player, other lines are step_player’s output, and the target turns out to be at (66, 40).

Note that the input to a player corresponds to a subset of the output of the game maker, and the input to the game maker corresponds to output from multiple players. The game maker and players cannot talk directly. Your run_tournament function will talk to all the other programs, accepting each output line from the game maker and sending it to an appropriate player, and accepting each player’s output (at the appropriate time) and sending it to the game maker.

Running a Tournament

Given a seed s, a round count r, and n player programs, your run_tournament program should run r rounds. The run_tournament program should keep track of the number of times each player wins, loses, and fails; a program will either win or lose every round, and it may fail on some rounds.

For each round i where i ranges from 0 to r-1,

• Run game_maker with the seed s+i, player count n, minimum initial distance 40, and maximum initial distance 45. By using s+i as the seed for the game maker, the whole tournament is predictable (as long as the players are predictable), but each round within the tournament has a different target and starting positions.

• Run each of the n players, keeping them in the order provided on the command line. Note that the first player will be first throughout the tournament, but the game is still fair, because the game_maker program will start players at varying distances from the target across rounds.

• When some player program wins, the round is over. Make sure that the winning program exits normally with status 0, otherwise count that round as a failure for the program (despite also being a win). Force all other player processes to terminate, and don’t count forced termination by itself as a failure.

• When a program makes a bad move, either through output that is not a valid position line or when the game maker replies with wrong!, count the program as both losing and failing for that round of the tournament.

  Although it’s possible for a player program to incorrectly terminate after its most recent move and just before some other player wins, you do not have to detect that situation and count it as a failure.

Your run_tournament program must end with a report of n+1 lines to standard output. (Other output before the last n+1 lines is allowed and ignored.) The first output line is the number of rounds played as a decimal number followed by a newline. Each additional line reports the results for each program, in the order of the players, as three decimal numbers: wins, loses, and failures. The three numbers should have a single space in between, and (obviously) the line must be terminated by a newline.

If the run_tournament program receives a SIGINT signal (i.e., it’s interrupted by Ctl-C), then it should finish the current round and report the results of the truncated tournament (i.e., report the number of rounds completed and the results for those rounds, then exit). When run_tournament is run in a terminal, Ctl-C should not cause the player programs to fail; that is, the Ctl-C should not reach the player programs, and they should continue to finish the current round.

Your run_tournament program can assume that the game_maker program is in the current directory and always works properly. Your run_tournament program can also assume that the given player programs are valid executables, but they might not function properly; that is, they may exit unexpectedly, exit in the wrong way, or produce bad output. As a simplification, however, the player programs will never become unresponsive without first behaving in some other detectable bad way, and they will never write to standard error as long as they are called properly and receive well-formed lines.

Implementation

The shlab-handout.zip archive provides an initial run_tournament implementation that just parses the command-line arguments. Your job is to complete the implementation in "run_tournament.c". Within "run_tournament.c", you can add functions, change function signatures, or whatever to implement new functionality.

You will handin a single file, "run_tournament.c", which must use only ANSI standard C syntax with GNU extensions (as is the default for CADE machines), standard C libraries, Linux system libraries, and the "csapp.c" wrapper functions.

You don’t need to modify "game_maker.c" or any of the player implementations. You may find it amusing or modestly instructive to create a better player than "jump_player.c", but that’s beyond the requirements of the assignment.

Examples and Tests

The shlab-handout.zip archive includes several players that you can run in a tournament:

• scan_player naively scans every position in the grid.

• step_player takes one step at a time, abandoning each of the four possible directions as soon as it gets a colder for that direction. This player will normally beat scan_player.

• jump_player tries to take bigger steps when it’s moving in the right direction. This player will normally beat all of the other provided players.

• fumble_player is a broken variant of step_player: it exits in different bad ways just after winning. So, fumble_player always ends up with the same number of wins and failures.

• garbled_player takes a bad step, after a while, by outputting a bad position line.

• distracted_player takes a bad step, after a while, by outputting a partial position line, closing its output, and going into an infinite loop.

• unreliable_player sometimes behaves correctly, sometimes fumbles a win, and sometimes takes a bad step. Its behavior depends on the starting position, so the player behaves deterministically (but differently for different rounds).

The shlab-handout.zip archive archive also includes a "test.rkt" script runs run_tournament with various combinations of players to check for specific expected results. Run "test.rkt" with racket test.rkt followed optionally by any of the following flags:

• -v or --verbose — prints information about the tests being run.

• --no-fail — skips tests that involve failing players.

• --no-ctl-c — skips tests that check Ctl-C behavior.

• --stop-on-error — stop as soon as a test fails.

When all tests pass (other than ones skipped by --no-fail or --no-ctl-c), the "test.rkt" script prints “All tests passed.” The full sets of tests should take only about 10 seconds to complete.

A test fails when run_tournament does not print the expected output for a tournament. A test also fails anything is printed to standard error by run_tournament, the game maker, or one of the player programs.

Evaluation

Grades will be assigned based on a level of completion, where each level requires success at the lower levels:

• up to 80 points: Works with non-failing players, such as scan_player, step_player, and jump_player.

  This level of completion corresponds to running "test.rkt" with the --no-fail and --no-ctl-c flags.

• up to 90 points: Works for all players, including those that sometimes fail.

  This level of completion corresponds to running "test.rkt" with --no-ctl-c flag.

• up to 100 points: Works on all players, including those that sometimes fail, and also implements Ctl-C handling.

  This level of completion corresponds to running "test.rkt" with no flags.

Although tests are provided, grading may use additional test players of similar complexity at each level.

Tips

• A single pipe only works for one-way communication, so create two pipes if you need to both send data to and receive data from another process.

• The Rio_readn and Rio_writen functions from "csapp.c" are helpful for avoiding the partial reads and writes that are possible with Read and Write. The functions have the same signatures as Read and Write, but Rio_readn will only return less than n if it encounters an end-of-file, and Rio_writen will write all n bytes (unless there is an error, which will terminate the program):

  ssize_t Rio_readn(int fd, void *usrbuf, size_t n);

  void Rio_writen(int fd, void *usrbuf, size_t n);

• Use Signal(SIGPIPE, SIG_IGN) to avoid unwanted signals when a pipe is closed by another process.

• Start by just running game_maker, which involves adding Fork. Instead of running a player, simulate good and bad players by sending literal strings the game_maker process and checking that you get the expected results back.

• Next, make game_maker cooperate with a single player for a single round.

• Next, support multiple well-behaved players and multiple rounds.

• Next, support misbehaved players like fumble_player, garbled_player, and unreliable_player.

• Finally, implement Ctl-C handling. You’ll probably need functions like Signal and Sigprocmask. Note that Setpgid is one way of preventing a Ctl-C that is intended for run_tournament from being sent to child processes of run_tournament, since a terminal will send Ctl-C to a process group. Also remember that relevant signals will need to be blocked while a process is being created.

• If your implementation includes a call to sleep, Sleep, pause, or Pause, then you’re doing it wrong.