A Database For A.I..

Summary

It is argued that progress in A. I. research requires reference data concerning cognitive processing . It is proposed that such information relevant to the needs of A. l. can be made available by the controlled study of man/machine interactive problem solving, a paradigm we hove called "The Cognitive Test-Bed". The system currently implemented at Reading is described and the methods of results analysis discussed.

Rationale

Progress in A. I. might be aided by a knowledge of human decision-making and data acquisition processes. We will describe a methodology we hove termed "The Cognitive Test-Bed" or CTB which is directed to acquiring this knowledge by empirical investigation. Such knowledge may be essential to A. I. since however "Artificial" future synthesised "Intelligence" may be, it will still need to be recognised as "Intelligence"- at least initially.

Consider how we could attempt to answer the question:"How do humans solve problems?". Ideally, we would monitor appropriate on-going activity whilst subjects perform the task and draw our conclusions from the results. The effectiveness of such research would depend upon the degree of resolution and the appro­ priateness of the application of the monitoring equip­ ment. Historically, the question above was approached by collecting verbal protocols from human subjects during their problem-solving task. Our CTB system aims to increase the degree of resolution of the monitoring equipment and to employ data processing facilities in the analysis of the resulting information .

Our aim in this research is to derive some of the processes in the repertoire of human cognitive activity and apply them to learning programs.

Requisites of a CTB system

A system designed to probe into the methods of human thought needs to meet the following formal requisites .

1. We must provide the human subjects with a problem environment complete with automatic collec­ tion of the resulting data since the method of data collection must not interfere or interrupt on-going problem-solving activity.
2. The problem itself must hove an interactive nature and yet, for the purpose of analysis, the "interactor" must be a "control".

A DATABASE FOR A.l.

J. G. St . Quinton and A. M. Andrew Department of Engineering & Cybernetics University of Reading, England

1. The problem chosen needs to have a simple definition and few rules of problem-state transformation so as to enable the participation of naive subjects.
2. The solution set should rely as little as possible upon the subject's previously obtained knowledge base, yet still contain sufficient complexity to require the utilisation by the subject of a wide range of thinking processes .
3. The essential property of the chosen problem task is that it contain heuristic devices whose acquisi­ tion by the subject is essential if the subject is to produce increasingly sophisticated solutions to the task. let us call such devices "Keys", attributing the property of data to them. The concept of a Key is described more fully below.
4. The essential property of the data collected from the experiment is that it permit the monitoring ot the acquisition of these Keys and provide information concerning the methods of human problem-solving evoked by the task. For such methods we wi II use the term "heuristic"- examples of which are "backtrack" and "means-ends" analysis . Contemporary work on problem-solving such as Chase and Simon (2) emphasises the role of recognition memory and thus-
5. The problem solving task chosen must be amenable to the examination of familiar solution constructs. That is the ways in which problem related information learnt by the subject during early stages of the task is used by him during the later stages of the task.

The Key Concept

The problem-solving task, in common with many others,· can be viewed as a walk through a building from a door to one marked "Goo I State". Consider that the intervening doors are locked. Some doors in this building lead to cul-de-socs, others lead us in circles and others, if passed in the correct sequence, to "Goal State" . To traverse this building one needs to acquire the appropriate set of Keys and to select for use on appropriate sequence of them. Continued attempts after a successful pass should, with learning, achieve increased efficiency in task performance.

Continuing this metaphor a moment we might consider that during one's experience, one acquires a collection of Keys and knowledge of when to use them - assuming of course we know how to use them . The process of using them we have termed "Heuristics", whilst what-we-use ore the "Keys". By Keys then, we mean sets of information, which once acquired and appropriately used, lead us to goal states.

Examples ore: "Centre Control" in Chess, pushing on the rope in the Maier pendulum problem (1) and being told to consider a "Chess Board" and/or a "Domino" in the notched checkerboard problem.

As we hove mentioned, whatever problem task is chosen for a CTB, it must facilitate the monitoring of the acquisition and utilisation of Keys by the subject when performing the task, thus enabling the deduction of human heuristic cognitive processes.

The CTB System at Reading

We envisage future Cognitive Test-Beds to be a combination of problem presentation and cognitive analysis in a single real-time system and employed for personality assessment and as a research tool.

