knockabout.search
Class ItMinMaxSearchAlgorithm

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

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

Iterative deepening, real-time expectiminimax search algorithm


Field Summary
static int READY
           
static int SEARCHING
           
static int STOPPING
           
 
Constructor Summary
ItMinMaxSearchAlgorithm()
           
 
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()
          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()
          See max()
 void run()
           
 Move search()
          Evaluate the best move to do
 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  float stochMax()
          In the case of a stochastic node, average the possibilities
protected  float stochMin()
          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
See Also:
Constant Field Values

SEARCHING

public static final int SEARCHING
See Also:
Constant Field Values

STOPPING

public static final int STOPPING
See Also:
Constant Field Values
Constructor Detail

ItMinMaxSearchAlgorithm

public ItMinMaxSearchAlgorithm()
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()
Description copied from interface: SearchAlgorithm
Evaluate the best move to do

Specified by:
search in interface SearchAlgorithm
Returns:

run

public void run()
Specified by:
run in interface java.lang.Runnable

max

protected float max()
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()
In the case of a stochastic node, average the possibilities

Returns:
Mean of the utility of the children

min

protected float min()
See max()

Returns:

stochMin

protected float stochMin()
See stochMax()

Returns:

getMaxDepth

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

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

Specified by:
getAverageBranchingFactor in interface SearchAlgorithm