Feng-Hsiung.Hsu@UNH.CS.CMU.EDU (12/06/86)
Large Scale Parallelization of Alpha-beta Search: An Algorithmic and Architectural Study Feng-hsiung Hsu Time: Thursday, 6:00 pm, Dec. 11 Place: WH 4605 Abstract This proposal presents a class of new parallel alpha-beta algorithms that gives speedup arbitrarily close to linear when the game tree is best-first ordered and sufficiently deep. It will also be shown that the parallel algorithms strictly dominate the weaker form of alpha-beta algorithm that does not use deep cutoff; that is, they never search a node that is not explored by the weaker form of alpha-beta algorithm, and usually search fewer nodes. Preliminary simulation results indicate that the parallel algorithms are actually much better than the weak alpha-beta in terms of the number of nodes searched. Moreover, unlike previous parallel algorithms, the new parallel algorithms do not degrade drastically when the number of processors exceeds certain small number typically around 6 to 8. In fact, based on simulation data, it appears that no serious degradation of speedup would occur before technological considerations such as system reliability limit the maximum speedup. As an example of the applications of the parallel algorithms, the possibility and complications of applying the algorithms to computer chess will be examined. A new design for special purpose chess processors that is orders of magnitude smaller than existing designs is presented as the basis for a proposed multi-processor chess machine. Based on the measured data from a single chip chess move generator that has already been fabricated, it is estimated that with a 3-micron CMOS process a 3-chip chess processor, two custom chips and one commercial SRAM, searching about one million positions per second can be built. Some architectural considerations on how to coordinate vast number of such processors will be presented here. In the case that the proposed multi-processor machine cannot be completed in time, a small scale system will be built using off-the-shelf components and the move generators.