No fun. No games. Hah, well, perhaps there will be. This project is to implement the popular Milton Bradley game Connect Four, or, as it was called for hundreds of years, "The Captain's Mistress."
If you are unfamiliar with the rules of Connect Four, you have only to refer to the name of the game. Two players take turns placing red and black checkers into a vertical board. Gravity pulls each piece down until it hits either the bottom of the board or checker already placed. The object is to get four of your color checkers in a row.
Your job is to create a Connect Four game. Of course, we will be covering GUI, and so you will have to implement a GUI that allows two humans to play. The more interesting problem, however, is to create an artificial intelligence that will allow you to face off against the computer. Naturally, you'll want to make it multi-threaded as well, for speed increases. We're going to break it into 4 parts:
The traditional Connect Four game takes place on a grid with 6 rows and 7 columns. Surely, we can do better than that in CS190M. The user should be able to specify the size of the game in rows and columns. To run the game, the user should type the following from the command line:
java ConnectFour 6 7 5 2
We'll get to the other arguments soon, but the 6 and 7 refer to the rows and columns, respectively, of the Connect Four game.
Clearly, your main() method should reside in class called ConnectFour.java.
Your code must enforce standard rules: Four in a row horizontally, vertically, or diagonally wins. Ties are possible. A checker placed in a given column falls all the way to the lowest empty row. A checker cannot be added to a full column.
For our version of the game, black or red randomly goes first. Your code should make this choice using a Random object.
Since you will not be learning any Java GUI until a full week after the project is assigned, we have provided a sample GUI in class form for you to use to get your game working. You must download the three following files and put them in the directory with your source code in order to use this GUI.
The Board class takes an object that implements the Playable interface as a parameter to its constructor. Your ConnectFour class should implement the Playable interface. This interace is available here. Note that this file also defines the Checker enum used to represent a black, red, or empty space on the board.
The Playable interface contains the following method definitions:
boolean addChecker( int column )true if the add was successful and false if the column was full.int getRows()int getColumns()
The public methods you should be aware of in the Board class are:
public Board( Playable game )Board. This sets up the GUI and makes it visible. Closing the window will end the application.public setLabel( String text )"Red Player's Move (Human)" are expected to be displayed in this way.public void setButton( int row, int column, Checker color )
The supplied Board class uses the following image files. You are encouraged but not required to use these for your GUI class. These files must be saved in the directory that you run your code from in order for the GUI to function properly. Right click and choose "Save Link As..." to download to your local directory.
The functioning GUI should look something like the image below (scaled to take up less space):
At the heart of the AI is an algorithm called minimax. The idea behind it is very simple: Choose the move that maximizes your advantage and minimizes your opponent's advantage. A useful article about minimax can be found here. The purpose of this algorithm is to assign a numerical value to a particular move. Once the values have been determined, the move with the highest value should be made.
We will focus on a recursive method that implements the minimax algorithm. Below is the algorithm in pseudocode:
minimax( move, depth )
{
if the move is a winning move
return ∞
if depth = 0
return the heuristic value of the current move
alpha := ∞
for all possible opponent moves
alpha := min( alpha, -minimax( opponent move, depth - 1 ))
return alpha
}
Note that this is a recursive method. Each step taken is making a move. Thus, each subsequent call is multiplied by a -1 in order to minimize the opponent's advantage. Two calls deep, the two -1's cancel each other out to become positive once again.
The first segment of the algorithm gives back an infinitely good value if a winning move has been found. It may be useful to use Integer.MAX_VALUE to represent this quantity.
The next segment refers to the depth of recursion. As you know, there are finite possible games of Connect Four. Thus, it is possible to test all possible moves and counter moves until you reach a win for either the player or the opponent. Unfortunately, doing so is not practical in terms of time. Instead, the minimax algorithm is designed only to look ahead a certain number of possible moves and then stop. At that point, however, you need to give some indication of how well a given player is doing. To do so, we use a heuristic function which assigns a number to the value of the board.
Before we move on to the heuristic function, note that the depth of look ahead in the minimax function is given by the user at the command line. In the sample command given earlier:
java ConnectFour 6 7 5 2
The number 5 refers to the depth that should be given as a parameter to the minimax algorithm.
A good heuristic function can be difficult to create. We want something relatively simple that gives a good measurement of how well a player is doing. Essentially, we want some weighted measurement of how many collections of 3 checkers of the same color, 2 checkers of the same color, and single checkers we have gained from a move.
Our heuristic function will be focused on a single move at a given row and column. We will consider rows, columns, and diagonals separately
In a given row, we need to try all possible 4 unit row segments that overlap with the new move. For each possible segment, we sum up the number of checkers that are the same color as the new move as long as the opposite color of checker does not appear. For example:
We are assuming that the new move was made by Red at row 4, column 3 (using a 0-indexed system, starting in upper left corner). Thus, there are four possible 4 unit segments that overlap with this move. These four possible segments are indicated with red, green, blue, and magenta rectangles, respectively. The red rectangle contains only a single red checker in it, adding 1 to the heuristic. The green, blue, and magenta rectangles each contain two red checkers, adding 4 to the heuristic. We have a weighted system where single checkers count for 1, two close checkers count for 4, and three close checkers count for 32.
For a given move, we count the size of the column that is the same color. For example, in the previous row example, with the move at (4, 3), there is a stack of two checkers, adding 4 to the heuristic total. The only exception to this rule is when there is not enough room to total four. For example, if those two red checkers were at (1, 3) and (2, 3) with black checkers beneath them, we would not count them because they could not possibly make four in a row.
Diagonal heuristics are essentially the same as row heuristics. We try every possible diagonal segment that is 4 units long and also includes the new move.
The above example shows the segments for the heuristics for the diagonals that come down and right. There are only two 4 unit diagonally down segments that overlap with the move at (4, 3). The first is shown with a blue rectangle and adds 1 to the total heuristic. The second is shown with a magenta rectangle and does not add anything to the heuristic because it includes a black checker.
Combining row, column, downward and upward diagonals into the final heuristic value for placing a red checker at (4, 3) gives 1 + 4 + 4 + 4 = 13 for the row, 4 for the column, 1 for the downward diagonal, and 1 for the upward diagonal, yielding a total heuristic value of 19 for this move. This final value would be used as the heuristic in the minimax algorithm.
Of course, this is a multicore course, and the AI can be very slow. By using threading, it is possible to speed it up. As you may have guessed by now, the fourth user-specified parameter when ConnectFour is invoked is the number of threads:
java ConnectFour 6 7 5 2
In this case, the number 2 represents the number of threads used to attack this problem.
The AI itself is going to be very difficult to code. The ideas are not complicated, but it is easy to get caught in boundary cases and ArrayIndexOutOfBoundExceptions. Because of this, we are giving you three options for making the AI multi-threaded:
wait()/notify() calls.Once you get everything working with our supplied GUI, you should create your own. The GUI ideas needed are not extremely complex, but getting GUIs to work can be time consuming unless you have experience with them.
Your basic window should be a subclass of JFrame. You will only need JButtons for the individual checker space. Each button should be 75 x 75 pixels in size. Again, you are encouraged to use the images provided earlier in the specification. Clicking on any button in a given column should attempt to add the current player's checker to that column.
The GridLayout layout manager is the obvious choice for the grid of buttons. You will need at least one additional JPanel in order to create this grid and still add the JLabel for output below it.
At the beginning of the game, a modal dialog box should pop giving the user the choice of playing against another human or the computer. This dialog box should look like this:
To create this dialog box (and get the user's choice back from it), the JOptionPane class has many useful static methods for creating such boxes on the fly. Here is a wonderful tutorial on the subject. Although with this design the computer will always play black checkers, remember that the color that goes first is determined randomly.
The GUI should not be difficult compared to the rest of the assignment. However, if you run out of time, you can use our supplied GUI for a 15% reduction in your final grade.
New Game StartedRed Player's Move (Human)Black Player's Move (Human)Black Player's Move (Computer)Red Player Wins! (Human)Black Player Wins! (Human)Black Player Wins! (Computer)Game Ends in a TieWhen you have tested your code and are satisfied with the results, you will need to turn in all of your Java source files, including at least ConnectFour.java. Make sure you run and test your code from the command line.
To turn in your project, navigate to the directory containing your source files. Then type the following command:
turnin -v -c cs190m -p project4 *.java
You can submit your code as many times as you want. Submit early and often.
Your project must compile with the command javac ConnectFour.java and run with the command as specified above.
Grading will be done based on the following guidelines:
30 points will be awarded for having a functional Connect Four game that can be played by two humans. Winning and tying rules must be enforced, and no illegal moves should be possible.
You can earn up to 30 points if you correctly implement the minimax algorithm for various amounts of user specified search depth.
If you choose not to thread the AI, you will forfeit all points in this category. Standard thread division of work can earn you up to 10 points. Using the thread pool solution gives you a chance to earn all 15 points.
You can earn up to 15 points for implementing a GUI with all the functionality of the one we provide.
As always, you should use good programming style and commenting in order to receive full credit. Every Java file should have a comment header at the top giving your name, the course, the project, the date, and a short explanation of the class(es) in the file.
Note: Submissions which do not compile will automatically score 0 points.
As always, be sure to uphold the high standards of academic honesty required by this course. Failure to do so can lead to consequences as dire as failing the course and expulsion from the school. If you have any questions about whether or not a given action is allowed, please ask your instructor or TA.