Randomized Parallel Proof-Number Search

Abstract. Proof-Number Search (PNS) is a powerful method for solv-ing games and game positions. Over the years, the research on PNS has steadily produced new insights and techniques. With multi-core proces-sors becoming established in the recent past, the question of parallelizing PNS has gained new urgency. This article presents a new technique called Randomized Parallel Proof-Number Search (RP–PNS) for parallelizing PNS on multi-core systems with shared memory. The parallelization is based on randomizing the move selection of multiple threads, which oper-ate on the same search tree. RP–PNS is tested on a set of complex Lines-of-Action endgame positions. Experiments show that RP–PNS scales well. Four directions for future research are given.