Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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

Author:Robert Döbbelin, Thorsten SchüttORCiD, 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)
Published in:Appeared in: Workshop on Computer Games, 2013
Licence (German):License LogoCreative Commons - Namensnennung-Keine Bearbeitung
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.