Class BstarBasic

java.lang.Object
algorithm.BstarBasic
All Implemented Interfaces:
SearchAlgorithm, SearchAlgorithm.SearchWithTree
public class BstarBasic extends Object implements SearchAlgorithm.SearchWithTree
This class implements B* with a few additional modifications:
  1. if the number of back-ups without leading back to the root reaches 1000, the algorithm is forced to back-up to the root
  2. if a terminal node is selected, the algorithm is forced to back-up to the root
  3. if the current node's best child is not its least pessimistic child, there is a 30% chance that the least pessimistic child is selected, this will not occur if this would select a terminal node

  • Field Details

    • num_expanded_total

      public static volatile long num_expanded_total

  • Constructor Details

  • Method Details

    • setMaxRootlessUpdates

      public void setMaxRootlessUpdates(long maxRootless)
      Sets the maximum number of rootless back-propagations made by the search until a back-propagation to the root is forced. Defaults to 1000.

      This can be disabled by calling disableMaxRootlessUpdates()

      Parameters:
      maxRootless - The maximum number of rootless updates / back-propagations.

    • disableMaxRootlessUpdates

      public void disableMaxRootlessUpdates()
      Disable the limit on the number of rootless back-propagations made by the search. This can be enabled again by calling setMaxRootlessUpdates(long).

    • setFilterTerminalNodes

      public void setFilterTerminalNodes(boolean set)

    • setRandomChance

      public void setRandomChance(double probability)

    • disableRandomChance

      public void disableRandomChance()

    • expectIncorrectBounds

      public void expectIncorrectBounds(boolean set)
      Correlates to the SearchTreeNode.enableIncorrectBoundsProtection(boolean) setting. If incorrect bounds are expected, setting this to true will keep discarded nodes in memory so they can be re-expanded again later. This defaults to false
      Parameters:
      set - the value to set to

    • search

      public <P extends IGamePosition<P>> SearchAlgorithm.SearchResult<?,P> search(P root, Duration time_limit, SearchAlgorithm.Limits space_limit, MetricKeeper... metrics)
      Description copied from interface: SearchAlgorithm
      Initiates the search of the provided game tree with a given time limit and spatial limit.
      Specified by:
      search in interface SearchAlgorithm
      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

    • searchWithTree

      public <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> SearchAlgorithm.SearchResult<N,P> searchWithTree(N root, Duration time_limit, SearchAlgorithm.Limits space_limit, MetricKeeper... metrics)
      Description copied from interface: SearchAlgorithm.SearchWithTree
      Initiates the search of the provided game tree with a given time limit and spatial limit.
      Specified by:
      searchWithTree in interface SearchAlgorithm.SearchWithTree
      Type Parameters:
      N - The type of GameTreeNode which is used for executing the search
      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

    • selectNext

      public <N extends GameTreeNode<N,P>, P extends IGamePosition<P>> N selectNext(N current, boolean provebest, MetricKeeper... metrics)