An effective two-level proof-number search algorithm

The paper presents a new proof-number (PN) search algorithm, called PDS–PN. It is a two-level search (like PN²), which performs at the first level a depth-first proof-number and disproof-number search (PDS), and at the second level a best-first PN search. Hence, PDS–PN selectively exploits the power of both PN² and PDS. Experiments in the domain of Lines of Action are performed. They show that within an acceptable time frame PDS–PN is more effective for really hard endgame positions than αβ and any other PN-search algorithm.