Firbush News, No 6. pp 26-30, July 1976
Recent [Artificial Intelligence] developments with CODIL
by
C.F. Reynolds, Department of Computer Science, Brunel University, England, U.K.
CODIL (1, 2) is a computer language designed for the non-mathematically orientated user with open-ended real-life information processing problems. Every attempt has been made to minimise mathematical sophistication of the basic language framework, and to find a processing algorithm and storage strategy simple enough to seem "obvious" to the proposed users. In achieving this goal many of the generally accepted features of computer languages - in particular the distinction between program and data - were abandoned as being too sophisticated. The resulting interpreter works by comparing strings of items and the basic algorithm is simple enough to be described on the back of an envelope.
While the simplicity of the language and interpreter is important, it is equally important that the system can be used for non-trivial problems. As such it must be able to tackle problems which are incomplete or ambiguous to a greater or lesser degree. Fortunately the very simplicity of the approach makes this type of flexibility possible - if only because there are no 'primitive operators' sophisticated enough to be seriously offended by uncertain information.
By the end of 1974 the CODIL system was working operationally on the ICL 1903A computer at BruneI University, and it had been tested on a very wide range of applications on a scale ranging from the very small up to a data base of research clinical records for a department in a local hospital. It had been pointed out (3) that the processing algorithm was not only very simple, but could be explained in evolutionary terms. In addition, the main work locations, the facts, show a number of properties in common with human short term memory. However, apart from such speculations, and the hand coding of a few New Scientist Tantalizers, other activities precluded detailed research into the language's relevance to A.I.
During 1975 the position has completely changed. The first significant development was the inclusion of a learning "MEMORY". This file looks like any other to the user and to the main part of the interpreter. However, its internal structure is different in that each statement has associated with it an activity and a usage indicator. Varied learning strategies may be examined by altering the size of the MEMORY, the learning and forgetting ratio. recall levels, etc., and by giving positive or negative reinforcements In addition it is used for internal sorting and optimisation of files. These included inputting a "program" in jumbled order and using MEMORY to reorganise statements into the right order to produce a result on a single pass, discarding surplus irrelevant information.
The next development was that CODIL could be readily extended to provide significant algorithmic processing power, despite the original design that the user should not need to know what an algorithm is. The first non-trivial application chosen to test this new facility was to write an interactive (or batch) problem solving aid called TANTALlZE. This allows the user to define the problem by supplying a series of keywords and then answering a series of questions. TANTALIZE then enters a "compilation" phase in which the information provided is pre-processed prior to the main search phase. The search itself may proceed in several different ways (either separately or in combination).
(a) In depth search, in which the action / selections are applied recursively until the goal is found or no more progress is possible. When this happens the solver backtracks until an alternative route is found.
(b) In breadth search, in which the effects of applying one action, two actions, ... , etc., are examined in full until a solution is found.
(c) A directed search in which the distance from the goal is evaluated by a simple system generated distance function and the most promising path taken.
(d) An extension of the above in which the user provides a problem specific distance function. This allows in depth searching in very promising situations, and also allows sufficiently unpromising leads to be discarded entirely.
(e) Actions may suggest one or more possible successor actions.
(f) Non-standard searching techniques can be introduced by modifying the information written to or collected from the files holding the intermediate problem states.
(g) By using the learning file, MEM0RY, to hold intermediate states it is possible to modify the course of the search by restricting the capacity of MEMORY and/or introducing a non-zero forgetting rate. This can lead to situation where the solver will only succeed if supplied with a good distance function, or where the solver is made to prefer recently generated problem states over more favourable, but older ones. This type of performance is clearly relevant to human problem solving. (A zero forgetting rate and a large enough MEMORY gives a graph traverser behaviour).
In unfavourable conditions, searching may take an inordinately long time and various techniques are available to speed the process. For instance the particular lead being followed is abandoned as soon as an illegal or prior situation is reached (assuming these have been defined). In addition rapid back tracking is provided for the situation in which it is not necessary to try different permutations of the actions.
Great savings can be made by ensuring that actions and selections are only made when they are likely to be productive. There are a variety of facilities available, and the most sophisticated of these include backtracking from the goal and extensive constraint processing of selections. In one example a suitable combination of 4 knights / steeds / helmets / banners / shields / plumes is required. The constraint processing is so efficient that the resulting problem space contains a mere 34 items compared with the minimum of 24 items needed to define the solution state and a maximum of 63,826,261.
Another important aspect of the solver is the series of facilities for inputting simplified problem definitions. For instance, the bridges of Konigsberg problem involves the crossing of each bridge in either of two directions. However only one direction need be described as the description can be automatically expanded by using the correct keyword in the problem description preamble.
Finally, the user has access to virtually the full facilities of the CODIL language to augment the problem definition and this may well extend to the modification of the solver and its work files. In particular the user may TRY AGAIN after modifying files such a ILLEGAL, GOAL and TERMINATE, and may even get the solver to carry out such modifications automatically. Thus when a goal is reached it may be used to produce new goal, as is done when the aim is to find a minimum value.
Problems that have been solved to date include the missionaries and cannibals crossing the river, placing eight queens on a chess board in such a way that no queen can capture another, filling water jugs and helping the monkey to get a banana. It fails to cross the seven bridges of Konigsberg. Over 30 New Scientist Tantalizers have been solved (some more than once using different definitions), and a number of similar problems solved by other problem solvers have also been tackled. Other miscellaneous tasks include finding the minimum cost of holding stock, searching external files, and generating the nursery rhyme "One man went to mow". Detailed comparisons with REF-ARF (R. E. Fikes, Artificial Intelligence 1 (1970), 27-120) are under way and have shown that TANTALIZE is well over an order of magnitude faster, about an order of magnitude smaller (in terms of the number of source statements), and in virtually every case the problem definitions are shorter and much simpler.
To conclude: In CODIL we have a single computer system that provides:
1). A good man-machine interface aimed at the non-mathematician.
2). An operational system for handling open-ended and poorly defined life problems.
3). A processing algorithm and storage structure that to some extent mimics human information processing, and which is explicable in evolutionary terms.
4). An inbuilt learning facility which can be tuned to give a wide range of learning behaviour.
5). The capability for supporting a powerful and readily extendable heuristic problem solving system.
6). Comparatively low computer processing overheads.
7). Minimal human effort in setting up systems (TANTALIZE represent! less than 6 man-months effort, and the vast majority of the time was in setting up and testing the problems solved).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Firbush News was a newsletter circulated among the Firbush group of Artificial Intelligence research departments around the world, and published from the Machine Intelligence Research Unit at the University of Edinburgh.
The paper as published omitted the original source references. These have been reinserted and listed below
(1) CODIL: Part 1: The Importance of Flexibility, Computer Journal, Vol 14, pp 217-229, August, 1971.
(2) CODIL: Part 2: The CODIL language and its interpreter, Computer Journal, Vol 14, pp 327-332, November, 1971.
(3) An Evolutionary approach to Artificial Intelligence, Proceedings, Datafair 73, pp 314-320, April 1973.
It is appropriate to comment on the above paper and what happened over the next few years.
ReplyDeleteCODIL was conceived in the world of complex basically non-numerical tasks where a good human interface was essential for efficient working and while the examples with the initial proposals in 1967 included a single formal logic problem the chief design criteria was open-endedness and an easy to use human interface. In the early 1970s it was realised that formal logic problems were useful for testing the interpreter and a colleague suggested that it might be worth looking at this area in more detail. The result was TANTALIZE, which asked the user questions about the problem. It then used the answers to generate a set of production rules which, when obeyed, generated the answer to the problem. The A.I. literature was scanned for published logic problems which had been solved by other researchers - and I showed that in each case the CODIL/TANTALIZE solution was more elegant and used less computer resources. In addition I set out to solve problems published for human solving in the New Scientist - and TANTALIZE succeeded in solving 15 consecutive puzzles as they were published.
However, getting papers published was another matter - as they were subject to peer review - and kept coming back with rejection slips which showed that the reviewer hadn't understood it. For instance a pair of papers - one describing TANTALIZE and the other describing its solution of a wide range of logical problems was rejected because the approach was too theoretical ever to work. Other rejections were less complimentary - and on several occasions I was told that if I wanted to get A.I. papers accepted I should write the programs in pop2 (the then "in fashion" computer language in A.I. Departments).
The difficulty seemed to be cultural. Basically the two sides lived in different mental boxes). My background my interests were in complex real world problems involving human interaction and my interests were in understanding human information processing at a grass root level. If what I was doing could not be explained in words meaningful to the average man in the street it was probably inappropriate. If my research threw any light on how the human mind worked that was a bonus - but not the goal of the research. Logic puzzles and competitive board games were seen by me as no more than fun items at the schoolboy level - and if CODIL could be used for such tasks it was interesting - but a side issue.
On the other side the A.I. establishment clearly considered studying such puzzles and games the best way forward to modelling intelligence, and were very much concerned with the computing tools used (such as pop2) and the description of the underlying logic in academic language which would defeat the average man in the street. They also controlled what was published - and what was able to get funding.
Rather than continue to try and publish in an area where I felt the emphasis was on ARTIFICIAL Intelligence, there were other aspects of CODIL to explore which had more practical relevance. In addition I became involved in the plans to move the University from a batch computing service to an interactive one (admittedly with no more than glass teletypes. This also involved some rewriting, and improvements to, the CODIL software, including its memory management algorithms - and the TANTALIZE package was never transferred. Another distraction was that I got involved in the BLEND online electronic journal project.
If anyone is interested in what I achieved with TANTALIZE some of the draft papers are in a box somewhere around the house - and the vast pile of old computer paper in the garage undoubtedly includes listings of at least some of the problems solved. Just ask if you would like me to post details.