Distributed Game-Tree Search¹

Article type: Research Article

Authors: Feldmann, R.^a | Monien, B.^a | Mysliwietz, P.^a | Vornberger, O.^b

Affiliations: [a] Department of Mathematics and Computer Science, University of Paderborn, West Germany | [b] Department of Mathematics and Computer Science, University of Osnabrück, West Germany

Note: [1] This work was partly supported by the Deutsche Forschung Gemeinschaft (DFG, the German Research Association).

Abstract: We present a distributed algorithm for searching game trees. Two new concepts are introduced in order to reduce search and communication overheads, viz. the Young-Brothers-Wait and the Helpful-Master concepts. We describe some properties of our distributed algorithm including optimal speedup on best-ordered game trees. An implementation of this algorithm in a distributed chess program is studied and experimental data showing surprisingly good performance are presented.

DOI: 10.3233/ICG-1989-12203

Journal: ICGA Journal, vol. 12, no. 2, pp. 65-73, 1989