Parallel game-tree search

Area of Science:

• Computer Science
• Artificial Intelligence
• Parallel Computing

Background:

• Designing efficient parallel algorithms for complex search problems like chess is challenging.
• Communication overhead significantly impacts performance in multiprocessor systems.
• Existing parallel search algorithms often struggle with communication delays.

Purpose of the Study:

• To discuss design issues in parallel alpha-beta search implementation.
• To present a tree decomposition scheme for well-ordered trees.
• To evaluate performance enhancements for multiprocessor chess programs.

Main Methods:

• Implementation of the principal variation splitting method.
• Experimental analysis of refinements: progressive deepening, narrow window searching, and memory tables.
• Development of a tree decomposition-based algorithm with modest message passing.

Main Results:

• Refinements like progressive deepening and memory tables improve performance.
• The proposed algorithm operates with low search overhead and minimal message passing.
• Communication overhead is identified as a key performance bottleneck with two distinct components.

Conclusions:

• The tree decomposition scheme effectively addresses design issues in parallel alpha-beta search.
• Minimizing communication overhead is crucial for high-performance parallel computing in AI.
• The presented algorithm offers a promising approach for efficient multiprocessor-based game playing programs.