---
title: "Dual Lookups in Pattern Databases"
authors:
  - "Ariel Felner"
  - "Uzi Zahavi"
  - "Jonathan Schaeffer"
  - "Robert C. Holte"
doi: ""
url: "https://ijcai.org/proceedings/2005/12"
pdf: "https://ijcai.org/proceedings/2005/0012.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "103-107"
track: ""
keywords:
---

# Dual Lookups in Pattern Databases

Ariel Felner, Uzi Zahavi, Jonathan Schaeffer, Robert C. Holte

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 103-107.

## Abstract

A pattern database (PDB) is a heuristic function stored as a lookup table. Symmetries of a state space are often used to enable multiple values to be looked up in a PDB for a given state. This paper introduces an additional PDB lookup, called the dual PDB lookup. A dual PDB lookup is always admissible but can return inconsistent values. The paper also presents an extension of the well-known pathmax method so that inconsistencies in heuristic values are propagated in both directions (childto-parent, and parent-to-child) in the search tree. Experiments show that the addition of dual lookups and bidirectional pathmax propagation can reduce the number of nodes generated by IDA* by over one order of magnitude in the TopSpin puzzle and Rubik’s Cube, and by about a factor of two for the sliding tile puzzles.