[an error occurred while processing this directive]

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.

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

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.

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:

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.

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:

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

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.

If we had such a function, then we could compute the values of the variables as: Ok, so how do we implement this walk function? Here is a sketch to get you going...

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:

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

  2. Play a stone adjacent to the last stone you played if possible. If not, play next to the last stone your opponent played.

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

Variations

Some things to think about...

Hints

We've put together some of the code fragments in this assignment to form a kind of sketch of your program.

Comments

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. [an error occurred while processing this directive] Tuesday, 26-Nov-1996 15:21:56 EST