Class GameTreeNode<N extends GameTreeNode<N,P>, P extends IGamePosition<P>>

java.lang.Object
gametree.GameTreeNode<N,P>
Type Parameters:
N - The implementing type of GameTreeNode that extends this class.
P - The type of IGamePosition objects stored in this GameTreeNode, represents the game which is being represented by this game tree.
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
DepthFirstNode, ResultTreeNode, SearchTreeNode, SimpleNode
public abstract class GameTreeNode<N extends GameTreeNode<N,P>, P extends IGamePosition<P>> extends Object implements Serializable
This class represents an abstract GameTreeNode which stores game positions of a game tree along with the structure of the tree itself through children(MetricKeeper...) and parent() relations.

The GameTree logic is kept separate from the IGamePosition logic to allow any kind of architecture to be more easily applied to any kind of game without having the two sides of code interact directly.

A GameTreeNode implementation thus provides exact implementations for data storage, retrieval, and management. Implementation details may affect the efficiency and memory usage of algorithms using them. In principle, any algorithm could work on any implementation of GameTreeNode, but some algorithms may be specifically designed with a particular implementation in mind.

Version:
1.0
Author:
Pascal Rodrigo Anema
See Also:

  • Constructor Details

    • GameTreeNode

      protected GameTreeNode(N parent, P position, MetricKeeper... metrics)
      Creates a GameTreeNode in the same game tree as the given parent node, as its child node, where the given position is the current game state. Or creates a new root node for the game tree of the given position if parent is null.
      Parameters:
      parent - the parent node of this node or null if this is a root node
      position - the current game state at this node

  • Method Details

    • position

      public P position()
      The game position IGamePosition this node represents. This is the current game position as reached by moves after the position represented by the root node of this tree through all ancestor nodes to this one.

      If this node is the root node, position() represents the current state of the game.

      However, it is possible that the GameTreeNode implementation determines to prune this object for memory conservation purposes after all necessary information has been obtained from this game position. In which case, position() will return null.

      Returns:
      The IGamePosition object representing the game position at this node, or null if this node has been pruned for memory conservation.

    • clearPosition

      protected void clearPosition()
      Sets position() to null

    • parent

      public N parent()
      The GameTreeNode object of the parent() of this node. the node representing the game state previous to position.

      If this node is the root node of the tree, the parent will be null.

      Returns:
      The parent GameTreeNode of this node.

    • depth

      public long depth()
      Returns:
      0 if this is the root, otherwise the number of ancestors until reaching the root.

    • isRoot

      public boolean isRoot()
      Returns:
      true if this node is a root (its parent is null) or false otherwise

    • setParent

      protected void setParent(N newParent)

    • maximising

      public abstract boolean maximising()
      This is IGamePosition.maximising() from the position() of this node.
      Returns:
      true if the current player-to-move is maximising the score, or false if it is minimising the score.

    • children

      public List<N> children(MetricKeeper... metrics)
      The children of this node are its direct descendants. During the search, these nodes' values may be updated with information gathered during the search. At first, the children of a node are exactly the same nodes as those returned from IGamePosition.next(), but may be modified later to aid the search. The returned children collection may be empty, but should never be null.
      Parameters:
      metrics - One or more MetricKeeper objects to keep track of node evaluations and expansions made by this GameTreeNode through this method. Or zero if there is no need to keep track of these metrics.
      Returns:
      The collection of game tree nodes directly reachable by moves from the current player to move in the game position this game tree node represents.

    • _children

      protected abstract List<N> _children(MetricKeeper... metrics)
      Method to implement functionality of children(MetricKeeper...).

    • savedChildren

      public abstract Optional<List<N>> savedChildren()
      Returns:
      An Optional containing all children nodes saved in the memory of this GameTreeNode or an empty Optional if none are saved in memory. An Optional containing an empty List signifies a terminal node with no children.

    • upperbound

      public double upperbound(MetricKeeper... metrics)
      The upper-bound value is the upper bound on the game-theoretical mini-max value of this game position().

      For the maximising player this is the best value achievable under perfect play.

      For the minimising player this is the worst-case value achievable under perfect play.

      This value is initially set as the value returned by IGamePosition.upperbound() and later updated to reflect a tighter upper-bound for the game-theoretical value of this node.

      Parameters:
      metrics - One or more MetricKeeper objects to keep track of node evaluations and expansions made by this GameTreeNode through this method. Or zero if there is no need to keep track of these metrics.
      Returns:
      The upper-bound value for this game position

    • _upperbound

      protected abstract double _upperbound(MetricKeeper... metrics)
      Method to implement functionality of upperbound(MetricKeeper...).

    • lowerbound

      public double lowerbound(MetricKeeper... metrics)
      The lower-bound value is the lower bound on the game-theoretical mini-max value of this game position.

      For the maximising player this is the minimum value that can be guaranteed under perfect play.

      For the minimising player this is the best value achievable under perfect play.

      This value is initially set as the value returned by IGamePosition.lowerbound() and later updated to reflect a tighter lower-bound for the game-theoretical value of this node.

      Parameters:
      metrics - One or more MetricKeeper objects to keep track of node evaluations and expansions made by this GameTreeNode through this method. Or zero if there is no need to keep track of these metrics.
      Returns:
      The lower-bound value for this game position

    • _lowerbound

      protected abstract double _lowerbound(MetricKeeper... metrics)
      Method to implement functionality of lowerbound(MetricKeeper...).

    • hasSavedBounds

      public abstract boolean hasSavedBounds()

    • adjustBounds

      public boolean adjustBounds(MetricKeeper... metrics)
      Adjusts the bounds of this node according to the values of the children nodes as given by children(MetricKeeper...). Maximising nodes will adjust their bounds to be the maximum of the lower- and upper-bound values of their children, whereas minimising nodes will instead use the minimum of the lower- and upper-bound values of their children.
      Parameters:
      metrics - One or more MetricKeeper objects to keep track of node evaluations and expansions made by this GameTreeNode through this method. Or zero if there is no need to keep track of these metrics.
      Returns:
      true if the bounds of this node have been altered, false otherwise

    • adjustBounds

      public boolean adjustBounds(boolean useExpansions, MetricKeeper... metrics)

    • adjustBounds

      public boolean adjustBounds(List<N> children, MetricKeeper... metrics)

    • _adjustBounds

      protected abstract boolean _adjustBounds(List<N> children, MetricKeeper... metrics)
      Method to implement functionality of adjustBounds(List<N>, MetricKeeper...).

    • depthOfUpper

      public long depthOfUpper(MetricKeeper... metrics)
      Depth-of-upperbound is the depth from which the upper bound of this node has been backed up. This denotes the depth of search from which the bounds of a node have been obtained. It can act as a metric to determine the effort expended at a certain node, but is not entirely reliable for this purpose.
      Parameters:
      metrics - One or more MetricKeeper objects to keep track of node evaluations and expansions made by this GameTreeNode through this method. Or zero if there is no need to keep track of these metrics.
      Returns:
      The depth from which the upperbound(MetricKeeper...) has been backed-up. Or 0 if it has not yet been updated from the initial IGamePosition.upperbound() value.

    • _depthOfUpper

      protected abstract long _depthOfUpper(MetricKeeper... metrics)
      Method to implement functionality of depthOfUpper(MetricKeeper...).

    • depthOfLower

      public long depthOfLower(MetricKeeper... metrics)
      Depth-of-lowerbound is the depth from which the lower bound of this node has been backed up.

      This denotes the depth of search from which the bounds of a node have been obtained.
      It can act as a metric to determine the effort expended at a certain node, but is not entirely reliable for this purpose.

      Parameters:
      metrics - One or more MetricKeeper objects to keep track of node evaluations and expansions made by this GameTreeNode through this method. Or zero if there is no need to keep track of these metrics.
      Returns:
      The depth from which the lowerbound(MetricKeeper...) has been backed-up. Or 0 if it has not yet been updated from the initial IGamePosition.lowerbound() value.

    • _depthOfLower

      protected abstract long _depthOfLower(MetricKeeper... metrics)
      Method to implement functionality of depthOfLower(MetricKeeper...).

    • countSavedSubTree

      public long countSavedSubTree()
      Returns:
      The size, in number of nodes, of the sub-tree of saved nodes starting at this node, including this one (minimum of 1)

    • attachMetrics

      public void attachMetrics(MetricKeeper... m)

    • getAttachedMetrics

      public MetricKeeper[] getAttachedMetrics()

    • hasAttachedMetrics

      public boolean hasAttachedMetrics()

    • combineMetricList

      protected MetricKeeper[] combineMetricList(MetricKeeper... metrics)

    • updateMetricsParental

      public boolean updateMetricsParental()
      Uses the parental line of succession of this node to retroactively add MetricKeeper objects from this node's ancestors to this node's personal list of MetricKeeper objects.
      Returns:
      true if the metrics of this node have been altered, and false otherwise.

    • updateMetrics

      public void updateMetrics()

    • CDF

      public double[] CDF(int maxDepth, MetricKeeper... metrics)
      Computes the Cumulative Distribution Function (CDF) P(X ≤ t) of this node, assuming that the distribution is a discrete one. The underlying sub-tree will not be further expanded, rather only evaluated based on its current state, and at most up to the given maximum depth.
      Parameters:
      maxDepth - the maximum depth to which evaluations will be performed to compute this. NO EXPANSIONS WILL BE MADE.
      metrics - MetricKeeper objects to keep track of node evaluations made by this method.
      Returns:
      The CDF of this node's distribution, given this distribution is assumed to be discrete.

    • survivalFunction

      public double[] survivalFunction(int maxDepth, MetricKeeper... metrics)
      Computes the Survival Function P(X ≥ x) of this node, assuming that the distribution is a discrete one. The underlying sub-tree will not be further expanded, rather only evaluated based on its current state, and at most up to the given maximum depth.
      Parameters:
      maxDepth - the maximum depth to which evaluations will be performed to compute this. NO EXPANSIONS WILL BE MADE.
      metrics - MetricKeeper objects to keep track of node evaluations made by this method.
      Returns:
      The Survival Function of this node's distribution, given this distribution is assumed to be discrete.

    • PMF

      public double[] PMF(int maxDepth, MetricKeeper... metrics)
      Computes the Probability Mass Function (PMF) P(X = x) of this node, assuming that the distribution is a discrete one. The underlying sub-tree will not be further expanded, rather only evaluated based on its current state, and at most up to the given maximum depth.
      Parameters:
      maxDepth - the maximum depth to which evaluations will be performed to compute this. NO EXPANSIONS WILL BE MADE.
      metrics - MetricKeeper objects to keep track of node evaluations made by this method.
      Returns:
      The PMF of this node's distribution, given this distribution is assumed to be discrete.

    • adjustBounds

      public static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> boolean adjustBounds(boolean maximising, double[] lowerUpper, long[] depthLowerUpper, List<N> children, MetricKeeper... metrics)
      Adjust the bounds of a node.
      Type Parameters:
      N - Type of the GameTreeNode
      P - Type of the IGamePosition
      Parameters:
      maximising - whether the parent node is maximising or not
      lowerUpper - an array of size 2 containing the lower- and upper-bound of the parent (unchecked)
      depthLowerUpper - an array of size 2 containing the depth of the lower- and upper-bound of the parent (unchecked)
      children - the children of the parent node
      metrics -
      Returns:
      true if the bounds were changed, false otherwise.

    • findBest2

      public static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> GameTreeNode.Result<N,P> findBest2(Collection<N> children, boolean maximising, boolean by_optimistic, MetricKeeper... metrics)
      Calculate the best 2 nodes from the perspective specified by the maximizing and by_optimistic flags.

      If maximizing is true and by_optimistic is true, nodes with maximum upperbound() value are selected. Ties are broken with the highest lowerbound() value.

      If maximizing is true and by_optimistic is false, nodes with maximum lowerbound() value are selected. Ties are broken with the highest upperbound() value.

      If maximizing is false and by_optimistic is true, nodes with minimum lowerbound() value are selected. Ties are broken with the lowest upperbound() value.

      If maximizing is false and by_optimistic is false, nodes with minimum upperbound() value are selected. Ties are broken with the lowest lowerbound() value.

      Type Parameters:
      N - the node type extending GameTreeNode
      P - the game-position type extending IGamePosition
      Parameters:
      children - the collection of nodes to evaluate
      maximising - a flag indicating whether to select from a maximising (true) or minimising (false) perspective
      by_optimistic - a flag indicating whether to select the most optimistic (true) or least pessimistic (false) nodes
      metrics - an array of MetricKeeper objects to keep track of evaluations and expansions made through this method, can be empty
      Returns:
      a record containing the best and second-best nodes and their corresponding indices.

    • mostOptimistic2

      public static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> GameTreeNode.Result<N,P> mostOptimistic2(Collection<N> children, boolean maximising, MetricKeeper... metrics)
      Same as findBest2(Collection, boolean, boolean, MetricKeeper...) where by_optimistic is assumed true.

    • leastPessimistic2

      public static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> GameTreeNode.Result<N,P> leastPessimistic2(Collection<N> children, boolean maximising, MetricKeeper... metrics)
      Same as findBest2(Collection, boolean, boolean, MetricKeeper...) where by_optimistic is assumed false.

    • separation

      public static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> boolean separation(Collection<N> children, boolean maximising, MetricKeeper... metrics)
      Type Parameters:
      N - the node type extending GameTreeNode
      P - the game-position type extending IGamePosition
      Parameters:
      children - the collection of nodes to evaluate
      maximising - a flag indicating whether we are observing from a maximising (true) or minimising (false) perspective
      metrics - an array of MetricKeeper objects to keep track of evaluations and expansions made through this method, can be empty
      Returns:
      true if the sub-tree from the parent of the given children could be terminated according to the separation rule; false otherwise.

    • separation

      public static <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> boolean separation(GameTreeNode<?,?> n, MetricKeeper... metrics)
      Type Parameters:
      N - The GameTreeNode type of the given node
      P - The IGamePosition type of the given node
      Parameters:
      n - The node at which the sub-tree originates (usually the root node)
      metrics - an array of MetricKeeper objects to keep track of evaluations and expansions made through this method, can be empty
      Returns:
      true if the sub-tree from the given node could be terminated according to the separation rule; false otherwise.

    • getComparator

      public static Comparator<GameTreeNode<?,?>> getComparator(boolean maximising, boolean by_optimistic, MetricKeeper... metrics)
      This method gives a comparator for GameTreeNode objects from the perspective of a parent node. Differently from natural ordering, this comparator will sort best values first. For example, for an optimistic && maximising perspective this means sorting by highest upperbound value first.
      Parameters:
      maximising - whether to select from a maximising perspective (true) or from a minimising perspective (false)
      by_optimistic - whether to select based on the optimistic value (true) or the pessimistic value (false). From a maximising perspective, the upperbound of a node is the optimistic perspective, whereas the lowerbound is the pessimistic perspective. From a minimising perspective, the lowerbound of a node is the optimistic perspective, whereas the upperbound is the pessimistic perspective.
      metrics - an array of MetricKeeper objects to keep track of evaluations and expansions made through this comparator, can be empty
      Returns:
      A comparator which sorts a list of nodes by the best nodes first, from the specified perspective.

    • isRelevant

      public boolean isRelevant(MetricKeeper... metrics)

    • remainingSolveEffort

      public double remainingSolveEffort(MetricKeeper... metrics)

    • updateTree

      public void updateTree(MetricKeeper... metrics)

    • getSavedLeafnodes

      public Stream<N> getSavedLeafnodes(int maxDepth, Predicate<N> include)

    • getAllLeafnodes

      public Stream<N> getAllLeafnodes(int maxDepth, Predicate<N> include, MetricKeeper... metrics)

    • printTree

      public String printTree(int depth, MetricKeeper... metrics)

    • printTree

      public String printTree(int depth, boolean toString, MetricKeeper... metrics)
      Visually represents the structure of the sub-tree starting from this node as a String.
      Parameters:
      depth - The maximum depth to which the tree should be displaced (starting from the current node)
      toString - Whether to print the identity of each node (rather than just its bounds)
      Returns:
      A String representation of the sub-tree of this node, up to the specified depth

    • printTree

      public String printTree(int depth, boolean toString, boolean printDist, MetricKeeper... metrics)
      Visually represents the structure of the sub-tree starting from this node as a String.
      Parameters:
      depth - The maximum depth to which the tree should be displaced (starting from the current node)
      toString - Whether to print the identity of each node (rather than just its bounds)
      printDist - Whether to show the distribution function of each node (computed up to the maximum depth specified)
      Returns:
      A String representation of the sub-tree of this node, up to the specified depth

    • toFile

      public void toFile(String fileName) throws IOException
      Throws:
      IOException

    • fromFile

      public static GameTreeNode<?,?> fromFile(String fileName) throws IOException, ClassNotFoundException
      Throws:
      IOException
      ClassNotFoundException