Operationalizing Heuristics: Some AI Methods for Assisting AI Programming

1. Introduction

In a longer version of this paper [4], we advocate machine-aided heuristic pro&rammin& as a paradigm for training computers to do new tasks, and formulate a set of research problems involved in building a machine­ aided heuristic programming system (hereafter abbreviated "mahps") capable of assimilating conceptually diverse knowledge and putting it to effective use. In this paradigm, an expert interactively gives the mahps advice about how to do a task, plus definitions of the concepts In terms of which that advice is. expressed. For example, ln 'trainlng a mahps to play the card game Hearts,** the expert might advise It to avoid taking points. Such advice is paned Into a syntax tree which Is interpreted Into an Internal representation. Advice may then be oper11tiono.li.zed, either sto.ti.co.lly -- Independent of a particular game state -- or dyn11micBlly -- exploiting current information arising from an actual game. Once operatlonalized, the advice can be applied to produce recommendations relevant to the decision at hand.

·Thia work wn .... ,..,orted In part by the National Science Foundation, RCN 6869, Grant No. MCS77-03273 to the Rand Corporation, in part by the Graduate Fellowahip procram aupport to the firat author, and in part by the Defen" Advencad R····rch Projach Atency (000), ARPA Order No. 3597, monitored by the Air F orca Avionin laboratory under Contrect F33815-78-C-15!51. The viewa and concluaion· conteinad in thit document ·r· tho .. of the authora end ahould not be interpretld 11 repreaentint the official polici .. , lither 1xpre11ed or implied, of the Oefenae Advanced R1111rch Project· Atency or the U.S. �ov~rnrnent.

··The card t·m· Hearta i1 u1ed throuchout thi· paper for purpoMI of lllu·tr~Uon1 the rulee of the '""' are tlven In (4~

Diverse advice is interro.ted by combining these recommendations, either rationally or heuristically, and o.ppli.ed to the system's game decisions and to Its Interpretations of its opponents· behavior. At any point, the system can pose questions to the expert usina the rule

If x is an important question which has resisted solution, explain It to the user (preferably with a small set of multiple choice answers) and ask for the answer or a piece of relevant advice.

The expert monitors the r.ystem·s behavior and Improves It by providin& additional advice.

In this paper, we focus on the automatic operationallzation of advice. We assume that the advice has been interpreted into an unambiguous Internal representation of its meaning, and suggest some approaches to the problem of transforming that representation so that it can be effectively applied to the task.

2. Representation of Conceptual and Heuristic knowledte

Our knowledge representation is a typed lambda-calculus combining an appllcatlve LISP-like language [3] with a schema-like structure. The basic unit of representation It the concept, which is a named lambda-expression. Schematic structure associated with each concept Is described In [4l Briefly, It provides type Information about the concept and Its lambda-variables, and defines inheritance relations between general and specific conceptj;.

A type is simply a class concept. Since one class may be a subclass of another, an entity may belong to more than one type. For instance, ~E (the machine·s card-playing persona) is both a PLAYER and a COMPUTER. Two types are said to mt1tcla if they overlap. Thus PLAYER matches HUMAN since it is possible to be both human and a player.

Although there Is no assianment operation In this representation, e·.'ery expression is implicitly a state function, I.e., its interpretation depends on the state of the world it describes. Actions are represented as functions from a state to an e11ent. A hi.1tory is an actual or hypothetical sequence of states and events. When an action is performed, the history of what happens durina its execution is recorded so it can be referred to subsequently. Thus at any point in time one can refer to the PAST -- the history of events that have already occurred, the PRESENT -- the set of events that have beaun and not yet ended, and the FUT~ -- the 11 yet undetermined history about to occur.

2.1. Meta-functions

Our representation provides a limited number of built-in meta-functions, characterized by their lack of strict type (some of them take a type as a parameter) and their need to examine some of their arauments without evaluating them. These meta-functions include the following (optional parameturs and their default values appear In brackets):

(EXISTS x S P) · there exists x In S such that P

(SET -OF x S P) · the set of x in S such that P

(THE x S P) · the unique w in S such that P

(SOME x S [P]) · any w inS [such that P]; any expression containina this construct is potentially non-deterministic

(All e) · set of possible values for the non-deterministic expression ea thus (All (SOME x S)) · S and (SOME x (All e)) · e

(SUM V x S [P]) · the summation of V(x) for x In S [such that P(x)]

<· S) · the number of elements in the set S

(GIVEN P x) · the value of x given that P is true

(PR P) · probability that P is true

(PR P Q) · conditional probability of P given that Q is true; thus (PR P Q) · (PR (GIVEN Q P)) · (GIVEN Q (PR P))

(CASE (P1 Vt) ... (Pk.. Vk) (V]) · the unique (GIVEN P1 VI) such that P1 s true [otherwise V]

(IF P 1 V 1 ... Pk Vk V) · the first (GIVEN P1 Vi) such that P1 Is true, otherwise V

(SET x1 ... xk) · the set {xl· ... , xk}

(SCENARIO x1 ... xk) · the event sequence w 1 ... Xkl each xi can be eltfier a slnale evant or a scenario

(EACH x l A) · (SCENARIO A(x 1) ... A(xk)) where l · (LIST x 1 ... xk)

(00 scenario state) · simulate the effects the scenario would have on the specified state

(ACTIONS-oF agent [state · PRESENT]) · the set of specified state]

