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

1 Introduction

The 8-puzzle is a prominent workbench model for mea­ suring the performance of heuristic search algorithms [Gaschnig, 1979; Nilsson, 1980; Pearl , 1985; Russell, 1992], learning methods [Laird et al., 1987] and the use of macro operators [Korf, 1985a]. It is simple, but has a combinatorially large problem space of 9!/2 states. The 8-puzzle is the largest possible N-puzzle that can be com­ pletely solved. There exist larger variants, e.g. the 15puzzle [Johnson and Storey, 1879], which can also be solved [Korf, 1985b], but not to completion. The gen­ eral N x N extension of the 8-puzzle is NP-hard [Ratner and Warmuth, 1986].

Complete Solution. We enumerated all9!/2 tile cc;m­ figurations and computed all optimal (shortest) solution paths for all problem instances with a fast iterative­ deepening search algorithm. Aside from Schofield's [1967] analysis of a weaker 8-puzzle variant, our work is the first that gives complete statistical data on this application. Our results (for a quick overview see the table in the Conclusions) includes statistical data on

• the lengths of optimal solutions,
• the solution density in the search tree,
• the "hardest" and "easiest" configurations,
• the average heuristi£. branching fador,
• the distribution of goal nodes in the search frontier .

Benefit of Node Ordering in IDA ·. Our experi­ ments were also moti¥ated by the need for a better un­ derstanding of the effectiveness of node ordering s.chemes in the IDA* search algorithm [Korf, 1985b]. L1ke any other iterative-deepening search, IDA* benefits by a good node expansion order, which reduces the time spent in the last (goal) iteration. Common ordering tech­ niques include basic hill-climbing methods, the longest­ path (principal variation) heuristic, the history heuristic and transposition tables. While some of these methods seem to work in practice (e.g. for the traveling salesman problem) it remained unclear how effective they are and which combination of the methods performs best. Our results give evidence that

• chances to find· a solution early in the last iteration are extremely poor for common IDA* implementa­ tions; simple random node selection is better ,
• steepest ascent hill-climbing does not help,
• a "history" table that holds a success score for each operator is better than random ordering,
• exploring the longest path first yields good perfor­ mance while requiring only 0( depth) storage space,
• the benefits of transposition tables are mainly due to caching previously expanded nodes rather than to an improved operator ordering.

2 The 8-Puzzle

The objective of the 8-puzzle is to rearrange a given ini­ tial configuration of eight squared tiles on a 3 x 3 board into a specified goal configuration by successively sliding tiles into the orthogonally adjacent empty square (the blank square). While it would seem easy to find any so­ lution to this problem, we are only interested in obtain­ ing optimal solutions with the fewest moves. We take, by convention, the following configuration to be the goal state:

There exist 9! possible tile permutations on a 3 x 3 board, and every second permutation is solvable [John­ son and Storey, 1879]. Hence, there is a total of 9!/2 = 181440 solvable problem instances.

A weaker variant of the 8-puzzle has been investigated by Schofield [1967] with a mixed analytical/empirical approach. His 8-puzzle variant includes only mappings from one 'standard position' into another, where a 'stan­ dard position' is one with the blank located in the mid­ dle square. The search space of this weaker puzzle has only 8!/2 = 20 160 states. Our definition of the 8-puzzle, in contrast, conforms to the larger 15- and 25-puzzles, which have the blank in the upper left square and which do not restrict the search space to 'standard positions'.

3 Complete Solution

We generated all 9!/2 solvable tile configurations and computed all optimal solutions for all problem instances. We used Korf's IDA* algorithm (for a description see Section 4) with the Manhattan distance as a heuristic estimate function. The whole experiment took less than one hour CPU-time on a SUN-SparcStation.

Solution Lengths. The average length of all optimal solution paths is r = 21.97, that is, almost 22 moves are needed to solve a given random configuration. Fig­ ure 1 shows the distribution of the optimal solution path lengths for all tile configurations. The two cases with the shortest (non-trivial) solution path r = 1 have either of tile 1 or 3 in the upper left corner:

