Randomized Parallel Proof-Number Search

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