Parallel search of narrow game trees
Chien-Ping Paul. Lu · 1993
One of the key determinants of a game playing program's strength is the depth of the game tree search. Therefore, researchers have turned to parallelism to search deeper trees in the same amount of real time. Tree decomposition algorithms extract parallelism by creating split nodes, where the subtrees rooted at the node are searched concurrently. If the game trees are narrow, then the degree of parallelism offered by the low branching factor may be insufficient to keep all the parallel processors busy, resulting in starvation and poor speedups. Chinook is a checkers (8 x 8 draughts) playing program developed at the University of Alberta. For the August 1992, Man Versus Machine World Draughts Championship match between Chinook and Dr.#Marion Tinsley, a parallel Chinook, or ParaChinook, was developed. This thesis describes the parallelization of Chinook's Alpha-Beta search. The initial implementation of ParaChinook was based on the Principal Variation Splitting (PVSplit) algorithm, devel...