SOLVING HEX OPENINGS USING JOB-LEVEL UCT SEARCH

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 article 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 on top of a JL framework. A mix of shared-memory and database techniques was used to achieve this improvement. Our experiments show that the adapted JL-UCT solver is able to solve positions faster as the number of cores increases. 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 four of five test cases. Overall, for the five test cases, the adapted JL-UCT solver, using 6 nodes each with 24 cores, obtained speedups of 1.6 to 2.6 over those for the SPDFPN solver using one node with 24 cores.