Algorithm
Development Kit 1.0

algs.model.gametree
Class AlphaBetaEvaluation

java.lang.Object
  extended by algs.model.gametree.AlphaBetaEvaluation
All Implemented Interfaces:
IEvaluation

public class AlphaBetaEvaluation
extends java.lang.Object
implements IEvaluation

Initiate AlphaBeta Evaluation over the given game state and ply.

Base this implementation on the Negmax algorithm, since the pruning code is simpler to understand.

To properly enable debugging, we must invoke the counter methods of the IGameState being processed (incrementing when we expand and decrementing when we retract). The number of states explored can be found in the numStates class variable.

The toString method is provided to make it a bit easier to debug.

All lines commented with STAT can be eliminated and are only here to make it possible to generate statistics about the execution of the algorithm. Their overhead is minimal.

Note that a lookahead of ZERO will only return the evaluation of the board state and the returned move will be null.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 int numStates
          statistical information to evaluate algorithms effectiveness.
 
Constructor Summary
AlphaBetaEvaluation(int ply)
          Create an evaluator with the given state.
 
Method Summary
 IGameMove bestMove(IGameState s, IPlayer player, IPlayer opponent)
          Initiates the AlphaBeta computations by determining the maximum number of moves in advance to look.
 java.lang.String toString()
          Expose board state as string (useful for debugging purposes).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

numStates

public int numStates
statistical information to evaluate algorithms effectiveness.

Constructor Detail

AlphaBetaEvaluation

public AlphaBetaEvaluation(int ply)
Create an evaluator with the given state. It is important that the same player evaluate the board regardless of MIN and MAX. The player will be known when bestMove is invoked.

Parameters:
ply - Depth to search; must be greater than zero.
Method Detail

bestMove

public IGameMove bestMove(IGameState s,
                          IPlayer player,
                          IPlayer opponent)
Initiates the AlphaBeta computations by determining the maximum number of moves in advance to look.

The original game state is copied prior to being processed so no external effect occurs. This implementation is derived from NegMax and selects moves accordingly.

If no moves are available to player, then null is returned.

Specified by:
bestMove in interface IEvaluation
Parameters:
s - Game state being evaluated.
player - The player making the next move.
opponent - The player's opponent.

toString

public java.lang.String toString()
Expose board state as string (useful for debugging purposes).

Overrides:
toString in class java.lang.Object

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.