Job-Level UCT Search for Solving Hex

Abstract

Recently, Pawlewicz and Hayward successfully solved many Hex openings based on the Scalable Parallel Depth-First Proof-Number Search algorithm (SPDFPN), which was performed in a single machine with multiple threads. However, further parallelization is limited by the number of cores a single machine can possess. This paper investigates adapting this SPDFPN solver to a distributed computing environment, using the previously proposed job-level upper-confidence tree algorithm (JL-UCT) in order to further increase parallelism. To improve on the adapted JL-UCT solver system, we make a new attempt to support transposition information sharing among jobs in JL implementations. A mix of shared-memory and database techniques was used to achieve this improvement. Our experiments show that the adapted JL-UCT solver scales for larger problems. Additionally, using a single machine with 24 cores, the adapted method is able to solve Hex openings with less time than the previous SPDFPN solver in three of four test cases. Overall, for the four test cases, the adapted JL-UCT solver, using 6 nodes each with 24 cores, obtained speedups of 1.6, 1.9, 1.8 and 2.6 over those for the SPDFPN solver using one node with 24 cores.