Zero-Aware Pattern Databases with 1-Bit Compression for Sliding Tile Puzzles

Proceedings of the International Symposium on Combinatorial Search, 12

Volume

Vol. 12 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search

Long Papers

A pattern database (PDB) is a pre-computed lookup table storing shortest distances from abstract states to abstract goal states. PDBs are key components in heuristic search as their entries are used to prune paths that cannot lead to an optimal solution. With the sliding-tile puzzle as an exemplary application domain, we present methods to improve the precision and size of PDBs by improving additive pattern databases to zero-aware additive pattern databases (ZPDBs), reducing the compression rate from previously 1.6 bit to 1 bit per entry, generating optimal additive pattern partitionings, and building effective collections of pattern databases. With these enhancements, we achieve an overall 8.59-fold performance gain on the 24-puzzle compared to the previously best set of 6-tile PDBs.

10.1609/socs.v10i1.18500