knockabout.search
Class MCSearchAlgorithm

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

public class MCSearchAlgorithm
extends java.lang.Object
implements SearchAlgorithm

A Monte Carlo search algorithm implementation


Constructor Summary
MCSearchAlgorithm()
           
 
Method Summary
 int getAverageBranchingFactor()
          Average branching factor
 float getBestMoveUtility()
           
 int getD()
           
 Heuristic getHeuristic()
           
 GameState getInitialState()
           
 int getK()
           
 int getMaxDepth()
           
 int getNumberOfExploredNodes()
          Number of min nodes + number of max nodes explored
protected  float MC(GameState state)
          MC() check the average of k simulations for the given state
 Move search()
          Evaluate the best move to do
 void setD(int i)
           
 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 setK(int i)
           
protected  float simulate(GameState state, int depth, int color)
          Simulate a line of the game Half of the time, we pick the best move using a greedy minmax, half of the time we pick a random move For the chance node, we pick one value of the die at random
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

MCSearchAlgorithm

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

MC

protected float MC(GameState state)
MC() check the average of k simulations for the given state

Parameters:
state -
Returns:
The average utility

simulate

protected float simulate(GameState state,
                         int depth,
                         int color)
Simulate a line of the game Half of the time, we pick the best move using a greedy minmax, half of the time we pick a random move For the chance node, we pick one value of the die at random

Parameters:
state - The state from where the simulation begins
depth - The required depth of the simulation
color - The color of the player currently simulated (alternates)
Returns:
The utility (computed by the heuristic if not a terminal) of this line of play

getBestMoveUtility

public float getBestMoveUtility()
Specified by:
getBestMoveUtility in interface SearchAlgorithm
Returns:
The utility of the move returned by the last call of search()

getNumberOfExploredNodes

public int getNumberOfExploredNodes()
Description copied from interface: SearchAlgorithm
Number of min nodes + number of max nodes explored

Specified by:
getNumberOfExploredNodes in interface SearchAlgorithm
Returns:

getAverageBranchingFactor

public int getAverageBranchingFactor()
Description copied from interface: SearchAlgorithm
Average branching factor

Specified by:
getAverageBranchingFactor in interface SearchAlgorithm

getD

public int getD()
Returns:

getK

public int getK()
Returns:

setD

public void setD(int i)
Parameters:
i -

setK

public void setK(int i)
Parameters:
i -

getHeuristic

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

setHeuristic

public void setHeuristic(Heuristic heuristic)
Description copied from interface: SearchAlgorithm
The heuristic function to evaluate the utility of non terminal nodes

Specified by:
setHeuristic in interface SearchAlgorithm
Parameters:
heuristic -

getMaxDepth

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