Unsynchronized iteratively deepening parallel alpha-beta search

Author

Newborn, Monroe

Author_Institution

Sch. of Comput. Sci., McGill Univ., Montreal, Que., Canada

Volume

10

Issue

5

fYear

1988

fDate

9/1/1988 12:00:00 AM

Firstpage

687

Lastpage

694

Abstract

A parallel alpha-beta search algorithm called unsynchronized iteratively deepening parallel alpha-beta search is described. The algorithm´s simple control strategy and strong performance in complicated positions make it a viable alternative to the principal variation splitting algorithm (PVSA). Processors independently carry out iteratively deepening searches on separate subsets of moves. The iterative deepening is unsynchronized, e.g. one processor may be in the middle of the fifth iteration while another is in the middle of the sixth. Narrow windows diminish the importance of backing-up a score to the root of the tree as quickly as possible (one of the principal objectives of the PVSA). Speedups measured on one, two, four, and eight chess-playing computers are reported

Keywords

iterative methods; parallel algorithms; search problems; trees (mathematics); parallel alpha-beta search algorithm; principal variation splitting algorithm; tree; unsynchronized iterative deepening search; Computer science; Councils; Iterative algorithms; Multiprocessing systems; Parallel algorithms; Pediatrics; Radio access networks; Sun; Velocity measurement; Workstations;

fLanguage

English

Journal_Title

Pattern Analysis and Machine Intelligence, IEEE Transactions on

Publisher

ieee

ISSN

0162-8828

Type

jour

DOI

10.1109/34.6777

Filename

6777