PS-6, due Nov 18

Connect 4

Important organizational notes

For this assignment, you are permitted to work with one other student currently in the class. You do not have to work with someone else, but you have the option of doing so. If you choose to work with a partner, you will both get the same grade on the assignment.

There will be no penalty, in terms of points, for working together on this assignment. Please make sure that both of you submit the code electronically. When you submit on Blackboard, be sure to state the name of your partner in the comments section.

You should weigh whether you will get more out of this assignment working alone or with someone else. The choice is up to you.

If you choose to work with someone else, pick your partner carefully. Make sure that there are times that you are both available to work together. If you frequent the lab and you notice someone else who often is there when you are, that person might be a good choice as your partner.

General Instructions

Before you do anything, please read the entire assignment carefully. It contains suggestions which can save you a lot of struggle later on.

Background on Connect 4

Connect 4 is tic-tac-toe with gravity played on a board with 6 rows and 7 columns. As the name implies, the goal is to get 4 in a row (vertically, horizontally, or diagonally). The following is an image of a Connect 4 board taken from Wikipedia:

Checkers are dropped at the top of a column and fall until they reach the bottom or land on another checker.

An applet that lets you play against a Monte-Carlo implementation of the puzzle is on this web page. However, your solution should generally beat this program.

You are to write a game-tree search program using alpha-beta pruning to play Connect 4. The Kalah program gives you the general outline of such a program. I have provided three interfaces that you should use: Connect4State, Connect4View, and Player. These three files are combined in the zip file: provided.zip.

I have also provided you with a graphical user interface (and some other methods to be described later) in the jar file Connect4.jar. Use the method described in SA-2 to add this file to your project. Once you have done so you can create a Connect4ViewGraphical object for communication between your game and the world, using a default (no-parameter) constructor. (Playing it this way is a lot more fun that a text interface!)

One point about the graphical view: its reportMove puts the thread to sleep for a half a second. This prevents moves from occurring so quickly that you can't see where they were played. However, this also means that funny things can happen if your program changes the state that has been passed to the graphical view during that half second. Checkers can appear and disappear and jump around. If this happens make a copy of the state and pass that to the view, so that it will not be changed.

Programming Exercises

You should create the following classes, along with any other clases needed to implement them:

A controller class to play the game, similar to Kalah. I recommend using the trick of looking for substrings of names to pick which sort of Players should be created as the first and second player.
A model class that implements Connect4State and holds information about the Connect4 game. Note that this interface defines a number of constants. Use these in your program, particularly the ones that describe the characters representing checkers and and empty space, so that you can use Connect4ViewGraphical to display the game. Note that your model class can include additional methods besides those required by the interface.
Two classes that extend the Player abstract class. One should be a human player. The other should be a computer player that uses alpha-beta game tree search to pick moves. Both should communicate with the world via a Connect4View object that is created in your controller class.
A class that implements Connect4View and provides interaction via text read from the keyboard and printed on the Console.

These should allow you to play Connect4.

One of the challenging aspects of this project is to create a good static evaluation function. For Kalah this was easy. For Connect 4 it will require a bit more thought and programming. Part of your grade is coming up with a reasonably good static evaluation function. Some things to consider when planning your static evaluation function:

In order to win a Connect 4 game you have to get 4 checkers in a row. Therefore the groups of 4 board squares in a row that are useful are the ones that do not contain at least one of each player's checkers. (A 4-in-a-row that contains a checker belonging to each player cannot eventually be a winning 4-in-a-row.) We will call such a set of 4 squares in a horizontal, vertical, or diagonal line an unblocked 4-in-a-row. So maybe your static evaluation function should look at unblocked 4-in-a-rows.
Having one checker in an unblocked 4-in-a-row is useful, but having 2 checkers in an unblocked 4-in-a-row is better and having 3 checkers in an unblocked 4-in-a-row is a whole lot better. One way to create a static evaluation function is to count unblocked 4-in-a-rows for each player, weighted by the number of checkers in the 4-in-a-row.
Implementing the static evaluation function described above is sufficient for full credit for the static evaluation function. However, there are other things that you could consider. Unblocked 4-in-a-rows that contain 3 checkers and where there is no checker directly below the place where the fourth checker would go are threats. Your opponent cannot immediately block this 4-in-a-row. If the opponent runs out of other moves and is forced to play in the square below the missing checker you can then complete the 4-in-a-row. Some threats are more valuable than others. Can you evaluate and incorporate threats into your static evaluation function? Extra credit for doing this or coming up with other ways to improve your static evaluation function.

Some things to be careful about

The bottom row of the board is row 0 of the matrix.
The first subscript is the row number and the second is the column number.
The move numbers returned by getMove are 0-6, not 1-7.

Testing

You must test your static evaluation function separately. If you just plug in a static evaluation function into a game tree search and look ahead a bunch of moves you will never know if it is working correctly or not.

The easiest way that I found to handle this was to write a small main program in the Connect4Game class that created a game with two human players and a graphical or text view. While the game is not over it gets and makes moves, displaying the board and printing out the value of the static evaluation function after each move. Then you can compare the values to what you get by doing the calculation by hand.

You can also test the static evaluation function in the context of the search. Search one or two levels deep, and print out the board and the value each time the static evaluation function is called. (Use your text view.) This way you can make sure that the game tree search is correctly picking the best move. You can also print the low and high values from alpha-beta pruning to see if that is working correctly.

Test Runs to Turn In

Include a test run that shows a game between your human player and your computer player using your text view. You should also include demonstrations of your error handling for things like entering non-numbers or out of range numbers, etc.

Also include test runs that show that you have tested your static evaluation function and it works correctly, and that the game tree search picks the correct move when looking ahead 2 moves.

Extra Credit

Implement a player that uses Monte Carlo evaluation to pick its next move.
Implement a hybrid player that uses game tree search, but uses a Monte Carlo static evaluation function.
Implement an especially nice static evaluation function and explain why it is good.
Implement improvements to speed up your alpha-beta search. These can include things like choosing a better order for considering moves. (Some EC for a fixed order that is better than left to right. More extra credit for sorting by static evaluation. Still more EC for ordering based on shallow search.)
Implement improvements to speed up your static evaluation and search code. Examples: A move in Kalah often changes most of the board, and the board was small. Therefore creating a new state for each recursive call was a reasonable choice. However, in Connect 4 the board is larger and a move changes very little, and it is easy to write an undoMove method. Therefore it is possible to make and undo moves and have only one game state in your game tree search that gets modified as you go down into and come back out of deeper levels.
The jar file also includes my version of a computer player. The class is ComputerPlayerABPlus, and its contructor has two parameters: a String name and an int desired look-ahead depth. Therefore you can play your game tree search player (or Monte Carlo player or hybrid player) against mine. You might find it interesting to play against it as a human player. Substantial extra credit (plus bragging rights) if your player beats mine when mine is playing with 16 lookahead. For full credit it should win as both the first and the second player. To be fair your program has to take about the same amount of time that mine does - the slowest moves take about 30 seconds on my Macbook Pro, and an entire game with the program playing itself takes just over 5 minutes. You can also try it on levels 14 and 12, which are much faster. Because of the horizon effect my player tends to play very defensively on odd depths, where the opponent has the last move.
Implement your own version of a graphical view.

Blackboard submission

Submit electronically via Blackboard the zip file of a folder that contains (1) all the java files needed to run your program, and (2) the text produced by the test runs described above. If you choose to do the extra credit, include those java files and text produced by their test runs also, but keep the extra credit files separate from the regular ones so that any errors in your extra credit work will not affect your grade for the regular assignment.

If you work with a partner, please make sure that each of you submits via Blackboard and be sure to state the name of your partner in the comments section.

Grading rubric

Total of 130 points

Correctness, Efficiency, and Elegance (85 points)

15	Code compiles and runs
10	Controller class
15	Game state class
5	Human player class
10	Computer player class
10	Correct implementation of game tree search with alpha-beta pruning
10	Static evaluation function
10	An implementation of View that uses text I/O

Structure (20 points)

13	Good decomposition, proper separation into model/view/controller.
3	Proper use of instance and local variable
2	Instance variables are private
2	Proper use of parameters

Style (10 points)

2	Comments for classes
2	Comments for methods (purpose, parameters, what is returned) in JavaDoc form.
2	Good names for methods, variables, parameters
2	Layout (blank lines, indentation, no line wraps, etc.)
2	Other unspecified style issues

Testing (15 points)

10	Include the test runs specified above. In particular show that your static evaluation function works correctly and that the game tree search works correctly for depth 2 lookahead.
5	Demonstrate that the text view works for error and boundary cases

Extra Credit

15	Player using Monte Carlo move choice
15	Player using hybrid move choice
10	An especially nice static evaluation function
10	Improve alpha-beta pruning
10	Speed up static evaluation and game-tree code
25	Implement your own graphical view
25	Beat my computer player at 16 lookahead (both directions), while using a comparable amount of time.
?	Other interesting additions