Building Large Compressed PDBs for the Sliding Tile Puzzle

Please always quote using this URN: urn:nbn:de:0297-zib-18095
  • 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.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Robert Döbbelin, Thorsten Schütt, Alexander Reinefeld
Document Type:ZIB-Report
Tag:heuristic search; pattern databases
CCS-Classification:E. Data / E.1 DATA STRUCTURES / Graphs and networks (REVISED)
I. Computing Methodologies / I.2 ARTIFICIAL INTELLIGENCE / I.2.8 Problem Solving, Control Methods, and Search (F.2.2) / Heuristic methods
Date of first Publication:2013/04/22
Series (Serial Number):ZIB-Report (13-21)
ISSN:1438-0064
Published in:Appeared in: Workshop on Computer Games, 2013
Licence (German):License LogoCreative Commons - Namensnennung-Keine Bearbeitung

$Rev: 13581 $