Symbolic and explicit search hybrid through perfect hash functions - a case study in connect four
Pages 101 - 110
Abstract
This work combines recent advances in AI planning under memory limitation, namely bitvector and symbolic search. Bitvector search assumes a bijective mapping between state and memory addresses, while symbolic search compactly represents state sets. The memory requirements vary with the structure of the problem to be solved. The integration of the two algorithms into one hybrid algorithm for strongly solving general games initiates a BDD-based solving algorithm, which consists of a forward computation of the reachable state set, possibly followed by a layered backward retrograde analysis. If the main memory becomes exhausted, it switches to explicit-state two-bit retrograde search. We use the classical game of Connect Four as a case study, and solve some instances of the problem space-efficiently with the proposed hybrid search algorithm.
References
[1]
Allen, J. D. 2011. The Complete Book of Connect 4: History, Strategy, Puzzles. Puzzlewright.
[2]
Allis, L. V. 1988. A knowledge-based approach of connect-four. Master's thesis, Vrije Universiteit Amsterdam.
[3]
Bakera, M.; Edelkamp, S.; Kissmann, P.; and Renner, C. D. 2009. Solving μ-calculus parity games by symbolic planning. In MOCHART, 15-33.
[4]
Botelho, F. C., and Ziviani, N. 2007. External perfect hashing for very large key sets. In ACM Conference on Information and Knowledge Management (CIKM), 653-662.
[5]
Botelho, F. C.; Pagh, R.; and Ziviani, N. 2007. Simple and space-efficient minimal perfect hash functions. In WADS, 139-150.
[6]
Breyer, T. M., and Korf, R. E. 2010. 1.6-bit pattern databases. In AAAI, 39-44.
[7]
Bryant, R. E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers 35(8):677-691.
[8]
Cooperman, G., and Finkelstein, L. 1992. New methods for using Cayley graphs in interconnection networks. Discrete Applied Mathematics 37/38:95-118.
[9]
Dietzfelbinger, M., and Edelkamp, S. 2009. Perfect hashing for state spaces in BDD representation. In KI, 33-40.
[10]
Edelkamp, S., and Kissmann, P. 2008. Symbolic classification of general two-player games. In KI, 185-192.
[11]
Edelkamp, S., and Kissmann, P. 2009. Optimal symbolic planning with action costs and preferences. In IJCAI, 1690-1695.
[12]
Edelkamp, S., and Kissmann, P. 2011. On the complexity of BDDs for state space search: A case study in Connect Four. In AAAI, 18-23.
[13]
Edelkamp, S., and Reffel, F. 1998. OBDDs in heuristic search. In KI, 81-92.
[14]
Edelkamp, S.; Sulewski, D.; Barnat, J.; Brim, L.; and Simecek, P. 2011. Flash memory efficient LTL model checking. Sci. Comput. Program. 76(2):136-157.
[15]
Edelkamp, S.; Kissmann, P.; and Torralba, Á. 2012a. Lex-partitioning: A new option for BDD search. In ETAPS-Workshop GRAPHITE, 66-82.
[16]
Edelkamp, S.; Kissmann, P.; and Torralba, Á. 2012b. Symbolic A* search with pattern databases and the merge-and-shrink abstraction. In ECAI, 306-311.
[17]
Edelkamp, S.; Sanders, P.; and Simecek, P. 2008. Semi-external LTL model checking. In CAV, 530-542.
[18]
Edelkamp, S.; Sulewski, D.; and Yücel, C. 2010. GPU exploration of two-player games with perfect hash functions. In ICAPS-Workshop on Planning in Games.
[19]
Edelkamp, S. 2005. External symbolic heuristic search with pattern databases. In ICAPS, 51-60.
[20]
Helmert, M.; Haslum, P.; Hoffmann, J.; and Nissim, R. 2013. Merge & shrink abstraction: A method for generating lower bounds in factored state spaces. Journal of the ACM. Accepted for Publication.
[21]
Kant, G., and van de Pol, J. 2014. Generating and solving symbolic parity games. In ETAPS-Workshop GRAPHITE.
[22]
Kissmann, P., and Edelkamp, S. 2010. Layer-abstraction for symbolically solving general two-player games. In SOCS, 63-70.
[23]
Korf, R. E. 2008. Minimizing disk I/O in two-bit breadth-first search. In AAAI, 317-324.
[24]
Kunkle, D., and Cooperman, G. 2007. Twenty-six moves suffice for Rubik's cube. In International Symposium on Symbolic and Algebraic Computation (ISSAC), 235-242.
[25]
Love, N. C.; Hinrichs, T. L.; and Genesereth, M. R. 2006. General game playing: Game description language specification. Technical Report LG-2006-01, Stanford Logic Group.
[26]
McMillan, K. L. 1993. Symbolic Model Checking. Kluwer Academic Publishers.
[27]
Romein, J. W., and Bal, H. E. 2002. Awari is solved. International Computer Games Association (ICGA) Journal 25(3):162-165.
[28]
Schaeffer, J.; Björnsson, Y.; Burch, N.; Kishimoto, A.; and Müller, M. 2005. Solving checkers. In IJCAI, 292-297.
[29]
Schuppan, V., and Biere, A. 2006. Liveness checking as safety checking for infinite state spaces. In INFINITY, 79-96.
[30]
Sievers, S.; Ortlieb, M.; and Helmert, M. 2012. Efficient implementation of pattern database heuristics for classical planning. In SOCS.
[31]
Sturtevant, N., and Rutherford, M. 2013. Minimizing writes in parallel external memory search. In IJCAI, 666-673.
[32]
Torralba, Á., and Alcázar, V. 2013. Constrained symbolic search: On mutexes, BDD minimization and more. In SOCS.
[33]
Torralba, Á.; Edelkamp, S.; and Kissmann, P. 2013. Transition trees for cost-optimal symbolic planning. In ICAPS, 206-214.
[34]
van Dijk, T.; Laarman, A.; and van de Pol, J. 2012. Multi-core and/or symbolic model checking. ECEASST 53.
[35]
von Neumann, J., and Morgenstern, O. 1944. Theory of Games and Economic Behavior. Princeton University Press.
Recommendations
Indexing internal memory with minimal perfect hash functions
SBBD '08: Proceedings of the 23rd Brazilian symposium on DatabasesA perfect hash function (PHF) is an injective function that maps keys from a set S to unique values, which are in turn used to index a hash table. Since no collisions occur, each key can be retrieved from the table with a single probe. A minimal perfect ...
Lexicon design using perfect hash functions
The research reported in this paper derives from the recent algorithm of Cichelli (1980) for computing machine-independent, minimal perfect hash functions of the form:hash value: hash key length + associated value of the key's first letter + associated ...
Lexicon design using perfect hash functions
CHI '81: Proceedings of the Joint Conference on Easier and More Productive Use of Computer Systems. (Part - II): Human Interface and the User Interface - Volume 1981The research reported in this paper derives from the recent algorithm of Cichelli (1980) for computing machine-independent, minimal perfect hash functions of the form:hash value: hash key length + associated value of the key's first letter + associated ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- NSF: National Science Foundation
- Artificial Intelligence Journal
- ECCAI123: European Coordinating Committee for Artificial Intelligence
- IBMR: IBM Research
- National ICT Australia
Publisher
AAAI Press
Publication History
Published: 21 June 2014
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025