Parallel Game-Tree Search with Conspiracy Numbers

Abstract

Conspiracy-number search (cn search) is an incremental min-max tree-growth algorithm. Experiments suggest that SSS*, a game-tree search algorithm superior to α-β, is a special case of cn search. Also, we experimented with 4 parallel cn-search algorithms on a shared-memory MIMD machine: A) a parallel successor evaluation resulting in a speedup of 4.5 on 10 processors; B) dividing subtrees among slave processors achieving a speedup of 3.4; C) a combination of the previous two algorithms with a speedup of 6.3; D) simultaneous search of all processors in the stored game tree yielding a speedup of 4.6. Algorithm A suffers from the costly tree-traversal time in cn search. Algorithm B has a large synchronization overhead. Algorithm C reduces the disadvantages of both algorithms A and B. Algorithm D is degraded by the narrow trees grown by cn search, so processors mutually interfere excessively in the costly updating of nodes. Finally, we tested the strengths of the algorithms in a chess program.