A parallel hardware architecture for accelerating computer chess system

Autor: Ke, Yi Fan, 柯奕帆
Rok vydání: 1996
Druh dokumentu: 學位論文 ; thesis
Popis: 84
As the speed of a Chess machine is the main factor affecting the performance of its intelligence, the best way to improve its play strength is to speed up two time-consuming components, search controller and move generator, of the Chess machine. Existing research adopts parallel search control algorithms to reduce the search time, as well as uses hardware to accelerate move generator. However, the resulting speed improvement is still limited by (1) the communication overheads, search overheads, and synchronize overheads in curred in existing parallel searching algorithms, and (2) legal move dependency between move generator and search controller. In this thesis, we propose for computer Chess a parallel hardware architecture t hat applies global broadcasting buses to communicate and update the newest move dependence information among the search control subsystems to reduce the three o verheads. Besides, the proposed parallel architecture reduce the legal move dependency eff ect by generating legal moves in advance and overlapping the clock cycles of the search controllers and the move generators; as a result, the search controller can directly search the game tree without waiting for the legal moves. Simulation results show that up to 50\% of thinking time can be reduced by the p roposed parallel move generator; besides, up to 179 folds of speed-up can be ach ieved by using 1444 search control subsystems. The overall speed-up of the whole Chess machine ranges from 3 to 360, depending on the number of search control subsystems, Chess position, legal move ordering, and the game tree depth.
Databáze: Networked Digital Library of Theses & Dissertations