CMU 15-211 Fundamental Structures of Computer Science I

Assignment #5: Not-So-Deep Blue

Due: Wednesday April 3, 1996, 11:59 PM (Wednesday night)

1. Written exercises

1.1 Heapsort

Consider an array of length 12 containing your first name followed by your last name followed by A,B,C,..., until the array is full. For example, Prof. Blum would have: AVRIMBLUMABC. Prof. Sleator would have: DANIELSLEATO.

A.

Run the ``build heap'' procedure discussed in class (the bottom-up heap construction) on your array. What does the array look like now? For instance, our first example would become: V U R M M C L I A A B B.

B.

Now, run the second phase of heapsort on this array until 4 elements have been swapped out from the heap portion of the array. What does the array look like now? For instance, our first example would become: M I L B A C B A M R U V.

1.2 Game search and Connect-4  

In the programming portion of this assignment, you will write a program to play the ``Connect-4'' game. Connect-4 is like a game of tic-tac-toe on its side. There are two players X and O, and a rectangular board that is empty at the start of the game. As in tic-tac-toe, the players alternate in putting their mark on empty squares until either one player wins by getting a specified number of its marks at consecutive positions ``in a row'' (row, column, or diagonal) or all the positions get filled. If all the positions get filled and there is no winner then the game is a tie. Unlike tic-tac-toe, a legal move must be at the lowest empty space in some column. In other words, think of each column as a vertical container and your mark (X or O) ``falls'' to the lowest unfilled position.

For instance, if there are 5 columns and 4 rows and ``4-in-a-row'' is needed to win, then each player has at most 5 choices for each move (maybe less if some columns get filled) and a board where X has won might look like:

 . . . . X
 . . . X O            (in this picture, a "." represents an empty square)
 . O X O O
 O X O X X
 ---------
 0 1 2 3 4        <--- column number

(In your programs, you will generally be dealing with versions where only 3-in-a-row are needed to win, which might be better called ``Connect-3.'')

Your job in the programming portion of this assignment will be to write a program that plays ``intelligently'' in the following sense. If there exists a strategy that guarantees it a win, then it will win. Otherwise, if there is a strategy that guarantees it a tie, it will never lose. Once you have the program working correctly, you will then improve its running time by using a hash table to implement a memoizing strategy.

The basic idea of this program will be as follows. Given a board configuration (a board with possibly some X's and O's in it) and a player whose turn it is to move (say, X) you want to find out if there is a move that X can make that guarantees X will win. What we mean by ``guarantees X will win'' is that no matter what player O does, there exists another move X can do so that no matter what player O does, there exists another move X can do so that, ..., X wins. If there is no such move then you want a move that at least guarantees a tie. If there is no such move, then for the purposes of this program, X can do anything at all.

The way you will check if there is such a move is the following. For each move you will temporarily add it into the board configuration and then recursively see what's the best thing player O can do. If your recursion returns saying ``O cannot guarantee either a win or tie'' then that means this move guarantees a win for X (you should think about this). If your recursion returns that O can guarantee a tie but not a win, then this means the move you tried for X guarantees a tie for X (again you should think about this) so you should remember this move in case none of the remaining are any better for X. If your recursion returns that O can guarantee a win, then this is a losing move for X so you should keep going and try the remaining possible moves for X.

We now ask you to answer the following questions, which are related to what you will be doing in your programming assignment. Show your work in your answers to questions C and D.

C.

Suppose you have a board with C columns and R rows. Suppose also that in each player's turn, the current player always has C choices of which move to make (this is a little bit of an overcount, but not too bad) and suppose also that the game continues until C times R moves have been made (this is also a bit of an overcount since often the game ends before all squares are filled). Under these assumptions, give a bound on how long the recursive procedure described above would take to figure out the best first move as a function of C and R. (use O notation)

D.

Again, say there are C columns and R rows. In a legal configuration, each square either is blank, has an X, or has an O. In addition, if a square is blank, all squares above it must be blank too. Use both of these facts to give an upper bound on the number of different configurations as a function of C and R (use O notation).

E.

As R and C get large, which is greater: your answer from (C) or your answer from (D)?

F.

In just a few sentences, say why your answer from (E) suggests using a memoizing strategy for speeding up performance.

Extra credit.

