Class DfBstar3

java.lang.Object
algorithm.DfBstar3
All Implemented Interfaces:
SearchAlgorithm, SearchAlgorithm.SearchWithTable
public class DfBstar3 extends Object implements SearchAlgorithm.SearchWithTable
This implementation of df-B* with initial node selection inspired by B* Disprove-Best, but not exactly following it.

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.

  • Field Details

  • Constructor Details

    • DfBstar3

      public DfBstar3(StopCondition extraStopCondition, StrategyFunction strategyFunction, double sigma, double epsilon, double selectAltChance)

    • DfBstar3

      public DfBstar3(StrategyFunction strategyFunction, double sigma, double epsilon, double selectAltChance)

  • Method Details

    • setInitialMaxDepth

      public void setInitialMaxDepth(long maxDepth)
      Whenever the search reaches a depth beyond the maximum depth, it returns to the root and increases the search depth by depthIncrement before continuing the search.
      Parameters:
      maxDepth - The initial maximum depth of the search, defaults to 10

    • setDepthIncrement

      public void setDepthIncrement(long depthIncrement)
      Whenever the search reaches a depth beyond the maximum depth, it returns to the root and increases the search depth by depthIncrement before continuing the search.
      Parameters:
      depthIncrement - The depth increment of the search, defaults to 1

    • setInitialStackSize

      public void setInitialStackSize(long stackSize)
      Whenever the search runs out of stack-size, it returns to the root and increases the stack-size limit by a factor of 2 before continuing the search.
      Parameters:
      stackSize - The initial stack-size of the search, defaults to 50000. The exact meaning of this number is platform dependent, but the cost of choosing a value that is too small is negligiable for large searches, whereas a value that is too large may reduce memory available to the JVM, depending on the platform specific implementation.

    • search

      public <P extends IGamePosition<P>> SearchAlgorithm.SearchResult<?,P> search(P root, Table table, Duration time_limit, SearchAlgorithm.Limits space_limit, MetricKeeper... metrics)
      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