Scalable Parallel DFPN Search
Jakub Pawlewicz, Ryan Hayward · 2014
Abstract. We present Scalable Parallel Depth-First Proof Number Search, a new shared-memory parallel version of depth-first proof number search. Based on the serial DFPN 1+ε method of Pawlewicz and Lew, SPDFPN searches effectively even as the transposition table becomes almost full, and so can solve large problems. SPDFPN uses two parameters and proof and disproof numbers in assigning jobs to threads. It uses no domain-specific knowledge or heuristics and so can be used in any domain. We tested SPDFPN on problems from the game of Hex. SPDFPN scales well: on a 24-core machine and a 4.2-hour single-thread task, parallel efficiency ranges from 0.8 on 4 threads to 0.74 on 16 threads. SPDFPN performs well on hard problems: it solved all previously intractable 9×9 Hex opening moves, with the hardest opening taking 111 days. It also solved one 10×10 Hex opening move, in 63 days. Previously, no computer or human had ever solved a 10×10 opening move. This is the state of the art in Hex solving. 1