Interface SearchAlgorithm

All Known Subinterfaces:

SearchAlgorithm.SearchWithTable, SearchAlgorithm.SearchWithTree

All Known Implementing Classes:

BstarBasic, BstarBasicDB, BstarSquaredDB, BstarSquaredSimple, BstarSquaredSimpleMax, BstarSquaredVariant, DfBstar, DfBstar2, DfBstar3, DfBstarDB

public interface SearchAlgorithm

General interface for all search algorithms.

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static final record	SearchAlgorithm.Limits	The limits imposed on the search.
static final record	SearchAlgorithm.SearchResult<N extends GameTreeNode<N,P>, P extends IGamePosition<P>>	Encapsulates the results and metrics captured from an adversarial tree search.
static interface	SearchAlgorithm.SearchWithTable	This represents a search algorithm which primarily stores search results in a transposition table.
static interface	SearchAlgorithm.SearchWithTree	This represents a search algorithm which can search a given tree and modify it during search.

Method Summary

Modifier and Type	Method	Description
static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> void	expand_tree_simple(N node, int depth, MetricKeeper... metrics)	Expands the search tree without stopping condition.
default <P extends IGamePosition<P>> SearchAlgorithm.SearchResult<?,P>	search(P root, SearchAlgorithm.Limits space_limit, MetricKeeper... metrics)	Initiates the search of the provided game tree without time limits.
default <P extends IGamePosition<P>> SearchAlgorithm.SearchResult<?,P>	search(P root, MetricKeeper... metrics)	Initiates the search of the provided game tree without time or spatial limits.
<P extends IGamePosition<P>> SearchAlgorithm.SearchResult<?,P>	search(P root, Duration time_limit, SearchAlgorithm.Limits space_limit, MetricKeeper... metrics)	Initiates the search of the provided game tree with a given time limit and spatial limit.
default <P extends IGamePosition<P>> SearchAlgorithm.SearchResult<?,P>	search(P root, Duration time_limit, MetricKeeper... metrics)	Initiates the search of the provided game tree without spatial limits.

Method Details

search

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

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

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

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

search

default <P extends IGamePosition<P>>
SearchAlgorithm.SearchResult<?,P> search(P root,
 SearchAlgorithm.Limits space_limit,
 MetricKeeper... metrics)

Initiates the search of the provided game tree without time limits.

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

space_limit - the spatial limits on this search

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

search

default <P extends IGamePosition<P>>
SearchAlgorithm.SearchResult<?,P> search(P root,
 Duration time_limit,
 MetricKeeper... metrics)

Initiates the search of the provided game tree without spatial limits.

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

time_limit - maximum time spent in 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

search

default <P extends IGamePosition<P>>
SearchAlgorithm.SearchResult<?,P> search(P root,
 MetricKeeper... metrics)

Initiates the search of the provided game tree without time or spatial limits.

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

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

expand_tree_simple

static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>>
void expand_tree_simple(N node,
 int depth,
 MetricKeeper... metrics)

Expands the search tree without stopping condition. This method most efficiently expands the tree to the specified depth by only evaluating the nodes at that depth and back-propagating the resulting bounds changes. This method does not stop if separation is achieved and will continue until all children at the specified depth have been evaluated.

This method is preferably used scarcely, as the irrelevance of nodes is also not considered when expanding the tree. This method works in a depth-first fashion without pruning.

Type Parameters:

N - Type of GameTreeNode used for this search

P - Type of IGamePosition which represents the tree to be searched

Parameters:

node - some initial node from which to expand the tree

depth - the maximum depth, as counted from the given node, to expand the tree to

metrics - MetricKeeper objects to keep track of expansions and evaluations made during this search