Class DfBstar

java.lang.Object

algorithm.DfBstar

All Implemented Interfaces:

SearchAlgorithm, SearchAlgorithm.SearchWithTable

@Deprecated
public class DfBstar
extends Object
implements SearchAlgorithm.SearchWithTable

Deprecated.

This is the purest df-B* implementation, developed as described in the thesis. However, this variant had severe issues such as frequent stack overflows and behaviour of getting stuck at very deep sub-trees. This is addressed in the DfBstar2.java implementation of df-B*.

Important to note that DfBstar is very experimental. Giving the search more stack-size to work with may be the difference between completion and failure, but not always in the same direction. When searching at depths where ranges do not tighten any further (e.g.: [59,61] with discrete node values), the search will forever attempt to raise or lower the same node by 1 point, which is often less useful to the search than switching to a different node.

This is a fundamental issue with df-Bstar, as the only information we have to set thresholds with is not effort information, the same additional effort does not lead to the same increase in bounds. Probability based search might help this, but it is unclear.

Nested Class Summary

Nested classes/interfaces inherited from interface algorithm.SearchAlgorithm

SearchAlgorithm.Limits, SearchAlgorithm.SearchResult<N extends GameTreeNode<N,P>, P extends IGamePosition<P>>, SearchAlgorithm.SearchWithTable, SearchAlgorithm.SearchWithTree

Field Summary

Fields

Modifier and Type	Field	Description
final DebugPrinter	DB	Deprecated.

Constructor Summary

Constructors

Constructor	Description
DfBstar(StopCondition extraStopCondition, StrategyFunction strategyFunction, double sigma, double epsilon)	Deprecated.
DfBstar(StrategyFunction strategyFunction, double sigma, double epsilon)	Deprecated.

Method Summary

Modifier and Type	Method	Description
<P extends IGamePosition<P>> SearchAlgorithm.SearchResult<?,P>	search(P root, Table table, Duration time_limit, SearchAlgorithm.Limits space_limit, MetricKeeper... metrics)	Deprecated. Initiates the search of the provided game tree with a given time limit and spatial limit.

Methods inherited from class java.lang.Object

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

Methods inherited from interface algorithm.SearchAlgorithm

search, search, search

Methods inherited from interface algorithm.SearchAlgorithm.SearchWithTable

search, search, search, search

Field Details

DB

public final DebugPrinter DB

Deprecated.

Constructor Details

DfBstar

public DfBstar(StopCondition extraStopCondition,
 StrategyFunction strategyFunction,
 double sigma,
 double epsilon)

Deprecated.

DfBstar

public DfBstar(StrategyFunction strategyFunction,
 double sigma,
 double epsilon)

Deprecated.

Method Details

search

public <P extends IGamePosition<P>>
SearchAlgorithm.SearchResult<?,P> search(P root,
 Table table,
 Duration time_limit,
 SearchAlgorithm.Limits space_limit,
 MetricKeeper... metrics)

Deprecated.

Description copied from interface: SearchAlgorithm.SearchWithTable

Initiates the search of the provided game tree with a given time limit and spatial limit.

Specified by:

search in interface SearchAlgorithm.SearchWithTable

Type Parameters:

P - The type of IGamePosition which represents the type of game to be searched

Parameters:

root - root of the tree to be searched

table - table to use during search, can be non-empty

time_limit - maximum time spent in the algorithm

space_limit - maximum node expansions, evaluations, and nodes saved in memory used by the algorithm

metrics - an array of MetricKeeper objects to keep track of evaluations, expansions, and node storage performed during the search, can be empty

Returns:

result from the search