Do item ``C'' above, but without the assumption that the current player always has C choices. For instance, once column 1 has R squares filled, you can no longer move into column 1. You should still assume the the game continues until all squares are filled. Give an exact formula. This is a hard question. Try to solve it for the special case of two columns (C=2).

2. Programming assignment

2.1 The files board.c and board.h

To help you with this assignment, we have supplied you with a C++ class called Board, defined in the file board.h and with member functions in the file board.c. A Board stores the moves made so far, as well as providing many useful operations, including displaying a board, determining if a move is legal, determining if a game is over, and determining who has won. Feel free to modify the class definition if you want to (though there is no need to do so); we are simply providing it to you to make your life easier.

There are 3 important defined constants used in the definition of a board: the number of rows, the number of columns, and the number needed in a row to win the game. These are called ROWS, COLS, and NEEDED_TO_WIN, respectively. You can change these to modify the parameters of the game.

The Board class contains the following useful member functions.

• int Board::is_full(int col) is a simple function that returns 1 if column ``col'' is full and 0 if it is not.

• void Board::make_move(int col, char who) is another simple function that makes a move in column ``col'' for player ``who''. Legal choices for ``who'' are XPLAYER and OPLAYER (defined in board.h).

• void Board::unmake_move(int col) undoes the most recent move in column ``col''.

• The most interesting function (and most painful to write, which is why we did it for you, though you may feel free to modify this if you wish) is the query_status function, defined as:

           char Board::query_status()
  

  This function will tell you if the game is over, and if so, who won. Specifically, this function returns the constant NON_TERMINAL if the game is not over yet, XPLAYER if the game is over and X has won, OPLAYER if the game is over and O has won, or TIE if the game is a tie.

• Finally, we have overloaded the operator << to print out a board. You can print out the boards in the same manner that you would use this operator to print an integer, character, etc.

We have also provided the following functions that you may find useful in part 3.