possible actions the aaent can do at present [or in a (DURING history c .. ent 1 ... eventk) · true iff the scenario event 1 ... eventk occurs during history (CURRENT event) · history of the current Incarnation of a aenerlc event such as TRICK (CHANGE PI P2 state) · altered state produced by making P 1 else and P 2 true (AFTER event) · state following a specified event 2.2. Example concept definitions An essential feature of this representation is its astanli.bi.li.ty. A mahps must be able to assimilate new concepts defined by the expert In terms of ewistina ones. The following definitions of concepts used In later examples Illustrate the representation. lOE TRICK NIL (SCENARIO (EACH P (OAOER-OF-PLAV) (PLAV-CARD P)) <TAKE-TRICK <TRICK-WINNER)))) (DE PLAV-CARD (P) (PLAV P (SOME C (LEGAL-CARDS-OF P)))) (DE CARO-OF (p) HHE C CARDS (QURING (CURRENT TRICK) (PLAV P C)))) (OE LEGAL-CARDS-OF (p) (SET-OF C CARDS !LEGAL PC))) (QE LEGAL <P C) (ANO £HOLDS P Cl (CASE (<FOLLOWING P) (OR £VOID P (SUIT-LED>l [. !SUIT -OF C) !SUIT -LED> l)) ((LEADING P) (OR [CAN-LEAD-HEARTS Pl lNEQ (SUIT-OF C) HJ))]))

• (DE TRICK-WINNER NIL £THE P PLA YEAS lOURING (CURRENT TRICK) (PLAY P (WINNING-CARD)))))

(OE TAKE-TRICK (p) lEACH C (CARDS-IN-POT) (TAKE PC)))

(OE TAKE (PLAYER CARD) lMOVE PLAYER CARD POT (PILE-OF PLAYER)))

COE PLAY (PLAYER CARD) lMOVE PLAYER CARD CHAND-OF PLAYER) POT))

• COE MOVE lAGT OBJ ORIG DEST) lCAUSE AGT lCHANGE (AT OBJ ORIG) lAT OBJ OEST))))

lOE CAUSE CAGENT EVENT) (SOME ACT lACTIONS-OF AGENT) (LEAD-TO ACT EVENT)))

COE POINTS lCAADJ

(CASE ((· CARD QS) 13) ((· (SUIT-OF CARD) H) 1) ((.CARD JD) -10) 9))

COE AVOID (AGENT EVENT) (SOME ACT (ACTIONS-OF AGENT) (SMALL lPR-LEAD-TO ACT EVENT))))

lDE SMALL (X) (c X 9.1))

COE PR-LEAD-TO CEVENT1 EVENT2 IH · FUTURE)) lPR CLEAD-TO EVENT1 .EVENT2 H)))

COE LEAD-TO lE'/ENTl EVENT2 IH · FUTURE) ) (GIVEN (DURING PRESENT EVENT1) (DURING H EVENT2)))

Heuristics are concepts too. A goal like ·avoid taking points" can be represented as a predicate to be satisfied by an agent:

lDE AVOID-TAKING-POINTS (p) (AVOID P £TAKE-POINTS PJ))

2.3. Discussion

A key feature of our approach is the separation of representation from implementation. The definition of a concept encodes only enough Information to specify Its meaning precisely. The task of converting this definition Into an effective implementation is factored out into the operatlonallzatlon process. Essentially we are retalnlna LISP-like semantics but replacing EVAL with a eolleetlofl of heuristic methods for evaluating expressions. We feel that the traditional popularity of LISP as an Implementation language has obscured Its potential as a powerful, concise representation of knowledse.

3. Operationallzation

This section su&~ests several methods for operatlonallzatlon, which we define as transformlns well-defined but non-effective expressions to make them effectively executable. The expressions used In the examples In this section use the representation described In Section 2. An expression may be non-effective In any of aeveral ways:

• It may depend on non-observable Information that can be deduced, or on uncertain data that can be predicted only probablllstlcally.
• It may depend on events that have not yet occurred but can be reasoned about.
• It may be defined intensionally over an Infinite or comblnatorlally' large domain and hence infeasible to compute systematically.
• It may be defined In terms of a function which can only be computed by special-ease reasoning because It has no known aeneral formula.
• It may be too complex to evaluate exactly but may still be amenable to approxlm1tion.

Operatlonalizetion seeks to resolve such difficulties by combining appropriate methods: means-ends rules, special-case reasoning, simplifying assumptions, search, etc. It Involves two Important subproblems:

1. Mo.pplnf upreui.ons to methods: Match an expression to a suitable method for operatlonalizlng It, and decide how to Instantiate the premises of the method In terms of the expression.
2. Represento.tion o/ AI methods: Represent inference methods in a form that can readily apply to novel problems. This requires form·llzetlon of techniques which, although widely used, have not previously been characterized with sufficient precision to permit automatic application to a wide ranae of tasks.

Given an Internal representation of what ·avoid IIkins points· means, the mahps must operoti.ono.Uze that concept, I.e., figure out !J2.!: to avoid takins points.

3.1. Goel·apeclflc opentlonallzetlon ruiH

The simplest wey is to use some method provided by the expert, such es

To avoid taking points, play a low cerd.

This method can be represented by a means-end rule thet essentially ignores the underlying conceptual structure of "evoid taking points" and simply treats It as 1 aoel symbol. S·1ch rules enable user-provided domeln-speclflc operetlonallzatlon of concepts.

3.2. Systemetlc ·veluetlon

Systemetic evaluation can be used as an operationalizatlon technique. In this approach, concepts ere treated as functions, and expressions are aystematlcelly expanded until known que.ntities Ire re1ched. Functions ere epplied to erguments by the rule

To operetlonalize an expression (Fel ... ·n> where F hes no known operationallzetlon, substitute e1 ... en for the correspondina lembde-verlebles In the functlonel definition of F.

Thua

AVOID-TAKING-POINTS

• lAVOIO ME (TAKE-POINTS ME))
• (SOME ACT (ACTIONS-OF MEJ
• (SMALL (PR-LEAO-TO ACT lTAKE-POINTS ME))))

The subupresslon

(PR-LEAO-TO ACT (TAKE-POINTS MEJ)

cen be expended to

(PR (QURING FUTURE (TAKE-POINTS ME)) (QURING PRESEN'f ACTJ)

• (GIVEN (QURING PRESENT ACT) (PR (QURING FUTURE (TAKE-POINTS ME))))

Systematic evaluation of this expression is precluded by the lack of a general definition that can be substituted for PR. In general, this approach encounters difficulties when there Is Inadequate knowledae to eveluete en expression, or when systematic evaluation is computationally exorbitant. Heuristics proposed elsewhere [4) for dealing wl'h such difficulties epply special-case knowledae about partially-defined functions or introduce simplifying assumptions thet permit 1pproxlmate solutions.

3.3. Generel operetioneiiZition methods

(This section uses fault tree analysis as an example of a general operationalization method and shows how it can be used to operationalize "avoid taking points." The purpose of this exercise is to suggest the feasibility of performing such reasoning automatically by applying simple search and manipulation operations to a knowledge base of user-defined concepts.)

A reasonable way to operationalize "avoid taking points" is to apply knowledge about how to avoid things in general. For instance, one method for avoiding an event is fault tree analysis: figure out what conditions can cause the event, and prevent them. Analysis of the game rules shows that taking points only occurs by winning a trick in which points have been played. Fault tree analysis might suggest trying to lose the current trick If it is likely to have points.* .

Note what reasoning is required to do this sort of operetionalization. The idea of using fault tree analysis tin be suggested by instantiating a rule like

If your goal is (operationalize (avoid x)) then find a necessary condition for x and make its negation a goal.

The analysis itself might be performed as follows. (This description omits numerous fruitless branches taken alona the wey; the intermediate steps of the derivation given below require some search to find.) First the definition of TAKE-POINTS Is expended In terms of TAKE:

(TAKE-POINTS ME)

• lTAKE ME (SOME X CARDS lHAS-POINTS X)))

Next the mahps looks for EVENT concepts In which TAKE occurs. (This simply requires the ability to Iterate over the set of defined concepts.) The only such concept Is

(QE TAKE-TRICK (p) lEACH C (CARDS-IN-POT) lTAKE P C)))

Thus TAKE-TRICK Is the only way the mahps knows about of taking a card. In particular, (TAKE ME (SOME X CARDS (HAS-POINTS X))) implies

(ANO £TAKE-TRICK MEl (EXISTS C (CARDS-IN-POT)

(HAS-POINTS CARD)))

· A ·ophi·ticeted pleyer will uve low urd· to uee durinc the Ill Iter pert of the c·-· when the ri·k of t·kinc pointe normelly incre11... It would be rether difficult for · mehp· to Infer thie eubtle tectlc from the lldvice "1void tekint point·"; it i· 111uch 111ore re11oneble for the ··pert to ·us···t It ··pllcitly.

The conjunct

<EXISTS C (CARDS-IN-POT) <HAS-POINTS CARD))

In this npresslon is the definition of TRICK-HAS-POINTS. Similarly, the only known case of TAKE-TRICK occurs In

<DE TRICK NIL <SCENARIO <EACH P <ORDER-OF-PLAY) <PLAY -CARD P) ) <TAKE-TRICK <TRICK-~INNER))))

so (TAKE-TRICK ME) Implies (· ME (TRICK-WII\WER)) In short, (TAKE-POINTS ME) occurs Iff

<AND [· ME <TRICK-~INNER>l [TRICK-HAS-POINTS])

To avoid (TAKE-POINTS ME), the mahps can add to Its goals the proposition

<IF <TRICK-HAS-POINTS) <NOT <· ME <TRICK-~INNER))))

Each step of this derivation can be accounted for by a simple operation, such as lambda-substitution or unification matchlns. It appears quite feasible to automate this sort of analysis as, say, a set of rules for when to perform each operation.

3.4. Weak methods

(This section uses heuristic search as an example of a standard AI "weak method" [5] and applies it to the operatlonallzatlon of "avoid .taklns points." It Is argued that the reasoning Involved In so doing might feasibly be performed mechanically. Some of the problems Involved In applylns a seneral method to a given problem are discussed, and some techniques for solving them are proposed.)

AI provides several weak methods applicable to the operatlonalization problem. One such method Is heuriStic search (hereafter abbreviated "HSM"), which can be used to find a sequencf· of elements satisfying a given property [5]. Figure 1 shows (In quasi-SAIL syntax) a generic "procedural" for HSM which yields an effective search procedure when the underlined components are Instantiated by the components of a particular search problem. Figure 2 gives a schematic description of these components. For example, It specifies "operator· as the type conslstlna of all functions from a node to a node.

Let us see how the mahps might operationalize "avoid taking points· In terms of heuristic search. Suppose It has encountered difficulties In operatlonallzlng

<SMALL <PR-LEAO-TO ACT <TAKE-POINTS ME))) and applies If you're having trouble operationallzing a predicate P, find a non-trivial predicate Q that Implies P, and operatlonalize Q as an approximation for P. with P · (SMALL (PR x)) and Q · (NOT x). The mahps Is now left with the problem of operatlonallzing (NOT <LEAD-TO ACT <TAKE-POINTS ME))) · (NOT (GIVEN <DURING PRESENT ACT) (DURING FUTURE <TAKE-POINTS ME)))) · <NOT <EXISTS H <ALL FUTURE> <DURING H ACT TAKE-POINTS ME))) ~ eequence procedure HSM-search · begin "search" r:l.!2S!!! n , n ' a operator opa eearch-spacer·flnodell repeat If (nr·select-node(search-space)) · NIL then return failure I search-space eMhausted else If prune-test(n) then remove n from search-space I prune nodes not worth considering elee begin "consider node" If (op:·select-op(n)) · NIL then remove n from search-space I no operators left to apply to n alee begin "eMpand node" n'r·op(n)a Llnk(n,n'h If solutlon-test(n') then return Path-to(n')a* I (lnode, ... , n') Is solution If --re\aln-test(n') I prune If not worth retaining then put n' in search-spacea end "eMpand node"a end "consider node"a end "search" 1

Flaure Ia Procedural for heuristic search To decide whether such a scenario H exists, the mahps cen use heuristic search. This method miaht be auaaested by partial-matchina the sub-expression

"Peth-to(n') f!Me the peth <IDS -~ n') by treciftt beck elone the linll1 eetlbHihed by L!M(II,n').

lEXISTS H (ALL FUTURE) lOURING H ACT(TAKE-POINTS ME)))

I I I I

I I I I

HSM

problem

node type METHOD

type PROBLEM

def (FINO S (SEQUENCES-oF node) (ADMISSIBlE S))*

type TYPE

search-space type node set

I node

operator type node type TYPE

def function with ara: node, result: node

operators-on type function with ara: node, result: operator set

test type TYPE def predlc:~te with ara: node

solution-teat type test

prune-test type test

retain-test type test

select-node type aeneralor** from search-space

select-op

solution type aenerator from operators-on(node) I with ara: node type node sequence def (HSM-search)

Flaure 2s Schema for heuristic search

·o.ftMdby

CDE AD"JBSJILE C8> lAND l· 8 1 lnodol

