Efficiently Searching the 15-Puzzle
Joseph C. Culberson and Jonathan Schaeffer
Date: May 1994
University of Alberta Computing Science Technical Report TR94-08
Abstract
The A* algorithm for single-agent search has attracted considerable
attention in recent years due to Korf's iterative deepening improvement
(IDA*). The algorithm's efficiency depends on the quality of the lower
bound estimates of the solution cost. For sliding tile puzzles,
reduction databases are introduced as a means of improving the lower
bound. The database contains all solutions to the subproblem of
correctly placing N tiles. For the 15-Puzzle, IDA* with reduction
databases (N=8) are shown to reduce the total number of nodes searched
on a standard problem set of 100 positions by over 1000-fold. With the
addition of transposition tables and endgame databases, an improvement
of over 1700-fold is seen.
Technical Report(postscript)
It can also be retrieved by
anonymous ftp
ftp.cs.ualberta.ca pub/TechReports
See also the final version
Searching with Pattern Database to appear in AI'96.
Queries: email joe@cs.ualberta.ca
or jonathan@cs.ualberta.ca
Joseph Culberson
May 13,1994