Optimal 8/15-Puzzle Solver
The 8-puzzle is a classic problem in AI that can be solved with the A* algorithm.
- A* maintains two lists, called open and closed.
- At the beginning of the algorithm, the initial node is placed on the open list. The list is sorted according to an admissible heuristic that measures how close the state of the node is to the goal state.
- At each step, bestNode is removed from the open list. In this case, bestNode is always the head of the open list. If the state of bestNode is the goal state, then the algorithm terminates. Otherwise bestNode is expanded (we determine all the possible states that can be reached within a single move), and bestNode is placed on the closed list.
- The successors of bestNode are placed on the open list if either:
- the successor is not already on the open or closed list, or
- the successor is already on the open or closed list but has a lower cost.
Many 15-puzzles cannot be solved with the A* algorithm, since it generates too many new states and consumes a lot of memory maintaining these lists. To solve this larger puzzle, Iterative-Deepening-A* (IDA*) can be used. Like the A* algorithm, it finds optimal solutions when paired with an admissible heuristic but is much more efficient with respect to space. IDA* is described as follows:
- Set threshold equal to the heuristic evaluation of the initial state.
- Conduct a depth-first search, pruning a branch when the cost of the latest node exceeds threshold. If a solution is found during the search, return it.
- If no solution is found during the current iteration, increment threshold by the minimum amount it was exceeded, and go back to the previous step.
Three heuristics have been implemented for comparison's sake:
- Manhattan Distance
- Manhattan Distance + Linear Conflict
- Additive Pattern Database Heuristic with Static 6-6-3 Partitioning
A. Felner, R. Korf, and S. Hanan, "Additive Pattern Database Heuristics," Journal of AI Research, Vol. 22, pp. 279-318, 2004.
This JAR file is about 5.8 MB. Please be patient while it loads.
Download executable JAR: PuzzleSolver.jar
|
|
Implementation
This applet provides a means of comparing how different algorithms and heuristics perform on the sliding-tile puzzles. A* is more than acceptable for solving the the 8-puzzle, with its 9! / 2 = 181,440 states and optimal solutions of up to 31 moves. It becomes painfully slow, however, for even average length solutions of the 15-puzzle, which has 16! / 2 = 10,461,394,944,000 states and optimal solutions of up to 80 moves.
IDA* works well on most 15-puzzle configurations, especially when paired with the additive pattern database heuristic. 6-6-3 partitioning provides a good compromise between speed and the amount of memory required to hold the state-to-cost mappings, of which there are 11,534,880. The application runs slightly faster on 64-bit systems running a 64-bit JVM, since there are operations on long primitives.
Starting with version 2.2.0, multi-threaded IDA* can be used to more efficiently solve puzzles. This new algorithm starts with a breadth-first search of the tree to a level that has a number of nodes greater than or equal to the number of threads. Any nodes that contain the same board configuration are pruned before starting the thread pool. Then multiple depth-first search workers crawl through the search space, looking for a solution of up to threshold moves, as discussed above.
The number of threads is curently hard-coded at twice the number of available cores. This seemingly unusual number has provided the best performance in most cases on my AMD Phenom II x6. Ideally, we want the algorithm to minimize CPU idle time. Idle time occurs toward the end of an iteration in IDA*, when the depth-first search workers start to taper off. Without more complicated code, the next iteration cannot start until we are certain there is no solution for the given threshold. Thus, starting more threads than cores keeps the CPU at max capacity over most of the iteration and generally performs better than when starting fewer threads, even with the added cost of context switching.
Why bother with multi-threading? A single-threaded Java implementation of IDA* cannot compete with the same C implementation. When profiling this code, one will observe that a large majority of execution time is spent in looking up costs in Node.h(). This section of this method that implements with the pattern database heuristic is simple, but Java's array bounds checking truly hinders performance. In a simple test of Java versus C (compiled with gcc, -O2) where array elements are accessed in random order millions of times, C outperformed Java by a factor of 8. When applying the applet's pattern database heuristic, arrays are used only for cost lookups and to store the path to the goal state. Everything else has been implemented with primitives and shift operations. So, in order to improve performance, one must turn to multi-threading.
Usage
The 8/15-Puzzle Solver is easy to use. The options should be straightforward. To enter the configuration of a puzzle, simply list the numbers of the tiles from left to right, top to bottom, each separated by a comma. Enter 0 for the space. For example, "2,4,0,1,8,5,3,6,7" is what you would enter for the board configuration below:
| 2 | 4 | |
| 1 | 8 | 5 |
| 3 | 6 | 7 |
Note that you must use IDA* to solve 15-puzzles, as the A* option has been purposefully disabled. Multi-threading is not available unless you accept the certificate, since the thread pool cannot be shutdown with the default policy settings, and is not available with the 8-puzzle (since a single thread is more than sufficient).