Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA

TL;DR

This paper presents the first exhaustive statistical analysis of the 8-puzzle, revealing detailed insights into solution lengths, search space characteristics, and the surprising ineffectiveness of complex node ordering strategies in IDA* search. It demonstrates that for this problem, a simple random operator selection often outperforms more sophisticated methods, and the "longest path first" heuristic offers a compelling balance of performance and efficiency.

What Problem Does This Paper Address?

The 8-puzzle, a classic sliding tile puzzle, serves as a fundamental benchmark for artificial intelligence search algorithms. While seemingly simple, its state space is combinatorially large (9!/2 solvable states), making exhaustive search computationally infeasible for many algorithms. Researchers have long sought efficient methods to find optimal (shortest) solutions. This paper tackles two main challenges:

  1. Complete Characterization: Providing a comprehensive statistical understanding of the 8-puzzle's problem space, including expected solution lengths, "hardest" and "easiest" configurations, and the distribution of goal nodes within search trees.
  2. IDA* Node Ordering Effectiveness: Evaluating the impact of various node ordering strategies on the performance of Iterative-Deepening A (IDA), a popular search algorithm for problems with large branching factors and low solution densities. The paper questions whether complex, domain-specific heuristics truly offer benefits over simpler approaches.

Methods

The authors employed two primary experimental approaches:

  1. Exhaustive Solution Generation: They systematically generated all 9!/2 (181,440) solvable configurations of the 8-puzzle. For each configuration, they computed an optimal solution path using Korf's IDA* algorithm with the Manhattan distance heuristic. This allowed for the collection of detailed statistical data on solution lengths, search tree properties, and solution densities.
  2. IDA* Node Ordering Evaluation: The 8-puzzle was used as a testbed to compare different node ordering strategies within IDA*. These strategies included:
  3. Fixed Operator Sequence: Applying operators (e.g., up, left, right, down) in a predefined order.
  4. Random Node Selection: Randomly choosing the next operator to apply.
  5. Longest Path First: Prioritizing nodes that represent the longest path explored in the previous iteration.
  6. History Heuristic: Learning from past search experience to guide node expansion.
  7. Transposition Table: Caching previously encountered states to avoid re-expansion.

Datasets

The paper uses the 8-puzzle as its primary dataset. Specifically, it analyzes all 9!/2 = 181,440 solvable configurations. This is a newly generated, exhaustive dataset for the 8-puzzle, differing from previous work that often relied on smaller, randomly sampled problem sets or weaker variants of the puzzle.

Key Insights and Ideas

  • The 8-Puzzle is "Easy" to Solve, But Its Search Space is Complex: While the average optimal solution length is around 22 moves, and the problem is fully solvable, the search space is vast. The paper highlights that a small number of "very hard" problem instances exist, requiring significantly more nodes to be explored than average.
  • Surprising Ineffectiveness of Complex IDA* Strategies: The most striking finding is that many common IDA implementations, which use fixed operator sequences, perform worse* than a simple random ordering of operators. This suggests that for the 8-puzzle, the assumed benefits of complex ordering might be illusory or even detrimental.
  • Simplicity Wins (Sometimes): A simple random operator selection scheme proved to be better than fixed sequences and, in many cases, competitive with or better than more elaborate heuristics.
  • "Longest Path First" is a Sweet Spot: The "longest path first" heuristic offers a significant improvement in finding solutions early in the search frontier, especially when stopping after the first solution is found. Crucially, it achieves this with minimal computational overhead and low memory requirements (O(depth)).
  • Transposition Tables Primarily Cache, Not Order: The significant speedups observed with transposition tables are largely attributed to avoiding redundant state expansions rather than to an improved operator ordering.

Key Results

  • Average Solution Length: 21.97 moves.
  • Total Solvable Configurations: 181,440.
  • Average Number of Solutions per Problem: 2.76.
  • Maximum Number of Solutions: 64.
  • Fixed Operator Sequence Performance: Worse than average.
  • Random Node Selection Performance: Better than fixed sequences.
  • Longest Path First Performance: Significantly improves goal density in the early search frontier, leading to faster first solutions.
  • Transposition Table Performance: Achieved an average 35% reduction in node expansions, primarily due to caching.

Limitations and Future Work

  • 8-Puzzle Specificity: The findings regarding the ineffectiveness of complex ordering might be specific to the 8-puzzle's relatively low branching factor. The authors suggest that more sophisticated ordering techniques might be more beneficial in domains with larger branching factors (like the Traveling Salesman Problem).
  • History Heuristic Limitations: The history heuristic, while promising in theory, did not perform as well as the longest-path heuristic for the 8-puzzle. This is attributed to the low branching factor and the difficulty in accurately measuring the "goodness" of a move.
  • Future Work: The paper implicitly suggests exploring more refined ordering heuristics for domains with higher branching factors and investigating why simple random ordering performs so well on the 8-puzzle. Further research could also delve into the specific characteristics of the "very hard" problem instances identified.

Summary updated

BibTeX
@inproceedings{1993complete,
  title = {{Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure