Parallel randomized Best-First Minimax Search

Parallel randomized Best-First Minimax Search

0.00 Avg rating0 Votes
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: ,
Keywords: graphs, programming: branch and bound, artificial intelligence
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.