[lolutlon-telt 8JL[NGTH 111 lFORAll I (IETIIEU 2 llEKTH Sll (f:XISTS OP loporatora-on s 1 _ 1 l ,. (OP s 1 _ 1 1 s 1 11J , aaalnst the HSM problem description

.. A w-.tO#' 11 1 procedure tt.t return1 111 elttMnt of He chol~ .. t Mch tl- It II ~led. The choice ·t My be 111pendM by other ,_,_ between ~II· to the tefll'ltot.

(FINO S <SEQUENCES-OF nodel <ADMISSIBLE Sl

The facets of HSM can then be instantiated by identlfyina correspondina residuals in the partial match [1], us ina

To operationalize an expression E in terms of a method M, partial-match E against M's problem description and instantiate the components of M with the corresponding components of the expression.

For instance, the correspondence between (ALL FUTURE) and (SEQUENCES-OF node) suggests using game states as nodes In the search, since each future is a sequence of aame states. However, additional information, not explicit in the expression, is needed to formulate an effective search. For instance, what are the operators?

The answer to this question is not explicit in the expression, but the HSM schema gives a clue: It specifies the operators as functions from 1 node to a node, I.e., from a state to a state. By examining the logical types of the concepts it knows about, the mahps can find that actions are functions from a state to an event. By applylna the rule

To view a concept c as an entity of type X, find a known function F whose domain contains c and whose ranse matches X, and view c as (F c).

the mahps can view any action (A x 1 ... xk) as the composite function (AFTER (A x 1 ... xk)) from a before state to an after state.

Next the mahps can decide which actions should be used as operators in the search. An adequate set of operators In this case Is given by (PLAY (PLAYER) C) for C In (LEGAL-CARDS (PLAYER)), where (PLAYER) denotes the player whose turn It Is to play In the current state. A more efficient search might use abstract operators like

(OVERPLAY (PLAYER) MEl

· lPLAV lPLAYERl

(ANO [HIGHER C (CARD-OF MEll [. lSUI T -OF Cl (SUIT -LEOl J)))

(SOME C CARDS

<SLUFF-POINTS <PLAYER))

· <PLAY (PLAYER)

(SOME C CARDS

lAND £YAS-POINTS CJ [NEQ (SUIT-OF Cl (SUIT -LED! J J))

·· suggested by To reduce a search space, suppress operator details that are irrelevant to the search criterion, and use the resulting abstractions In place of the original operators.

Such abstract operators have been used to increase planning efficiency In problem-solving systems [6, 7].

Other information absent in the expression includes the functions select-node and seiect-op. The simplest solution to this problem Is to use random selection functions. However, this would result In an inefficient search. A better choice can be made by applying

When selecting nodes and operators In a search, select first those most likely to satisfy the search criterion.

Thus when assigning successive values to the non-deterministic expression (SOME C (LEGAL-CARDS P)), the mahps should choose first those cards most likely to satisfy (TAKE -POINTS ME), namely cards that underplay Its own choice or that break suit. This ordering preference can be solicited from the expert by or derived by applylna fault tree analysis to the search criterion. If (TAKE-POINTS ME) occurs In some plausible scenario (i.e., a scenario consistent with ME's knowledge about legal play and the distribution of unplayed cards), this would be detected early in the search. If it doesn't, however, the whole combinatorial space would be searched. This could be avoided in a couple of ways. First, the mahps might simply prune branches of the search considered unlikely to lead to (TAKE-POINTS IIAE), using

If a search node is unlikely to lead to a solution, prune it.

Second, It could apply the general rule

If you search for something and look at the most likely candidates without finding it, Its probability of being there is small.

Thus an incomplete, unsuccessful heuristic search for

(SOME H (ALL FUTUREI

(DURING H ACT (TAKE-POINTS MElli

could Itself serve as evidence for the hypothesis (S~ALL (PR-LEAD-TO ACT (TAKE-POINTS ME))).

3.5. Dynamic operatlonalizatlon

(This section illustrates how information arising from an actual task situation can be used to simplify the problem of operationalizlng a generally applicable concept or heuristic. A hypothetical game situation is described, and a line of reasoning a human player might use in that situation Is presented. The problem of automatically aenerating a similar line of reasoning Is examined, and some general heuristics useful in solving it are proposed.)

Let's see how a n.ahps might operationalize "avoid taklna points" In the context of a specific game situation such as the following: The order of play is Joe, then ME (the machine), then Ann. Joe has just led the 15th trick of the round with the Kina of diamonds. The machine has two diamonds (the 10 and the Ace) and knows that the only outstanding diamond Is the Jack, and that the only point card still out is the Queen of spades. Clearly It behooves the machine to compare carefully the consequences of playing the 10 or the Ace.

A person In this situation might reason as follows: "I can certainly avoid taking points by playing the 10, since then Joe will take the trick. If I play the Ace and Ann has the Jack, she,l have to play It, so I won't take points. But If she doesn't have the Jack and she does have the Queen of spades, she might stick me with it. Otherwise I'm safe."

How might a similar line of reasoning be generated automatically? To start with, the mahpa expands the definition of AVOID-TAKING-POINTS to

(SOME ACT (ACTIONS-OF MEl (SMALL <PR-LEAD-TO ACT lTAKE-POINTS MElli)

This generates the goal of evaluating (SMALL (PR-LEAD-TO ACT (TAKE-POINTS ME))) for each ACT in (ACTIONS-OF ME). In the situation at hand, (ACTIONS-OF ME) consists of (PLAY ME 100) and (PLAY ~ AD). It Is easy to evaluate (PR-LEAD-TO (PLAY ME 10D) (TAKE-POINTS IIAE)) as zero by applying fault tree analysis (3.3): (NEQ 10D (WINNING-cARD)) follows from (LOWER 100 1<0) and the definition

<DE WINNING-CARD NIL <HIGHEST (SET-OF C (CARDS-IN-POTI (· (SUIT-OF Cl (SUIT-LEOI I II I

It is trickier to evaluate (PR-LEAD-TO (PLAY ME AD) (TAKE -':lQINTS t..£)). Expanding the definition of PR-LEAD-TO and substltutlna (CURRENT trick) for FUTURE yields

lPR lOURING (CURRENT TRICKl (TAKE-POINTS MEII (DURING PRESENT lPLAY ME ADIII

· <PR (DURING (SCENARIO (PLAY JOE KDI (PLAY ME AOI <PLAY ANN

lSOME C (LEGAL-CARDS ANNI I) (TAKE-TRICK (TRICK-WINNERI)) (TAKE-POINTS MElll Consider the sub-expression (TAKE-POINTS ME) In this expression. (TAKE-POINTS ME) occurs iff (AND (· (TRICK-WINNER) ME) (TRICK-HAS-POINTS)). (PLAY ME AD) Implies (· (TRICK-WINNER) ME) since no higher card can be played, so (TAICE-POINTS ME) reduces to (TRICK-HAS-POINTS) In the case at hand. Furthermore, since (CARDS-IN-TRICK) · (SET KD AD (CARD-OF At-.t-0), (TRICK-HAS-POINTS) reduces to (PLAY ANN (SOME C CARDS (HAS-POINTS C))). This expression Instantiates the definition lDE UNLOAD-POINTS NIL (PI

(PLAY P (SOI'E C CARDS lAND [HAS-POINTS Cl CNEQ C U.ll NNI t«<-CAROI J I I))

alnce (· (TRICK-WINNER) ME) precludes (PLAY ANN (WINNING-cARD)). Thus (TAKE -POINTS ME) reduces to (UNlOAD-POINTS ANN).

Now consider the sub-expression (SCENARIO _). Evaluatlna It requires determining (LEGAL-cARDS ANN). Since (OOT (LEADING ANN)); (LEGAL-cARDS At-.t-0 simplifies to

(SET-OF C (HAND-OF ANNI lOR (VOID ANN OIAMONOSl

[. (SUIT-OF Cl DIAMONOSlll

Since JD Is the only outstanding diamond, (· (SUIT -OF C) DIAMONDS) reduces to (· C JD) and (VOID ANN DIAMONDS) reduces to (NOT (~OS ANN JD)). Thus (LEGAL-CARDS ANN) reduces to (IF (HOLDS ANN .JO) (SET JO) (HAND-oF ANN)).

The resulting expression

(PR lOURING lSCENARIO (PLAY JOE KOI (PlAY ME AOI (PLAY ANN (IF lHOLOS ANN JD) JO (SOME C (HAND-OF At.Wl l l l lTAKE-TRICK MEl l lUNLOAO-POINTS ANNlll

cen be simplified to

(PR lOURING lPLAY ANN

ll F (HOLDS ANN .XU JO !SOME C (HAND-OF ANN I I I) !UNLOAD-POINTS ANNlll

since (UNLOAD-POINTS ANN) can only occur as part of (PLAY ANN ... ). The IF construct can be factored out of this expression, yielding liF (HOLDS ANN JOI lPR lOURING (PLAY ANN JOI (UNLOAO-POINTS ANNII lPR lOURING (PlAY ANN (SOME C lHANO-OF ANNIII (UNLOAD-POINTS ANNIIIIJ

The falsity of

lOURING (PLAY ANN JOI (UNlOAD-POINTS ANNII

follows from (· (POINTS JO) -10). We still have the problem of evaluatlna

(PR lOURING (PLAY ANN (SOME C (HAND-OF ANNIII <UNLOAD-POINTS ANNIII

This expression can be slmpUfied by worst-case analysis usina the rule

(PR (DURING (f ... (SOME x S) ... ) bad-eventlr­ (PR (EXISTS x S (DURING (f ... x ... )bad-event)))

Applylna this rule yields

(PR (EXISTS C (HAND-OF ANNI lOURING <PLAY ANN Cl (UNlOAD-POINTS ANN))))

which reduces to

lPR (EXISTS C lHAND-OF ANNI lHAS-PO I NTS C I I I

· <PR (HOLDS-POINTS ANNII

In other words, worst-case analysis assumes

(GIVEN (HOLDS-POINTS ANNI (DURING (CURRENT TRICKI

<UNLOAD-POINTS ANNIII

Combining the above simplifications, we have (PR-LEAD-TO (PLAY ME AD) (TAKE-POINTS ME)) · (IF (HOLDS ANN JD) 0 percent (PR (HOLDS-POINTS ANN))).

Of course, the rules of the game prevent the mahps from Inspecting Ann's hand in order to evaluate (HOLDS ANN JD) and (HOLDS-POINTS ANN). This Illustrates a particular type of operatlonallzation problem: evaluation of well-defined expressions based on unobservable data. There are various ways to cope with this problem. Sometimes an expression can be evaluated Indirectly by deduction from data that are observable. For Instance, if the mahps remembers that Ann has shown void In diamonds, It can infer that (HOLDS ANN JD) is false. Another way to cope with unobservable data Is to treat It probabllistlcally. This approach Is discussed In some detail in (4].

3.6. Mappln& expressions to methods

This section has described several methods which might be used to operationalize the expression (AVOID ME (TAKE-POINTS ME)). An important issue in operationallzation Is mapping expressions to methods. This mapping Involves not only finding a method appropriate to a given expression but also determlnlna the correspondence between the elements of the expression and the elements of the method: the mahps must figure out how to satisfy the informational requirements of the method given the information contained In the expression or otherwise inferrable. The examples in this section involved a variety of techniques for doing this mapping. These include goal-specific means-end rules (3.1), expanding expressions in terms of lower-level concepts (3.2), instantiation of general rules (3.3), partial-matching expressions against problem descriptions associated with known methods (3.4), viewing concepts as related concepts (3.4), and Introduction of simplifying approximations (3.5).

Intuitively, the further removed the method from the expression, the weaker tt,e method, since it exploits less specific knowledge about the expression. Thus fault tree analysis can be c><pected to produce a better {more efficient) operatlonalization of "avoid laking points" than heuristic search, since the fault tree solution operates at the level of scenarios, while the heuristic search solution operates one conceptual step lower at the level of sequences.

4. Current and Future Work

The body of previous research related to this work is too large to cite here, but is discussed elsewhere [2, 4].

The first author's dissertation (in progress) focuses on operatlonalization. We have operationalized several examples of Hearts advice by hand and are formulating general rules to account for the derivations. A working program generates such derivations interactively. At each step It determines which rules are applicable and applies the one ranked highest according to some simple criteria. In case of a lie, the user selects from among the best-ranked candidates. In addition we have defined a procedural for heuristic search and are working towards a formalization of fault tree analysis. The representation used in this paper has been Implemented, including most of the meta-functions described in Section 2.1. An Interpreter capable of executing this representation has been Implemented in LISP.

Aeknowled1ments

This work has benefited from discussions with our colleagues at the Rand Corporation and Carnegie-Mellon University. Stan Rosenscheln was especially llelpfulln clarifying many knowledge representation Issues.

Reference·

• [ 1] Hayes-Roth, F. "The Role of Partial and Best Matches In Knowledae Systems." In D. A. Waterman and F. Hayes-Roth (eds), Pattern-Directed Inference Sy1tetm. Academic Press: New York, 1978, pp. 557-574.
• Hayes-Roth, F., Klahr, P., Burge, J., and Mostow, D.l "Machine Methods for Acquiring, Learning, and Applying Knowledge: Technical Report P-6241, The Rand Corporation, Santa Monica, Calif., 1978.
• McCarthy, J., et al. LISP 1.5 Prorrommar'1 Monuol. MIT Press: Cambridge, Mass., 1963.
• Mostow, D.J., and Hayes-Roth, F. "Machine-Aided Heuristic Proarammlng: A Paradigm for Knowledge Englneerlna: Technical Report N-1007, The Rand Corporation, Santa Monica, Calif., 1979.
• [5) Newell, A. "Heuristic Programming: Ill-Structured Problems." In J. Aronofsky (ed.), Prorre11 in Operatioru Research. Wiley: New York, 1969, pp. 363-414.
• Newell, A., and Simon, H.A. Hu.mlln Problem Sowinf. Prentice-Hall: Englewood Cliffs, N. J., 1972.
• Sacerdotl, E.D. "Planning in a Hierarchy of Abstraction Spaces." Artificial IntatU,ence. 5, (1974) 115-135.