MINDS @ UW-Madison

Searching Game Trees in Parallel

Show simple item record


Files Size Format View
TR877.pdf 2.094Mb application/pdf View/Open
Key Value Language
dc.contributor.author Steinberg, Igor en_US
dc.contributor.author Solomon, Marvin H en_US
dc.date.accessioned 2012-03-15T16:51:42Z
dc.date.available 2012-03-15T16:51:42Z
dc.date.created 1989 en_US
dc.date.issued 1989
dc.identifier.citation TR877 en_US
dc.identifier.uri http://digital.library.wisc.edu/1793/59184
dc.description.abstract 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. en_US
dc.description.provenance Made available in DSpace on 2012-03-15T16:51:42Z (GMT). No. of bitstreams: 1 TR877.pdf: 2094348 bytes, checksum: 159aa63ac9ed77f16a715cc38f3a2905 (MD5) en
dc.description.provenance Create and Issued dates reconciled by Wendt Commons staff on 2014-July-14 (BH). en_US
dc.format.mimetype application/pdf en_US
dc.publisher University of Wisconsin-Madison Department of Computer Sciences en_US
dc.title Searching Game Trees in Parallel en_US
dc.type Technical Report en_US

Part of

Show simple item record