Class DfBstar2

java.lang.Object
algorithm.DfBstar2
All Implemented Interfaces:
SearchAlgorithm, SearchAlgorithm.SearchWithTable
public class DfBstar2 extends Object implements SearchAlgorithm.SearchWithTable
This is the df-B* implementation applied in the thesis. The only additional adaptations are the ones described in the thesis in the Experiments section. This adaptation is NOT described in section 3.3. This df-B* variant includes a depth limit and a stack limit. The stack limit is very operating system dependent, and I cannot exactly predict how it will work on other machines. However, the implementation is intended to double the stack-size limit every time the search exceeds it. This seems to work on Java 17 on Windows 11. The depth limit is more consistent, and simply increases the limit by 1 every time it is exceeded. Both these limits force the search to backup to the root when they are exceeded.

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

  • 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