Game Tree Search on a Massively Parallel System

During the World Computer Chess Championships in Madrid, November 1992, our distributed chess program ZUGZWANG ran on a 1024 processor machine and finished second place without having lost a game. This article presents measurements that show the behaviour of ZUGZWANG using massive parallelism. We will show that the network used to interconnect the processors is a crucial point for the efficiency of our algorithm. This will be done by comparing the behaviour of our program with 256 processors using a DeBruijn network, a torus and a grid as interconnection network. On the other side we will point out, that even grid structured networks suffice to produce reasonable efficiency with up to 1024 processors. 1 INTRODUCTION There is a long history of parallel game playing programs now. Most of the recent parallel game playing programs use as their basic part the PV-Split algorithm of Marsland and Campbell from [MC82], which assumes that the game tree to be searched is well ordered. The basic..