Consistent linear speedup in parallel Alpha-Beta search

Rattikorn Hewett, Krishnamurthy Ganesan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Alpha-Beta search is an important heuristic technique used in pruning a game tree. Recently, parallelism has been introduced to further improve the efficiency of heuristic searches, including Alpha-Beta search. This paper presents a new parallel Alpha-Beta search algorithm that applies prioritizing scheme. To verify its performance, we implemented the algorithm on Sequent Symmetry shared memory multiprocessor system. Our experimental results show that for the best ordering uniform trees, we are able to obtain a consistent speedup of a linear order to the number of processors used. An overall speedup with random node ordering isillustrated. The paper concludes with some characteristics of the Alpha-Beta search that make the application of priorities suitable for its corresponding parallel algorithm.

Original languageEnglish
Title of host publicationProceedings - ICCI 1992
Subtitle of host publication4th International Conference on Computing and Information
EditorsPeter E. Lauer, Anestis A. Toptsis, Waldemar W. Koczkodaj
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages237-240
Number of pages4
ISBN (Electronic)081862812X, 9780818628122
DOIs
StatePublished - 1992
Event4th International Conference on Computing and Information, ICCI 1992 - Toronto, Canada
Duration: May 28 1992May 30 1992

Publication series

NameProceedings - ICCI 1992: 4th International Conference on Computing and Information

Conference

Conference4th International Conference on Computing and Information, ICCI 1992
CountryCanada
CityToronto
Period05/28/9205/30/92

Fingerprint Dive into the research topics of 'Consistent linear speedup in parallel Alpha-Beta search'. Together they form a unique fingerprint.

  • Cite this

    Hewett, R., & Ganesan, K. (1992). Consistent linear speedup in parallel Alpha-Beta search. In P. E. Lauer, A. A. Toptsis, & W. W. Koczkodaj (Eds.), Proceedings - ICCI 1992: 4th International Conference on Computing and Information (pp. 237-240). [227665] (Proceedings - ICCI 1992: 4th International Conference on Computing and Information). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCI.1992.227665