Strategy Game Framework

The Java implementation of the strategy game framework is described here. Emphasis is on the concepts and the overall structure rather than the low-level detail, which is provided in the javadocs.

The interfaces and classes that comprise the strategy game framework all reside in the net.lurgee.sgf package. The code may be found in the sgf directory in the source code archive available on the downloads page. The structure of the sgf directory is as follows:

• src - Java source for the strategy game framework.
• test-src - Unit tests for the strategy game framework based on JUnit.
• doc-res - Resources referenced by javadoc comments in the code.
• 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.

The compiled classes are not packaged into a jar file, as it is more convenient to include the required classes directly when creating applets or midlets.

Features

The features of the strategy game framework include:

• Extensible, reusable framework for abstract strategy games.
• Lightweight and efficient.
• Employs a variety of search mechanisms, which can be tailored to the game being implemented.
• Includes supporting classes for rapid implementation of Java console applications and applets using the framework.

Future Features

Possible future features for the strategy game framework include:

• J2ME version.
• .net and/or .net compact version.

Object Pooling

The recursive process of searching game trees results in the creation of many short-lived objects, which keeps the garbage collector very busy and can have a detrimental affect on performance. It is therefore advantageous to reuse short-lived objects (especially those whose construction is expensive) as much as possible rather than creating new ones. For this reason, the strategy game framework employs an object pool, which maintains a pool of these objects for reuse.

The ObjectPool class realises this functionality by pooling homogenous objects that implement the Poolable interface. The responsibility lies with the code that uses objects from the pool to check the objects out of the pool, and to then check them back into the pool when it is done with them. Not checking objects back into the pool will result in a memory leak. ObjectPool creates new objects by reflection as they are required, so that the pool only contains the maximum number of objects that are required concurrently and no more.

Game Elements

Player

The Player interface represents a player in the game and should be implemented by games that use the strategy game framework to encapsulate the required properties of a player (such as the colour of the player's pieces).

Board

The AbstractBoard abstract class represents the board in the game and should be subclassed by games that use the strategy game framework to encapsulate the behaviour of the game being implemented. AbstractBoard implements the Poolable interface, as the game tree search process requires many short-lived boards, which are obtained from an object pool. AbstractBoard keeps track of the player whose turn it is to go, the last move that was played on the board and whether or not the game has ended.

The Position interface represents a position on the board and only needs to be implemented if used. Position is a marker interface - it does not specify any methods that need to be implemented. A marker interface is used to convey intention throughout the rest of the framework, which would not be evident if just Objects were passed around.

Move

The Move interface represents a move in the game and should be implemented by games that use the strategy game framework to encapsulate the required properties of a move (such as the start and end position on the board of the piece being played). Move is a marker interface - it does not specify any methods that need to be implemented. A marker interface is used to convey intention throughout the rest of the framework, which would not be evident if just Objects were passed around.

A factory class implementing the MoveFactory is used to create moves. This allows for reuse of immutable move objects in games that are suitable - these are games with a small finite set of possible moves (like reversi, which has 60 and connect-four, which has 7).

Evaluating Board State

Evaluator

An implementation of the Evaluator interface is used to score the game state for leaf nodes in a game tree. A game that uses the strategy game framework needs to implement this interface in a manner appropriate to the game being built. The range of scores returned by the evaluator is determined by the implementation.

Library

An implementation of the Library interface is used to select some moves from a library rather than generating and searching a game tree. A game that uses the strategy game framework that requires a move library (such as an opening book) needs to implement this interface in a manner appropriate to the game being built.

Game Engine

Searchers

The engine of the strategy game framework is the AbstractSearcher abstract class, which defines the base contract for all searchers that find the best move given a particular game state, and provides common functionality. Two subclasses are defined: AbstractSinglePassSearcher, which defines the base contract for a single-pass searcher, and IterativeSearcher, which implements iterative-deepening using an instance of a AbstractSinglePassSearcher to perform the actual searches.

AbstractSinglePassSearcher brings together the game elements, an evaluator and a move library to allow a move to be selected for a game state either by generation and search of a game tree or by lookup in a move library. Two subclasses are defined: NegamaxSearcher, which provides an implementation of a negamax-based game tree search with or without alpha-beta pruning, and NegascoutSearcher, which extends NegamaxSearcher to provide an implementation of a negascout-based game tree search.

Move Ranking

Ranking moves improves the search process. The MoveRanker interface defines a means to generically rank moves and should be implemented by games that use the strategy game framework to encapsulate a suitable ranking mechanism for the game. The interface includes a callback method that is invoked during the search process to allow move rankers to alter their state based on information gleaned during the search process. The KillerHeuristicMoveRanker class implements a move ranker that does just this to rank 'killer moves' appropriately so that they are searched first. KillerHeuristicMoveRanker can delegate ranking to another ranker if it is determined to not be a 'killer move'.

The MoveList class stores a list of moves ordered by rank. It can be configured to randomly rank moves with equal rank.

Listeners

As mentioned, implementations of MoveRanker used in a search are provided with feedback regarding the search process - specifically node evaluation. In addition, implementations of the SearchProgressListener interface may be provided to a searcher, which are provided with feedback too - iteration start/end, branching, node evaluation and leaf evaluation.

Other Artifacts

The GameContext class encapsulates global game information such as the list of players taking part in the game, and provides factories/pools for obtaining game entities.

Class Diagram

The UML sketch class diagram below shows the key classes that comprise the strategy game framework.