TEACH SOLVEMS                                Steven Hardy, May 1982

                              TEACH SOLVEMS
                      (Problem solving by computer)

Computer problem solving is a huge area and we'll only be scratching
the surface in this file.

Two main issues dominate the study of problem solving. The first is
representation and the second is search. For a computer to solve a
problem, it must have representation of the problem. Usually, the
problem can be solved only be searching through a 'space' of alternative
solutions. Finding techniques for ordering such searches was once an
important endevour in AI circles; recently techniques for representing
problems are the main focus of attention.

There is a wealth of literature about search techniques which is now
fairly well understood. Most of this literature is rather mathematical
in nature. Discussion of the relative merits of different
representations is inappropriate at this stage and we will not spend
much time discussing it.

For details of different search strategies see:

    THE THINKING COMPUTER (chapter 3) Bertram Raphael
    ARTIFICIAL INTELLIGENCE (pp 89 to 106) Patrick Winston
    ARTIFICIAL INTELLIGENCE AND NATURAL MAN (ch 12) Margaret Boden
    PROBLEM SOLVING METHODS IN ARTIFICIAL INTELLIGENCE Nils Nillson

However, before looking at any of these books do the exercise described
below. Reading always makes more sense if one has played with the
problem oneself before looking at other people's ideas!

-- AN EXAMPLE: SLIDING TILES -------------------------------------------

A problem typical of those that occupied early AI researchers is the
sliding tiles puzzle. A square frame holds eight smaller squares each
with a number written on it. The frame has room for nine small squares,
so one position is free, for example:

        *************
        * 6 * 8 * 7 *
        *************
        * 3 * 5 * 1 *
        *************
        * 4 * 2 * - *
        *************

In this configuration, two moves are open to us: we can slide the 2 to
the right or slide the 1 down, thus:

        *************               *************
        * 6 * 8 * 7 *               * 6 * 8 * 7 *
        *************               *************
        * 3 * 5 * 1 *               * 3 * 5 * - *
        *************               *************
        * 4 * - * 2 *               * 4 * 2 * 1 *
        *************               *************


After sliding the 2 to the right, three further moves are open to us: we
could slide the 2 back to the left, slide the 4 to the right or slide
the 5 down, thus:

        *************               *************
        * 6 * 8 * 7 *               * 6 * 8 * 7 *
        *************               *************
        * 3 * 5 * 1 *               * 3 * - * 1 *
        *************               *************
        * - * 4 * 2 *               * 4 * 5 * 2 *
        *************               *************

The aim of the puzzle is to find some sequence of moves that leaves us
in the configuration:

        *************
        * 1 * 2 * 3 *
        *************
        * 4 * 5 * 6 *
        *************
        * 7 * 8 * - *
        *************

PROBLEM SOLVING METHODS IN AI contains a full discussion of this problem.

-- EXERCISE ------------------------------------------------------------

Solve the sliding tiles puzzle given above. Do this by getting a BIG
piece of paper and writing out the 'tree' of possible configurations
starting at the given initial state. As there 40,320 different
configurations you will have to employ some strategy to avoid having to
explore every possible combination of moves. Almost certainly, this will
involve you making some assesment of 'how close' any given configuration
is from the goal configuration. Try and develop a formula giving an
estimate of this number; a not very good estimate of distance is to
merely count how many tiles are misplaced. Once you have devised a
formula, then re-solve the problem, this time being entirely guided by
your formula. use the following method:

  (a) Write the number generated by your formula along side the intial
      state.
  (b) Repeat this operation for the configurations one move away from the
      intial configuration and cross out the initial configuration.
   (c) Pick the configuration which has not been crossed out and which has
      the smalled number beside it.
  (d) If this is the goal configuration then stop.
  (e) Repeat from step (b) with the chosen configuration in place of the
      intial configuration.

How good is your formula? If your formula were perfect you need only
have looked at those configurations en-route to the goal.

Try out your formula on at least one more configurations of your own
devising.

------------------------------------------------------------------------

We now describe a program which can carry out a 'forward chaining'
search from an initial state to a goal state. The main procedure is called
SEARCH; it takes as argument an INITIAL state. It finds a path (ie list of
states) from INITIAL to some goal state (tested with the sub-procedure
ISGOAL, a user supplied predicate).

The sub-procedure ADJACENT is used to find states 'adjacent' to any
given state. This procedure must be supplied by the user. It is given as
argument a state and returns a list of states adjacent to that state.

SEARCH uses a number of 'local variables'. CURRENT is the state
currently under consideration. HISTORY contains a list of states from
INITIAL up to but not including CURRENT. The states adjacent to CURRENT
are converted to complete paths and, using sub-procedure INSERT, added
to a list of UNTRIED paths. Only those new paths which not 'looping
back' on themselves are added to the UNTRIED list.

Having added all states ADJACENT to the current state to the UNTRIED
list, the SEARCH procedure picks the next element of UNTRIED and makes
it the CURRENT state.

Here is the definition of SEARCH:

1   define search(initial);
2       vars current, history, untried, option, new;
3       initial -> current;
4       [] -> history;
5       [] -> untried;
6       until isgoal(current) do
7           for option in adjacent(current) do
8               unless member(option, history) do
9                   [^^history ^current ^option] -> new;
10                  insert(new, untried) -> untried;
11              endunless;
12          endfor;
13          untried --> [[??history ?current] ??untried];
14      enduntil;
15      [COMPLETE PATH IS ^^history ^current] =>
16  enddefine;

Line (1) states that this is the defintion of the procedure SEARCH which
takes one argument, INITIAL.

Line (2) declares the 'local variables' used by SEARCH.

Line (3) says that the INITIAL state is the CURRENT state.

Line (4) says that the HISTORY of this CURRENT state is an empty list.

Line (5) says that there are initially  no other UNTRIED paths.

Line (6) starts a loop that won't be complete until the CURRENT state is
a goal state (ie ISGOAL returns TRUE whhen given CURRENT).

Line (7) starts a loop of all states ADJACENT to the CURRENT state.
These new states are referred to with the variable OPTION.

Line (8) checks if the OPTION under consideration is looping back on
itself. This will be so if OPTION is a MEMBER of the HISTORY. Lines (9)
and (10) are obyed only if this is not the case.

Line (9) constructs the NEW path. This is the HISTORY of the CURRENT
state followed by the CURRENT state and finally the new OPTION.

Line (10) INSERTs this NEW path in the list of UNTRIED paths.

Line (11) is the end of the UNLESS statement started on line (8).

Line (12) is the end of the FOR loop started on line (7).

Line (13) is complicated. It is a 'pattern matched assignment' which
splits up the UNTRIED list into a new CURRENT state, its HISTORY and the
remaider of the UNTRIED list.

Line (14) is the end of the UNTIL started on line (6).

Line (15) is obeyed once the UNTIL loop from lines (6) to (14) is
complete (that is, once the CURRENT state is the GOAL state). It prints
the path from INITIAL to CURRENT (a goal state); this is HISTORY
followed by CURRENT.

Line (16) is the end of the defintion of the procedure SEARCH.

    -----------------------------------------------------------

We want to SEARCH to be clever and put the 'good' paths closest to the
front of the UNTRIED list. This is the task of INSERT which uses COMPARE
(supplied by the user) to find the best of any two paths. Here is the
defintion of INSERT using COMPARE:

1       define insert(this, others) -> result;
2           vars first, rest;
3           if others matches [?first ??rest] then
4               if compare(this, first) then
5                   [^this ^first ^^rest] -> result;
6               else
7                   insert(this, rest) -> rest;
8                   [^first ^^rest] -> result;
9               endif
10          else
11              [^this] -> result;
12          endif
13      enddefine;

Line by line, the meaning of this is:

Line (1) says that this is the definition of the procedure INSERT.
INSERT takes two arguments called THIS and OTHERS and produces a RESULT.
Although its not stated explicitly, THIS is a path and OTHERS is a list
of paths. RESULT will also be a list of paths containing all of OTHERS
and also THIS.

Line (2) declares the two local variables FIRST and REST used by INSERT.

Line (3) looks to see if OTHERS can be split up into FIRST and REST.
FIRST will be a path and REST a list of paths. If OTHERS can be so split
then lines (4) to (9) will be obeyed otherwise line (11) will be obeyed.

Line (4) tells POP-11 to COMPARE the given path THIS with the FIRST of
the other paths. COMPARE returns TRUE if and only if THIS is a better
path than FIRST. By 'better than' we mean 'more likely to give the
result wanted by SEARCH'. If THIS is better than FIRST then it it should
come at the front of the new UNTRIED list. This is accomplished by line
(5). If FIRST is better than THIS, then THIS must be INSERTed into the
REST; this is accomplished by lines (7) and (8).

