Reversi Code

The Java implementation of a set of classes that implement the game of reversi 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 reversi directory in the source code archive available on the downloads page. The structure of the reversi directory is as follows:

src - Java source for the reversi classes, the console application and the applet.
test-src - Unit tests for the reversi 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 reversi code.

Package diagram for reversi code

Reversi Implementation

Features

The features of the reversi implementation include:

At lower levels, 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 beat most players most of the time.
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'.

Improvements

Improvements that could be made include:

The evaluation function could be made stronger; in particular, support for stable pieces and parity could be introduced.
A more fully implemented opening-move library.

Constants

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

The Direction class defines the eight directions in which a square on the board may be adjacent to another square on the board. These are the usual orthogonal directions: up, down, left, right; as well as the diagonal directions: up-left, up-right, down-left and down-right.

Board

The ReversiBoard class extends the AbstractBoard class from the strategy game framework to provide the specifics of the board in reversi. Squares on the board are identified by x and y co-ordinates, which are one-based (so each has the range 1 to 8).

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

Colour.NONE (0) - The square is empty.
Colour.BLACK (1) - The square contains a black piece.
Colour.WHITE (2) - The square contains a white piece.

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

Implementation of a row of the board

To allow valid moves to be determined quickly, the empty squares that are adjacent to black or white pieces on the board are maintained in a 2x8 array. Adjacent means in a square next to that piece, orthogonally or diagonally. The first array is for the black pieces on the board and the second for the white. Each element in each of the two arrays represents a row on the board, with each group of eight bits representing a square in that row, starting with the 8 least significant bits (for the first column). Each set of 8 bits represents a bit mask containing the directions that the square is in with respect to the adjacent black or white piece using the 8 directions defined in the Direction class. For example, the adjacents for white are shown on the section of board below:

Implementation of the adjacent array

The values in the adjacent array for white for these three squares are:

Direction.RIGHT | Direction.LEFT | Direction.UP | Direction.UP_RIGHT
Direction.UP_LEFT | Direction.UP_RIGHT
Direction.UP

The ReversiDifferenceBoard interface specifies only the methods that are applicable when two boards are compared with the compare method in ReversiBoard.

Player

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

Move

The ReversiMove class implements the Move marker interface from the strategy game framework to provide the specifics of a move in reversi. As playing a move in reversi simply involves a player placing a piece on the board, the ReversiMove class represents a move by the board co-ordinates (x and y) that a piece is being placed on. Internally, this is stored as an instance of ReversiPosition. The colour is not associated to the move as a move is always associated to a player, so it is implicit. The ReversiMove class is immutable.

The ReversiMoveFactory class implements the MoveFactory interface from the strategy game framework to provide methods that return instances of ReversiMove given the x and y co-ordinates, or a string in the usual reversi notation (such as 'a8'). As the ReversiMove class is immutable and there are only 60 possible moves in reversi, 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 ReversiMoveRanker 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. Corners are given the highest rank, X-squares the lowest rank, and so on. 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 ReversiEvaluator 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 on some of the common reversi strategies. The overall score is determined by summing the scores for each of the implemented strategies. Some strategies are applied only to pieces that have changed (placed on the board or flipped) from the original state of the board (the board at the foot of the game tree), some only to placed pieces, and some to all pieces on the board.

Piece differential - a count of the number of pieces the player has gained minus the same count for the opponent; only pieces that have changed are considered.
Mobility - a count of the number of valid moves the player has minus the same count for the opponent; all pieces on the board are considered.
Potential mobility - a count of the number of potential moves (open squares that are adjacent to an opponent's piece) that the player has minus the same count for the opponent; all pieces on the board are considered.
Corners - a count of the number of corners the player has gained minus the same count for the opponent; only pieces that have changed are considered.
Edges - a count of the number of A-squares and B-squares the player has gained minus the same count for the opponent; only pieces that have changed are considered.
X-squares - a count of the number of X-squares adjacent to open corners the player has gained minus the same count for the opponent; only placed pieces (not flipped pieces) are considered.
Wipe-out prevention - a move that results in a wipe-out for the player (a player losing all their pieces) is given a score of -1000.

Stage of the game - different weights are applied to each of the calculated scores for the various strategies. As indicated in the table below, these weights are changed depending on the stage of the game, which is represented by the number of pieces on the board. Some strategies are not relevant in certain stages of the game - the weight is set to 0 at these times.

	Up to 16	17 to 32	33 to 48	49 to (64 - tree depth)	(64 - tree depth) or more
Piece differential	0			4	1
Potential mobility	5	4	3	2	0
Mobility	7	6	5	4	0
Edges	0	3	4	5	0
Corners	35				0
X-Squares	-8				0

Library

The ReversiLibrary class implements the Library interface from the strategy game framework to provide a simple move library for selecting the second move of the game only. One of the opening moves is randomly selected, weighted by the effectiveness of the above evaluation scheme with each opening, as follows:

If the tree depth is 3 or less (which implies the computer level is low):

The parallel opening is selected 11% of the time,
the diagonal opening is selected 33% of the time,
the perpendicular opening is selected 56% of the time.

If the tree depth is greater than 3:

The diagonal opening is selected 33% of the time,
the perpendicular opening is selected 67% of the time.

Reversi Console Application

The reversi 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 reversi, 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:

Screenshot of reversi console application

Purpose

The user interface of the reversi console application is less than elegant and is not conducive to good game play. Its primary purpose is to assess the reversi implementation. Playing the computer against itself is a particularly good way of assessing the effectiveness of various strategies. A second reversi evaluator class, AlternativeEvaluator, is included in the application to allow strategies to be changed and tried against the default evaluator in the reversi implementation. Assessing strategies should involve many games being played (at least 20, but more is better) to even out the results. Various tree depths (usually 5 or more) should be used for both players, unless the strategy being assessed is specifically to improve shallow searches. Also, various combinations of each evaluator being used for the starting player and the second player should be assessed to ensure that it is not too effective for only the one (for example, this would be important for parity).

Alternative Evaluator

The AlternativeEvaluator class implements the Evaluator interface from the strategy game framework and is a copy of the ReversiEvaluator class from the reversi 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.

For example, changing the weights for all the strategies to 0 except for piece differentials makes the evaluator operate on the greed principle, which is it always plays the move that results in the most pieces being won. This is a poor strategy and if played against the default evaluator in the reversi implementation, it should lose most of the time with a tree depth of 1 for both competitors, and should always lose with a higher tree depth.

Statistics

The ReversiGameStats, ReversiPlayerStats and ReversiResultStats classes extend the common GameStats, PlayerStats and ResultStats classes to add additional stats specific to reversi.

Game

The ReversiGame 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 ReversiGame class and calls its run method, which initiates the application.

Reversi Applet

The reversi applet uses the classes described above, as well as the common applet classes, the common AWT classes and the strategy game framework. Below are two screenshots of the applet in action:

Screenshot of reversi applet

Features

The features of the reversi applet include:

Colourful graphical user interface.
Simple layout, with all options available directly on the main screen (rather than popup menus).
Graphical indication of the valid moves on a player's turn.
Six difficulty levels ranging from easy to difficult (can be changed during a game).
User can play black or white (can be changed during a game).
Unlimited undos.
Animated moves.
Audio (which can be disabled).

Game Play

The reversi applet uses iterative deepening with a negascout searcher. The difficulty levels 1 to 6 map to tree depths and evaluation thresholds as follows:

Level	Maximum Search Depth	Evaluation Threshold
1	5	250
2	7	1000
3	8	2500
4	9	7500
5	10	25000
6	16	50000

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 reversi 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 ReversiApplet class extends the common applet AbstractGameApplet class and creates the appropriate main window for the game.

Main Window

The ReversiMainWindow 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 ReversiMainWindow class overrides the paint method to appropriately paint the display. The widgets contained in the window paint themselves.

Main window in reversi applet

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 ReversiBoardWidget class extends the common applet AbstractBoardWidget class and overrides the paint method to paint the reversi 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 square (making a move).

Status Bar

The ReverisStatusWidget class extends the common AWT Widget class and overrides the paint method to paint the status bar, which contains a black piece and a white piece with an indication of whose turn it is; the score for each player; 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 ReversiGame class extends the common applet AbstractGame class and provides implementations of the abstract methods in this class appropriate to the game of reversi.

< PREVIOUS: Reversi

NEXT: Applet >