Some Experiments with Case-Based Search

Steven Bradtke, Wendy G. LehnertAAAI 1988

Abstract

This paper explores the integration of Case-Based Reasoning (CBR) with heuristic search in the domain of the 8-puzzle. By utilizing a library of past solutions and a coarse indexing function, the proposed Case-Based Search (CBS) algorithm demonstrates that raw experience can effectively guide search processes in complex state spaces, often outperforming traditional hand-coded heuristics.

Introduction

In traditional AI, solving puzzles like the 8-puzzle typically requires a "domain model"—a set of rules and a hand-crafted evaluation function (like Manhattan distance) to guide the search. This research asks a provocative question: Can we solve these problems using nothing but a memory of past successes?

The challenge is that the 8-puzzle has over 181,000 possible states. A system cannot simply memorize every solution. To be effective, a "Case-Based Search" (CBS) algorithm must be able to generalize from a small set of known solutions to solve entirely novel board configurations.

Methods

The authors introduce the Case-Based Search (CBS) algorithm, which operates in three main steps:

  1. Coarse Indexing: Instead of looking at exact board positions, CBS uses a "coarse index function" to map board states into equivalence classes (represented by integers). This allows the system to treat different but "similar" boards as the same state, facilitating generalization.
  2. Discrimination Nets: Past solutions (sequences of board states) are stored in a tree-like structure called a discrimination net. This makes it computationally efficient to check if a current search path matches a known solution pattern.
  3. Search Masking: During active problem-solving, the algorithm generates possible moves but "masks" (prunes) any move that doesn't match a sequence stored in the discrimination net.
Structure of a Discrimination Net for storing solution sequences.

If the algorithm gets stuck (the "mask" fails), it employs two fallback heuristics:

  • Near-miss: A local search of the immediate neighborhood to find a state that is in the case-base.
  • Far-miss: A random walk to a new area of the state space, hoping to land in a region covered by the case-base.

Experimental Setup

The researchers evaluated CBS using several different "case-bases" (libraries of solutions), each containing roughly 1,000 board states:

  • Random: Solutions generated by random walks away from the goal.
  • Human: Solutions recorded from a human player using a sub-goal strategy.
  • Perfect: Minimum-length (optimal) solutions.

They also tested seven different index functions, ranging from simple "City-block" (Manhattan distance) to complex "Toroidal Adjacency" (which treats the board as a wrap-around surface).

Key Results

The empirical evaluation showed that the choice of index function is critical to performance.

Performance of CBS across various index functions and case-bases.
  • Total Success: Using the Relaxed Toroidal Adjacency index, the system solved 100% of 1,000 random test cases, regardless of whether the case-base was "Random," "Human," or "Perfect."
  • Efficiency: With the right index, the average search required looking at only 21 to 31 boards to find a solution.
  • Generalization through "Blurriness": The "coarse index" is the secret sauce. By intentionally losing some detail about the board state, the algorithm can apply a solution from a "similar" past case to a new problem.
  • Randomness Beats Human Logic: Surprisingly, case-bases built from random walks often outperformed those built from human solutions. Human strategies tend to visit a very narrow subset of board states, whereas random walks provide broader coverage of the state space.

Conclusion

While successful on the 8-puzzle, scaling this to more complex domains remains a challenge due to the exponential growth of states. Furthermore, the "Perfect Index" mentioned in the paper is a theoretical benchmark; calculating it requires solving the entire state space beforehand. Despite these limitations, the study demonstrates that CBS is a powerful heuristic search algorithm that effectively leverages raw experience to navigate complex problem spaces.

Summary updated

BibTeX
@inproceedings{bradtke1988some,
  author = {Steven Bradtke and Wendy G. Lehnert},
  title = {{Some Experiments with Case-Based Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure