About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ICGA Journal
Paper
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.