Article ID: | iaor20032940 |
Country: | United States |
Volume: | 137 |
Issue: | 1/2 |
Start Page Number: | 165 |
End Page Number: | 196 |
Publication Date: | May 2002 |
Journal: | Artificial Intelligence |
Authors: | Shoham Y., Toledo S. |
Keywords: | graphs, programming: branch and bound, artificial intelligence |
We describe a novel parallel randomized search algorithm for two-player games. The algorithm is a randomized version of Korf and Chickering's best-first search. Randomization both fixes a defect in the original algorithm and introduces significant parallelism. An experimental evaluation demonstrates that the algorithm is efficient (in terms of the number of search-tree vertices that it visits) and highly parallel. On incremental random game trees the algorithm outperforms Alpha–Beta, and speeds up by up to a factor of 18 (using 35 processors). In comparison, Jamboree speeds up by only a factor of 6. The algorithm outperforms Alpha–Beta in the game of Othello. We have also evaluated the algorithm in a Chess-playing program using the board-evaluation code from an existing Alpha-Beta-based program (Crafty). On a single processor our program is slower than Crafty by about a factor of 7, but with multiple processors it outperforms it: with 64 processors our program is always faster, usually by a factor of 5, sometimes much more.