Construction of Large Zero-Aware Pattern Databases for Sliding Puzzles on Distributed Memory Machines

Construction of Large Zero-Aware Pattern Databases for Sliding Puzzles on Distributed Memory Machines

연구 분야: Databases

학회: International Conference on Computational Science and Its Applications

A pattern database, which is a precomputed lookup table that estimates the cost required to reach the goal state, is used for pruning in heuristic searches. In the search for an optimal solution to a sliding puzzle, a zero-aware pattern database (ZPDB) enables highly effective pruning. Using a database that considers the interactions of more tiles enhances pruning but increases computational time and memory usage. Here, we develop a program for constructing a large ZPDB on a distributed memory system. The program is based on a breadth-first search algorithm and is parallelized using MPI and OpenMP. An evaluation of its parallel performance reveals that increasing the number of MPI processes by 48-fold results in up to a 24x speedup. Furthermore, we construct a large ZPDB for the 24-puzzle on a board that stores all patterns formed by nine tiles and the blank (more than 1.7 trillion entries) in 41 min using 2304 compute nodes.