Note: [1] Center for Frontier Science and Engineering, the University of Electro-Communications, Tokyo, Japan. E-mail: hoki@cs.uec.ac.jp
Note: [2] Department of Graphics and Computer Sciences, the University of Tokyo, Tokyo, Japan. E-mail: kaneko@acm.org
Note: [3] IBM Research, Dublin, Ireland. Email: AKIHIROK@ie.ibm.com. This research was mostly conducted when the author was affiliated with the Department of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology.
Note: [4] Department of Information and Communication Engineering, the University of Electro-Communications, Tokyo, Japan. E-mail: ito@cs.uec.ac.jp
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 shared-memory 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.
DOI: 10.3233/ICG-2013-36103
Journal: ICGA Journal, vol. 36, no. 1, pp. 22-36, 2013
