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:
- 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.
- 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.
- 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.
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.
- 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