Connect Four

Connect Four is an old children's game consisting of a vertical plastic grid into which the players alternately drop colored checkers. A player wins when he or she manages to line up four checkers either vertically, horizontally, or diagonally. Here is a fairly sophisticated online version of the game that you can play against to get a sense of the game.

You are to finish the implementation of a computer version of the game by first writing the game rules and testing them with several "dumb" players, then writing a "smart" player that is capable of regularly beating the dumb players. Your player does not need to be as strong as the one in the example (although you can try it for extra credit). You also do not need to worry about updating the graphics to make the game look better.

Completing the Game

Currently, the game consists of two players that each move interactively. However, since the board does not correctly verify a legal move or when the game is over, nothing really happens. A legal move in Connect Four is specified by only its column. Since Connect Four is a vertical game, when you place a piece, it slides down the column until it hits another piece. Thus pieces are filled in from the bottom with no gaps in between. You should implement this "gravitational effect" by assigning the given piece value to the last possible empty space. There are several methods of the GameBoard class that need to be completed to make the game fully playable.

Note, your game must be written so that it works for any size board, any number of players, and any number of pieces in a row required. Although we may not test it, it should be possible to play the game with five players, needing five in a row, on a 100x100 sized board.

Making your own player

Create your own computer player by creating a class, StudentPlayer.

You should write the makeMove method such that it returns the column you think is the best move. At the very least, your code should win if possible (i.e., if you currently have three pieces in a row and the fourth space is free, you should take it), not lose when possible (i.e., if your opponent has three pieces in a row and the fourth space is free, you should block it) and otherwise move randomly. At the very least, this makes your piece better than any of the given players and difficult for a novice player to defeat.

Any intelligence you add beyond that will be extra credit. Intelligence in this case requires you to learn more about the game and how to build and block threats (i.e., three in a rows). There are several algorithms for doing this, including one that is perfect (i.e., cannot lose if it is the first player). Essentially, the basic idea is to determine how many possible threats each space on the board contributes to and rank your move accordingly. For example, it should be clear that moving in the middle is a better initial strategy than moving in a corner since more winning combinations are possible from the middle (i.e., at least both left and right horizontal and diagonal directions).

The following resources may help you to come up with some more intelligent strategies for playing the game:

• The Wikipedia entry on Connect Four
• A detailed analysis of Connect Four play by James Allen
• Psuedocode for a Connect Four player by Keith Pomakis

Submitting your work Electronically

When you are satisfied you have completed the problems above, you should electronically submit your project through Eclipse. A submission is not considered complete unless it includes all the Java code for the project (both what you have written and the code provided when you downloaded the project) and a README file as described here.