@misc{DoebbelinSchuettReinefeld, author = {D{\"o}bbelin, Robert and Sch{\"u}tt, Thorsten and Reinefeld, Alexander}, title = {Building Large Compressed PDBs for the Sliding Tile Puzzle}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18095}, abstract = {The performance of heuristic search algorithms depends crucially on the effectiveness of the heuristic. A pattern database (PDB) is a powerful heuristic in the form of a pre-computed lookup table. Larger PDBs provide better bounds and thus allow more cut-offs in the search process. Today, the largest PDB for the 24-puzzle is a 6-6-6-6 PDB with a size of 486 MB. We created 8-8-8, 9-8-7 and 9-9-6 PDBs that are three orders of magnitude larger (up to 1.4 TB) than the 6-6-6-6 PDB. We show how to compute such large PDBs and we present statistical and empirical data on their efficiency. The largest single PDB gives on average an 8-fold improvement over the 6-6-6-6 PDB. Combining several large PDBs gives on average an 12-fold improvement.}, language = {en} }