On this page:
The Hot-or-Cold Game
Game Protocol
Running a Tournament
Implementation
Examples and Tests
Evaluation
Tips

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

  100

  1 99 0

  99 1 0

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

  66, 40

  64, 41

  65, 42

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

  63, 41

the server responds with

  colder

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

If the input were instead

  65, 41

then the server would respond with

  hotter

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

If the input were

  65, 42

then the server would respond with

  wrong!

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.

  66, 40

  64, 41

  65, 42

  65, 41

  hotter

  65, 43

  colder

  67, 41

  steady

  00, 43

  colder

  66, 41

  hotter

  01, 40

  wrong!

  66, 42

  colder

  66, 40

  winner

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).

  64, 41

  65, 41

  hotter

  66, 41

  hotter

  67, 41

  colder

  66, 41

  hotter

  65, 41

  colder

  66, 41

  hotter

  66, 42

  colder

  66, 41

  hotter

  66, 40

  winner

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,

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:

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:

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:

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

Tips