Part of the book series:Communications in Computer and Information Science ((CCIS,volume 408))
Included in the following conference series:
689Accesses
2Citations
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. We computed 9-9-6, 9-8-7, and 8-8-8 PDBs for the 24-puzzle that are three orders of magnitude larger (up to 1.4 TB) than the 6-6-6-6 PDB. This was possible by performing a parallel breadth-first search in the compressed pattern space. Our experiments indicate an average 8-fold improvement of the 9-9-6 PDB over the 6-6-6-6 PDB on the 24-puzzle. Combining several large PDBs yields a 13-fold improvement.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Breyer, T.M., Korf, R.E.: 1.6-bit pattern databases. In: AAAI (2010)
Cooperman, G., Finkelstein, L.: New methods for using Cayley graphs in interconnection networks. Discrete Appl. Math.37, 95–118 (1992)
Culberson, J.C., Schaeffer, J.: Pattern databases. Comput. Intell.14(3), 318–334 (1998)
Edelkamp, S., Jabbar, S., Kissmann, P.: Scaling search with pattern databases. In: Peled, D.A., Wooldridge, M.J. (eds.) MoChArt 2008. LNCS, vol. 5348, pp. 49–64. Springer, Heidelberg (2009)
Felner, A.: Improving search techniques and using them on different environments. Ph.D. thesis (2001)
Felner, A., Adler, A.: Solving the 24 Puzzle with instance dependent pattern databases. In: Zucker, J.-D., Saitta, L. (eds.) SARA 2005. LNCS (LNAI), vol. 3607, pp. 248–260. Springer, Heidelberg (2005)
Felner, A., Korf, R.E., Hanan, S.: Additive pattern database heuristics. J. Artif. Intell. Res.22, 279–318 (2004)
Felner, A., Meshulam, R., Holte, R.C., Korf, R.E.: Compressing pattern databases. In: AAAI, pp. 638–643 (2004)
Holte, R.C., Newton, J., Felner, A., Meshulam, R., Furcy, D.: Multiple pattern databases. In: Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS-04), pp. 122–131 (2004)
Korf, R.E.: Depth-first iterative-deepening an optimal admissible tree search. Artif. Intell.27(1), 97–109 (1985)
Korf, R.E., Felner, A.: Disjoint pattern database heuristics. Artif. Intell.134(1–2), 9–22 (2002)
Korf, R.E., Schultze, P.: Large-scale parallel breadth-first search. In: Proceedings of the National Conference on Artificial Intelligence, vol. 20, pp. 1380–1385. AAAI Press/MIT Press (2005)
Zhou, R., Hansen, E.A.: Space-efficient memory-based heuristics. In: Proceedings of the National Conference on Artificial Intelligence, pp. 677–682. AAAI Press/MIT Press (2004)
Zhou, R., Hansen, E.A.: Breadth-first heuristic search. Artif. Intell.170(4–5), 385–408 (2006)
Acknowledgments
This work was partly supported by the EU project CONTRAIL, the DFG project FFMK and the North German Supercomputer Alliance HLRN.
Author information
Authors and Affiliations
Zuse Institute Berlin, Berlin, Germany
Robert Döbbelin, Thorsten Schütt & Alexander Reinefeld
- Robert Döbbelin
Search author on:PubMed Google Scholar
- Thorsten Schütt
Search author on:PubMed Google Scholar
- Alexander Reinefeld
Search author on:PubMed Google Scholar
Corresponding author
Correspondence toThorsten Schütt.
Editor information
Editors and Affiliations
Université Paris-Dauphine, Paris, France
Tristan Cazenave
Universiteit Maastricht, Maastricht, The Netherlands
Mark H.M. Winands
School of Information Science, JAIST, Nomi, Japan
Hiroyuki Iida
Appendix
Appendix
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Döbbelin, R., Schütt, T., Reinefeld, A. (2014). Building Large Compressed PDBs for the Sliding Tile Puzzle. In: Cazenave, T., Winands, M., Iida, H. (eds) Computer Games. CGW 2013. Communications in Computer and Information Science, vol 408. Springer, Cham. https://doi.org/10.1007/978-3-319-05428-5_2
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-319-05427-8
Online ISBN:978-3-319-05428-5
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative