jms@sun.udel.edu (John Milbury-Steen) (06/29/90)
Anybody recall a discussion from any AI literature on a heuristic for deciding which tile to move next in the 8-tile puzzle? In this puzzle, there are 9 locations for tiles: 8 actual tiles, and one empty space. The tiles are out of order, and the user has to sort the tiles by repeatedly moving a tile into the empty space. Anyone seen a Prolog program that does this? A friend of mine wants to see what happens when you apply it to a 15-tile puzzle. -- | John Milbury-Steen (302)451-2698 jms@sun.acs.udel.edu | | Office of Academic Computing and Instructional Technology | | University of Delaware Newark DE 19716 | | "I like to think I have another life." |
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/30/90)
In article <12398@sun.udel.edu>, jms@sun.udel.edu (John Milbury-Steen) writes: > [the 8-puzzle, any heuristics? how about a Prolog program?] A reasonable approach is to use the A* algorithm. That requires an estimate of the distance from the current position to a solution, and a fairly common heuristic for that is to count the number of tiles which are not in their final position. A* is not _quite_ as trivial as depth first search (although if you have the DEC-10 Prolog or Quintus Prolog library(heaps) and library(ordsets) packages or functional equivalents it's actually rather simple) but for a problem like this where the search space has more cycles than you can shake a stick at and isn't all that small even if you disregard the cycles, the extra performance of A* is well worth having. -- "private morality" is an oxymoron, like "peaceful war".
coleman@makaha.cs.ucla.edu (Michael Coleman) (07/03/90)
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <12398@sun.udel.edu>, jms@sun.udel.edu (John Milbury-Steen) writes: >> [the 8-puzzle, any heuristics? how about a Prolog program?] >[How about A*? ] An improvement on A*, particularly for this problem is IDA*, which stands for iterative-deepening A*. Rich Korf used this algorithm to solve the 15-puzzle, which is difficult or impossible using A* (or was at the time), because of memory use. The algorithm is basically iterative depth-first search where cutoff is chosen in an A* manner. Quickly, you cut off search when the estimated length of the shortest completion path from the current node is greater than the bound. The bound for each iteration is the smallest estimate seen in the previous interation which is greater than the bound of the previous iteration. See Korf's paper for more details. The most surprising (to me) feature of this algorithm is that it is faster and uses less memory than A* for the 8-puzzle. The reason is that there is no "OPEN" list to manage; the action is all DFS-like. I've implemented this in C. Average solution time for random initial configurations is 0.2 seconds on a SS1+. -- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% try. %% "When at first you try :- try. %% don't succeed, ..." (coleman@cs.ucla.edu)
peter@uk.ac.ed.aipna (Peter Ross) (07/04/90)
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <12398@sun.udel.edu>, jms@sun.udel.edu (John Milbury-Steen) writes: >> [the 8-puzzle, any heuristics? how about a Prolog program?] > >[How about A*? ] A lightweight comment: the heuristic I use which enables me to solve the 8- and 15-puzzles by hand without much trouble is, to refer to the 8-puzzle case, to look at it as a roundabout of the eight exterior cells and a single register in the centre. I use the single register while doing a sort of the sequence of the eight exterior cells to achieve the order 1/2/3/6/blank/8/7/4. The operators are obvious: cycle the roundabout one left, cycle it one right, move the blank to or from a centre-side. The same idea applies to the 15-puzzle; the main memory load is remembering the ordering of the exterior cells to be achieved. I find it harder to work the 24-puzzle.. Not difficult to implement this in Prolog, of course. Peter Ross Dept of AI Edinburgh University