The system presently implemented at Reading is two-stage . On-line problem presentation and data acquisition is achieved by a DEC PDP 12 at assembly level and off-line data analysis by on ICL 1904 Sin Algol 68-R, a language able to cope with orbitrori ly complex data structures, mutual recursion and u wide variety of mode definitions.

The choice of problem and its presentation

The requisites of a CTB system may be met by the careful choice of on interactive board game programmed for on-line ploy against human subjects. The computer is also capable of automated boord presen­ tation, data collection and the monitoring and adap­ tation to the increasing adeptness of its initially-naive human opponents.

We shall briefly describe the game chosen for this study, indicating its suitobi lity with respect to the Key concept. It is also necessary to outline the game playing program since the subject's thinking is a function of the "thinking" of the machine opponent. (The demand characteristics of the experiment.)

However, we must emphasise that this research is not concerned with the game playing program per se. We describe the program only because its design speci­ fication must be borne in mind when the results of the experiment ore discussed since it directly affects these results, just as one would need to describe a "one-off" piece of laboratory test equipment. The research is concerned with the processes this experimental apparatus detects in human thought and not with the apparatus itself. -

Our experimental apparatus for this study is a "Peggity" playing PDP 12 computer. Also known as "Go-Moku" and "5-in-a-line", this game con be played on various sizes of board (we used 20 x 20), has only one type of piece and one type of move (entry).

A player's expertise depends upon his ability to perceive complex logical relationships between the opposing pieces.

The two players alternately place one of their own tokens on one of the remaining positions (nodes} of a square matrix of positions. The first player to achieve a line of 5 adjacent tokens in any direction, vertical, horizontal or diagonal, wins.

In order to win, one must form on unbeatable pattern. For example, if one hos four pieces in an open-ended straight line, this is unbeatable not more than two moves ahead, provided of course that the opponent does not hove such a pattern already. If one hos three pieces adjacent in on open-ended line, then the opponent is forced to move so as to block the three pieces to prevent it becoming on unbeatable four, else the player with three pieces wi II win in not more than three moves. This sequence of unbeatable patterns represents the "Keys" to this problem task. If one has two open-ended lines of two pieces, each of which intersects at some unployed position and then ploys at that node, he creates two open-ended threes (a Key we may call "crossed threes"} both of which must be stopped by the opponent at the next move to prevent a win. Since only one con be stopped, this pattern of two intersecting lines is unbeatable some five moves from the end. An innocuous pattern of pieces forming on "L", see fig. 1, is in fact on unbeatable pattern not more than twelve moves ahead if played appropriately.

2

3

4

X

X

5

X

fig.1. Section of playing lattice. "X" represents a played token, and the numerals indicate a potentially winning playing sequence.

Thus the successful Peggity player must acquire a set of such Keys, each of which, though not guaran­ teeing success in any one game, increases his chances of winning when he is able to implement those which are potentially unbeatable more moves ahead than his opponent con comprehend as dangerous.

The informational Keys inherent in this game are readily described in terms of pattern description lists and their occuronce during any game is easily monitored, thus making the choice of this problem task for our experimental paradigm clear.

We wi II now describe the apparatus used in our experiment. The program utilises a maximisation algorithm. The PDP 12 in which the program operates also displays on a CRT the board position lattice at each problem state, inputs its human opponent's move via analogue channels fed by a joystick device, measures move latency (that is the time the human tokes to make a move} and registers, via a pair of human-operated buttons, those positions at which the human

1. considers a game inevitably won or lost
2. considers that he has notices a significant problem trait

Finally, the apparatus is able to adapt the level of problem task complexity to match the acquired prowess of its initially naive human interactor.

In their study of machine learning and heuristic programming, Murray and Elcock (3,4) programmed Peggity using a backtrack analysis learning technique. In order for a computer to perform the required game playing task within a region of competence suitable for naive human subjects to be consistently challenged throughout an experimental session lasting not more than twa hours, a simple maximisation algorithm whose scope regulated task complexity was found to be suffi­ cient. When it was the machine's turn to move, it performed a centre outwards sweep of all board locations and for each unoccupied position generated, a vector describing the immediate vicinity of the unplayed position (node). This vector consists of a set of four ordered pairs - each pair associated with a particular direction about the node, namely, vertical, diagonal -ve gradient, horizontal, and diagonal +ve gradient.

In any one direction, for a particular node there are 5 groups of 5 adjacent locations which encom­ pass that node, see fig.2.

