Parallel dovetailing and its application to Depth-first proof-number search

Abstract

Depth-first proof-number (df-pn) search is an effective sequential AND/OR tree search algorithm using the notion of proof and disproof numbers. Although df-pn has been parallelized in sharedmemory environments thus far, parallelizing df-pn in distributed-memory environments still remains a challenge. This paper presents simple yet empirically effective parallel df-pn methods for distributed computing environments. Our methods are based on parallel dovetailing that has been successfully applied to a number of algorithms and they incur almost no communication overhead by independently performing df-pn search that exploits a different part of the search space in each processing node. More specifically, we present two methods of parallelizing an enhanced df-pn variant called df-pn+: the first is based on leveraging non-deterministic behaviors of a shared-memory parallel df-pn search algorithm (SPDDFPN+), and the second is based on randomly initializing proof and disproof numbers (RPDDFPN+). Experimental results using state-of-the-art solvers indicated that RPDDFPN+ achieves reasonable speedups in both tsume-shogi (checkmate problems in Japanese chess) and tsume-Go (life-and-death problems in Go), which have completely different characteristics. Moreover, parallel dovetailing occasionally yields superlinear speedups with a reasonably small number of base solvers and can even solve additional instances that the original solver is unable to solve. Our results also revealed that SPDDFPN +improves the efficiency of a high-performance tsume-shogi solver.