Path: utzoo!attcan!uunet!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!sdd.hp.com!ucsd!orion.oac.uci.edu!ucivax!druby
From: druby@ics.uci.edu (David Ruby)
Newsgroups: comp.ai
Subject: Re: 15-puzzle
Message-ID: <270CC470.29340@ics.uci.edu>
Date: 5 Oct 90 17:35:44 GMT
References: <1491@meaddata.meaddata.com> <20930@well.sf.ca.us> <1990Oct05.010238.9554@comp.vuw.ac.nz>
Distribution: comp
Organization: UC Irvine Department of ICS
Lines: 69

>In article <20930@well.sf.ca.us>, nagle@well.sf.ca.us (John Nagle) writes:
>|> gordon@meaddata.com (Gordon Edwards) writes:
>|> 
>|> >I would like references on the 15-puzzle and various approaches to
>|> solving it.
>|> 
>|>      One simple approach is to get the top row and left column in
>|> order by
>|> suitable manipulation.  Having done this, which is easy, you have
>|> reduced the
>|> 4x4 15-puzzle to the 3x3 8-puzzle.  Repetition of this process
>|> reduces the
>|> 8-puzzle to the 2x2 3-puzzle.  A final repetition solves the puzzle.
>|> Who needs AI?
>|> 
>|> 					John Nagle

>I'd like to see a system that, given a description of the puzzle, could
>find this way of solving the puzzle, rather than just finding *a*
>solution.  Then I'd think there might be something intelligent going
>on!

>Lindsay

SteppingStone, a learning problem solver, does solve the tile sliding puzzle is
a manner very similar to this.  It begins by ordering the subgoals (tiles to be
placed) using a general heuristic called openness.  The effect of this
ordering is to set up the tiles along the upper row and left hand column to
be solved first, reducing the problem difficulty as mentioned.  A means-ends
analysis like approach is then used to try and place the tiles without undoing
them once solved.  With the orderings produced using the openness heuristic,
there is only one tile along the upper row and one tile along the left
hand column that can't be solved in this manner.

When a tile cannot be solved under this assumption, the system searches
through its knowledge to see if it has an approach for solving this type of
subproblem.  Knowledge is stored as a new sequence of subgoals for leading the
means-ends analysis component to a state where all of the previously solved
subgoals are still solved and the current subgoal is also solved.  When the
system does not have knowledge for solving a particular subgoal it falls back
on a local search approach.  After solving the subproblem, the solution is
generalized into a new sequence of subgoals for reuse on other problems.
Note, that the system only checks its knowledge when it cannot solve a subgoal
(tile) under its simplifying assumption.

Unlike previous learning problem solvers that learn control rules or
macro-operators, SteppingStone learns sequences of subgoals or stepping
stones.  Here a subgoal is a partial state description.  The stepping stones
are used by the means-ends analysis component to lead the system through
difficult portions of the problem.  SteppingStone solved tile sliding problems
ranging in size from the 3x3 8-puzzle to the 6x6 35-puzzle.  The results were
published in the article:

	"Learning subgoal sequences for planning" by David Ruby and Dennis Kibler
in the proceeding of the Eleventh International Joint Conference on Artificial
Intelligence (IJCAI-89).

More recently SteppingStone has been used to learn to optimize logic synthesis
problems.  The goal is now to demonstrate it on a series of benchmarks in the
logic synthesis community as well as extend it to other domains.

David Ruby
Graduate Student
University of California, Irvine



-- 
David Ruby