# AI: Tracking knowledge

2 views

### Phil Goetz

Nov 2, 1996, 3:00:00 AM11/2/96
to

Tonight I hacked out some elementary code about belief spaces.
It keeps track, for every action, of who the witnesses to that action
are, and what they know. This is used within the planning code,
to anticipate when forming a plan who would witness each of the actions
in the plan and what they would know. Thus I can now give a plan
specification like

plan(me,
achieve([not(lockedp(door))],[not(knows(joe,not(lockedp(door))))]),
[[],[]],PLAN,S2,[],0). % don't worry about stuff on this line

which means, "Unlock the door without Joe finding out about it."

The next step is to simulate reasoning, so that characters will derive
new knowledge from what they observe, and so that characters constructing
plans can predict what witnesses to their actions will infer from them.
The next step after that is to link the inferences to responses and
formation of counter-plans. The final step is for characters to
simulate the counter-plans of other characters and take them into
account while still forming their original plans.

What am I talking about? Well, suppose Curly has the goal
of killing Judd Fry. Curly might form a plan to walk up to Judd in the
middle of the street and shoot him. What I want to happen is for Curly
to anticipate that the witnesses will know he has killed Judd, they
will infer that murder is a crime, and they will respond to this
knowledge by forming plans to capture Curly and hang him. This would
violate Curly's plan constraint of staying alive, so he would give up
on this plan.

I plan to subsume emotions under reasoning, by having rules that basically
let characters infer what their emotions are. Emotion will be treated
not as a state of a character, but as a belief of a character.
Thus if I say a character is angry, by definition I mean he believes
he is angry.

What do people think about these efforts?
Will these capabilities make a great difference in the type of games
that can be written, or is some other aspect more important?

Would anybody give up Inform/TADS/Hugo and program in Prolog
if I provided an engine with these capabilities?

I keep hitting the escape key, but I'm still here...

### Dan Shiovitz

Nov 3, 1996, 3:00:00 AM11/3/96
to

In article <55eo4c\$3...@prometheus.acsu.buffalo.edu>,
Phil Goetz <go...@cs.buffalo.edu> wrote:
[..]

>What do people think about these efforts?
>Will these capabilities make a great difference in the type of games
>that can be written, or is some other aspect more important?
>
>Would anybody give up Inform/TADS/Hugo and program in Prolog
>if I provided an engine with these capabilities?

Umm.. no, probably not. Why? Well, a couple reasons. First, there's the
portability issue. I know this was brought up before, but I wasn't sure
what the general response was. Are there relatively small Prolog
interpreters readily available for most platforms? Beyond that, it's
mostly programming questions. Are we really ready for games that support
NPCs that can be even twice as intelligent as the ones we have now? For
most games, I think the answer is still the same as the answer to "are
we could use some limited improvements in the way NPCs believe and talk.
But when you come right down to it, it's the author that still has to
program all this stuff, even with the game engine's assistance, and I
know I'm just not good enough to make using Prolog worth my time. For
any of my current half-formed story ideas, anyway.

>Phil Go...@cs.buffalo.edu
--
dan shiovitz scy...@u.washington.edu sh...@cs.washington.edu
slightly lost author/programmer in a world of more creative or more
sensible people ... remember to speak up for freedom because no one else
will do it for you: use it or lose it ... carpe diem -- be proactive.
my web site: http://weber.u.washington.edu/~scythe/home.html some ok stuff.

### Bruce Stephens

Nov 4, 1996, 3:00:00 AM11/4/96
to

>>>>> "Phil" == Phil Goetz <go...@cs.buffalo.edu> writes:

> What do people think about these efforts?

I think that's the right way to go. Having NPCs use the real database
gives them the wrong kind of knowledge.

> Will these capabilities make a great difference in the type of games
> that can be written, or is some other aspect more important?

I think it's clear that they have the potential of changing the kind
of games that can be written, but I'm not at all sure that anybody has
enough experience to know whether or not such games can work. The Oz
project is doing this kind of thing, have they produced anything
convincing yet?

There have been games with independentish characters: The Hobbit
springs to mind, as do some of the later Level-9 games. The Hobbit's
handling of characters wasn't bad. The Level-9 games were a bit
hack-and-slash, and felt a lot like MUD games, so it was more an
atmosphere than anything.

> Would anybody give up Inform/TADS/Hugo and program in Prolog if I
> provided an engine with these capabilities?

