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
Additional Services
| 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) |
| ISSN: | 1438-0064 |
| Published in: | Appeared in: Workshop on Computer Games, 2013 |
| Licence (German): |  Creative Commons - Namensnennung-Keine Bearbeitung |
