knockabout.search
Class MinMaxSearchAlgorithm

java.lang.Object
  extended byknockabout.search.MinMaxSearchAlgorithm
All Implemented Interfaces:
SearchAlgorithm

public class MinMaxSearchAlgorithm
extends java.lang.Object
implements SearchAlgorithm

A fixed depth expectiminmax search algo


Constructor Summary
MinMaxSearchAlgorithm()
           
 
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()
 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
 void setMaxDepth(int i)
          The depth for which minmax stops expending and begin to use its heuristic instead
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
 

Constructor Detail

MinMaxSearchAlgorithm

public MinMaxSearchAlgorithm()
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:

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:

setMaxDepth

public 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

Specified by:
getAverageBranchingFactor in interface SearchAlgorithm