About This Item

Ask the MINDS@UW Librarian

Searching Game Trees in Parallel

Show full item record


Steinberg, Igor; Solomon, Marvin H
University of Wisconsin-Madison Department of Computer Sciences
Mar 15, 2012
We present a new parallel game-tree search algorithm. Our approach classifies a processorís available work as either mandatory (necessary for the solution) or speculative (may be necessary for the solution). Due to the nature of parallel game tree search, it is not possible to keep all processors busy with mandatory work. Our algorithm ER allows potential speculative work to be dynamically ordered, thereby reducing starvation without incurring an equivalent increase in speculative loss. Measurements of ERís performance on both random trees and trees from an actual game, show that at least 16 processors can be applied profitably to a single search. These results contrast with previously published studies, which report a rapid drop-off efficiency as the number of processors increases.
Permanent link
Export to RefWorks 

Part of

Show full item record

Search and browse


Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.