Connect-Four Code

The Java implementation of a set of classes that implement the game of connect-four using the strategy game framework is described here. The implementation of a console application and an applet using these classes and the common classes is covered too. Emphasis is on the concepts and the overall structure rather than the low-level detail, which is provided in the javadocs.

The code may be found in the connect4 directory in the source code archive available on the downloads page. The structure of the connect4 directory is as follows:

• src - Java source for the connect-four classes, the console application and the applet.
• test-src - Unit tests for the connect-four classes based on JUnit.
• bin - Target directory for classes when the code is built with Ant.
• test-bin - Target directory for unit tests when the code is built with Ant.
• test-results - Target directory for JUnit test results when the code is built with Ant.
• doc - Target directory for javadocs when the code is build with Ant.
• res - Image and audio resources used by the applet.
• www - Test web page for the applet.
• dist - Target directory for the applet jar when the code is built with Ant.

Package Diagram

The package diagram below shows the package dependencies for the connect-four code.

Connect-Four Implementation

Features

The features of the connect-four implementation include:

• At the lowest level, game play is of a decent level, but can be beaten by novice to good players.
• At higher levels, game play is good enough to all (human) opponents.
• Performance is good enough for the classes to be used on a mobile device.
• The computer does not always make the same moves, so game play does not feel 'mechanised'.

Constants

The Colour class defines constants for red and yellow, as well as constants to indicate 'any piece' (red or yellow) and 'no piece'.

Board

The Connect4Board class extends the AbstractBoard class from the strategy game framework to provide the specifics of the board in connect-four. Squares on the board are identified by x and y co-ordinates, which are one-based (so, 1 to 7 horizontally and 1 to 6 vertically).

To allow entire rows on the board to be checked quickly and to facilitate bitwise-operations on boards, the 42 squares on the board are represented by a single 6-element array, each element of which represents a horizontal row of 7 squares. Each set of 2 bits, starting with the 2 least significant bits, represent an individual square in the row. Each square on the board may be empty, or may contain a red piece or a yellow piece. The values are:

• Colour.NONE (0) - The square is empty.
• Colour.RED (1) - The square contains a red piece.
• Colour.YELLOW (2) - The square contains a yellow piece.

For example, if the value of an element in the array (which represents one of the rows on the board) is 0x0A51 (00101001010001 in binary), the row is as follows:

To allow possible winning groups to be examined quickly, a static map of squares to winning groups, numbered 1 to 69 (in the same way as in the possible winning groups diagram) is held, as well as the reverse (winning group to square), which is generated initially. A count of the number of squares that a player has filled in each possible winning group, as well as whether or not the group has been broken by an opponent piece, is maintained to assist the evaluation process.

Player

The Connect4Player class implements the Player interface from the strategy game framework to provide the specifics of a player in connect-four. Each player is identified by the colour that they are playing (red or yellow). This class includes static instances for each of the two players and a static accessor method to obtain references to them.

Move

The Connect4Move class implements the Move marker interface from the strategy game framework to provide the specifics of a move in connect-four. As playing a move in connect-four simply involves a player selecting a column to drop a piece into, the Connect4Move class represents a move by the column on the board (the x co-ordinate). The colour is not associated to the move as a move is always associated to a player, so it is implicit. The Connect4Move class is immutable.

The Connect4MoveFactory class implements the MoveFactory interface from the strategy game framework to provide methods that return instances of Connect4Move given the x co-ordinate. As the Connect4Move class is immutable and there are only 7 possible moves in connect-four, immutable instances are created once by the factory and re-used. As thousands of moves are obtained and used during the search process, using immutable instances rather than instantiating moves whenever they are used has a substantial positive impact on performance.

