Parallel Game-Tree Search

The design issues affecting a parallel implementation of the alpha-beta search algorithm are discussed with emphasis on a tree decomposition scheme that is intended for use on well ordered trees. In particular, the principal variation splitting method has been implemented, and experimental results a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 1985-07, Vol.PAMI-7 (4), p.442-452
Main Authors: Marsland, T. A., Popowich, Fred
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Alpha-beta search
Applied sciences
Artificial intelligence
chess programs
Computer science
Computer science
control theory
systems
concurrent programming
Councils
Decision trees
Delay effects
Delay systems
Exact sciences and technology
graph and tree search strategies
Message passing
message passing multiprocessors
Parallel algorithms
Parallel processing
Problem solving, game playing
tree decomposition
Tree graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The design issues affecting a parallel implementation of the alpha-beta search algorithm are discussed with emphasis on a tree decomposition scheme that is intended for use on well ordered trees. In particular, the principal variation splitting method has been implemented, and experimental results are presented which show how such refinements as progressive deepening, narrow window searching, and the use of memory tables affect the performance of multiprocessor based chess playing programs. When dealing with parallel processing systems, communication delays are perhaps the greatest source of lost time. Therefore, an implementation of our tree decomposition based algorithm is presented, one that operates with a modest amount of message passing within a network of processors. Since our system has low search overhead, the principal basis for comparison is the communication overhead, which in turn is shown to have two components.
ISSN:0162-8828
1939-3539
DOI:10.1109/TPAMI.1985.4767683