Consistent linear speedup in parallel Alpha-Beta search

Rattikorn Hewett; Krishnamurthy Ganesan

doi:10.1109/ICCI.1992.227665

Consistent linear speedup in parallel Alpha-Beta search

Rattikorn Hewett, Krishnamurthy Ganesan

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 language	English
Title of host publication	Proceedings - ICCI 1992
Subtitle of host publication	4th International Conference on Computing and Information
Editors	Peter E. Lauer, Anestis A. Toptsis, Waldemar W. Koczkodaj
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	237-240
Number of pages	4
ISBN (Electronic)	081862812X, 9780818628122
DOIs	https://doi.org/10.1109/ICCI.1992.227665
State	Published - 1992
Event	4th International Conference on Computing and Information, ICCI 1992 - Toronto, Canada Duration: May 28 1992 → May 30 1992

Publication series

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

Conference

Conference	4th International Conference on Computing and Information, ICCI 1992
Country/Territory	Canada
City	Toronto
Period	05/28/92 → 05/30/92

Access to Document

10.1109/ICCI.1992.227665

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

Hewett, Rattikorn ; Ganesan, Krishnamurthy. / Consistent linear speedup in parallel Alpha-Beta search. Proceedings - ICCI 1992: 4th International Conference on Computing and Information. editor / Peter E. Lauer ; Anestis A. Toptsis ; Waldemar W. Koczkodaj. Institute of Electrical and Electronics Engineers Inc., 1992. pp. 237-240 (Proceedings - ICCI 1992: 4th International Conference on Computing and Information).

@inproceedings{5d1e7428dce0474996e21ede57cbd5c8,

title = "Consistent linear speedup in parallel Alpha-Beta search",

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.",

author = "Rattikorn Hewett and Krishnamurthy Ganesan",

note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 4th International Conference on Computing and Information, ICCI 1992 ; Conference date: 28-05-1992 Through 30-05-1992",

year = "1992",

doi = "10.1109/ICCI.1992.227665",

language = "English",

series = "Proceedings - ICCI 1992: 4th International Conference on Computing and Information",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "237--240",

editor = "Lauer, {Peter E.} and Toptsis, {Anestis A.} and Koczkodaj, {Waldemar W.}",

booktitle = "Proceedings - ICCI 1992",

}

Hewett, R & Ganesan, K 1992, Consistent linear speedup in parallel Alpha-Beta search. in PE Lauer, AA Toptsis & WW Koczkodaj (eds), Proceedings - ICCI 1992: 4th International Conference on Computing and Information., 227665, Proceedings - ICCI 1992: 4th International Conference on Computing and Information, Institute of Electrical and Electronics Engineers Inc., pp. 237-240, 4th International Conference on Computing and Information, ICCI 1992, Toronto, Canada, 05/28/92. https://doi.org/10.1109/ICCI.1992.227665

Consistent linear speedup in parallel Alpha-Beta search. / Hewett, Rattikorn; Ganesan, Krishnamurthy.
Proceedings - ICCI 1992: 4th International Conference on Computing and Information. ed. / Peter E. Lauer; Anestis A. Toptsis; Waldemar W. Koczkodaj. Institute of Electrical and Electronics Engineers Inc., 1992. p. 237-240 227665 (Proceedings - ICCI 1992: 4th International Conference on Computing and Information).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Consistent linear speedup in parallel Alpha-Beta search

AU - Hewett, Rattikorn

AU - Ganesan, Krishnamurthy

PY - 1992

Y1 - 1992

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77955106819&partnerID=8YFLogxK

U2 - 10.1109/ICCI.1992.227665

DO - 10.1109/ICCI.1992.227665

M3 - Conference contribution

AN - SCOPUS:77955106819

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

SP - 237

EP - 240

BT - Proceedings - ICCI 1992

A2 - Lauer, Peter E.

A2 - Toptsis, Anestis A.

A2 - Koczkodaj, Waldemar W.

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 4th International Conference on Computing and Information, ICCI 1992

Y2 - 28 May 1992 through 30 May 1992

ER -

Hewett R, Ganesan K. Consistent linear speedup in parallel Alpha-Beta search. In Lauer PE, Toptsis AA, Koczkodaj WW, editors, Proceedings - ICCI 1992: 4th International Conference on Computing and Information. Institute of Electrical and Electronics Engineers Inc. 1992. p. 237-240. 227665. (Proceedings - ICCI 1992: 4th International Conference on Computing and Information). doi: 10.1109/ICCI.1992.227665

Consistent linear speedup in parallel Alpha-Beta search

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this