This assignment is due on Tuesday, 2 March, no later than 5:00 p.m.
See the assignment turn-in page (last modified on 9 February 2004) for instructions on
turning in your assignment.
Corral (also known as All the King's Horses is a simple, two-player using a chess board (or
more genarally, an n-by-n grid) and some number of knights placed on
the board. The objective of the game is to move all the knights into the
2-by-2 square, called the barn, in the upper-left corner of the board.
However, the player that moves the last free knight into the barn is the loser;
the winning objective is to force the other player to corral the last knight in
the barn.
The board is n-by-n, where n > 2. Each square is identified
with a pair of positive integers (x, y), 0 <= x < n
with (0, 0) in the lower left corner. x increases to the right; y
increases going up.
The game starts with some number of knights randomly scattered around the
board; unlike regular chess, a square can hold more than one knight. Knights
move as they do in chess: two squares straight then one to the right or left.
However, any move that would place the knight further from the barn than it was
before the move is illegal.
Distance is measured using the Manhattan distance; the Manhattan distance
between two squares is the number of squares traversed (exclusive of the
initial and final squares) by moving first horizontally (or vertically) and
then vertically (or horizontally). For example, the two squares A and
B
are at Manhattan distance 3 + 2 = 5 from each other. Notice that the pivot
square (the square in which the movement direction changes from horizontal to
vertical or vice versa) is counted twice.
Using the Manhattan distnace admits a larger number of legal moves
than is
allowed by Conway.
The distance measured is from a knight's position to the back of the barn at
(0, n - 1).
The two players alternate turns. At each turn, a player moves all knights not
yet in the barn; once a knight reaches the barn, it may be removed from the
board. Each knight not yet in the barn is moved exactly once per turn. Unlike
chess, a square may hold more than one knight. The loser is the player who
moves the last uncorraled knight into the barn.
The second half of this project involves extending the first half to create
fully capable Corral server and Corral client. The Corral client plays Corral;
the Corral server coordinates Corral clients so they play a game together.
Each message starts with a one-byte value giving the message tag; the
recognized message tags are defined in /export/home/class/cs-537/p1b/corral.h. The
structure of the rest of the message depends on the message tag.
- The error message - The sender of an error message indicates to the receiver of the
error message that the sender has detected an error; the error message, if
present, gives a brief description of the error. An error message has the
format
where
error - The error message tag.
- n - The number of bytes in the message; n may be
zero if there's no message.
- C1 through Cn - The characters in the message. Each
character Ci must be in the range space (ASCII value 32 decimal) to
'~' (ASCII value 126 decimal) inclusive. Characters outside this range
are invalid.
- The game message - When a server pairs two clients wanting to play Corral, it sends a
game message to each of the clients. A game message has the format
where
game - The game message tag.
- C - The board is C-by-C, 2 < C <= 30.
- The lose message - The client losing a game receives a lose message from the server. A
lose message has the format
where
lose - The lose message tag.
- The move message - A client makes its moves by sending a move message to the server;
the server also relays one player's move to the other player using a move
message. A move message has the format
where
move - The move message tag.
- n - The board contains n knights.
- Xi, Yi - The ith knight is at square (Xi,
Yi) on the board. If the move message is being sent from a client to
the server, then all the knights must be on the board, including the barn (that
is, 0 <= Xi, Yi < C). If the move message is being sent
from the server to a client, then all the knights must be on the board outside
the barn. The knignts are listed in an arbitrary order.
- The play message - A client in search of a partner with which to play Corral
sends a play message to the server. A play message has the format
where
play - The play message tag.
- The quit message - The client quitting a game sends a quit message to the server. A
quit message has the format
where
quit - The quit message tag.
- The win message - The client that wins a game receives a win message from the server.
The win message has the format
where
win - The win message tag.
All values are unsigned and in network-byte order.
The event diagram 
gives a general idea of the way in which clients and servers interact. More
specifically, the interaction between client and server can be broken up into
three phases: set-up, play, and shut-down.
Once a client connects to a server, the server waits for the client to send a
play message; a client cannot be considered for a game of Corral until it sends
a play message. The server should receive a play message from the connecting
client within 5 seconds of connection establishment. If the server fails to
receive a play message within 5 seconds, it should send an error message to the
client and close the connection.
Upon receiving a play message from the connecting client, the server pairs the
playing client with a waiting client and starts a game of Corral between the
two clients. If there is no waiting client, the playing client becomes the
waiting client. A waiting client may wait an arbitrarily long time.
Note that the server can have at most one waiting client, but can have an
arbitrary number of clients that are connected but are still missing their play
messages.
Once the server pairs two clients for a game of Corral, it generates a random
game (board size and knight placement) and sends each client a game message.
It then randomly selects one of the two players and sends it the first move
message.
The playing client receiving a move message from the server has somewhere
around 10 seconds to respond with a move message. The playing client can reset
the 10 second clock by sending a move message with n equal to zero back to
the server; the client then has another 30 seconds or so to send another move
message.
When the server receives a non-empty move message from the client, it adjusts
the board according to the moves given in the move message. If the game is
over, the server shuts the game down; otherwise, it sends a move message to the
other client in the game.
When the server receives an empty move message, it resets its move-response
time-out clock for that game. A client can send at most 10 consecutive empty
move messages during its turn. If the client fails to send any moves after 10
consecutive empty move messages, the server should disconnect the client and
declare the other playing client the winner.
When the game ends, the server sends win and lose messages to the appropriate
clients. After sending the lose message, the server closes the connection to
the losing client. The winner remains connected to the server to face the next
client. The winning client need not send another play message to the server to
start the next game, but it will receive another game message from the server
to indicate when the new game starts.
A client may withdraw from the server at any time by sending a quit message.
If a game is in progress, the server declares the other client the winner,
sending it a win message (this means a client may receive a win message before
the game is over). If a client disconnects from the server without sending an
quit message, the servers should behave as if it had received a quit from the
disconnected client.
When one side of a connection detects an error from the other side of the
connection, it should close its half of the connection and act accordingly (a
client should probably halt, a server should continue to handle other
connections). If the error permits it, the working side of the connection may
send a error message with a helpful error description to the faulty side of the
connection before closing the connection. However, the error description is
optional; the error message may, at any time, contain an empty error
description.
The receiver of an error message should assume the connection over which the
message arrived has been closed (this means the receiver should not try to send
an error message back when it receives a faulty error message). The receiver
should print the error message (if any) to std-err and close the connection.
What happens next depends on the receiver; a client should probably halt, a
server should clean-up the connection and continue.
Error messages can be sent at any time, even at times when no error has been
detected by the sender. The receiver's response to an error message, however,
should always be as described in the previous paragraph.
Erroneous behavior includes receiving undefined messages, receiving incorrectly
formatted messages, receiving messages with bad values, receiving messages out
of expected order, failure to interact within a reasonable amount of time, and
unexpected connection terminations.
Clients and a server communicate using TCP; if you're really into it, you might
try UDP, but I recommend you get a TCP version of the project working before
you try UDP.
The client should support the -h and -p command-line options to
specify the server's host IP address and listening-port number, respectively.
The server should support the -p command-line option to pick specific
listening-port number.
The client should implement an automated Corral player so it can play the game
without input from the user. The client should not prompt the user for moves
(you can add this as an option as you want, but the client's default behavior
should be to generate moves automatically by itself). And remember, the
objective of this project is to learn about client-server computing, not to
implement winning algorithms for Corral. Having the client generate random
moves is good enough.
The server should handle as many simultaneous games as possible. The maximum
number of simultaneous games your sever should be able to handle depends, in
part, on your implementation, but certainly the maximum number of open file
descriptors allowed per process is one reasonable upper limit.
The choice of implementation language is up to you. However, you should make
sure that whatever you chose is available on the cslab machines, which is where
I'm going to test your code. It would also be nice, but not required, that
your system also run on rockhopper.
You should include a makefile among the files you turn in, either for testing
or to turn-in. Your makefile should understand three targets: clean, clnt, and
srvr. The clean target should delete all dependent files (.o and executables
for C++, class files for Java, for example). The clnt target should build the
Corral client; the name of the executable should be clnt. The srvr target
should build the Corral server; the name of the executable should be srvr.
When you test or turn-in your project, the turn-in script runs (among other
things) the following three commands:
$ make clean
$ make clnt
$ make srvr
You should make sure this works correctly.
There's an example makefile you can use in the assignment
directory. If anybody feels the need to use ant or some other build mechanism,
they should get in touch with me (essentially, what I'll tell you to put it in
a makefile, but we'll have to work that out together).
You may work in teams of two for this half of the project. Independent of
whether or not you work in a group, it's also a good idea to work with another
group (of one, pehaps) to make sure your implementations interoperate.
The grade for this project determines 75% of your grade for the entire first
project; the first half of the project determined the first 25% of your grade
(that is, your final grade for Project 1 is the sum of 25% of your grade for
the first half plus 75% of your grade for the second half).
This page last modified on 25 February 2004.