I suspect different authors (and I'm not an author) will react in
different ways. Part of the appeal of current games is this artistic
conflict of the game telling a story, and restricting the player from
doing things that would break the story, and giving the player the
illusion of as much choice as possible. What your system seems to
offer is the ability to build a bunch of agents with individual goals
and knowledge, together presumably with a traditional environment of
rooms, objects, and the opportunity of puzzles. So how can I build a
story out of it? How can I either control things sufficiently so I
know how the plot's going to work, or (presumably better) have the
system develop sufficiently interesting plots on the fly?

Many puzzle forms look a bit dangerous. What if I need to use a bomb
in a particular place, but some NPC sets it off somewhere else, just
to see what'll happen? What happens if I need a particular key, and I
know where it should be, but some stupid NPC has picked it up and
moved it somewhere else, or even worse, has gone through the door and
locked it from the other side?

Or am I going to be writing something like an interactive soap-opera?
Nothing particularly long-term happens, but in the short term there
are interesting plots and little puzzles, all with suitable NPC
behaviour.
--
Bruce Stephens | email: B.Ste...@math.ruu.nl
Utrecht University | telephone: +31 30 2534630
Department of Mathematics | telefax: +31 30 2518394
P.O. Box 80010, 3508 TA Utrecht, The Netherlands

### Joe Mason

Nov 4, 1996, 3:00:00 AM11/4/96
to

"AI: Tracking knowledge", declared Phil Goetz from the Vogon ship:

PG>Tonight I hacked out some elementary code about belief spaces.
PG>It keeps track, for every action, of who the witnesses to that action
PG>are, and what they know. This is used within the planning code,
PG>to anticipate when forming a plan who would witness each of the
PG>actions in the plan and what they would know. Thus I can now give a
PG>plan specification like

Is someone archiving these messages? My news server's only picking up
messages intermittently, so I can only see a couple of them, and I'd
really like to get caught up with the whole thing.

Joe

joe....@tabb.com

-- The 1996 Interactive Fiction Contest is now open! --
-- From Oct. 30 to Nov. 30, vote for the best of '96 --
-- ftp://ftp.gmd.de/if-archive/games/competition96 --

ž CMPQwk 1.42 9550 žTelevision is democracy at its ugliest.

Nov 4, 1996, 3:00:00 AM11/4/96
to

Well, I probably wouldn't use it, because I don't ever have time to do any
IF programming, but it's really, really, really cool.

--
ad...@phoenix.princeton.edu | Viva HEGGA! | Save the choad! | 64,928 | Fnord
"Double integral is also the shape of lovers curled asleep":Pynchon | Linux
Thanks for letting me rearrange the chemicals in your head. | Team OS/2
You can have my PGP passphrase when you pry it from my cold, dead brain.

### Greg Ewing

Nov 6, 1996, 3:00:00 AM11/6/96
to

Phil Goetz wrote:
>
> The final step is for characters to
> simulate the counter-plans of other characters and take them into
> account while still forming their original plans.

This sounds very interesting. I'm a bit worried, however,
that this sort of reasoning process might not terminate.
Is there anything to stop a character getting into an
infinite loop while considering other characters' reactions
to his actions, his reactions to their reactions, their
reactions to his reactions to their reactions, etc...?

I'm rather uncomfortable in general with these kinds of
systems where you throw a whole bunch of facts and rules
together and let them loose to interact. It's far from
clear to me that anything useful will come out, or even
that anything will come out at all, or if it does, that
it will do so in reasonable time.

> Will these capabilities make a great difference in the type of games
> that can be written, or is some other aspect more important?

It sounds like an interesting thing to explore. I don't
think it will address all of the problems of creating a
believable autonomous NPC, but it may help with some of
them.

> Would anybody give up Inform/TADS/Hugo and program in Prolog
> if I provided an engine with these capabilities?

As has been said, that would depend partly on whether a
sufficiently portable, efficient and compact Prolog
implementation can be found to support it. I think people will
want to know that their Prolog works can be used as widely and
easily as those produced with the established IF systems
before they'll be willing to put in the large intellectual
effort of switching to Prolog.

Still, by all means make whatever you come up with in
Prolog available. I'm sure there will be some people
interested in taking a look - I will, for one.

Greg

### Carl Muckenhoupt

Nov 11, 1996, 3:00:00 AM11/11/96
to

a...@puppy.demon.co.uk (Andrew Clover) writes:

>go...@cs.buffalo.edu (Phil Goetz) wrote:

>> What am I talking about? Well, suppose Curly has the goal of killing
>> Judd Fry. Curly might form a plan to walk up to Judd in the middle of
>> the street and shoot him. What I want to happen is for Curly to
>> anticipate that the witnesses will know he has killed Judd

> Whoah! Are you sure this is all going to work? :-)

