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 ------------