aima.core.search.adversarial

Class IterativeDeepeningAlphaBetaSearch<STATE,ACTION,PLAYER>

java.lang.Object

aima.core.search.adversarial.IterativeDeepeningAlphaBetaSearch<STATE,ACTION,PLAYER>

Type Parameters:

STATE - Type which is used for states in the game.

ACTION - Type which is used for actions in the game.

PLAYER - Type which is used for players in the game.

All Implemented Interfaces:

AdversarialSearch<STATE,ACTION>

Direct Known Subclasses:

ConnectFourAIPlayer

public class IterativeDeepeningAlphaBetaSearch<STATE,ACTION,PLAYER>
extends java.lang.Object
implements AdversarialSearch<STATE,ACTION>

Implements an iterative deepening Minimax search with alpha-beta pruning and action ordering. Maximal computation time is specified in seconds. The algorithm is implemented as template method and can be configured and tuned by subclassing.

Author:

Ruediger Lunde

Field Summary

Fields

Modifier and Type	Field and Description
protected int	currDepthLimit
protected Game<STATE,ACTION,PLAYER>	game
static java.lang.String	METRICS_MAX_DEPTH
static java.lang.String	METRICS_NODES_EXPANDED
protected double	utilMax
protected double	utilMin

Constructor Summary

Constructors

Constructor and Description
IterativeDeepeningAlphaBetaSearch(Game<STATE,ACTION,PLAYER> game, double utilMin, double utilMax, int time) Creates a new search object for a given game.

Method Summary

Modifier and Type	Method and Description
static <STATE,ACTION,PLAYER> IterativeDeepeningAlphaBetaSearch<STATE,ACTION,PLAYER>	createFor(Game<STATE,ACTION,PLAYER> game, double utilMin, double utilMax, int time) Creates a new search object for a given game.
protected double	eval(STATE state, PLAYER player) Primitive operation, which estimates the value for (not necessarily terminal) states.
Metrics	getMetrics() Returns some statistic data from the last search.
protected boolean	hasSafeWinner(double resultUtility) Primitive operation which is used to stop iterative deepening search in situations where a safe winner has been identified.
protected void	incrementDepthLimit() Primitive operation which is called at the beginning of one depth limited search step.
protected boolean	isSignificantlyBetter(double newUtility, double utility) Primitive operation which is used to stop iterative deepening search in situations where a clear best action exists.
ACTION	makeDecision(STATE state) Template method controlling the search.
double	maxValue(STATE state, PLAYER player, double alpha, double beta, int depth)
double	minValue(STATE state, PLAYER player, double alpha, double beta, int depth)
java.util.List<ACTION>	orderActions(STATE state, java.util.List<ACTION> actions, PLAYER player, int depth) Primitive operation for action ordering.
void	setLogEnabled(boolean b)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

METRICS_NODES_EXPANDED

public static final java.lang.String METRICS_NODES_EXPANDED

See Also:

Constant Field Values

METRICS_MAX_DEPTH

public static final java.lang.String METRICS_MAX_DEPTH

See Also:

Constant Field Values

game

protected Game<STATE,ACTION,PLAYER> game

utilMax

protected double utilMax

utilMin

protected double utilMin

currDepthLimit

protected int currDepthLimit

Constructor Detail

IterativeDeepeningAlphaBetaSearch

public IterativeDeepeningAlphaBetaSearch(Game<STATE,ACTION,PLAYER> game,
                                         double utilMin,
                                         double utilMax,
                                         int time)

Creates a new search object for a given game.

Parameters:

game - The game.

utilMin - Utility value of worst state for this player. Supports evaluation of non-terminal states and early termination in situations with a safe winner.

utilMax - Utility value of best state for this player. Supports evaluation of non-terminal states and early termination in situations with a safe winner.

time - Maximal computation time in seconds.

Method Detail

createFor

public static <STATE,ACTION,PLAYER> IterativeDeepeningAlphaBetaSearch<STATE,ACTION,PLAYER> createFor(Game<STATE,ACTION,PLAYER> game,
                                                                                                     double utilMin,
                                                                                                     double utilMax,
                                                                                                     int time)

Creates a new search object for a given game.

Parameters:

game - The game.

utilMin - Utility value of worst state for this player. Supports evaluation of non-terminal states and early termination in situations with a safe winner.

utilMax - Utility value of best state for this player. Supports evaluation of non-terminal states and early termination in situations with a safe winner.

time - Maximal computation time in seconds.

setLogEnabled

public void setLogEnabled(boolean b)

makeDecision

public ACTION makeDecision(STATE state)

Template method controlling the search. It is based on iterative deepening and tries to make to a good decision in limited time. Credit goes to Behi Monsio who had the idea of ordering actions by utility in subsequent depth-limited search runs.

Specified by:

makeDecision in interface AdversarialSearch<STATE,ACTION>

maxValue

public double maxValue(STATE state,
                       PLAYER player,
                       double alpha,
                       double beta,
                       int depth)

minValue

public double minValue(STATE state,
                       PLAYER player,
                       double alpha,
                       double beta,
                       int depth)

getMetrics

public Metrics getMetrics()

Returns some statistic data from the last search.

Specified by:

getMetrics in interface AdversarialSearch<STATE,ACTION>

Returns:

all the metrics of the search.

incrementDepthLimit

protected void incrementDepthLimit()

Primitive operation which is called at the beginning of one depth limited search step. This implementation increments the current depth limit by one.

isSignificantlyBetter

protected boolean isSignificantlyBetter(double newUtility,
                                        double utility)

Primitive operation which is used to stop iterative deepening search in situations where a clear best action exists. This implementation returns always false.

hasSafeWinner

protected boolean hasSafeWinner(double resultUtility)

Primitive operation which is used to stop iterative deepening search in situations where a safe winner has been identified. This implementation returns true if the given value (for the currently preferred action result) is the highest or lowest utility value possible.

eval

protected double eval(STATE state,
                      PLAYER player)

Primitive operation, which estimates the value for (not necessarily terminal) states. This implementation returns the utility value for terminal states and (utilMin + utilMax) / 2 for non-terminal states. When overriding, first call the super implementation!

orderActions

public java.util.List<ACTION> orderActions(STATE state,
                                           java.util.List<ACTION> actions,
                                           PLAYER player,
                                           int depth)

Primitive operation for action ordering. This implementation preserves the original order (provided by the game).