> Though the biggest problem I have with it is that even if you manage to
>make this model work, you're going to have to write text to go with it. You
>could leave this to be generated automatically by the program, but that
>would leave you with extremely flat, boring writing. On the other hand, you
>could write it yourself, but then you have to think of every situation
>possible and write the text for it, and then you've got just as much code
>as it would have taken to 'hack' the situation into a traditional IF
>programming system. (And that's about as far as I can go! Yee-hah!)

> How do you plan to resolve this?

Any sort of simulation in a game has this problem. Ideally, it would be
solved in more or less the same way it's always been solved: by providing
both default descriptions and hooks for different ones. We already have
lots of formulaic text in games - consider inventory lists, for example.
Consider canned responses like "Taken" and "You can't go that way". We
recognize these as part of the mechanics of the game, and accept them.
The author cannot anticipate our every action, and so must generalize.
The author cannot anticipate every action of a sufficiently independent
NPC, either.

In other words, we can have "flat, boring writing" or extremely mechanical
characters that only perform scripted actions. It's difficult to say which
is preferable until we actually see a game written in Prolog. I suspect
that independent characters with flat descriptions will ultimately prove
to be more interesting than highly mechanical ones, however fine the prose
used to describe their limited repertoire. After all, it isn't the prose
that got us all interested in IF.

>> Would anybody give up Inform/TADS/Hugo and program in Prolog if I
>> provided anengine with these capabilities?

> I'd not think too many people would without the same high level of backup
>that the likes of TADS and Inform have - fast interpreters and compilers
>for a large range of machines, in particular.

I would be willing to give it a try. Note, however, that I do not have a
spectacular tack record of finishing the games that I start to write.

My only doubt about the whole scheme is that it makes the machine responsible
for behavior that is quite complex and therefore quite bug-prone. With
today's adventure systems, authors recognize the limitations of their
characters and tend to put them in highly-controlled situations where
inappropriate behavior is a near impossibility. The more freedom we allow
the characters to respond changes in their environment, the more code needs
to be written to allow them to recognize changes in their environment. The
smarter they are, the smarter we'll expect them to be.

This is no reason not to try, of course. I just expect the first attempts to
be quite rough.

--
b...@tiac.net | Read rec.[arts|games].int-fiction to see
http://www.tiac.net/users/baf | what you're missing!

### Phil Goetz

Nov 11, 1996, 3:00:00 AM11/11/96
to

In article <n2B2...@puppy.demon.co.uk>,

Andrew Clover <a...@puppy.demon.co.uk> wrote:
>go...@cs.buffalo.edu (Phil Goetz) wrote:
>
>> What am I talking about? Well, suppose Curly has the goal of killing
>> Judd Fry. Curly might form a plan to walk up to Judd in the middle of
>> the street and shoot him. What I want to happen is for Curly to
>> anticipate that the witnesses will know he has killed Judd
>
> Whoah! Are you sure this is all going to work? :-)

It works already. I'm not saying it's bug-free, mind you. ;)

> Though the biggest problem I have with it is that even if you manage to
>make this model work, you're going to have to write text to go with it. You
>could leave this to be generated automatically by the program, but that
>would leave you with extremely flat, boring writing.

What I described in that post was just planning.
I don't think you have to write text unless you also implement

>ask curly, "why are you behind a barrel?"
Curly says, "I don't want the Sheriff to see me here."

Then it's a problem. Imagine the computer-generated text:

Curly says, "Standing behind a barrel protects my goal of not being dead."

Right, Curly.

>> Would anybody give up Inform/TADS/Hugo and program in Prolog if I

>> provided an engine with these capabilities?

>
> I'd not think too many people would without the same high level of backup
>that the likes of TADS and Inform have - fast interpreters and compilers
>for a large range of machines, in particular.

<sigh>

Phil
just a coder who can't say "no"

### Andrew Clover

Nov 11, 1996, 3:00:00 AM11/11/96
to

go...@cs.buffalo.edu (Phil Goetz) wrote:

> What am I talking about? Well, suppose Curly has the goal of killing
> Judd Fry. Curly might form a plan to walk up to Judd in the middle of
> the street and shoot him. What I want to happen is for Curly to
> anticipate that the witnesses will know he has killed Judd

Whoah! Are you sure this is all going to work? :-)

Though the biggest problem I have with it is that even if you manage to

make this model work, you're going to have to write text to go with it. You
could leave this to be generated automatically by the program, but that

would leave you with extremely flat, boring writing. On the other hand, you
could write it yourself, but then you have to think of every situation
possible and write the text for it, and then you've got just as much code
as it would have taken to 'hack' the situation into a traditional IF
programming system. (And that's about as far as I can go! Yee-hah!)

How do you plan to resolve this?

> Would anybody give up Inform/TADS/Hugo and program in Prolog if I

> provided an engine with these capabilities?

I'd not think too many people would without the same high level of backup
that the likes of TADS and Inform have - fast interpreters and compilers
for a large range of machines, in particular.

BCNU, AjC

### Phil Goetz

Nov 12, 1996, 3:00:00 AM11/12/96
to

In article <baf.84...@max.tiac.net>,

Carl Muckenhoupt <b...@max.tiac.net> wrote:
>Any sort of simulation in a game has this problem. Ideally, it would be
>solved in more or less the same way it's always been solved: by providing
>both default descriptions and hooks for different ones. We already have
>lots of formulaic text in games - consider inventory lists, for example.
>Consider canned responses like "Taken" and "You can't go that way". We
>recognize these as part of the mechanics of the game, and accept them.
>The author cannot anticipate our every action, and so must generalize.
>The author cannot anticipate every action of a sufficiently independent
>NPC, either.

Oh, Andrew meant how to describe the actions the character is taking.
Basically by running an English parser backwards.
You have to come up with a description for every basic action,
Simple example:

msg(eat(Actor,Obj), _, MSG, ".") :-
objname(Actor, AN), objname(Obj, ON),
person(Actor, N), form("eat", N, EAT),
bigappend([AN, " ", EAT, " ", ON], MSG).

produces messages like

You eat the poisoned apple.
or
Jim eats the sundae.

A more complex example is the following rule:

msg(put(Actor,Obj,in,Actor), _, MSG, ".") :-
objname(Actor,AN), person(Actor, N), form("get", N, GET),
in(Obj,L), objname(Obj,ON), objname(L, LN),
bigappend([AN, " ", GET, " ", ON, " from ", LN], MSG).

which produces sentences like

Jim gets a small paper clip from the desk.

Your grammar can put these simple phrases together.
For example, the message

You can't move north while you are in the garage.

is generated from the following information:

Failed plan: achieve([map(Loc, north, _)], [in(me,Loc)])
In context: move(me, north)
Database contains the statement in(me,garage)

This says that the planner was unable to find a situation in which you
can move north, with the restriction that you ("me") must be in the
garage when you find this situation. The "backwards parser" uses the rule

msg(achieve([A],[PROT]), Context, MSG, P) :-
msg(achieve([A],[]), Context, M1, P1),
append(M1, " while ", M2),
msg(PROT, Context, M3, P2),
dominant_punct(P1,P2,P),
append(M2, M3, MSG).

to say that the output message should be of the form

MSG1 while MSG2

It uses the rule

msg(in(Actor,Loc), _, MSG, ".") :-
person(Actor, N), form("are", N, ARE), % N=1: am, N=2:are, N=3:is
objname(Actor, AN),
objname(L, LN), bigappend([AN, " ", ARE, " in ", LN], MSG).

to construct the subphrase "you are in the garage".

It uses the rule

msg(not(achieve([map(_,Dir,_)],[])), _, MSG, ".") :-
atom_chars(Dir, DN),
append("you can't move ", DN, MSG).

to construct the phrase "you can't move north".
It puts the parts together into

you can't move north while you are in the garage

capitalizes it, and adds a period.

Apologies for how ugly my "grammar" is right now.
In the future I want to put it into a format like

sentence([Actor,Verb,Object, Person, Tense]) -->
actor(Actor, Person, subject), verb_phrase(Verb, Object, Person, Tense).
verb_phrase(Verb, Object, Person, Tense) -->
verb(Verb, Person, Tense), noun_phrase(Object).
verb(eat, 1, present) --> [eat].
verb(eat, 2, present) --> [eat].
verb(eat, 3, present) --> [eats].
actor(me, 2, subject) --> [you].

Phil