ALCOMFT-TR-02-107

Ulf Lorenz
Parallel Controlled Conspiracy Number Search
Paderborn. Work packages 2 and 4. May 2002.

Abstract: Tree search algorithms play an important role in many applications in the field of artificial intelligence. When playing board games like chess etc., computers use game tree search algorithms to evaluate a position. In this paper, we present a procedure that we call Parallel Controlled Conspiracy Number Search (Parallel CCNS). Shortly, we describe the principles of the sequential CCNS algorithm, which bases its approximation-results on irregular subtrees of the entire game tree. We have parallelized CCNS and implemented it in our chess program P.ConNerS, which now is the first in the world, that could win a high-ranked Grandmaster chess-tournament. We add experiments that show a speedup of about 50 on 159 processors running on an SCI-workstation-cluster.

Postscript file: ALCOMFT-TR-02-107.ps.gz (57 kb).