Development of a concurrent tree search program.
Curt Powley · Defense Technical Information Center (DTIC) · 1982
Search, especially tree search, is fundamental to the field of artificial intelligence. Even with good heuristic functions, the time it takes on a single processor to solve progressively more difficult tree search problems grows exponentially and quickly becomes constraining. It seems reasonable that the use of concurrency should significantly improve the speed of a tree search. After discussing concurrent programming issues as background, this thesis outlines some high-level approaches to concurrent tree search. Development of each high-level approach includes development of required operating system interfaces. With the warning that choosing the best approach requires empirical evaluation, a concurrent tree search algorithm for the eight-puzzle is presented. (Author)