ERA

Download the full-sized PDF of Dynamic Splitting of Decision TreesDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R32R3P02F

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Dynamic Splitting of Decision Trees Open Access

Descriptions

Author or creator
Farrage, S
Marsland, Tony
Additional contributors
Subject/Keyword
decision trees
tree splitting
Type of item
Report
Language
English
Place
Time
Description
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.
Date created
1993
DOI
doi:10.7939/R32R3P02F
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-30T22:13:37.054+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 387160
Last modified: 2015:10:12 16:29:07-06:00
Filename: TR93-03.pdf
Original checksum: 1c4538a07125fddf38fc63f9bb562480
Well formed: true
Valid: true
Page count: 35
Activity of users you follow
User Activity Date