Line (5) (obyed if THIS is better that FIRST) says that the RESULT of
INSERT is a list with THIS as its first element, then FIRST then
followed by the elements of REST.

Line (7) is a recursive call to INSERT asking for the result of
INSERTING THIS into REST. This gives a new value for REST.

Line (8) constructs the RESULT for this call of INSERT, it is FIRST
followed by the new value for REST.

Lines (7) and (8) will be confusing to you. Part of the reason for this
is that you may not fully understand what INSERT is doing. The name
INSERT is badly chosen since it implies that THIS is 'inserted' into
OTHERS so altering OTHERS. This is not the case; what INSERT does is
make a brand new list which is a kind of copy of OTHERS except that the
'copy' includes THIS. This is a standard way of programming in POP-11
where it usually better to build new structures rather than modify
existing ones. We will discuss this in the seminar.

Line (11) is for the case when there are no OTHERS to COMPARE this with.
The RESULT is a simple one element list of THIS.

    --------------------------------------------------------

We can make SEARCH perform either a DEPTH or BREADTH first search by
providing an appropriate definition of COMPARE. To get DEPTH first
search, we would say that long paths are preferable to short ones. To
get a BREADTH first search we would say we preferred short paths to long
ones. For example, to get depth first search we would have:

    define compare(new, old);
        length(new) >= length(old)
    enddefine;

Alternatively, we can ignore the length of the path so far and use as
the basis of our comparison an estimate of the number of steps left to
the goal.

        -------------------------------------------------------------

The library file SOLVEMS.P contains a variation of this procedure (with
more printing instructions). You can examine the program with the
command:

    ENTER showlib solvems

Use VED to look at it if you wish, but don't expect to find it easy to
understand.

To use the program, give the command:

    : LIB SOLVEMS

The file contains procedures for putting a list of numbers into order
using a search. A typical initial 'state' is [3 4 2 1]. The goal state
for this is [1 2 3 4]. The allowable 'moves' are to swap over any two
numbers. The procedure ADJACENT does this, for example:

    : ADJACENT([3 4 2 1]) =>
    ** [[3 5 4 2 1] [5 4 3 2 1] [5 3 2 4 1] [5 3 4 1 2]]

There are five procedures DEPTH, BREADTH, BEST, HILL and ASTAR for use
as COMPARE. Pick some intial state, say [3 4 2 1] and then get SEARCH to
sort that list.

To get a DEPTH first search do:

    : DEPTH -> COMPARE;
    : SEARCH([3 4 2 1]);

To get a BREADTH first search do:

    : BREADTH -> COMPARE;
    : SEARCH([3 4 2 1]);

To get a BEST first search do:

    : BEST -> COMPARE;
    : SEARCH([3 4 2 1]);

To get an ASTAR search, (which is like BEST but takes account of length
of path so far), do:

    : ASTAR -> COMPARE;
    : SEARCH([3 4 2 1]);

To get a HILL climbing search do:

    : HILL -> COMPARE;
    : SEARCH([3 4 2 1]);

The version of ESTIMATE in the file is not very good - its guesses that
the anything followed by a number smaller than itself can be put in the
right position by a single move. There is also a procedure called
PERFECT which gives the exact number of moves required. Try the
preceding examples again after doing:

    : PERFECT -> ESTIMATE;

To get back to the original, do:

    : MEDIOCRE -> ESTIMATE;

You can get the program to produce more printing by doing:

    : TRUE -> VERBOSE;

    -------------------------------------------------------------

Comment on the efficacy of the various searching strategies. Do any of
them have any psychological plausibility? Is the SEARCH program
creative? That is, does it find the solution itself or did I program
ithe solutions into it? Could I be surprised by the program's behaviour?

Draw out the full search tree for the initial state [3 4 2 1]. Write the
MEDIOCRE score against each 'node'. If it helps, you can use the
ADJACENT and MEDIOCRE procedures directly, thus:

    : ADJACENT([3 4 2 1]) =>
    ** [[4 3 2 1] [3 2 4 1] [3 4 1 2]]
    : MEDIOCRE([3 4 1 2]) =>
    ** 1


Write instructions in English on how to sort a list of numbers (or books
on a bookshelf) into order.

See also TEACH * SOLVER

-----<Copyright University of Sussex 1987.  All rights reserved.>-------
