Distributed Game-Tree Search Using Transposition Table Driven Work Scheduling
- Akihiro Kishimoto
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
The algorithm for two-player game-tree search has a notorious reputation as being a challenging algorithm for achieving reasonable parallel performance. MTD(f), a new variant, has become the sequential algorithm of choice for practitioners. Unfortunately, MTD(f) inherits most of the parallel obstacles of , as well as creating new performance hurdles. Transposition-table-driven scheduling (TDS) is a new parallel search algorithm that has proven to be effective in the single-agent (one-player) domain. This paper presents TDSAB, the first time TDS parallelism has been applied to two-player search (the MTD(f) algorithm). Results show that TDSAB gives comparable speedups to that achieved by conventional parallel algorithms. However, since this is a parallelization of a superior sequential algorithm, the results in fact are better. This paper shows that the TDS idea can be extended to more challenging search domains. Keywords: search, transposition-table-driven scheduling, single-agent search, transposition table.
Citation
A. Kishimoto, J. Schaeffer. "Distributed Game-Tree Search Using Transposition Table Driven Work Scheduling". International Conference on Parallel Processing (ICPP), June 2002.| Keywords: | |
| Category: | In Conference |
BibTeX
@incollection{Kishimoto+Schaeffer:ICPP02,
author = {Akihiro Kishimoto and Jonathan Schaeffer},
title = {Distributed Game-Tree Search Using Transposition Table Driven Work
Scheduling},
booktitle = {International Conference on Parallel Processing (ICPP)},
year = 2002,
}Last Updated: June 05, 2007Submitted by Staurt H. Johnson
