TANTALIZE
A Conversational Problem Solver
written in CODIL
by
C. F. Reyno1ds
Department of Computer Science
Brune1 University
Presented at the Second One Day
Conference on Recent Topics in Cybernetics held by The Cybernetics
Society at Chelsea College on 1st September 1975.
ABSTRACT
CODIL is an
unconventional computer language designed for people who know little or
nothing about computers or mathematics. It is particularly suited for
open-ended or poorly defined information processing problems. The
language interpreter models certain aspects of human decision making,
short term memory and learning.
TANTALIZE is an
interactive/batch heuristic problem solving aid that has been used to
solve a wide range of formal puzzles. It offers a choice of heuristic
constraint processing techniques in an easy to use and readily
extendible format.
Taken together CODIL and TANTALIZE
provide a good man-computer interface, the ability to process
non-trivial real life applications and highly formal problems and a
working mode1 of human information processing. This combination of
facilities represents a significant advance in Artificial Intelligence
research.
1 INTRODUCTION
The most noticeable feature of human
information processing is its flexibility over a highly diverse
range of applications. The most noticeable feature of artificial
intelligence research to date is its lack of success in either
providing a general purpose information processing facility or in
understanding how human beings may process information. The reason
for this is almost certainly the great emphasis that has been put on
developing mathematically sophisticated algorithms that operate on
comparatively trivial universes. Chess. playing programs provide a
good example of this. They operate on a board of a mere 64 squares
arranged symmetrically, 32 pieces of two different colours and six
different types, and a limited and precise set of moves. The
interest arises from the high degree of sophistication needed in
designing the algorithms. However, chess playing, while highly
enjoyable, is a far from typical human activity, and there could be
no grounds for saying that the optimal algorithms for long range
planning in such a trivial environment can have any immediate
relevance to the forward planning needed by a child learning to
cross the road. In
the child's case neither the universe nor the rules can be
considered to be trivial or unambiguous and the goal must be to find
a reasonable solution based on incomplete information. The problem
does not have the symmetry and rigidity needed to use clever
processing tricks and even if it did, the child is not likely to be
sophisticated enough to take advantage of such techniques .
Similar objections apply to one of the frequently quoted practical
applications of artificial intel1igence research, HEURISTIC DENDRAL
(Buchanan et al, 1969). Its success depends on a sophisticated graph package which
prepares candidate chemical structures. Such a package could, given
the right interface, be of
considerable use to an extremely wide range of chemists.
Unfortunately the problems of interfacing the package to handle
various types of measurement and many different classes of chemical
compound have not been solved. As a result HEURISTIC DENDRAL is
confined to one extremely simple class of spectrum and one
comparatively simple category of chemical compound. As with chess
playing programs, the success has been achieved by applying a highly
sophisticated algorithm to an artificially simplified universe, and
the result, while of use to a small group of chemists, says nothing
about the far more important problem of how a chemist handles
chemical information.
[NOTE: Most of the A.I.
packages at the time were presented with a high degree of hype, and
I choose to comment on HEURISTIC DENDRAL because my training as a
chemist meant that I was in a good position to assess how little it
really had achieved.]
The approach taken in this paper is
in complete contrast to the above. CODIL was designed as a practical
language for people with no mathematical or computer knowledge. It
provides them with facilities for handling poorly defined and
open-ended problems simply because one cannot expect such users to
be able to predefine problems in the way needed for more
conventional computer languages. The keynote has been simplicity.
flexibility and the absolute minimum of mathematical sophistication,
(at least as seen by the user).
From the beginning it was felt that
the language's flexibility might have some relevance to the problems
of human and artificial intelligence, but it is only in the last
year or so that this has become obvious. In fact progress has been
so rapid in a number of directions that it has been impossible to
explore any but the most obvious possibilities, much less to prepare
detailed reports for publication. The aim of this paper is to
summarise some of the progress relevant to artificial intelligence
research and give a more detailed account of one of the most
significant developments - a heuristic problem solving aid called
TANTALIZE.
A bibliography of the more important
pub1ications of CODIL, together with some recent technical reports
is listed at the end of this paper.
Figure 1 - Simple Set
Processing
[NOTE: CODIL was originally conceived
as the symbolic assembly language of a user-friendly information
processor - and the above example is at that level. A similar
example - written in the symbolic assembly language of a
conventional store program computer would be most unfriendly.]
|
||||||||||||||||||||||||||||||||||||||||||
2 CODIL
The current version of the CODIL interpreter is written in Cobol
to run under the George 3 operating system on the
ICL 1903A computer at Brunel University. It uses about 20k words of core and user files are paged onto a disc file (there are no program overlays). Any
user of the computer may access the language via a job control macro called CODIL. At the present time a modified version is being prepared which can easily be adapted to run on any of the 1900 series, with
a significant subset being available on machines as small as a 16k 1901.
CODIL has been designed to have as simple a man-computer interface as possible and
Figure 1 illustrates how a schoolchild might define groups of animals and carry out simple tests on them. Apart from
a small number of system commands and a very simple basic syntax
each user defines his own language which he uses to carry out further interactions. Alternatively he uses packages such as TANTALIZE or LESSONS, or communal files, and in such cases there will already be
an existing vocabulary. The emphasis CODIL places on context rules
out the possibility of using anything approaching natural language
at the empty interpreter level - initially there is no vocabulary
or context to talk about. On the other hand there is no reason why users should not develop their own packages to converse about particular applications in a meaningful approximation to natural language.
2.3 Real-life Applications
CODIL was designed to be at its best handling non-trivial real-life problems where open-endedness and/or uncertainties in the problem definition are important.
Figure 2 shows a mini-example of a poorly structured file of chemical data being searched. It has recently been used to handle clinical records for a research project at a local hospital. Obviously the more uncertain the problem the greater is
the possibility of ambiguity and inconsistency, but this only reflects
the ambiguity and inconsistency of the real world as seen by a participant. If there is no uncertainty and the structure of the application is known in advance there is usually no great difficulty. This is because a system designed for open-ended problems can trivially cope with closed problems - as long as the user does not wish to exploit his knowledge that the problem is closed. Under such circumstances CODIL can be considered as a naive user's Cobol, in that it provides an easy file handling and information processing system that can be used for similar, small scale, problems. A CODIL package to give a relational data
base facility (Codd, 1970) is currently being developed by a research student.
|
||||||||||||||||||||||||||||||||||||||||||
The basic building blocks of CODIL are items such as GORILLA,
COMPOUND = ACRIDINE, PKl > 12, etc. These are ANDed together to
form statements terminated, on input, by colons or full stop/new ine. A file is simply a list of statements and the file name is an item in its own right. Any file may be used (sometimes simultaneously) as a command, as a condition name (a major extension of the Cobol condition name concept), as data, or as a parameter to any of the
file handling commands. There is no reason why a user should not designate some files as
"programs" and some "data" and many conventional applications naturally lend themselves to this approach. However
the power of a package such as TANTALIZE owes much to the irrelevance
of these conventionally essential distinctions to the CODIL interpreter.
Figure 3
At anyone time the information held by the interpreter is not equally accessible or permanent and this is represented in
figure 3. At the top of the pyramid is the highly
transitory "criteria" item, which represents a window on one of the files or the computer terminal. It is the interpreter's equivalent to the current program instruction of a conventional CPU. Next comes the "facts" statement - a list of up
to 31 items which are addressed associatively by name. These items
are normally handled on a last in/first out basis and are often read
from files. Apart from some system control items (whose names start
with a $) these are the only items that can be directly addressed.
Next comes the self-organising "memory" - a single file in which there
is a limited addressing facility at the statement level. All other
files are held in a "data base" and can only be addressed by name.
Finally there may be external files held by the George 3 operating system and these have to be OBTAINed into the data base before they can be
used. Apart from a limited facility affecting the facts, all references within CODIL are by name, and all addressing, paging files on and off disc, etc., are carried out automatically.
Figure 4
2.5 The Decision Making Unit
How a criteria item is processed depends on its context and the basic algorithm is given in figure 4. If the item terminates a statement it is "obeyed") if not it is compared with the current fact items and a true/false decision is made. This algorithm was chosen because it is easy to demonstrate to mathematically unsophisticated users. No deliberate attempt was made to model human information processes but the idea of automatically comparing identically formatted items of information is more anthropomorphic than the often discussed "programmed computer" model. The decision making unit can be interpreted in terms of simple comparator units linked together in series and parallel and there is no reason why a CODIL-like processing algorithm should not have evolved from successively simpler algorithms. It does not require the development of separate mechanisms for program and data neither of which would be of any use until the other had evolved2.6 The Facts/Short Term Memory
All directly addressable items of information are held in the facts which) in the current implementation, can hold up to 31 items. This is a completely arbitrary limit and the idiotically low value -(as compared with the amount of work space available with conventional programming languages) was chosen because there was no demand for anything larger: It has been observed that the facts seldom contain more than a dozen items, and the number of items is often closer to six. Even the problem solver, TANTALIZE, is only rarely embarrassed by this limit, although it uses the facts as a stack for local/global variables. This extremely low requirement for directly addressable variables) coupled with the comparatively short lifetimes of items contained therein) are highly reminiscent of human short term memory and it is not unreasonable to draw attention to the similarity between the two. (For anyone wishing to explore the similarity a trivial amendment has been made to the interpreter that leads to the automatic deletion of items from the facts if they are not accessed within a predefined period.)2.7 The CODIL Learning Capability
A recent addition to the CODIL interpreter is the self-organising file called MEMORY. To the decision making unit it looks exactly like any other file but it has the following additional properties:-The result is an integrated learning facility within the CODIL system. It was originally devised to help to model learning situations but it can also be used to optimise the order of files, for internal sorting and for diagnostic tests involving frequency counts. Figure 5 illustrates the use of MEMORY to optimise a file for calculating the costs of holding stock. A description of the problem is input in top down order, copied to MEMORY, and the completely general recursive routine, CONTEMPLATE, is written and entered. CONTEMPLATE attempts to execute MEMORY and continues the process until there is no further change in the facts. By suitable reinforcement the statements in MEMORY are ordered on the number of times they have been obeyed and the result is a file in the logically correct order for sequential execution.
- It contains a limited predefined number of statements.
- Associated with each statement is a counter containing its "activity" and statements are usually stored in order of decreasing activity.
Figure 5
Optimisation of the calculation of stock costs using
MEMORY
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3. TANTALIZE
TANTALIZE is a collection of CODIL files that can be used to solve a wide range of formal puzzles. It is held as a ready formed data base on disc, having been prepared by reading in about 1000 cards. It
is designed to be used in interactive mode, in which the user answers questions and types in keywords in order to describe the problem and indicate the type of solution desired. Emphasis has been put on keeping the problem definition process as simple as possible, while offering as wide a range of alternative techniques as possible.
3.2 An Old Hindu Problem
The basic features
of TANTALIZE can best be illustrated via examples of how it works. To begin with
a very simple problem will be discussed
| < | SOLVE: OLD HINDU PROBLEM |
| TYPE IN A TEXT DESCRIPTION 0F THE PROBLEM, ETC | |
| 2< | * While three watchmen were guarding an orchard a thief slipped in |
| 2< | * and stole some apples. On his way out he met the three workmen one |
| 2< | * after the other, and to each in turn he gave half of the apples he |
| 2< | * then had, and two beside. Thus he managed to escape with one apple. |
| 2< | * How many apples had he stolen? |
| 2< | |
| 2< | * Taken From "Mathematical Recreations" by Maurice Kraitchik |
| 2< | |
| 2< | SINGLE ACTIONS. |
| 2< | IDENTICAL NOT HIS ESCAPE. |
| 2< | ONE SOLUTION. |
| 2< | END. |
SOLVE
initializes the problem solving process. A test description of the problem is
typed in as a comment together with three key words. SINGLE ACTIONS indicates that no action
may occur more than once in the solution (i.e. the thief cannot pass the same
watchman twice). IDENTICAL NOT HIS ESCAPE
shows that all the watchman's actions are equivalent (but not HIS ESCAPE).
ONE SOLUTION is used to stop the solver as
soon as one of the several equivalent solutions is found.
| ACTION = ? | |
| I< | FIRST WATCHMAN & SECOND WATCHMAN & THIRD WATCHMAN & HIS ESCAPE |
| TYPE IN SHARED FILE | |
| C< | AFTER IS = BEFORE. |
| C< | BEFORE IS = (AFTER + 2) *2. |
| C< | END. |
| TYPE IN A DESCRIPTION OF HIS ESCAPE | |
| C< | AFTER = 1. |
| C< | END. |
| DESCRIBE ILLEGAL CONDITIONS | |
| C< | END. |
| TYPE IN GOAL | |
| C< | EVERY ACTION. |
| C< | END. |
| WHICH ITEMS DEFINE THE STATE OF THE PROBLEM | |
| ITEM = ? | |
| I< | NONE |
Three further
questions are then asked. There are no illegal situations to complicate this
problem., the goal is to EXECUTE every action (i.e. to pass all watchmen and
make his escape) and there is no items of which the system should take special
cognisance.
| THE FOLLOWING REPRESENTS A SOLUTION OF OLD HINDU PROBLEM | |
| START & HIS ESCAPE & FIRST WATCHMAN & SECOND WATCHMAN & THIRD WATCHMAN | |
| SOLUTION FOUND = 1. | |
| PROBLEM TITLE = OLD HINDU PROBLEM. | |
| ACTION = START, | |
| ACTION = HIS ESCAPE, | |
| AFTER = 1, | |
| ACTION = FIRST WATCHMAN, | |
| BEFORE = 6, | |
| ACTION = SECOND WATCHMAN, | |
| AFTER = 6, | |
| BEFORE = 16, | |
| ACTION = THIRD WATCHMAN, | |
| AFTER = 16, | |
| BEFORE = 36. | |
| SOLUTION FOUND = 1. | |
| < | |
The question asking
process used about 4 seconds of computer mill time and when complete a
compilation process of about 5 seconds is undertaken to organise the information
into an appropriate format for the solution process. The final problems solving
time took a further 2 seconds including the printing out of the answer.
3.3 School Colours
The next example
involves one of the many New Scientist Tantalizers (Hollis)
that have been solved, after which TANTALIZE is named. SUPERSOLVE is used
because the solution used the self-organising MEMORY whose size has to be
predefined.
| < | SUPERSOLVE:5: TANTALIZER NO 226. |
| TYPE IN A TEXT DESCRIPTION 0F THE PROBLEM, ETC | |
| 2< | * TANTALIZER No 226 NEW SCIENTIST |
| 2< | * SCHOOL COLOURS |
| 2< | * "Tell Me, Professor Pinhole, which school does your daughter Alice |
| 2< | * go to?" |
| 2< | * "Let me think. Is it the one with the orange hat and the turquoise |
| 2< | * scarf? or with the khaki blazer and orange emblem? or with the pink |
| 2< | * blazer and orange scarf? or with the khaki scarf and pink emblem? or |
| 2< | * with the khaki hat and turquoise emblem? I fear I cannot recollect." |
| 2< | * "Good Heavens, Professor! However many schools are there?" |
| 2< | * "Just four and I have one daughter at each. Bess goes to St |
| 2< | * Gertrude's, Clare wears a turquoise hat and Debbie wears a khaki |
| 2< | * Emblem. St Etheldreda's flaunts a pink scarf, St Faith's and orange |
| 2< | * blazer and St Ida's a pink hat." |
| 2< | * "And whose are those clothes flung down on the floor over there?" |
| 2< | * "The turquoise hat and the khaki blazer belong to different girls. |
| 2< | * As for the turquoise blazer, well, I think you might work out whose |
| 2< | * that is for yourself." |
| 2< | * Martin Hollis |
| 2< | REQUIREMENTS. |
| 2< | END. |
The single key word REQUIREMENTS
triggers off a modified set of questions.
| SELECT = ?. | |
| I< | HATS & SCARVES & BLAZERS & EMBLEMS & DAUGHTERS & SCHOOLS. |
| TYPE IN HATS | |
| SELECT NAME = ?. | |
| I< | HAT: ORANGE & KHAKI & TURQUOISE & PINK. |
| TYPE IN SCARVES | |
| SELECT NAME = ?. | |
| I< | SCARF: TURQUOISE & ORANGE & KHAKI & PINK |
| TYPE IN BLAZERS | |
| SELECT NAME = ?. | |
| I< | BLAZER: KHAKI & PINK & ORANGE & TURQUOISE |
| TYPE IN EMBLEMS | |
| SELECT NAME = ?. | |
| I< | EMBLEM: ORANGE & PINK & TURQUOISE & KHAKI |
| TYPE IN DAUGHTERS | |
| SELECT NAME = ?. | |
| I< | DAUGHTER: ALICE & BESS & CLAIRE & DEBBIE |
| TYPE IN SCHOOLS | |
| SELECT NAME = ?. | |
| I< | SCHOOLS: ST GERTRUDE & ST ETHELDREDA & ST FAITH & ST IDA |
| TYPE IN REQUIREMENTS | |
| C< | HAT = ORANGE; SCARF = TURQUOISE. |
| C< | BLAZER = KHAKI; EMBLEM = ORANGE. |
| C< | BLAZER = PINK; SCARF = ORANGE. |
| C< | SCARF = KHAKI; EMBLEM = PINK. |
| C< | HAT = KHAKI; EMBLEM = TURQUOISE. |
| C< | DAUGHTER = BESS; SCHOOL = ST GERTRUDE. |
| C< | DAUGHTER = CLAIRE; HAT = TURQUOISE. |
| C< | DAUGHTER = DEBBIE; EMBLEM = KHAKI. |
| C< | SCHOOL = ST ETHELDREDA; SCARF = PINK.. |
| C< | SCHOOL = ST FAITH; BLAZER = ORANGE. |
| C< | SCHOOL = ST IDA; HAT = PINK. |
| C< | END. |
| TYPE IN A DESCRIPTION OF ANY ILLEGAL SITUATION | |
| C< | HAT = TURQUOISE; BLAZER = KHAKI. |
| C< | END. |
| TYPE IN A DESCRIPTION OF THE GOAL | |
| C< | DAUGHTER (NUMBER) = 4. |
| C< | END. |
|
THE FOLLOWING
REPRESENTS A SOLUTION OF TANTALIZER NO 226 SOLUTION FOUND = 1, PROBLEM TITLE = TANTALIZER NO 226, START SELECT = HATS, HAT = PINK, SCARF = ORANGE, BLAZER = PINK, EMBLEM = KHAKI, DAUGHTER = DEBBIE, SCHOOL = ST IDA, HAT = TURQUOISE, SCARF = KHAKI, BLAZER = ORANGE, EMBLEM = PINK, DAUGHTER = CLAIRE, SCHOOL = St FAITH, HAT = KHAKI, SCARF = PINK, BLAZER = TURQUOISE, EMBLEM = TURQUOISE, DAUGHTER = ALICE, SCHOOL = ST ELTHEDREDA, HAT = ORANGE, SCARF = TURQUOISE, BLAZER = KHAKI, EMBLEM = ORANGE, DAUGHTER = BESS, SCHOOL = ST GERTRUDE. |
|
3.4. Heuristic Search Facilities
3.4.1. Aims
As TANTALIZE is designed as a problem
solving aid it is clearly essential that it offers a choice of heuristic
search facilities. In deciding how this should be done three main factors
have been taken into consideration:-
-
TANTALIZE should allow as many of the established heuristic search techniques as possible (see for example Michie, 1971). Facilities are included for in depth searching, shortest path searches,· and directed searches using system generated or user defined distance functions.
-
It should be possible for the search technique to change during the problem solving process. Thus a shortest path search can be speeded up by using a distance function produced by backtracking from the goal. This produces an effect analogous to the bidirectional search of Pohl (1971), although the algorithms used are different. Alternatively a directed search that fails to find the goal quickly might take a broader look at possible alternative leads reverting to the full power of a directed search only when a suitably promising lead presents itself.
-
Most existing problem solvers produce results by exploiting the high speed and effectively unlimited working storage of modern digital computers, the resulting brute force solutions tell us nothing about how humans solve problems. TANTALIZE is already restricted by the limited size of the facts and it is felt that it should contain facilities which prescribe other aspects of brute force approaches. . At the present time these take the form of adjustable limits to its ability to remember possible backtracking paths. With tight limits a good distance function will still rapidly find the goal, while a weak distance function will rapidly become lost and terminate (In theory TANTALIZE should then generate an alternative distance function or' ask the user to provide a new one, but to date such a facility has not been implemented).
3.4.2. In depth searching
In many of the problems the choice of
a heuristic search technique is not the most critical aspect in the
description of the problem, and as a result the default technique in
TANTALIZE is a simple in depth search. In this an action is selected and if
it is legal, successive actions are selected and the process repeated until
either the goal is reached or no further progress is made, In the latter
case the solver automatically backtracks until alternative actions can be
tried.
This type of search is the one used in
the two examples discussed above. In the case of the Old Hindu Problem,
there are a number of equivalent answers and in depth searching is sure to
find one of these very quickly.
In the School Colours problem a
subsidiary aim is to show that the solution is unique and the whole problem
space must be searched. As the in depth searching facility is the fastest
available to TANTALIZE, this is again the method of choice. However this
technique leaves all intermediate information in the facts and in some
cases, particularly where the technique is not really suitable, there is a
possibility of the limit of 31 items being reached.
Figure 6
The Water Jug Problem
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3.4.3. Shortest Path or In-breadth Searching
In problems such as Filling the Water
Jugs, figure 6, the aim is to find the shortest
of a number of possible answers. By using the SHORTEST key word TANTALIZE
carries out a systematic search stage by stage. Each action is applied in
turn to the initial problem state and the resulting intermediate states are
stored, to become new initial states in the subsequent pass. This continues
until an answer is found.
3.4.4. Distance Functions
For any goal directed search, a
distance function is needed to assess the nearness of the intermediate
solution state to the goal. This can be a user supplied function that
provides a RATING value for the problem state. Alternatively there are two
system generated distance functions available. DISTANCE sets a RATING
proportional to the number of items in the goal that are correct in the
problem state. BACKTRACK runs the solver backwards from the goal to a given
depth and records the distance of each generated state from the goal. The
resulting function forms a potential hollow that guides the solver rapidly
to the goal. BACKTRACK may be used in conjunction with either DISTANCE or a
user defined function.
3.4.5. Goal-Directed Searching
The basic Graph Traverser type search
is activated by the word DYNAMIC. This uses the self organising MEMORY to
hold the intermediate states, and the basic cycle of operations is to select
the state with the highest rating, apply all feasible actions, testing for
GOAL, ILLEGAL, etc., and storing new states back in the MEMORY with an
activity proportional to their rating.
The backtracking ability of this
technique can be reduced in two ways. The first is to restrict the size of
MEMORY so that it cannot hold all possible states. The second is to apply a
forgetting function to the learning memory (the numeric value associated
with DYNAMIC is used), to encourage retention of recent, rather than old,
intermediate states.
3.4.6. The Pigeon Hole Technique
One of the aims in designing TANTALIZE
is to allow the search techniques to vary during a search. To achieve this a
pigeon hole technique is used to process intermediate problem states. When
this is done a maximum and minimum value for PRIORITY are used. If the
RATING for an intermediate state exceeds the maximum, an in depth search is
carried out for as long as RATING continues to exceed the maximum. If the
RATING is less than the minimum the intermediate state is discarded Other
states are assigned to one of five pigeon hole files depending on the actual
value of RATING. At appropriate intervals the highest rated pigeon hole is
emptied into a work file and used to continue the search.
This technique produces an in depth
search if the RATING always exceeds the maximum priority and a shortest path
search if the RATING is constant and within the priority range. If a
distance function is used progress is made along a moderately broad front.
This can be narrowed by use of the MAXIMUM RATING key word which 'boosts'
the RATING of any state which exceeds the previous maximum. In many case
this narrowed front is only a single state and this approximates to a goal
directed search in terms of the number and order of states examined.
Figure 7
Moving a knight across the chess board
[NOTE: The descriptions of the moves could be simplified by
leaving out the conditional tests and making moves off the edge
of the board illegal.]
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3.4.7. A Comparison of Searching Techniques
A full comparison of these different approaches to heuristic search
is not possible in a short paper of this nature. Instead figure 7
gives a basic description of the simple problem of moving a knight from one corner of a chess board to another.
Figure 8 shows the route taken for a number of different key word descriptions. The first, in depth, search finds the answer by accident after taking a tortuous route. SHORTEST finds the goal after having examined every other square on the board (this is the worst case for this type of search). The other techniques pursue more or less direct routes, all of which are satisfactory and for this simple problem there is not a lot to choose between them.
Figure 8: Knights
moves using different heuristics
3.5. Restricting the Problem Space
Important as search techniques are in many situations, it is often more profitable to minimise the problem space to be searched. In some cases it is sufficient to find one solution and then stop, as
, was done in the Old Hindu problem given earlier. In some such situations a facility such as OPTIMISE, which optimises the order in which actions are selected by comparison with GOAL, may give a significant improvement, by :increasing the probability of a solution being found early in the
search.
3.6. Simplifying the Problem Description
Bigger savings can be achieved by only selecting actions when they
are likely to produce profitable results. This is done automatically for all actions containing conditions, but additional tests are possible. For instance, SINGLE ACTIONS ensures that named actions are not used twice in any solution, while CHECK ensures that executing the action
will change the current problem state. Other key words help to avoid the permutation of actions when a combination is adequate to find
or eliminate a possible route to the goal. By choosing key words appropriate to the problem in hand, it is often possible to reduce~ considerably the number of intermediate problem states to be examined and this often makes it possible to simplify the search. This is because the test for repeating situations, PRIOR MOVES, can be dropped as redundant. As the time taken to carry out this test increases rapidly as the problem size increases its elimination plays an important role in reducing run time.
The use of the SELECT facility for generating mutually exclusive alternatives again reduces overheads compared with the use of actions to generate the same information and this is particularly true when
a number of selections are automatically linked together. Here again
a series of key words can be used to produce similar constraining effects to those described for actions. In addition there is a powerful constraint processing facility, used in the School Colour problem,
in which specific requirements, together with appropriate illegal conditions,
are used to ensure that unsuitable combinations are never generated and that the
generation order is such as to reduce the problem space to a minimum. This often serves to reduce an
impossibly large search space to a trivially small one.
3.7. Extending the Power of the Problem Solver
Because TANTALIZE and the problem descriptions are both written in CODIL, it is possible to use virtually the whole power of the CODIL
language in the action descriptions or in supplementary files. In
a simplest case it is usually possible to redefine the initial conditions, ILLEGAL or GOAL, and then TRY AGAIN after an attempt to find a solution. If the problem GOAL is inexactly defined, for instance when finding
a minimum condition, the GOAL may be dynamically redefined during
the problem solving process to be less than the last solution found.
By redefining the file TERMINATE, the user can modify the terminal procedure and can automatically arrange to modify other files and
TRY AGAIN. This would allow the system to be set up with an explicitly defined series of subgoals to be solved in a given order. A wide range of other such modifications are practicable and if a given type of modification to the workings of TANTALIZE proves to be common it can always be adopted as a permanent option.
3.8 The Problems Solved
At the present time about 60 different
problems have been solved and in some cases up to a dozen different versions
of a single problem has been tried to explore the different features of
TANTALIZE. Despite this variety there are many features, and particularly
combinations of features that have not been properly exploited.
Many of the problems examined are New
Scientist Tantalizers (3) of which over 30 different ones have been solved
to date. All but 2 are solved in less than one minute processor time on the
1903A computer. Many took less than 20 seconds. In addition a number of
problems solved by other workers have been solved. These include:
Bridges of Konigsbery
(Ernst & Newell,
1969)
Confusion of Patents
(Fikes, 1970)
Couples Tennis Problem
(Fikes, 1970)
Eight Queens on a Chess Board
(Fikes, 1970)
Magic Square
(Fikes, 1970)
Missionary and Canibals
(Ernst & Newell,
1969)
Monkey and Bananas
(Ernst & Newell,
1969, Fikes, 1970)
Smith, Robinson and Jones
(Weston, 1970)
Three Coins
(Ernst & Newell,
1969)
Water Jug Problem
(Ernst & Newell,
1969,Fikes, 1970)
In all cases where a comparison is
meaningful, the solution time is very much faster (never more than 90
seconds) and in almost every case the problem definition is much simpler.
(It should be noted that TANTALIZE in its present form, is not: able to cope
with problems that require a capability for algebraic manipulation.)
The final group of problems have
mainly been chosen to illustrate the novel features of TANTALIZE/CODIL. They
include alternative transliterations of Colonel Gadafy's name, acting as an
umpire in a game of cows and bulls, generating the nursery rhyme "One Man
Went to Mow”, matching a single payment against a series of outstanding
invoices to find the best fit; minimising the cost of holding stock and
searching externally held files on various subjects. A number of simple
algebraic problems, such as the Old Hindu problem described earlier have
also been described.
4. CONCLUSIONS
4.1 What has been achieved
CODIL can best be considered as a
highly unconventional general purpose information processing system aimed at
unsophisticated users who have non-trivial real life problems. In developing
this language various observations have been made concerning unplanned
similarities with human information processing activities. These
observations include similarities between the facts and short term memory,
the naturalness with which powerful learning facilities are included, and
the existence of a simple yet extremely powerful decision making capability
which can be interpreted in evolutionary terms. The ability of the language
to handle open-ended, ambiguious and poorly defined problems, coupled with a
relatively poor capability (compared with more conventional computer
languages) in the formal mathematics area is also relevant.
TANTALIZE represents the first
deliberate use of CODIL for artificial intelligence research, and the result
is a powerful yet easy to use problem solver system which offers a very wide
range of facilities. It has already solved a wide range of problems in a
reasonable time and in addition there is plenty of scope for writing a new
and much more powerful successor. However, perhaps the most surprising thing
about it is the way CODIL rallied to a task so far removed from its design
aim of serving unsophisticated users who do not even need to know what an
algorithm is.
4.2 Comparison with Other Systems
Over the past few years many attempts
have been made to compare the basic structure of stored program computers
with human information processing techniques. The basic CODIL philosophy of
a controlling decision making unit and a memory hierarchy which includes
learning facilities, provides a very much better global model than any based
on the idea of program and data as separate concepts. In fact the sooner the
stored program computer model of human information processing joins the
earlier telephone exchange model and the dodo, the better. However at this
level of comparison it should be realised that CODIL still forms an
exceedingly crude working model and it should be considered as no more than
an important step in the right direction.
There are problems in making
comparisons between the approach described here and the simulations of
specific human information processing activities. For instance, how can one
compare a model of a specific aspect of short term memory, which has been
designed to test a highly specific theory, and do nothing else, with a
system designed to perform on as wide a range of tasks as possible without
any attempt to model memory at all? The approaches are complementary and the
work of reconciling them represents a major task for the future.
Compared with other problem solvers,
the TANTALIZE problem descriptions are almost always simpler, the time to
process problems is often more than an order of magnitude less, and with a
mere thousand source cards TANTALIZE provides an unrivalled range of
heuristic search and other facilities. Its comparative weakness in algebraic
manipulation is more than compensated for by the ease with which it can be
extended by the use of CODIL to carry out a wide range of operations.
4.3 The Future
CODIL and TANTALIZE together provide a
system with a good man-computer interface, an ability to handle poorly
defined real life problems, a global model of human information processing
and a powerful heuristic problem solving facility. This represents a breadth
of ability unique to artificial intelligence but it is merely the spin-off
of an unfunded research project to develop a language for untrained users.
Given adequate support there are many
possibilities for further research. For instance TANTALIZE represents no
more than about 5 man-months effort and could greatly benefit from being
rewritten in a more powerful form. CODIL was in no sense designed for
artificial intelligence work and modifications to the interpreter could
greatly improve efficiency and also provide further facilities. In addition
packages analogous to TANTALIZE could be developed to provide facilities for
developing and testing more refined models of learning and other specific
aspects of human information processing. Detailed comparison with more
specialised work on artificial intelligence problems will almost certainly
suggest ways in which the basically unsophisticated structure or CODIL can
be extended to accommodate more sophisticated~structures and techniques. If
this work is done in parallel with the development of CODIL for practical
applications a reasonable aim would be for- a system that could greatly
reduce the need for systems analysts and programmers.
References
(1) B. G.
Buchanan, G. L. Sutherland, and E. A. Feigenbaum. Rediscovering some
Problems of Artificial Intelligence in the Context of Organic Chemistry,
Machine Intelligence 5, ed. B. Meltzer & D. Michie. 253-281, 1969.
(2) E. F. Codd.
A Relational Model of Data for Large Shared Data Banks, Comm.
A.C.M. 13, 377-387, 1970
(3) M. Hollis,
Tantalizer, New Scientist. (A series of puzzles published
weekly in this popular science journal over a period of about 8 years.)
(4) D. Michie,
Heuristic Search, Comp. J. 14, 96-102, 1971
(5) I. Pohl,
Bidirectional Search, Machine Intelligence 65, ed. B.
Meltzer & D. Michie. 127-140, 1971
(6) G. W.
Ernst and A. Newell, GPS: A Case Study in Generality and Problem Solving,
Academic Press, 1969
(7) R. E.
Fikes, REF_ARF - A System for Solving Problems stated as Procedures,
Artificial Intelligence 1, 27-120, 1970
(8) P.E.
Weston, To Uncover, To Deduce, To Conclude, Comp. Stud. Hum.
Verb. Behav. 3, 77-89, 1970
Further Reading on CODIL
(1) C. F. Reynolds,
CODIL, Part 1, The Importance of Flexibility, Comp. J. 14,
217-220, 1971.
(2) C. F. Reynolds,
CODIL, Part 2, The CODIL Language and its Interpreter, Comp. J.
14, 327-332, 1971
(3) C. F. Reynolds,
An Evolutionary Approach to Artificial Intelligence, Datafair 73,
314-320, 1973
(4) C. F. Reynolds,
Designing an Interactive Language for the Pragmatic User, Proc.
European Computing Conference, 991-1006, 1974
(5) C. F. Reynolds, A Simple
Minded Approach to Artificial Intelligence, Brunel Univeristy, Computer
Science Technical Report, 7, 1975.
(6) C. F. Reynolds, An
Operational Interpreter for Online and Batch Use, Brunel Univeristy,
Computer Science Technical Report, 8, 1975.
(7) C. F. Reynolds,
Programs. Data or Information, Brunel Univeristy, Computer Science
Technical Report, 9, 1975.
(8) Teach Yourself CODIL
(Interactive lessons [that were] available on the
Brunel University 1903A)
(9) CODIL Newsletter,
issued 2 or 3 times a year and containing news of the latest developments in
CODIL.
No comments:
Post a Comment