Title :
Consistent linear speedup in parallel alpha-beta search
Author :
Hewett, Rateikom ; Ganesan, Krishnamurthy
Author_Institution :
Dept. of Comput. Sci. & Eng., Florida Atlantic Univ., Boca Raton, FL, USA
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 such heuristic searches. The paper presents a new parallel alpha-beta search algorithm that applies a prioritizing scheme. To verify its performance, the algorithm was implemented on sequent symmetry shared memory multiprocessor system. Experimental results show that for the best ordering uniform trees, one is able to obtain a consistent speedup of a linear order to the number of processors used. An overall speedup with random node ordering is illustrated. The paper concludes with some characteristics of the alpha-beta search that make the application of priorities suitable for its corresponding parallel algorithm
Keywords :
heuristic programming; parallel algorithms; search problems; trees (mathematics); game tree pruning; heuristic searches; parallel algorithm; parallel alpha-beta search; prioritizing scheme; random node ordering; sequent symmetry shared memory multiprocessor system; uniform trees; Algorithm design and analysis; Artificial intelligence; Computer science; Concurrent computing; Iterative algorithms; Multiprocessing systems; Parallel algorithms; Parallel architectures; Parallel processing; Terminology;
Conference_Titel :
Computing and Information, 1992. Proceedings. ICCI '92., Fourth International Conference on
Conference_Location :
Toronto, Ont.
Print_ISBN :
0-8186-2812-X
DOI :
10.1109/ICCI.1992.227665
