Finding Optimal Solutions to the Twenty-Four Puzzle

AAAI 1996

TL;DR

This paper presents the first optimal solutions for random instances of the Twenty-Four Puzzle, a significantly larger sliding-tile puzzle than previously solved optimally. The authors introduce a novel theory for automatically discovering and applying more powerful admissible heuristics, moving beyond simple subproblems to consider multiple subgoals simultaneously.

What Problem Does This Paper Address?

The Twenty-Four Puzzle, a 5x5 sliding-tile puzzle, presents a massive search space (nearly 10^25 states), making it computationally infeasible to find optimal solutions using traditional AI search techniques. While smaller puzzles like the Eight and Fifteen Puzzle have been solved optimally, scaling up to the Twenty-Four Puzzle requires more efficient search algorithms and, crucially, more informed heuristic functions that can guide the search effectively. Existing heuristics, like Manhattan distance, are insufficient for such large state spaces.

Methods

The core of the paper lies in a new theory for automatically generating admissible heuristics. Instead of relying on domain-specific "hacks," the authors propose a general framework based on considering multiple subgoals simultaneously. This theory allows for the derivation of existing heuristics like Manhattan distance and its enhancements (linear conflict, last moves, corner tiles) through automated search processes.

Key techniques include:

  • Iterative-Deepening-A (IDA): A memory-efficient search algorithm that finds optimal solutions.
  • Manhattan Distance Heuristic: A standard admissible heuristic that sums the grid distances of each tile to its goal position.
  • Linear Conflict Heuristic: An enhancement that accounts for tiles in their goal row/column but reversed relative to each other.
  • Last Moves Heuristic: An enhancement that considers the moves required to place the blank in its goal position.
  • Corner-Tiles Heuristic: An enhancement that accounts for tiles adjacent to corners that need to be moved to correctly position corner tiles.
  • Pruning Duplicate Nodes: A technique using a finite-state machine to prevent the search from revisiting already explored states, significantly speeding up depth-first search.
  • Automated Heuristic Discovery: The paper outlines a method to derive heuristics by performing searches on simplified versions of the problem (e.g., considering only pairs of tiles) and storing the results in lookup tables. This process can be extended to consider triples, quadruples, and so on, leading to more powerful heuristics.

Datasets

The paper evaluates its methods on:

  • Random Nineteen Puzzle Instances: 100 randomly generated solvable instances of the 4x5 puzzle (approx. 10^18 states).
  • Random Twenty-Four Puzzle Instances: 10 randomly generated solvable instances of the 5x5 puzzle (approx. 10^25 states). These are presented as new benchmarks for optimal solving.

Key Insights and Ideas

  • The Power of Multi-Subgoal Heuristics: The most significant insight is that considering multiple subgoals simultaneously, rather than in isolation, leads to much more powerful admissible heuristics. This is a departure from traditional approaches.
  • Automated Heuristic Generation: The paper demonstrates that complex heuristics can be automatically learned through search, reducing the need for manual, domain-specific engineering. This has broad implications for AI search.
  • Cost-Effectiveness of Heuristics with Scale: While more powerful heuristics incur higher computation costs per node, their benefit in reducing the effective branching factor becomes crucial and cost-effective as problem sizes increase.
  • Pruning is Essential for Large State Spaces: The technique for pruning duplicate nodes, while orthogonal to the heuristic development, is shown to be critical for making depth-first search feasible on large problems.

Key Results

  • The paper reports the first optimal solutions found for random Twenty-Four Puzzle instances.
  • Nine out of ten randomly generated Twenty-Four Puzzle instances were solved optimally, with optimal solution lengths averaging over 100 moves.
  • The Nineteen Puzzle instances were all solved optimally, with an average solution length of 71.5 moves.
  • The developed heuristics, combined with duplicate node pruning, significantly reduced the number of nodes generated and the search time compared to simpler approaches.
  • The automated heuristic discovery process successfully derived Manhattan distance and its known enhancements, suggesting the generality of the theory.

Limitations and Future Work

  • Higher-Order Heuristics Complexity: While considering triples, quadruples, and higher-order combinations of tiles can lead to even more powerful heuristics, the problem of matching in hypergraphs becomes NP-Complete. The authors suggest a greedy approach might be necessary, leading to a lower heuristic value.
  • Computational Overhead: The process of learning and applying these more complex heuristics involves significant computational overhead, which might not be cost-effective for smaller problems.
  • Future Work: The authors suggest extending the theory to other combinatorial problems and exploring greedy approaches for higher-order matching. They also note that as machines get faster and problems grow larger, the necessity and cost-effectiveness of encoding more knowledge into heuristics will continue to increase.

Summary updated

BibTeX
@inproceedings{1996finding,
  title = {{Finding Optimal Solutions to the Twenty-Four Puzzle}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure