Symbolic and Explicit Search Hybrid through Perfect Hash Functions — A Case Study in Connect Four

Authors

  • Stefan Edelkamp University of Bremen
  • Peter Kissmann University of Saarbrücken
  • Martha Rohte University of Bremen

DOI:

https://doi.org/10.1609/icaps.v24i1.13637

Keywords:

Game Playing, Symbolic Search, Memory-Limited Search, Bitvector Search

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.

Downloads

Published

2014-05-10

How to Cite

Edelkamp, S., Kissmann, P., & Rohte, M. (2014). Symbolic and Explicit Search Hybrid through Perfect Hash Functions — A Case Study in Connect Four. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 101-110. https://doi.org/10.1609/icaps.v24i1.13637