A Comparison of Parallel α-β Search Algorithms

概要

論文の詳細を見る
The α-β search algorithm is central to most programs that play games. In the past few years, many attempts have been made to parallelize the α-β search. Because game trees tend to be highly irregular and α-β severe pruning mechanism conflicts with parallelism, it proves difficult to search game trees in parallel on parallel machines. This paper compares the existing parallel search algorithms and describes our algorithm:different node types are identified to exploit parallelism with a lower extra overhead; multiple promising branches are searched first with full windows and then all remaining branches are assumed to be inferior to the best move found so far and are searched with a minimal window. The experiments on the massively parallel machine AP1000 have shown that a significant speedup can be obtained through this approach.
社団法人人工知能学会の論文
1996-03-01