Interestingly, these configurations do not build the largest trees. Their (complete) search trees have both 15 890 leaves, whereas the 'hardest' configurations spawn trees with three times as many nodes. Similar to other NP-complete problems [Cheeseman et al., 1991], the 8puzzle has a small number of very hard problem in­ stances which require significantly more leaf node ex­ pansions than average.

Solutions per Problem. For the 181440 solvable configurations, we found a total of 500 880 optimal so­ lutions. This gives an average solution density of 2. 76 per problem, with the minimum and maximum number lying at 1 and 64 solutions, respectively (see Figure 2) . About 3/4 of the problem instances have only one, two or three solutions. The two configurations with the most (64) solutions are:

The tiles are almost reversely ordered in these configu­ rations, resulting in long solution paths with many move transpositions. The search tree is relatively large (with

11333 total leaves), but it is not the largest (which has 41794 leaves) . There are 50 problems with more than 20 000 leaves on the optimal search frontier .

4 Benefit of Node Ordering in IDA*

Iterative-Deepening A*. IDA* [Korf, 1985b] is an efficient search method for applications with high heuris­ tic branching factors and low solution densities [Rao et al., 1991]. Typical applications of IDA* include single agent games like the N -puzzle, some variants of the trav­ eling salesman problem, floorplan optimization and the cutting stock problem.

IDA* performs a series of depth-first searches with successively increased cost-bounds. The total cost f(n) of a node n is made up of the cost already spent in reaching that node g(n), plus the estimated cost of the path to a goal state h(n). At the beginning, the cost bound is set to the heuristic estimate of the initial state, h(root) . Then, for each iteration, the bound is increased to the minimum path value that exceeded the previous bound:

procedure IDA* (n); bound:= h(n); while not solved do bound:= DFS(n, bound); function D F S ( n, bound) ; if f(n) >bound { initial bound is h( root) } { iterate until solved ... } { with increased cost bound} then return f( n ); { path cost exceeds bound } if h(n) = 0 then return solved; { goal found } return lowest value of D F S( n;, bound) for all succ. n; of n

With an admissible (non-overestimating) heuristic function h, IDA* is guaranteed to find an optimal (short­ est) solution path [Korf, 1985b]. Moreover, IDA* obeys the same asymptotic branching factor as A*, if the num­ ber of newly expanded nodes grows exponentially with the search depth [Korf, 1985b; Mahanti et al. , 1992]. This growth rate, the heuristic branching factor bh, is defined as the node ratio of two consecutive iterations.

It depends on the number of applicable operators per node (the edge branching factor be) and the discrimina­ tion power of the heuristic estimate function h. Using the Manhattan distance (the sum of the minimum dis­ placement of each tile from its goal position) as a heuris­ tic estimate function, we computed bh = 3.81 for the 8-puzzle. The corresponding value for the 15-puzzle, bh ~ 6.68, is much higher because there are more in­ terior squares with more move options [Reinefeld and Marsland, 1991].

The time to solve a problem is dominated by the time spent in the final (goal) iteration, which in turn depends on the expansion order of the leaves. A node is said to be expanded, when all its successors have been generated, or when it is a goal node. A leaf is an expanded node that has no expanded successors. Figure 3 illustrates a sample tree with three leaves. They all lie on a search frontier of an IDA* search with cost bound 7. We are primarily interested in optimal search frontiers that contain one or more goal nodes, as shown in the example.

Normalization. We want to find out how node order­ ing techniques improve the chances to find a solution early in the search frontier. For this purpose, we run IDA* on all 8-puzzle configurations and gathered sta­ tistical data on the location of goal nodes in the search front . In order to allow a direct comparison of the exper­ imental data, we normalized the search frontiers (which vary in size between 1 and 41794 leaves) to a common scale of 101 discrete data points. Here, 0 and 100 corre­ spond to the location of the leftmost and the rightmost leaf node, respectively. When the leaves are numbered from left ( = 1) to right ( = n ), the i-th leaf lies on posi­ tion !-=.~ in the normalized search frontier .

