A Java Framework for Search and Game Playing:
The general interface for the Java classes that we will develop in this section was
inspired by the Common LISP game-playing framework written by Kevin Knight
and described in (Rich, Knight 1991). The abstract class GameSearch contains the
code for running a two-player game and performing an alpha-beta search. This class
needs to be sub-classed to provide the eight methods:
public abstract boolean drawnPosition(Position p)
public abstract boolean wonPosition(Position p,
boolean player)
positionEvaluation(Position p,
boolean player)
public abstract void printPosition(Position p)
public abstract Position [ ]
possibleMoves(Position p,
boolean player)
public abstract Position makeMove(Position p,
boolean player,
Move move)
public abstract boolean reachedMaxDepth(Position p,
int depth)
public abstract Move getMove()
The method drawnP osition should return a Boolean true value if the given position
evaluates to a draw situation. The method wonP osition should return a
true value if the input position is won for the indicated player. By convention, I
use a Boolean true value to represent the computer and a Boolean false value to
represent the human opponent. The method positionEvaluation returns a position
evaluation for a specified board position and player. Note that if we call positionEvaluation
switching the player for the same board position, then the value
returned is the negative of the value calculated for the opposing player. The method
possibleMoves returns an array of objects belonging to the class Position. In an
actual game like chess, the position objects will actually belong to a chess-specific
refinement of the Position class (e.g., for the chess program developed later in this
chapter, the method possibleMoves will return an array of ChessP osition objects).
The method makeMove will return a new position object for a specified
board position, side to move, and move.
The method reachedM axDepth returns
a Boolean true value if the search process has reached a satisfactory depth. For the
tic-tac-toe program, the method reachedM axDepth does not return true unless either
side has won the game or the board is full; for the chess program, the method
reachedM axDepth returns true if the search has reached a depth of 4 half moves
deep (this is not the best strategy, but it has the advantage of making the example program short and easy to understand). The method getMove returns an object of a
class derived from the class Move (e.g., Tic Tac Toe Move or Chess Move).
The GameSearch class implements the following methods to perform game search:
protected Vector alphaBeta(int depth, Position p,
boolean player)
protected Vector alphaBetaHelper(int depth,
Position p,
boolean player,
float alpha,
float beta)
public void playGame(Position startingPosition,
boolean humanPlayFirst)