Any of these 9 locations may be occupied by one or other of the tokens or have o mixture of both, or be unoccupied. If node A in fig.2 had been the third location from the edge of the board then only 3 groups of 5 would hove encompassed it.

We define a function to describe the immediate vicinity of o node at any given board state in terms of an ordered integer pair T, G. (ForT, 0 to 4 and for G, 0 to 5). T is the number of tokens of one type and G, the maximum number of groups of 5 locations which are either unoccupied or contain only tokens of that type. A few examples of TG pairs are given in fig.3.

The value of TG is not affected by the type of tokens in the vicinity of the node but groups of 5 loca­ tions which contain mixed token types are excluded from the evaluation of TG. The algorithm employed by the apparatus is concerned with the maximum value of TG it finds when considering a line of locations, at any orientation, through o node.

Thus, in fig. 3 (iii), the example has two TG values associated with it1 TG (d)= (1, 1) when consi­ dering the token "X" and TG (d) = (1, 2) for "0". The maximum, (1, 2) is therefore the final value for TG. The precedence order for choosing between TG's is that firstly, T's are examined and when they happen to be equal, the TG value selected is the one with the greatest G.

A description of o region about any node In the figures 2 to 4 below the character 11 · 11 represents an unoccupied board location. 11 0 11 and "X" represent human and machine playing tokens respec­ tively. Lower case alphabetic characters represent particular unplayed nodes we whh to draw attention to in the text.

requires four such number pairs, one for each orienta­ tion. We illustrate examples of these vector sets using a section of a board lattice for a possible game situation in fig .4 and we shall use this example to explain the three "Strategy Levels" the apparatus selectively evokes in response to the performance of the human subjects under test.

The playing strategy is switched from the initial level 1 to 2 and from 2 to 3 when the subject wins two successive games. (Players have first move every alternate game). The move processor in the apparatus is directed to move according to the following rules:

Strategy Level 1. "Partial two-line maximisation."

The move is made at the first location in the board sweep having TG maximum in up to four orienta­ tions. In the example in fig .4 this would mean that in any one of 5 positions including "k", "z" and "q", depending on what area of the board, the pattern shown in fig,4 was located.

Strategy Level 2. "Two-line maximisation".

Moves are made at the first node having TG maximum for two orientations. In our example, at node "q", though had a node existed with a vector set, say (0,5 3,1 0,5 0,5), it would have moved there in preference to "q".

Strategy Level 3. ''Crossed Threes Potential".

Moves are made in accordance with rule 2 except thot when potential "crossed threes" exist in the board pattern, the move is always made there ("q" in our example) in preference to any other node exct!pt those containing TG pairs such that T-4 and G=1, or 2 or T=3 and G=2, when these nodes would take precedence. (These particular nodes represent potential end-game situations).

The implementation of these algorithms requires 0.5 K of store and enables moves to be processed in some 7 seconds,

The level of difficulty may be judged from the fact thot, of the 40 graduate-level subjects used in this research, (20 mole and 20 female) who on average were tested over 16 games each, 20% of moles reached Strategy Level 3 and 50% of females achieved Level 2. Generally, the humans won one game in seven.

These algorithms, though simple produce an interesting problem task for subjects and even though they represent a controlled problem-solving task, their behaviour was so life-like that a number of subjects were convinced that their opponent was another human secreted in another room.

CTB Analysis Techniques

As well as a problem presentation section, a CTB systern consists of a dota analysis section. The latter being designed to generate and test hypotheses

fig.4. Section of an otherwise unplayed lattice

Vector Sets for nodes:- h, k, w, z, q

Where V, D, Hand U indicate orientations:

(Vertical), diagonal -ve gradient (Down), (Horizontal), diagonal +ve gradient (Up).

concerning cognitive processing. When a CTB analysis section for any task is fully evolved it is, in effect, a process model of cognition whose descriptive efficiency moy be measured by a comparison of its own behaviour with that of the system it models.

An aspect of analysis which needs to be included in any CTB system is one capable of gauging the effects of the demand characteristics of the experimental problem task. This is because in any interactive problem solving situation, the way an interactor learns is a function of the partner's overt behaviour.

A practical consideration for the design of any CTB system is the achievement of an optimum balance between the complexity of the problem task and the complexity of the resulting analysis.

Analysis Implementation

The analysis section of the Reading CTB is divided between three units -

