|
CMSC201
Programming
Project Five
MiniRenju
out Thur 11/21
due Midnight Tue 12/10
|
|
Objective
The purpose of this assignment is to give you experience writing an
interactive program with a command line interface, using scanf for
input, using the ANSI string library, and using arrays.
Your assignment
Write a program to help people play "miniRenju", a game loosely based
on the Japanese game of five-in-a-row or Renju
.
The game will be played on a grid of 10 by 10 intersections with black
or white stones placed on the intersections. Play alternates between
one player who starts the game (Black, by Renju convention) and
another player (White). A player can place a stone on any empty
intersection. The first player to get an unbroken line of four stones
whether vertically, horizontally, or diagonally, wins the game.
Your program will have a simple command line interface not
unlike the Unix shell. The user can type one of a set of commands to
the program to make a move, retract a move, request that the board be
printed, etc. The commands will be simple words (e.g., move
or help ) and some will allow or require arguments (e.g.,
move 3 4). After reading a valid command, your program will take
appropriate action which may result in providing some feedback.
The following is a sample session with the program with the human's
input in italics. Note that the prompt is B> if it
is Black's turn to move next and W> if it is White's.
% miniRenju
Welcome to miniRenju 1.0.
Type "?" to see the commands and "help"
for more information information.
B> help
Ok.
...helpful info is printed...
B> moev 5 5
Huh? I didn't recognize that command.
B> move 5 5
Ok.
W> move 6 6
Ok.
B> board
Ok.
0 1 2 3 4 5 6 7 8 9
+--------------------+
0|....................|
1|....................|
2|....................|
3|....................|
4|....................|
5|..........B.........|
6|............W.......|
7|....................|
8|....................|
9|....................|
+--------------------+
(3) BLACK TO MOVE
B> move 6 6
Huh? You can't move there.
B> moves
1: 5,5
2: 6,6
B> resign
Ok.
After 2 moves, White has won.
I hope you enjoyed the game.
Bye...
%
A command line interface is a very common way to structure an
interaction between a human and a computer. The computer types a
prompt (e.g., B>) and waits for the human to type a line of text
which represents a command chosen from a set of possible commands the
computer can process. Assuming the command is recognized and is well
formed, the computer then executes it and gives appropriate feedback.
If the command is unrecognized or somehow malformed, an error message
is printed and the next command sought. A command is a simple command
name or a command name followed by one or more arguments.
The commands
Your command-line interface should be able to handle the following
commands.
- ? -- Print out a list of recognized commands.
- help -- Print out a list of recognized commands with a
one-line description of each.
- print -- Print the current board.
- board -- Print the current board.
- autoprint on/off -- Toggle whether the board is
automatically printed after every pair of moves. This implies that
there is a boolean variable (e.g., autoPrinting) what indicates
whether the board should be automatically printed after every move.
The "autoprint on" command will have the side effect of setting this
variable to TRUE and the "autoprint off" command will set it to false.
- move R C -- Place a stone for the current
player on the intersection at row R and Column C. If
(R,C) is not a legal board position or if there is already a stone at
this location, then an appropriate warning is printed.
- moves -- Print a history of all of the moves.
- undo -- Undo the last move.
- resign -- The currently player resigns. The other
player wins.
- quit -- Upset the board and leave. No one wins.
- exit -- Upset the board and leave. No one wins.
- play black/white -- (OPTIONAL) Make moves for the
specified player. (e.g., the command "play white" will cause the
computer to make the remaining moves for the white player).
- display -- (OPTIONAL) Display the current board using
the graphics library.
- autodisplay on/off -- (OPTIONAL) Toggle whether
the board is automatically printed after every pair of moves.
Make sure your program gives appropriate feedback for unrecognized or
illegal commands. You are not required to implement the optional
commands unless you are in the Honors section or are having fun
hacking. We look kindly on people who like to hack. So does the
world, it seems. Bill Gates and Mark Andreesen liked to hack.
Using scanf and friends for input
In order to implement your command line interface you will have to use
lower-level C functions for reading input -- gets and
sscanf . You should also use the functions in the ANSI string
library instead of the Robert's library. You can do a man sscanf and man
gets and man string to get some
documentation on these functions.
The function scanf() is analogous to printf() in that it has a "format
string" and a set of variables, one for each code in the "format
string".
scanf("%d", &n) ;
scanf("(%d,%d)", &i, &j) ;
scanf("%s %d %d", command, &arg1, &arg2);
Of course, it reads from the standard input rather than writing to the
standard output. Note that scanf takes pointers to variables as
parameters (parameters passed by reference) so it can store the user's
input in those variables. See pages 539-547 in our text for more
information.
We recommend that you use the gets and sscanf
functions. The gets() function is used read in a line of
text from the standard input and put into a variable. The
sscanf() function is like scanf except that it takes its
input from a string rather than from the standard input. The string
that sscanf reads from is given by its first argument. For example,
the following code fragments suggest how your program reads and begins
to process a command.
void main() {
char cmdLine[128];
...
gets(cmdLine); /* read a line from standard input*/
doCommand(cmdLine)
...
}
void doCommand(char *cmd){
char name[20];
...
sscanf(cmd,"%s",name); /* get the command name */
if (0==strcmp(name,"move")) { /* do a move command */
sscanf(cmd,"%s %d %d",name,&row,&col);
doMove(row,col);
}
else if ...
else doUnknown(cmd); /* complain about an unknown command */
}
Constants and new types
As usual, you should identify important parameters in your program
which would be appropriate to define as constants. For example, the
size of the board, the number of interesections, how many stones in a
row it takes to win, etc.
You are encouraged to define new types as appropriate. For example,
you might have an enumerated type player with the possible
values Back and White, as in:
typedef enum {Black,White} player;
Representing the board
You might use a 10x10 array of integers with 0 representing an empty
intersection, -1 for a black stone and +1 for a white stone.
Boundary condition
What happens when your program is trying to determine if playing a
stone at location (0,0) leads to a winning move? If you follow our
suggestion, your program will try to see how long the northerly line
is. It can't be very long, since we are at the boards's northern
extreme. Your program could easily degenerate into a mess of ugly
if-then-elses as you check for the dreaded "boundary conditions".
There is a nice way to prevent this, however -- define special
functions to access and set array elements. These functions will do
the checking to see if they are "up against the wall" and return an
appropriate value. It is as if there are cells off the board which
are always empty and can never have a stone placed on them.
- int value(int i, int j) returns the value at row i,
column j or 0 if i,j is off the board.
- bool setValue(int i,int j,int v) sets the value of cell
(i,j) to v and returns TRUE if (i,j) is an empty and on the board.
If (i,j) is not empty or is off the board (e.g., (12,34) or (-4,2)) it
prints a warning message and returns FALSE.
If you always use these two functions to access or set board positions
it will simplify the rest of your code.
Undo and keeping track of the moves
Supporting the undo feature is not as hard as it sounds. You
will not have to remember and restore all of tha past board positions.
Rather, you can recreate a past board position from the current one if
you know all of the past moves. This is because the moves are
reversible. If you know that you got from board position B2 by a
player placing a stone at intersection (i,j), you can undo the move
simply by making intersection (i,j) be empty.
So, in order to provide an undo feature, you will need to remember up
to 100 moves where each move would be remembered by storing the two
coordinates of the intersection on which a stone was played. You
don't have to remember which player moved, because black always plays
first in Renju and the players alternate. Thus, Black makes all the
odd numbered moves and White the even numbered ones.
We suggest that you consider using two arrays and a variable to keep
track of the past moves:
int nextMove = 0; /* number of the next move to be made */
int movesRow[100]; /* array of rows of the moves made */
int movesCol[100]; /* array of rows of the moves made */
where movesRow[i] is the row for the i-1th move and
movesCol[i] is the column for the i-1th move and nextMove
is a global variable whose value is the index of the next move. An
alternative would be to define a structure to represent a move and
then to have an array of moves, but we still haven't covered
structures.
Is the game over?
One thing your program will have to do is to recognize when it has won
or its opponent has won or if there are no more moves that can be
made. Recognizing when no more moves can be made is easy. How can
you tell if the last stone that was played results in a win? There
are a number of ways to check this, some more clever and efficient
than others. Here is one you might consider.
For example, consider the following algorithm. Assume a stone of
player P has has just been placed a stone in position (i,j). There
are eight lines which emanate from this intersection which we could
name with the compass points (NN, NE, EE, SE, SS, SW, WW, NW). What
we would like to know is the length of the row of P's stones going off
in each of these directions. If we include the stone at (i,j) then it
might be 1, 2, 3 or 4. How do we compute this?
Well, let's put that problem off for a moment and assume we have it
done already. Let's assume that we have a local variable for each
direction (i.e., NN, NE, EE, SE, etc) whose value is the length of the
row of stones going off in that direction. If we do, then a stone of
player P is a wining move if
NN+SS>4 || EE+WW>4 || NE+SW>4 || NW+SE>4
We check to see if any of the sums are greater than four since we end
up counting the center stone twice. Notice that this method could
easily generalize to five-in-a-row, six-in-a-row, etc.
So, how do we compute these numbers. Let's imagine a function
walk that takes a player P, an intersection (i,j) and a
direction expressed as an increment to the row di and an
increment to the column dj and returns the length.
int walk(player p, int i, int j, int di, int dj);
If we had such a function, then we could compute the values of the
variables as:
NN = walk(p,i,j,0,1);
NE = walk(p,i,j,1,1);
EE = walk(p,i,j,1,0);
SE = walk(p,i,j,1,-1);
...
NW = walk(p,i,j,-1,1);
Ok, so how do we implement this walk function? Here is a sketch to
get you going...
Let the number of stones be 0, row be i, and col be j.
while (cell (row,col) has a stone for player p)
{Increment the number of stones.
Add di to row.
Add dj to col.}
return the number of stones.
Having the computer play
If you implement the optional feature of having a computer play for
one of both of the players the project will be a lot more fun. You
can impress your friends with the result, too. You will need to have
some variables which indicate whether the computer is playing for
Black and/or for White. You will need to add some logic in your code
so that if it is player P's turn to move and the computer is playing
for P, then instead of reading in a command line and processing it,
you call your function (makeMove that will select and make a
move. Note that if the computer isd playing both sides, no more input
should be sought!
What's a good move?
If you implement a function to choose moves it does not have to play
well. The only real requirement is that it make legal moves, i.e.,
follow the rules. We suggest you use some very simple heuristics to
choose a move without really looking ahead to the consequences. (A
heuristic is a "rule of thumb" or maxim that seems to work
much of the time. Something like "it's good to trade pieces when you
are ahead" in chess.) If you are interested in how to write a program
that plays well, you should consider taking CMSC471 (Artificial
Intelligence). Possible heuristics for miniRenju, in order of
increasing power:
- Randomly try intersections until you find one that is empty.
If you do use this heuristic, you program will take a long time to
find an open intersection if the board is full. You may want to scan
the board in some regular pattern looking for an open move.
- Play a stone adjacent to the last stone you played if
possible. If not, play next to the last stone your opponent played.
- If you have a winning move, take it. If not, place a stone to
block a winning move by your opponent. If there are none, place a
stone to lengthen your longest run.
Again, if you only want to implement the first one (random move)
that's ok.
Total Quality Management
We will test your program by feeding it a standard test script. We
will make some similar, but not identical, test scripts available to
help you debug your program. If you put such a script in a file, say
test1.in, you can easily feed it to your program using i/o
redirection, as in...
If you wanted to capture the out put in the file test1.out
then you could
<![CDATA[
% miniRenju <test1.in >test1.out
]]>
Variations
Some things to think about...
- What would you have to change in order to play on a cylinder?
How about a torus? Can you make this an option at the beginning of
the program?
- Could you generalize your program to play N-in-a-row and make
N a parameter?
- Suppose you and a friend want to hook up your miniRenju
programs to play each other. How would you do that?
Hints
We've put together some of the code fragments in this assignment to
form a kind of sketch of your program.
Be sure to check this section from time to time for comments, hints
and clarifications added after the initial release of this assignment.
Disclaimer of liability
Although every effort is made to assure the accuracy of the
information contained in documents associated with this project,
neither the Computer Science and Electrical Engineering Department,
nor the University of Maryland Baltimore County, nor any of its
employees, makes any guarantee, express or implied, regarding the
accuracy of information or fitness for a particular purpose, or
assumes legal liability or responsibility for the accuracy,
completeness, or usefulness of any information, or process disclosed,
and is not responsible for the contents of any off site web page or
print documents referenced. Discontinue use of this document if any
of the following occurs: itching, vertigo, dizziness, tingling in
extremities, loss of balance or coordination, slurred speech,
temporary blindness, profuse sweating, or heart palpitations.