For trees with more than 100 leaves, normalization is no problem. Care must be taken when there are only few leaves, because this causes the values to cluster at certain data points. As an example, the first leaf in Figure 3 lies at location 0/2 = 0, the second at 1/2 = 50% and the third at 2/2=100% of the normalized search frontier .

Fixed Successor Ordering. For practical reasons, common IDA* implementations generate the node suc­ cessors in an arbitrary, but fixed sequence (e.g. up, left, right, down) . With such a scheme, one would expect the goal nodes to be evenly distributed over the whole search frontier. Surprisingly, this is not the case. Figure 4 de­ picts the distribution of all goal nodes in the last (deep­ est) search frontier ('all-solution-case'). The continuous plot shows the distribution of goal nodes with a fixed suc­ cessor ordering. In the middle part, each goal location occurs ~ 5000 times. This is as it should be, because the occurrences of all101 goal locations must add up to the total solution number 500 880. The zigza~ appearance with extreme points at specific locations (:4, ~, !· ... ) is caused by the normalization of small search trontiers with < 100 leaves, as discussed above.

More interesting are the 'shoulders' at both sides of the graph. They indicate a lower solution density in the left and right parts of the search frontier. This inter­ esting phenomenon reveals a serious deficiency of our - and presumably most other - IDA* implementation: To be time efficient, common implementations use a table driven operator selection scheme, which applies the oper­ ators always in the same order. Our program (and also Korf's [1985b]) first tries to move the blank up, then to the left, to the right and finally down. If done in a row, this results in a circular move path which finally runs into a dead end situation. Hence, chances to find a solution in the first path of the search tree are low.

Random Node Selection is Better. Figure 4 clearly indicates, that a fixed operator sequence is worse than average. The chances to hit a solution right at the beginning of the search tree can be greatly improved by randomly perturbing the operator sequence in each node. The resulting solution density graph (not shown here) is almost flat in the left part, as it should be.

Expanding the Longest Path First. While simple random node ordering outperforms any kind of fixed op­ erator sequence, we can do much better by applying do­ main dependent heuristics. One possibility is to inves­ tigate the deepest path of the previous iteration first. In multi-agent games, this path is called principal vari­ ation. It is the preferred move sequence, if both parties adhere to the minimax principle. In single-agent (IDA*) search, the longest path is the one that came closest to the goal. Since all nodes in the search frontier have the same /-value, the leaves on the longest paths have the highest g- and consequently lowest h-values.

The dotted graph in Figure 4 shows a much increased goal density in the left hand part of the search fron­ tier. The chances to find a goal in the first leaf node are more than three times higher than with a random node selection scheme. Consequently, the right part of the graph lies at a lower level, because all cases again add up to 500 880. Note that the longest-path heuristic af­ fects only the first few leaf expansions, because only one path is stored. However, additional experiments with a refined version that stores all longest paths were not successful, because the branching factor is too low in the 8-puzzle. Sophisticated variants only pay off in domains with a large branching factor, like the traveling salesman problem [Reinefeld and Marsland, 1991].

In practice, it often suffices to determine one optimal solution. When the search is stopped after a first so­ lution, the benefit of the longest-path heuristic is even more pronounced, as can be seen in Figure 5. Other favorite aspects of this heuristic are its low space com­ plexity of 0(/*) and its negligible CPU time overhead.

Steepest Ascent Hill-Climbing does not Help. Hill-climbing methods have been found useful in many AI applications. They sort the node successors in in­ creasing order of their heuristic estimates. Successors with low h-values are expanded first, with the expecta­ tion that they are closer to a goal. Our empirical results, however, did not reveal any significant ad vantage of hill­ climbing. This observation confirms an earlier assump­ tion of Powley and Korf [1991] and our own experiments with the larger 15-puzzle. In the 15-puzzle, we spotted a slight advantage of hill climbing in the left part of the tree, but this does not pay for the increased overhead of move pre-sorting. A quick investigation [Reinefeld and Marsland, 1991] reveals that hill-climbing favors tile con­ figurations with the blank located in either an edge or border square, because these configurations enjoy (sta­ tistically) lower h-values. Such configurations, however, have a lower 'mobility' and are thus less desirable.

History Heuristic. Dynamically acquired knowledge usually outperforms static sorting schemes (such as hill­ climbing). One dynamic method, that proved useful in adversary games, is Schaeffer's [1989] history heuristic. It maintains a score table, the history table, for every move seen in the search graph. In a given position, all applicable moves are examined in order of their previous success.

The history heuristic does not depend on domain spe­ cific knowledge (like heuristic estimate functions). It simply learns from the success in previously expanded subtrees. For the 8-puzzle, one needs a three dimensional array that holds a measure of the goodness of a move for each possible tile, each source position and each move direction. This gives 9 (tiles) x 9 (positions) x 4 (move directions) = 324 scores. As a measure of the goodness of a move, we counted the number of occurrences the specific move led to the deepest subtree.

Compared to the longest-path heuristic, the history heuristic provides ordering information for all nodes in the tree, and not only for the nodes on the first path. Even so, our empirical results (see the dashed lines in Figures 4 and 5) indicate, that the history heuristic is dominated by the longest-path heuristic. This might be attributed to the low branching factor of the 8-puzzle, and the inexact methods to measure the goodness of a move. We expect the history heuristic to be more suit­ able in domains with a larger branching factor and a fine grained evaluation function.

Transposition Table. Transposition tables are used in two-player games [Zobrist, 1970] to avoid unnecessary re-expansions of duplicate nodes (due to move transpo­ sitions and due to node re-expansions in successive iter­ ations). When there is enough memory space available, transposition tables are also used to store node informa­ tion for guiding the search process into the most promis­ ing direction.

We implemented a transposition table that holds a representation of every tile configuration seen in the search, the cost-bound to which the configuration has been searched and a best move (the move leading to the deepest subtree). As expected, the transposition table greatly reduces the number of node expansions, see Fig­ ure 6. We achieved an average 35% node count reduction per problem. However, most of the savings are due to eliminated transpositions. Node ordering plays only a minor role, and so the solution density graph looks very similar to that of the longest-path heuristic in Figures 4 and 5 (hence we did not plot it). This is again caused by the difficulties to distinguish between 'good' and 'bad' moves. We took the depth of the emanating subtree as a utility measure. But many subtrees end at the same level and hence a finer grained scoring function is needed. Another problem is the low branching factor of this spe­ cific application, which leaves only few node successors to be sorted.

5 Conclusions

Table 1 gives a summary of our empirical results. The 8-puzzle data has been derived by exhaustively solving all possible board configurations. For the 15-puzzle, no exact data can be given, because the search space is too large to be completely enumerated. We used Kor­ f's [1985b] selection of 100 randomly generated problem instances as a test set 1 .

In our second set of experiments, we used the 8-puzzle as a workbench to evaluate the benefit of node ordering techniques in iterative-deepening search. Surprisingly, we found that common IDA* implementations with a fixed operator sequence (e.g. up, left, right, down) per­ form worse than average. A simple random operator selection scheme is better!

The longest-path heuristic was found most effective. Consisting of a linear moves array, it is easy to implement and its space overhead of O(depth) is negligible. More sophisticated ordering techniques did not yield better performance, because the 8-puzzle has a low branching factor and it lacks a clear criterion for measuring the goodness of a move.

1 We identified three cases with differing node counts, which are J>robably due to typographical errors in the origi­ nal paper [Korf, 1985b] :

Acknowledgements

Thanks to Sam Loyd for providing the AI community with such an entertaining research subject . As early as 1878, he surely must have recognized the beauty of sim­ ple problem structures that spawn combinatorially large search spaces. Thanks also to Martin Lehmann (Univ. Hamburg) for his continuous interest and many stimu­ lating discussions.