A PARALLEL HARDWARE ARCHITECTURE FOR ACCELERATING ALPHA-BETA GAME TREE-SEARCH

Overheads caused by frequently communicating alpha-beta values among n umerous parallel search processes not only degrade greatly the perform ance of existing parallel alpha-beta search algorithm but also make it impractical to implement these algorithms in parallel hardware. To so lve this problem, the proposed architecture reduces the overheads by u sing specially designed multi-value arbiters to compare and global bro adcasting buses to communicate alpha-beta values. In addition, the arc hitecture employs a set of alpha-beta search control units (alpha-beta SCU's) with distributed alpha-beta registers to accelerate the search by searching all subtrees in parallel. Simulation results show that t he proposed parallel architecture with 1444 (38 x 38) (alpha-beta SCU' s) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 alpha-bet a SCU's. The chip can achieve a search speed of 13, 381,345 node-visit s per second, which is more than three orders of improvement over that of existing parallel algorithms.