Ranks for moves are determined by the Connect4MoveRanker class, which selects a rank for a particular move from a static table based on the position on the board. Moves that are likely to be good moves (without considering the state of the board, as it's a static table) are given higher ranks. The ranking table is therefore based on the diagram showing the distribution of possible winning groups to squares. As lists of moves are sorted according to rank, this approximation helps to increase the likelihood of alpha-beta cut-offs during a tree search.

Evaluator

The Connect4Evaluator class implements the Evaluator interface from the strategy game framework to provide the means for scoring the state of the board, which is used when searching a game tree to determine the best move. Evaluation is based purely on maximising the number of pieces a player has in unbroken possible winning groups, whilst minimising the same count for the opponent. Different weights are given to unbroken possible winning groups depending on the number of the player's pieces in the group, as follows:

• If any group has all four squares filled with the player's pieces, the board is given a constant score of 5000.
• Otherwise, the score is (4 * 2 ^ n3) + (2 * 2 ^ n2) + (2 * n1), where n3 is a count of the number of unbroken possible winning groups that have three squares filled with the player's pieces (and therefore one open), n2 is a count of the number of unbroken possible winning groups that have two squares filled with the player's pieces (and therefore two open) and n1 is a count of the number of unbroken possible winning groups that have one square filled with the player's pieces (and therefore three open).

This strategy is based on the premise that unbroken groups containing increasing numbers of the player's pieces become exponentially more valuable. The above calculation is done for the player and for the opponent and the final score for the board is the player's score minus the opponent's score.

Library

The Connect4Library class implements the Library interface from the strategy game framework to provide a simple move library for selecting the first and second moves of the game only, based on some simple rules for opening moves - it is best for the starting player to play in the middle column (4) and for the second player to play in one of the four outer columns (1, 2, 6 or 7).

For the starting player:

• Always play in column 4.

For the second player:

• Randomly select one of the four outer columns, if there is already a piece in that column (which means the starting player played there), select another.

Connect-Four Console Application

The connect-four console application uses the classes described above, as well as the common console classes and the strategy game framework. This is a full implementation of the game of connect-four, in which each player can be played by a user or by the computer at varying skill levels. The console application looks something like this:

Purpose

The user interface of the connect-four console application is less than elegant and is not conducive to good game play. Its primary purpose is to assess the connect-four implementation. Playing the computer against itself is a particularly good way of assessing the effectiveness of various strategies. A second connect-four evaluator class, AlternativeEvaluator, is included in the application to allow strategies to be changed and tried against the default evaluator in the connect-four implementation.

Alternative Evaluator

The AlternativeEvaluator class implements the Evaluator interface from the strategy game framework and is a copy of the Connect4Evaluator class from the connect-four implementation. It is included in the console application to allow the effectiveness of various strategies to be assessed, as described above in the purpose section.

Statistics

The common GameStats, PlayerStats and ResultStats classes are used to store statistics for the games played.

Game

The Connect4Game class extends the common console AbstractGame class and contains the static main method, which is the entry point for the application. The main method creates a singleton instance of the Connect4Game class and calls its run method, which initiates the application.

Connect-Four Applet

The connect-four applet uses the classes described above, as well as the common applet classes, the common AWT classes and the strategy game framework. Below is a screenshot of the applet in action:

Features

The features of the connect-four applet include:

• Colourful graphical user interface.
• Simple layout, with all options available directly on the main screen (rather than popup menus).
• Four difficulty levels ranging from easy to difficult (can be changed during a game).
• User can play red or yellow (can be changed during a game).
• Unlimited undos.
• Animated moves.
• Audio (which can be disabled).
• Visual indication of winning group of pieces.

Game Play

The connect-four applet uses iterative deepening with a negascout searcher. The difficulty levels 1 to 4 (smiley face to worried face on the GUI) map to tree depths and evaluation thresholds as follows:

Level	Maximum Search Depth	Evaluation Threshold
1	4	250
2	10	5000
3	12	50000
4	16	100000

GUI Design

The applet is fairly small (240x320 pixels). This size was specifically selected as it is a common size for PDA devices and a PDA version of connect-four is planned. So, rather than designing the user interface twice, this same interface will be used for the PDA version.

Constants

The AppletConsts class contains common constants that are used throughout the applet.

Applet

The Connect4Applet class extends the common applet AbstractGameApplet class and creates the appropriate main window for the game.

Main Window

The Connect4MainWindow class extends the common applet AbstractGameWindow class and contains (and creates) several widgets, as shown below, each of which is responsible for painting an area of the window and managing mouse events generated within them. The Connect4MainWindow class overrides the paint method to appropriately paint the display. The widgets contained in the window paint themselves.

The undo, help and new game icons are not stateful, whilst the colour, level and sound are. Only the undo and new game icons are ever disabled during the game, so only these two are provided with disabled images on construction.

The main window also contains two other windows: the help window and the new game option window. Both are created hidden and only made visible when they are required. The help window is an instance of the common AWT TextWindow class and the new game option window is an anonymous inner class that extends the common AWT OptionWindow class.

Board

The Connect4BoardWidget class extends the common applet AbstractBoardWidget class and overrides the paint method to paint the connect-four board and the pieces on it. It implements the common applet WidgetEventListener and Animatable interfaces and is registered as a listener for widget events. This widget deals with mouse events relating to the user moving the mouse over the board, and clicking on a column (making a move).

Status Bar

The Connect4StatusWidget class extends the common AWT Widget class and overrides the paint method to paint the status bar, which contains an indication of the last move played and a status message (which is often blank). It implements the common applet WidgetEventListener interface and is registered as a listener for widget events.

Game

The Connect4Game class extends the common applet AbstractGame class and provides implementations of the abstract methods in this class appropriate to the game of connect-four.