The Dynamic Tree-Splitting Parallel Search Algorithm

Article type: Research Article

Authors: Hyatt, R.M.^{; *}

Affiliations: Birmingham, Alabama

Note: [*] Computer and Information Science Department, University of Alabama, Birmingham, AL, USA. E-mail: hyatt@cis.uab.edu.

Abstract: This paper describes a High-performance parallel tree-search algorithm that uses Dynamic Tree Splitting (DTS) for searching αβ minimax game trees. The Algorithm Divides the search tree among several processors on a shared-memory parallel machine. The paper deals with the following topics: (1) the DTS algorithm, (2) analyzing αβ to select split points, (3) performance results of the algorithm, and (4) analysis of the results to see where further improvements might occur.

DOI: 10.3233/ICG-1997-20102

Journal: ICGA Journal, vol. 20, no. 1, pp. 3-19, 1997