You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Parallel Game-Tree Search with Conspiracy Numbers


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.