• int Board::hash_me(int n) generates a number between 0 and n-1 that is a function of the board state. You should feel free to modify this function if you want to try a different hash function (but you don't need to).

• We have also overloaded the equality ``=='' operator so that it works correctly on Boards. Since Boards have no dynamically allocated memory, the standard assignment operator `` =' works correctly on them as well.

2.2 Your job

Your first programming task is to write a computer program that plays the above game ``intelligently'' in the sense described in Section 1.2. The program's opponent will be the user. Given the board configuration, you will choose a move, the program will respond with its move in turn, and so on until there is a winner.

The way that we suggest you do this is to write a function called find_winner whose prototype is listed below.

verdict_s find_winner(Board b, char whose_turn);

The input to this function is a Board and a parameter saying whose turn it is to move (XPLAYER or OPLAYER). The function will return two things: (1) what the best move is for the player whose turn it is to move, where ``best'' is as defined earlier in this document, and (2) the value of that move, which is a char of value XPLAYER, OPLAYER, or TIE. What we mean by the ``value of the move'' is who the computer has determined will eventually win, assuming both players play optimally. Your routine will return these results in a verdict_s structure which is defined in the board.h header file. (Since the function needs to return two things, it is easiest to put these two things into a single struct). The verdict_s structure is defined like this:

struct verdict_s {
  int move;               /* which column to move in to */
  char result;            /* either XPLAYER, OPLAYER, or TIE */
};

We have provided to you a main routine that runs a game between a human and the computer. This program will will then keep track of the game, calling the find_winner routine to make the computer's moves. You may feel free to modify main if you wish, but you don't need to. We have also provided you with a ``stub'' version of find_winner that just returns the first available move.

2.3 Files supplied to you

The files you are given are in /afs/andrew/scs/cs/15-211/assignments/assign5. They are:

• board.h, which is the header file for the Board class

• board.c, which contains the Board member functions.

• connect.c, with function main, which runs a game between a human and the computer (who uses your find_winner function)

• player.c, which contains a stub of the find_winner function.

2.4 Assorted programming hints

In interpreted Objectcenter, these programs will run slowly on 3x3 boards or larger so you may wish to start with smaller boards. Or, you can use the swap command in objectcenter to have objectcenter compile your programs. For example, to compile the entire program, type swap board.c, swap connect.c, and swap player.c. (You can also compile just the board.c portion if you wish, which speeds things up reasonably well by itself.)

You may wish to test your program on small boards before trying it out on larger boards. To do this, you should change the defined constants in board.h. On a 2x2 board with 2-in-a-row needed to win, the first player is guaranteed a win. On a 3x3 board with 3-in-a-row needed to win, either player can force a tie. This is also true for a (3-column)x(4-row) board with 3-in-a-row needed to win. With a (4-column)x(3-row) board with 3-in-a-row needed to win, the first player is guaranteed a win. Keep this in mind when you test your program. For instance, if you are able to beat your program on a 3x3 board with 3-in-a-row needed to win, your program has some kind of problem. (This is how Spock determined that the on-board computers on the Enterprise were malfunctioning.)

2.5 What you should hand in

For this part of the assignment, you should write a function called find_winner and place it in a file called player.c. If you use a header file, please call it player.h.

3. Memoizing

In this part of the assignment you will create routines to implement memoizing of Connect-4 board positions using hashing. You will then use these routines to write a faster program for optimal play of Connect-4.

The idea is that before embarking upon a search, you can first see if you have already figured out the answer. Note that the question of ``who wins'' depends both on the contents of the board, and whose turn it is. However, notice also that once we specify who goes first, the question of ``who wins'' is solely determined by the contents of the board (since that determines whose turn it is). So, we may simply store the board contents in our hash table and not worry about also storing whose turn it is.

Your hashing scheme will use the ``separate chaining'' method for resolving collisions. As mentioned in class, the separate chaining method is one whose performance degrades gracefully as the ratio of number-of-elements to size-of-table increases. As part of this assignment, you will try out several hash table sizes and report on how this affects the speed of your program, as well as how the performance of your program with hashing compares to the performance without hashing.

3.1 Hashing

The first thing that you will need to do is to implement a class called Hash_table. We have given you the following definition in the file hash.h:

struct list_element {
  Board key;
  verdict_s value;
  list_element *next;
}
class Hash_table {
  public:
    Hash_table(int size);
    verdict_s *lookup(Board key);
    void insert(Board key, verdict_s value);
  private:
    list_element **table;
    int size;
}

In other words, a hash table is an array of pointers of type list_element*. Each entry in the array points to the first element in a linked list of list_element's. Each list_element is a structure that contains three things: a key (which in this assignment is a Board), a value (which in this assignment is a verdict_s), and a pointer to the next element in the list. You will write three routines that are needed to implement hashing. These routines are as follows.

• Hash_table::Hash_table(int size);

  This routine creates an empty hash table of the given size.

• verdict_s * Hash_table::lookup(Board key);

  This routine takes a key looks for it in the hash table. If it's not there, it returns NULL. Otherwise, it returns the address of the value associated to that item in the hash table. (The only reason lookup has return type ``verdict_s *'' instead of ``verdict_s'' is to easily allow the routine to say ``it isn't there'' by returning NULL.)

• void Hash_table::insert(Board key, verdict_s value);

  This routine inserts the key and value into the hash table. You may assume that the item is not already in the hash table. Remember, you are using separate chaining.

You may create additional ``helper'' routines if you wish. All the routines you write should be put in a file hash.c.

3.2 The faster game player

Now that you have implemented hashing, you will use it to incorporate memoizing into your find_winner function. If you used a good hash function, this should speed up your game-playing program. In order to simplify matters, you may wish to define a global hash table so that you don't need to pass it into find_winner as a parameter. In fact, we have defined one for you, that you may use by uncommenting the line ``#define USING_HASHING 1'' in connect.c.

3.3 Experiments

Experiment with different-sized hash tables and hashing versus not hashing. Pick a problem size where running find_winner without hashing on your computer takes at least a second or so to make the first move when it goes first. Try find_winner both with and without memoizing using hash tables of size 10, 1000, 100000. Try both without hashing. How long does it take the program to make the first move? (You can just time this with a watch or make your best guess.) Report your results in written.txt and give a couple sentences of explanation of your findings. Also, you will notice that if you type y to the question ``do you want to play again?'' and play several times, that your program is much faster in subsequent games. Why is that the case?

3.4 What you should hand in

Please place the functions for your hash-function class in a file called hash.c. Place the version of your find_winner function that uses hashing in the file memoplayer.c. Describe the results of your experiments at the end of your file written.txt.