Dynamic Splitting of Decision Trees

• Author(s) / Creator(s)

  • Farrage, S
  • Marsland, Tony

• Technical report TR93-03. There are several ways to search decision trees (one and two-person game trees) in parallel, from simple splitting at the root and Principal Variation Splitting, to Baudet's use of aspiration windows. These static schemes are simple and effective, but dynamic methods like Feldmann's \"young brothers wait\", Hyatt's Dynamic Tree Splitting, and Schaeffer's Distributed Search, though more complex, are even better. In two-person game trees some splitting methods assume that the minimal game tree is being traversed, and so split at the expected ALL nodes (well defined nodes where all successors must be examined). In the search of typical game trees, these ALL nodes are not so easily found. Here we consider a simple dynamic splitting scheme, which balances the work across the processors without being redundant and without excessive duplication. This report describes a method to curtail excessive searching by simply dividing in half the remaining work along the current solution path, and giving it to another processor. We study a method developed for Parallel IDA* and test a variation of it in a single agent game, hence providing data from a working dynamic work distribution method. We also provide insights into issues that must be considered for an equivalent implementation in two-person games. | TRID-ID TR93-03

• Date created

  1993

• Subjects / Keywords

  • Decision trees
  • Tree splitting

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R32R3P02F

• License

  Attribution 3.0 International