knockabout.search
Class AlphaBetaSearchAlgorithm

java.lang.Object
  extended byknockabout.search.AlphaBetaSearchAlgorithm
All Implemented Interfaces:
java.lang.Runnable, SearchAlgorithm

public class AlphaBetaSearchAlgorithm
extends java.lang.Object
implements SearchAlgorithm, java.lang.Runnable

A real-time implementation of expected alpha-beta, with iterative deepening, move ordering and stochastic cut-off


Field Summary
static int READY
          The search operation is ready to start
static int SEARCHING
          An active search operation is in progress
static int STOPPING
          The signal for the search thread to stop and go back to READY
 
Constructor Summary
AlphaBetaSearchAlgorithm()
           
 
Method Summary
 int getAverageBranchingFactor()
          Average branching factor.
 float getBestMoveUtility()
           
 Heuristic getHeuristic()
           
 GameState getInitialState()
           
 int getMaxDepth()
           
 int getNumberOfExploredNodes()
          Number of min nodes + number of max nodes explored
protected  float max(float alpha, float beta)
          Note that this function will leave the board in the same configuration as the it was when the function was called, because the inverse move is always applied after each move tried.
protected  float min(float alpha, float beta)
          See max()
 void run()
          What is done by the search thread is in there: an implementation of iterative deepening
 Move search()
          Perform the real-time search operation This method will take [timeLimitMillis] millisecond to complete & return
 void setHeuristic(Heuristic heuristic)
          The heuristic function to evaluate the utility of non terminal nodes
 void setInitialState(GameState initialState)
          The initial state of the game
protected  void setMaxDepth(int i)
          The depth for which minmax stops expending and begin to use its heuristic instead
protected  float stochMax(float alpha, float beta)
          In the case of a stochastic node, average the possibilities A cut-off is sometimes possible too since the utility is bounded
protected  float stochMin(float alpha, float beta)
          See stochMax()
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

READY

public static final int READY
The search operation is ready to start

See Also:
Constant Field Values

SEARCHING

public static final int SEARCHING
An active search operation is in progress

See Also:
Constant Field Values

STOPPING

public static final int STOPPING
The signal for the search thread to stop and go back to READY

See Also:
Constant Field Values
Constructor Detail

AlphaBetaSearchAlgorithm

public AlphaBetaSearchAlgorithm()
Method Detail

getInitialState

public GameState getInitialState()
Specified by:
getInitialState in interface SearchAlgorithm
Returns:

setInitialState

public void setInitialState(GameState initialState)
Description copied from interface: SearchAlgorithm
The initial state of the game

Specified by:
setInitialState in interface SearchAlgorithm
Parameters:
initialState -

search

public Move search()
Perform the real-time search operation This method will take [timeLimitMillis] millisecond to complete & return

Specified by:
search in interface SearchAlgorithm
Returns:

run

public void run()
What is done by the search thread is in there: an implementation of iterative deepening

Specified by:
run in interface java.lang.Runnable

max

protected float max(float alpha,
                    float beta)
Note that this function will leave the board in the same configuration as the it was when the function was called, because the inverse move is always applied after each move tried.

Returns:
the evaluated utility of the node

stochMax

protected float stochMax(float alpha,
                         float beta)
In the case of a stochastic node, average the possibilities A cut-off is sometimes possible too since the utility is bounded

Returns:
Mean of the utility of the children

min

protected float min(float alpha,
                    float beta)
See max()

Returns:

stochMin

protected float stochMin(float alpha,
                         float beta)
See stochMax()

Returns:

getMaxDepth

public int getMaxDepth()
Specified by:
getMaxDepth in interface SearchAlgorithm
Returns:

setMaxDepth

protected void setMaxDepth(int i)
The depth for which minmax stops expending and begin to use its heuristic instead

Parameters:
i -

getHeuristic

public Heuristic getHeuristic()
Specified by:
getHeuristic in interface SearchAlgorithm
Returns:

setHeuristic

public void setHeuristic(Heuristic heuristic)
The heuristic function to evaluate the utility of non terminal nodes

Specified by:
setHeuristic in interface SearchAlgorithm
Parameters:
heuristic -

getBestMoveUtility

public float getBestMoveUtility()
Specified by:
getBestMoveUtility in interface SearchAlgorithm
Returns:

getNumberOfExploredNodes

public int getNumberOfExploredNodes()
Number of min nodes + number of max nodes explored

Specified by:
getNumberOfExploredNodes in interface SearchAlgorithm
Returns:

getAverageBranchingFactor

public int getAverageBranchingFactor()
Average branching factor. Formula: (syncNumberOfExploredNodes - 1) / (syncNumberOfInnerNodes + 1); // avoid div by 0

Specified by:
getAverageBranchingFactor in interface SearchAlgorithm