TANTALIZE - A heuristic problem solver written in CODIL

 

 

The New Scientist magazine published the following news item on 21 August 1975

For those who have trouble solving the Tantalizers that run each week in New Scientist, Dr Chris Reynolds of Brunel University has developed a computer programme.

"I'm sorry it can be done," commented Martin Hollis, a philosopher at the University of East Anglia, who creates the Tantalizer each week. "The best puzzles are the ones which are too elusive for a computer."

And some are too elusive.- Reynolds' computer can only solve about one-third of the Tantalizers: "It won't handle any which involve deep insight  or those which are easy once you see the catch."

Reynolds has developed a new computcr language, Codil, which is designed to permit non-computer people to use the computer for information processing (as distinct from data processing). It is especially useful for projects which involve data base or record manipulation. (Tantalizers often involve just such information.) Codil does not make the standard distinction between program and data.

"Tantalize" is a problem solving package "designed to cope with open-ended poorly-defined problems, while ordinary computer systems deal with only precise problems," he said. Tantalize starts by asking questions about the problem. The user defines relationships, illegal conditions, and the goal. The program then searches until it finds a solution.

In Late knight extra, Tantalizer no. 407 (10 July, p 88), four knights have a set of attributes - colours of plume, banner and shield; degree of bravery; and name of horse. The question is which knight has the purple plume. The Tantalize user first types in the categories: knight, steed, plume. ete. Then the computer asks him to name the knights, name the steeds, and so on. Finally, it asks him to type in what he knows, for example "Knight=Sir Bruce: Steed= Geronimo". Finally. the user gives the goal, and the computer finds the answer.

Reynolds has solved more than 30 Tantalizers this way, and is still working on more. On Monday he solved the 7 August Tantalizer, no. 411 Diplomatic Niceties, about assigning the right ambassadors to the right countries.

Tantalize also permits simple arithmetic computations. On Monday, Reynolds also solved no. 409 Fe, Fi, Fo, Fum, (24 July, p 230) about giants with five, six, and seven league boots.

Hollis sees two types of Tantalizers.

In the first, the setting has nothing to do with the problem. Late knight extra is one of these, and Hollis first draws a skeleton and then sets the attributes. The second kind "depends on having the right thought in the bath." In these the location and characters are integral to the problem. I spin a web out of an idea. These are tricky and depend on things which seem irrelevant being not irrelevant at all."

Among those which Reynolds' computer could not solve was no. 365 Acknowledgements (vol 63, p 750) which depended on the definition of the word "pedantry", and no. 369, Find the catch about how many fish were caught by Hook, Line, and Sinker. The latter is mechanical in reasoning, Hollis said, but the problem is to see where to start.

Hollis himself prefers the latter kind.

"But doing them once a week, I'm afraid the computer has to be allowed a fair bite of them."

Joseph Hanlon

********

The CODIL archive includes a binder containing the solutions of the following Tantalisers

10 The case of the Mangled Millionaire 76 Eeny Meeny Miny Mo 86 Flip-Flop 87 Who's Who 99* Jackpot 100 Amazing Reductions 111 Macaristotle 119 Naming the Baby 122 Skeleton 166 Ancient Greeks 175 Fancy Dress 222 Cher D'oeuvres 226 School Colours 255 Down Memory Lane 266* Light of the World 341 Calling a Spade 347** Long Odds 361 From the Top 362 Wish you were here 363 England their England

364 The Long Vacation 366 Ins and Outs 367 Ratsfelpfeffer 370 Who's Who 371 Jolly Jumbo 377 The Case of the Fried Egg 396 Finals Reckoning 407 Late Knight Extra 409 Fe, Fi, Fo, Fum 410 The Clans Gather 411 Diplomatic Niceties 412 Consider Your Verdict 413 Sports Day 414 Three Men in a Catastrophe 415 Dizzy spell             There are also answers to 25 other puzzle, including some well known puzzles such as The Missionaries and the Cannibals and cases where TANTALIZER moved pieces across a chess board.

I will be posting further examples on the blog, in a way that you can try to solve the problem yourself, and then see the computer solution, usually including a trace of the route found to the answer, and a commentary where necessary as in the example School Colours. Please ask, using the comment facility below, if there is a particular problem where you would like to see the way TANTALIZE solves the problem.

CODIL was started as research into the design of an "electronic clerk" which could work symbiotically in a human team, in the context of large commercial management information systems.  The link with AI  and heuristic problem solving started almost accidentally in about 1973 when  colleague Roland Sleep,  who had been reading a recently published Ph.D. thesis on heuristic problem solving suggested that I should see if CODIL could solve any of the puzzles.  Within days I had used CODIL to solve all the. problems used as examples in the thesis and started to write CODIL system, called TANTALIZE which would ask questions about the problem and use the answers to generate the set descriptions needed to solve the problem.   The approach was transparent, as if you selected the Trace option you could follow the path to the solution  step by step. This can be seen in the solution of TANTALIZER 226 where the search involves several exploration of dead end branches.

In addition a search for contemporary published AI heuristic problem solving literature produced a range of other problems - such as the missionary and the cannibals crossing the river with only one boat.  In each case where a comparison was possible the TANTALIZE input was simpler, and the solution was found in less time. In addition I had set  TANTALIZE was set a unique goal. I was attempting  to solve successive "human" problems set weekly in a magazine - the challenge was that the researcher had no idea what kind of problem was coming next. Of course it didn't solve everyone, as Martin Holiis explains in his article. In contrast the published AI papers tended to concentrate on a few cherry-picked (and often well known) problems and none had challenged their AI problem solver with a weekly list of problems where the researcher idea what the next problem would be.

However there was a big problem. I did successfully submit the paper "A Conversational Problem Solver written in CODIL" but further publication was difficult.  For example I submitted a pair of papers to an AISB conference. One gave details of how TANTALIZE worked, and the other gave details of the problems solved, including problems from the New Scientist and from other AI publications. The papers were rejected because TANTALIZE was "too theoretical to ever work" - in effect labelling the information on the solved problems in the second paper as impossibly good and therefore fraudulent. After several such rejections I got the opportunity to show original CODIL and TANTALIZE listings to a leading AI guru who kindly explained that my research was not Artificial Intelligence because TANTALIZE couldn't play Chess. He considered that the fact that CODIL was irrelevant  because it was simply based on a complex real world study of a commercial system involving over a million dynamically changing sales contract lines (each line representing a different pricing rule) and therefore had nothing to do with Artificial Intelligence while a game such as chess (where the never changing rules can be written on one side of a sheet of A4 paper) did. After such difficulties I redirected my CODIL research towards educational computing and abandoned banging my head against an AI brick wall.

So does CODIL have anything to do with Artificial Intelligence? If it is agreed that the words "Artificial intelligence" refers only to research involving the use of very sophisticated mathematical routines (which 99% of humans will not properly understand) and massive computers and data files (the bigger the computer, and the more voluminous the data, the bigger the research grant and the more prestige for the researcher and the department) I would agreed that CODIL and TANTALIZE do not count as "Artificial Intelligence."

In contract CODIL is concerned with producing an interactive working model of how non-mathmaticians' brains handle information. In effect it attempts to produce an intelligent system which processes information like a human on a scale which compatible with what is known about the human brain and using easily understood algorithms which were simple enough to have evolved under the supervision of Dawkin's blind watchmaker. However it extends the simple brain model approach by acting as a tool which can process, retrieve and store potentially large quantities of information in a transparent and reliable way, and it can also provide users with access to a range of conventional "black box" computer tools if needed.