Package gametree

package gametree

Various classes for storing and generating game trees for the use by algorithms and tree visualisation.

This package contains game tree classes (such as search trees and depth-first trees) and game position classes (such as artificial game trees). Game trees store the progress of the search of a game, whereas game positions represent the tree of the game itself, which generates its underlying structure.

The underlying structure of this package relies on the GameTreeNode abstract (for game trees) and the IGamePosition interface (for game positions).
The main implementations used in this thesis are:

• The SearchTreeNode (game tree) class for storing best-first trees for algorithms.
• The DepthFirstNode (game tree) class for storing depth-first trees for algorithms.
• The ArtificialGamePosition (game position) class for generating artificial game trees, the main domain we test algorithms on.
• The MetricKeeper (utility) class used by algorithms to keep track of their computational cost during the search.

Additionally, we provide a more generalised class for generating artificial game trees with VariantAGP. This implementation uses Generator interfaces to replace the branching factor and bounds generation aspects of artificial game trees with flexible function implementations.

Class	Description
ArtificialGamePosition	Represents a game position in an artificial game tree.
ArtificialGamePosition.Settings	A class that stores the settings for a ArtificialGamePosition tree.
DepthFirstNode<P extends IGamePosition<P>>	GameTreeNode implementation that does not store children nodes, but does store the depth of bounds and the bounds themselves.
DepthFirstNode.RootDFNode<P extends IGamePosition<P>>	An optional variant of the DepthFirstNode which stores the nodes at depth 1 in memory.
GameTreeNode<N extends GameTreeNode<N,P>, P extends IGamePosition<P>>	This class represents an abstract GameTreeNode which stores game positions of a game tree along with the structure of the tree itself through GameTreeNode.children(MetricKeeper...) and GameTreeNode.parent() relations.
GameTreeNode.Result<N extends GameTreeNode<N,P>, P extends IGamePosition<P>>	A record to hold the two best nodes (and their indices in the original collection).
Generator<T,S>	A generator for customising the tree structure of artificial game trees made with the VariantAGP class.
Generator.Bounds	The generator type specifically used for generating the bounds of the children generated as the children of each node of a VariantAGP artificial game tree.
Generator.Width	The generator type specifically used for generating the variable branching factor at each node of a VariantAGP artificial game tree.
IGamePosition<P extends IGamePosition<P>>	This interface represents a game position in any game which can be modelled as an adversarial or non-adversarial game.
MetricKeeper	This class is intended for use with algorithm testing by keeping track of metrics used to evaluate different algorithms on game tree search problems.
ResultTreeNode<N extends GameTreeNode<N,P>, P extends IGamePosition<P>, Q extends IGamePosition<Q>>	Creates a tree of position type Q from a source tree with position type P with the help of a P-to-Q transformer.
SearchTreeNode<P extends IGamePosition<P>>	Implementation of GameTreeNode that stores all nodes directly in memory.
SearchTreeNode.Settings	A class that stores the settings for a SearchTreeNode tree.
VariantAGP	Represents a game position in a variant artificial game tree.
VariantAGP.NodeInfo	A record holding the information provided to Generator functions for determining the bounds of a generated child node.
VariantAGP.Settings	A class that stores the settings for a VariantAGP tree.