Pattern Databases (PDBs)

A pattern database (PDB) is a lookup table that stores exact shortest distances for a reduced version of a problem. During search, the current state is projected to the reduced representation and the stored distance is used as an admissible heuristic (a lower bound) for the full problem.

Workflow

Offline construction (one-time per goal state)

1. Select a pattern (e.g. subset of cubies / features).
2. Define an abstraction (reduced state space) that keeps only the pattern-relevant information.
3. Run BFS from the goal in the reduced space (retrograde construction).
4. Store the exact distance-to-goal for every abstract state.

Online use (during search)

1. Project the full state to the abstract pattern state.
2. Compute a unique index for the abstract state.
3. Lookup h(n) from the table.
4. Use h(n) inside A* or IDA* in case of limited memory.

Why PDB heuristics are admissible?

Let:

• S be the full state space,
• S' be the abstract state space,
• \pi : S \to S' be the projection (abstraction mapping),
• d'(s') be the exact goal distance in the abstract space.

Because abstraction removes constraints/details, solving the abstract problem cannot be harder than solving the original problem. Therefore the abstract distance is a lower bound on the real distance:

h(s) := d'(\pi(s)) \le d(s),

so h is admissible.

Korf’s Rubik’s Cube PDB design (1997)

Korf constructs three PDBs and combines them safely via a maximum.

Corner PDB (all 8 corners)

• Entries:

  8!\cdot 3^7 = 88{,}179{,}840
  

• Stored distances: 0,\ldots,11 (fits in 4 bits)
• Storage: \approx 42\,\mathrm{MB} with 4-bit packing

Two edge PDBs (two disjoint sets of 6 edges)

For each chosen set of 6 edges:

• Entries:

  \frac{12!}{6!}\cdot 2^6 = 42{,}577{,}920
  

• Stored distances: 0,\ldots,10 (fits in 4 bits)
• Storage: \approx 20\,\mathrm{MB} per table

Total storage for all three tables is \approx 82\,\mathrm{MB}.

Combining multiple PDB heuristics

Maximum (always safe)

For Rubik’s Cube, a single move can affect multiple cubies simultaneously, so corner and edge abstractions are not additive in a way that guarantees correctness. Korf therefore uses:

h(s) \;=\; \max\!\Bigl(h_{\text{corners}}(s),\; h_{\text{edgesA}}(s),\; h_{\text{edgesB}}(s)\Bigr).

This preserves admissibility while strengthening pruning.

Summation (only under additivity conditions)

Summing heuristics is admissible only when abstractions are constructed so that move costs can be safely distributed (additive / disjoint abstractions). This is not the combination strategy used in Korf (1997) for the cube.

Technical notes

4-bit packing

Distances are small, so storing each entry in a nibble gives:

• 2 entries per byte
• reduced memory footprint with cache-friendly sequential arrays

Indexing must be constant-time

The lookup path is on the hot loop of node expansion:

• encode orientations compactly
• rank permutations with combinatorial indexing
• avoid allocations and hashing

Amortization

PDB construction is expensive once and then reused across many solves with the same goal state.

References

• Richard E. Korf. Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. AAAI (1997).