APHID: Asynchronous Parallel Game-Tree Search
✍ Scribed by Mark G. Brockington; Jonathan Schaeffer
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 488 KB
- Volume
- 60
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Most parallel game-tree search approaches use synchronous methods, where the work is concentrated within a specific part of the tree or at a given search depth. This article shows that asynchronous game-tree search algorithms can be as efficient as or better than synchronous methods in determining the minimax value.
APHID, a new asynchronous parallel game-tree search algorithm, is presented. APHID is implemented as a freely available portable library, making the algorithm easy to integrate into a sequential game-tree searching program. APHID has been added to four programs written by different authors. APHID yields better speedups than synchronous search methods for an Othello and a checkers program and comparable speedups on two chess programs.