1. A program for transforming the raw experimental data into position-descriptive and play-evaluative information and storing all three on the CTB system's database.
2. A program to transform the original database into one containing descriptions of all keys which had occurred during the experimental sessions. Such keys moy have beon originated or utilised by either player. By utilise we mean, in this context, responding to a key situation by forcing/preventing or attempting to force/prevent a win if the key pattern consisted of that player'v'opponent's own tokens.
3. A program to test hypotheses concl:!rning the possible existence of specified forms of ~ognitive processing by the appropriate extraction of data structures from the database.
4. SCAN-TEST is designed to analyse all subjects' data in terms of position-descriptive and ploy-evaluative functions for each move in every game across the three strategy levels. It is directed to ask: 11 Whot did a particular move achieve? 11 (Be it human or machine. The program makes no distinction so as to enable analysis for the effects of the tasks demand characteris­ tics.) It further asks: 11 What did a particular move fail to achieve by n:ot being made at any other available play position? 11 · SCAN-TEST implements numerical functions defined so as to enable evaluation of these questions cind at the same time to provide a transform of the original experimentrJI data such that later analysis programs will have less board-pattern descrip­ tion/recognition computation to perform.

The resulti'69 database for the 40 subjects consists of some 10 informational items.

Position Descriptive and Play Evaluative Parameters.

We shall describe briefly these parameters and indicate their use in respect of analysing for the task's demand characteristics. Those functions which are purely evaluative in character are followed by (E).

ACHMNSET - The vector set describing the immediate region about a played location.

MOVETYPACH - A categorisation of the move in terms of possible fore ing and preventing FP move types, e.g. crossed threes utilisation.

MOVETYPUNACH - A categorisation of moves that could have been made. (E)

MAXLVLACH -A measure of the degree to which the move achieved the greatest vector set possible for that board position {E).

NFPL- The number of locations at which FP moves were possible. (E)

NFPMACH -The total number of FP elements contained within a move.

STFPE -The total number of FP elements contained within unployed positions. (E)

NFL - The number of locations at which the play could have achieved a forcing move. (E)

NPL - ditto for preventing moves. (E)

ACHMNSET provides information concerning perceptua I aspects of the task and the resu Its shaw, for example, that subjects take greater notice of the orientations horizontal and vertical than the diagonals when making a move.

The validity of the Evaluative functions is indicated by the fact that they hove been shown for humans to hove higher values for games won than for those lost. The assumption that the CTB system acted as a "cQntrol" player is verified by the fact that values for all these functions for machine moves were not significantly different for games won or lost by the machine at any one of the three levels.

A number of these functions ore indicators of the subject's learnt behaviour as shown by their increa­ sing value as the subject progresses through on experimental session. Therefore on examination of those variables for which there is a tendency for the human­ generated values to approach systems-generated values will indicate some of the ways in which the manner the tos k was presented to the humans (i.e. the playing algorithms) affected the subjects' learnt performance.

1. KEY DESCRIPTOR. Keys form the basis of this CTB analysis. Their occurrence and mode of occurrence during subject testing provides the clues for answering the question which motivated this study. KEY DESCRIPTOR accesses the database and forms a description list for each key in a language whose grammar is sensitive to its orientation but insensitive to its location and plots their occurrence. This information is then add·Jd to ihe database.
2. HEURISTIC PROBE. The database is now accessed by HEURISTIC PROBE which is directed to search the database for evidence of particular heuristic methods used by the subjects.

As on example in respect of the work cf Murryo and Elcock (3,4), suppose we wished to search for evidence that one cognitive process ovoi loble to the subject is the obi lity to store in the form of sub­ goals those keys first utilised by the opponent. The HEURISTIC PROBE would be directed to compare descriptions of those keys which first utilised by the systern were later utilised by the subject. The oct of comparison for this search would also provide evidence for the degree in which the generalisation by rotation of these keys was available in the human repertoire of thought.

A full description of these techniques and results will be presented at the conference and is available from the authors.

The system has so for been used with graduate­ level subjects and permits comparison of cognitive proce>sing between sex and performance levels. Consi­ deration of the developmental and personality factors involved in cognition is a motter of running the appro­ priate subjects on the Reading CTB system.

Conclusion

We have presented an introduction to the concept of a "Cognitive Test-Bed" and outlined the Reading system.

The importance of informational keys hos been emphasised in respect of CTB analysis techniques and in the context of problem-solving tasks in general .