In this assignment, you will write a program to play a version of the "Connect-4" children's game. Connect-4 is like a game of tic-tac-toe on its side. The game has 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 the empty squares until either one player wins by getting a specified number of its marks in at consecutive positions "in a row" (row, column, or diagonal) or all the positions are filled. If all of the positions are filled and there is no winner, the game is a tie. Unlike tic-tac-toe, a legal move must be at the lowest empty space in a column. In other words, think of each column as a vertical container and your mark (X or 0) "falls" to the lowest unfilled position.
For example, if the board has 5 columns, 4 rows and 4 consecutive marks are needed to win, then the player has at most 5 choices for each move (the number of unfilled columns). A board where player X has won might look like the following:
. . . . X
. . . X O (a "." represents an empty square)
. O X O O
O X O X X
---------
0 1 2 3 4 (the column number)
(In your programs, you will be dealing with boards of any size where any number of consecutive marks is needed to win, it might be better called "Connect-N.")
Your task in the first two parts of the assignment is to write a program that plays Connect-N "intelligently" in the following sense. If there exists a strategy that guarantees it a win, then it will win. Otherwise, if there exists a strategy that guarantees it a tie, it will never lose. In the first part of the assignment, you will do this in a straightforward, but inefficient manner. Once the first part of the assignment is working, you will greatly improve its efficiency using a hash table which takes advantage of symmetry in the game. The first two parts of the assignment will both exhaustively examine the Connect-N game tree.
The basic idea of the exhaustive solutions is the following. Given a board configuration (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 make that assures that X will eventually win. If there is no move which guarantees X will win, you want a move that at least guarantees X a tie. If no such move can be found, then for the purposes of this program X can do anything at all (because if the other player chooses optimally X will lose no matter what).
The way that you will choose a move for X programmatically is the following. For each possible move, you will temporarily add it into the board configuration and then recursively see what is the best move that player O can make. If your recursion returns that "O cannot guarantee either a win or a tie," that means that the move that X tried guaranteed a win for X (you should think about this). If your recursion returns that "O can guarantee a tie but not a win," that means that the move that X tried guarantees a tie for X (so you should remember this move in case none of the other possible moves guarantee X a win). If your recursion returns that "O can guarantee a win" you know that X tried a losing move, so you should keep going and try the remaining possible moves for X.
In the first part of the assignment, you will write the method find_winner_exhaustive, which is declared in the following way:
public static Verdict find_winner_exhaustive(Board b, char whose_turn)
The input to the function is a representation of the board, and a character indicating whose turn it is to play (XPLAYER or OPLAYER). The function will return the best move for the player whose turn it is to move, and the value of that move which is a char of value XPLAYER, OPLAYER, or TIE. The "value" of the move is what your function has determined the outcome of the game to be (assuming both players play optimally). Your function will return these results in an object of type Verdict (see class Verdict). This function should follow naturally from the paragraph above.
In the second part of the assignment, you will write a method similar to find_winner_exhaustive, but much more efficient. This method, find_winner_hashing, is declared in the following way:
public static Verdict find_winner_hashing(Board b, char whose_turn)
This method will use a special separate-chaining hash table class (class Hash_table) to implement a memoizing strategy that eliminates re-expanding search states and takes advantage of the natural symmetry in the Connect-N board. The idea is that before exhaustively examining the game tree for a given board, you will check the hash table to see if your program has already expanded this board (or a symmetrical board) in the past. If you are forced to expand the board, you will store the results in the hash table for future use (so you will never have to expand it again). In the hash table, each Board configuration has an object of type Verdict associated with it (containing the best move for the current player, and the result of the game). The hash table class has already been created for you. In the find_winner_hashing method, you will need to call the hash table lookup and insert methods (see class Hash_table).
In the final part of the assignment, you will write the find_winner_heuristic method which is declared in the following way:
public static Verdict find_winner_heuristic(Board b, char whose_turn)
This method is unlike find_winner_exhaustive and find_winner_hashing in that you can only expand the game tree to a depth of three ply (you may examine the possible moves for the whose_turn player, the possible responses of the opponent, and then one more of the whose_turn player moves). YOU MAY NOT EXPAND THE GAME TREE ANY FURTHER THAN THREE PLY. By only examining three ply, you will be forced to choose a move without knowing the outcome of the game (without being able to "guarantee" a win, loss, or tie). The number of states that you expand will be much fewer, but your performance will suffer greatly compared to find_winner_exhaustive and find_winner_hashing. You should think carefully about how to choose a move when you don't have all of the information. What characteristics of a board are good for a player? We don't expect your heuristic method to be able to win or tie against the exhaustive and hashing methods, but it should be able to play intelligently. An intelligent heuristic will earn more points than one that picks the first available move.
We have provided a "main" routine that runs a game of Connect-N between your methods and the methods written by the TA. The main routine also keeps track of the number of states that you expand. The syntax for running the program is the following:
java Assign2 [ROWS] [COLS] [NEEDED_TO_WIN] [YOUR_METHOD] [OPPONENT_METHOD] [FIRST_OR_SECOND]
For the YOUR_METHOD and OPPONENT_METHOD parameters, input a 0 (zero) for the exhaustive method, a 1 for the hashing method, or a 2 for the heuristic method. For FIRST_OR_SECOND, input a 1 to go first (XPLAYER), or a 2 to go second (OPLAYER). For example:
java Assign2 3 3 3 0 1 1
This indicates a game with a 3 by 3 board and 3 consecutive marks needed to win, where the exhaustive method is called for your moves, the TA's hashing method is called for his moves, and you go first.
Experiment with different size boards, with different numbers needed to win, and going first or second. If you are using the exhaustive or hashing methods for your moves or the TA's moves, don't try a board larger than 4 by 4 (it will take far too long). On a 3 by 3 board, your exhaustive method and hashing method should be able to force a tie against the TA's exhaustive method or hashing method. For each method, compare the number of states expanded. You should see a marked difference between the methods.
Good Luck!
Revised on Monday, October 27, 1997