1.6-Bit Pattern Databases

Teresa Maria Breyer, Richard E. KorfAAAI 2010 · DOI

Introduction

In heuristic search algorithms like A or IDA, the efficiency of the search is primarily dictated by the quality of the heuristic function $h(n)$. Pattern Databases (PDBs) have emerged as a powerful method for generating high-quality heuristics by precomputing and storing exact solutions to sub-problems in large lookup tables. However, the effectiveness of a PDB is often limited by available RAM; larger, more accurate databases require more memory than most systems can provide.

While lossy compression techniques can reduce the memory footprint, they often introduce errors that lead to increased node expansions during search. This paper presents a lossless compression technique that reduces PDB storage to just 1.6 bits per entry without sacrificing heuristic accuracy.

The Modulo-Three Heuristic

The core of the proposed method relies on a mathematical property of search spaces with unit-cost, reversible operators. In such environments, the heuristic value of a child node $h(c)$ can only differ from its parent $h(p)$ by -1, 0, or +1.

By storing only the heuristic value modulo three ($h(n) \pmod 3$), the system only needs to represent three possible states (0, 1, or 2). During the search process, the absolute heuristic value is reconstructed by comparing the child's modulo value to the parent's known absolute value. This allows the search to unambiguously determine if the child is closer to, further from, or at the same distance to the goal as the parent.

Illustration of heuristic value reconstruction using modulo-3 values in a search space.

1.6-Bit Packing

Standard binary storage for three values typically requires 2 bits per entry (which can represent up to 4 values). To achieve higher density, the authors utilize a packing optimization. Since $3^5 = 243$, five "modulo three" entries can be packed into a single 8-bit byte ($2^8 = 256$). This results in an effective storage rate of $8 / 5 = 1.6$ bits per entry. While this requires a small computational overhead for decoding (integer division or a small lookup table), the memory savings allow for significantly larger PDBs to reside in RAM.

Performance Evaluation

The technique was evaluated across several combinatorial puzzles, including the Rubik’s Cube, Top-Spin, and the 24-Puzzle. The results demonstrate that the memory efficiency of 1.6-bit PDBs allows for the use of larger patterns that were previously too big for standard memory limits.

In the case of the Rubik’s Cube, the 1.6-bit approach outperformed previous state-of-the-art optimal solvers by a factor of four. For puzzles like Top-Spin, where adjacent entries in the PDB lack high local correlation, this lossless method proved far superior to traditional lossy compression techniques.

Performance comparison of different compression techniques on the Rubik's Cube (8-corner) puzzle.

Conclusion

1.6-bit Pattern Databases provide a robust baseline for lossless compression in unit-cost search spaces. By leveraging the modulo-three property and efficient bit-packing, researchers can achieve a 2.5x to 5x compression factor compared to uncompressed tables. While the method is restricted to unit-cost and reversible operators, its ability to maintain perfect heuristic accuracy while significantly expanding the effective size of PDBs makes it a vital tool for solving complex combinatorial problems.

Summary updated

BibTeX
@inproceedings{breyer2010bit,
  author = {Teresa Maria Breyer and Richard E. Korf},
  title = {{1.6-Bit Pattern Databases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7558},
}
Figure