Proof-Number Search (PNS) is a powerful method for solving games and game positions. Over the years, the research on PNS has steadily produced new insights and techniques. With multi-core processors 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 (RPPNS) for parallelizing PNS on multi-core systems with shared memory. The parallelization is based on randomizing the move selection of multiple threads, which operate on the same search tree. RPPNS is tested on a set of complex Lines-of-Action endgame positions. Experiments show that RPPNS scales well. Four directions for future research are given.
['Jahn-Takeshi Saito', 'Mark H. M. Winands', 'H. Jaap van den Herik']
Randomized parallel proof-number search