Why you must use Prolog
Phil Goetz
TADS, Hugo, Inform, ALAN, Advsys, AGT --
You're all wrong. :)
My adventure language of choice, at the moment, is Prolog. Partly because
it's easy to write an adventure in Prolog. Mostly because it's *necessary*
to write huge parts of the game in a logical notation anyway so that
non-player characters can reason about the gameworld and form plans.
I've implemented an adventure engine in Prolog, and I spent last week
adding a planning system to it. Now I can give my NPCs goals like
"Get the babel fish" or "Kill Fred", and they can construct plans to
accomplish them.
There are basically three ways to construct a plan. One is to backchain
on the effects of actions. Another is to take plan hints that the
programmer writes ahead of time -- "Y is a plan to do X." The third,
and perhaps the most powerful, is to analyze the program's code that
specifies how the gameworld works, to find out how to achieve your goal.
You can do the first two in any language. To do the third, you have two
choices: Either
1. Write a runtime interpreter for your language, so that a running program
can disassemble and run pieces of itself, or
2. For every piece of Inform/TADS/Hugo code in your program, write the same
thing again in a logical notation for use by your planner, making sure that
the program code and the logic code give the same results under all
circumstances, or
2. Use a logical programming language such as Prolog.
In other words: If you are using TADS, Hugo, Inform, etc., you can never
match the power of what I can do in Prolog unless you basically rewrite
most of your program in something very like Prolog.
The following example should explain what I mean.
Say I give Jim the goal of giving Fred the whistle.
I do this by giving him the goal achieve([has(fred,whistle)],[]).
This reads as "achieve all the formulae in [has(fred,whistle)]
while not violating any of the formulae in []".
Each action has a set of preconditions, a set of facts no longer true after
performing the action, and a set of facts newly true after performing the
action. (This is the STRIPS formalism of Fikes and Nillson from 1971).
The entry for give might look like this:
action(give(Actor, Recipient, Obj),
[has(Actor,Obj), canreach(Actor, Recipient)], % preconditions
[has(Actor,Obj)], % delete list
[has(Recipient,Obj)]). % add list
The planner searches for any action which has has(fred,whistle) in its
add list. It finds that the action give(jim,fred,whistle) does, if we make
Actor = jim, Recipient = fred, and Obj = whistle.
The preconditions are then
[has(jim,whistle), canreach(jim,fred)]
the delete list is
[has(jim,whistle)]
and the add list is
[has(fred,whistle)]
The planner then tries to form a plan to achieve all the preconditions of
give(jim,fred,whistle), and then execute the act. The code says:
P3 is a plan for
achieve([has(fred,whistle)],[])
starting in situation S_In and ending in situation S_Out, if P1 is a plan for
achieve([has(jim,whistle), canreach(jim,fred)],[])
starting from situation S_In and ending in situation S2, and P2 is a plan for
do(give(jim,fred,whistle))]
starting from situation S2 and ending in situation S_Out,
and P3 = P1 followed by P2.
The planner then says that P1 is a plan for
achieve([has(jim,whistle), canreach(jim,fred)],[])
starting in situation S_In and ending in situation S2 -- which I will now
denote as
plan(achieve([has(jim,whistle), canreach(jim,fred)],[]), S_In, P1, S2)
if
plan(achieve([has(jim,whistle)],[]), S_In, P4, S4)
and
plan(achieve([canreach(jim,fred)],[has(jim,whistle)]), S4, P5, S2)
and P1 = P4 followed by P5.
(The last plan statement means, P5 is a plan for achieveing
canreach(jim,fred) while keeping has(jim,whistle) true, starting from S4
and ending in S2.)
The planner finds that has(jim,whistle) is already true. It then tries to
achieve canreach(jim,fred). It has two ways of doing this:
1. Find an action which has canreach(jim,fred) as a result.
(This is standard STRIPS planning, and can be done in any language.)
2. Find the definition in the program of "canreach", and construct a plan
to achieve a situation in which canreach(jim,fred) is true.
This second method is essential. It is very unlikely that any of
your actions will have canreach(jim,fred) as a result. canreach is
a complex predicate that specifies all the situations in which Jim can
reach Fred.
Here's why we can only do this in Prolog and not in TADS, Inform, Hugo,
or any of the other procedural languages: The planner needs to find out
how to make it true that Jim can reach Fred. The program code will say
something like, Jim can reach Fred if Jim is in the same room as Fred.
Prolog, unlike those other languages, is a logic programming language
(Prolog stands for "programming in logic").
So every precondition is written as a logical assertion about objects --
canreach(jim, fred) is true if there is some L such that in(jim,L) is
true and in(fred,L) is true. In other words, the preconditions have
preconditions, and so on, ad infinitum. The planner just pulls out
the precondition canreach(jim,fred) from its plan-under-construction
and plugs in the preconditions in(jim,L) and in(fred,L), then continues
on its merry way.
This is a simple example, and could be hacked around in a procedural
language, but if you work out some more complicated examples I think
you will come to agree with me that the only practical way to have an
effective planning system is to use a logical programming language.
If people are interested, I'll write a post explaining how the
planning system works in theory and in practice.
Phil Go...@cs.buffalo.edu
Katy Mulvey
go...@cs.buffalo.edu (Phil Goetz) wrote:
> TADS, Hugo, Inform, ALAN, Advsys, AGT --
>
> You're all wrong. :)
>
> My adventure language of choice, at the moment, is Prolog. Partly because
> it's easy to write an adventure in Prolog.
>
> If people are interested, I'll write a post explaining how the
> planning system works in theory and in practice.
>
> Phil Go...@cs.buffalo.edu
I'd be more interested in knowing where I can get a free prolog compiler/
interpreter that will work on a large variety of computers. (Windows PC,
Linux, Macintosh, other unix variants, Amiga, Acorn, etc...)
If I'm going to write an adventure game, I'm more interested in showing
off my story to the widest possible audience, and I'll be willing to
put some blood, sweat and tears into using one of the freely available
systems like TADS or Inform, even if it makes the programming difficult.
A game is no good if nobody sees it.
Katy
--
Rich or Katy Mulvey
mul...@frontiernet.net
Phil Goetz
In article <54gbrh$e...@cheatum.frontiernet.net>,
Katy Mulvey <mul...@frontiernet.net> wrote:
>go...@cs.buffalo.edu (Phil Goetz) wrote:
>> TADS, Hugo, Inform, ALAN, Advsys, AGT --
>>
>> You're all wrong. :)
>>
>> My adventure language of choice, at the moment, is Prolog. Partly because
>> it's easy to write an adventure in Prolog.
>
>interpreter that will work on a large variety of computers. (Windows PC,
>Linux, Macintosh, other unix variants, Amiga, Acorn, etc...)
>
>If I'm going to write an adventure game, I'm more interested in showing
>off my story to the widest possible audience, and I'll be willing to
>put some blood, sweat and tears into using one of the freely available
>systems like TADS or Inform, even if it makes the programming difficult.
>
>A game is no good if nobody sees it.
>
> Katy
Yep, you're right. Fortunately there are a lot of public-domain Prolog
implementations. There's a list of them at
<a href="http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/
prolog/impl/prolog/0.html">Public domain Prolog</a>
It is a problem that no one version runs under Unix, MS-DOS, and the Mac OS.
It might take a little extra work to provide an engine that worked across
all those systems, on different versions of Prolog.
It might be hard to get files in an executable format, too.
I haven't looked into that.
But I think Prolog, or something like that, is the way to go.
This is the same thing I was saying three years ago.
I didn't convince anyone then -- my arguments seem to have sunk into
oblivion -- perhaps because I was working with SNePS, a very interesting
logical language that unfortunately wasn't practical for implementing
IF in. Now, though, I've got code that runs.
Phil
Andrew Plotkin
Phil Goetz (go...@cs.buffalo.edu) wrote:
> There are basically three ways to construct a plan. One is to backchain
> on the effects of actions. Another is to take plan hints that the
> programmer writes ahead of time -- "Y is a plan to do X." The third,
> and perhaps the most powerful, is to analyze the program's code that
> specifies how the gameworld works, to find out how to achieve your goal.
> You can do the first two in any language. To do the third, you have two
> choices: Either
> 1. Write a runtime interpreter for your language, so that a running program
> can disassemble and run pieces of itself, or
My (Inform) competition entry was designed with precisely this in mind. I
didn't use it that way, of course, but when I programmed the engine I was
thinking "Hey, dynamic programming system for the Z-machine."
Feel free to steal the idea and write a Prolog system in Inform. I don't
expect it would be too hard.
--Z
--
"And Aholibamah bare Jeush, and Jaalam, and Korah: these were the
borogoves..."
John Hartnup
: >
: > You're all wrong. :)
: If I'm going to write an adventure game, I'm more interested in showing
: off my story to the widest possible audience, and I'll be willing to
: put some blood, sweat and tears into using one of the freely available
: systems like TADS or Inform, even if it makes the programming difficult.
: A game is no good if nobody sees it.
Ah, but if Phil was in the mood to write a Prolog-like language which
compiled to Z-Code (because Inform isn't the only way to produce Z-code,
obviously)... then he may start something revolutionary :)
One of the competition entries proves you could do it in principle.
I won't go any further lest someone bite my head off about discussing
entries...
John
--
-----------------------------------------------------------
John Hartnup | You can drink your weak lemon drink
sl...@ladle.demon.co.uk| now, or you can save it 'til later.
-----------------------------------------------------------
Katy Mulvey
mul...@frontiernet.net (Katy Mulvey) wrote:
> I'd be more interested in knowing where I can get a free prolog compiler/
> interpreter that will work on a large variety of computers. (Windows PC,
> Linux, Macintosh, other unix variants, Amiga, Acorn, etc...)
Rather than wait, I found the following web site, which lists free
Prolog compilers:
http://www.cis.ohio-state.edu/hypertext/faq/usenet/prolog/resource-guide/part2/faq-doc-2.html
So now I have another question for Phil Goetz - do you know of
any predicate libraries specialized for use in writing adventure
games?
Carl Muckenhoupt
Now this is an interesting line of thought. Anything that can make
it easier to code NPC's with believable behavior is a Good Thing.
Unfortunately, I know very little about Prolog other than its
ideology. How feasable would it be to write a Prolog-to-Z-code
compiler? I suggest it as a way do give any Prolog games you may
write a widely-portable standard compiled format. (Mind you, this
would be a different project from writing a Prolog interpreter in
Inform, as someone has suggested.
Also, if one were to write such a version of Prolog specifically for
use as an adventure system, would it be preferable to modify the
language? I am thinking of the special syntaces adopted by C++
based languages like Inform and TADS to make adventure code shorter
and more readable.
--
Carl Muckenhoupt | Text Adventures are not dead!
b...@tiac.net | Read rec.[arts|games].int-fiction to see
http://www.tiac.net/users/baf | what you're missing!
Phil Goetz
In article <baf.84...@max.tiac.net>,
Carl Muckenhoupt <b...@max.tiac.net> wrote:
>
>Now this is an interesting line of thought. Anything that can make
>it easier to code NPC's with believable behavior is a Good Thing.
>Unfortunately, I know very little about Prolog other than its
>ideology. How feasable would it be to write a Prolog-to-Z-code
>compiler? I suggest it as a way do give any Prolog games you may
>write a widely-portable standard compiled format. (Mind you, this
>would be a different project from writing a Prolog interpreter in
>Inform, as someone has suggested.
I don't know enough about Z-code to say.
One problem is that, in order to work backwards through the program
like I want my NPCs to do to construct plans, the code has to be
interpreted, not compiled.
I'm worried about efficiency, too. I've got a very small sample world,
and I'm running on a Sparc 10, and sometimes responses take a few seconds.
This will probably end up being something you need Pentium
(or "Hexium"!) speeds to enjoy.
>Also, if one were to write such a version of Prolog specifically for
>use as an adventure system, would it be preferable to modify the
>language? I am thinking of the special syntaces adopted by C++
>based languages like Inform and TADS to make adventure code shorter
>and more readable.
Probably.
It would be nice to have a cleaner way of handling inheritance, I think.
But Prolog is one of those "self-modifying" languages, like LISP.
Most of the time you write new predicates to extend the language.
Phil
Phil Goetz
In article <54gsio$a...@cheatum.frontiernet.net>,
Only my own. I'm having my Prolog class write an adventure as their
term project, though, so I don't want to post the whole thing until
December. I'm still assigning them parts of it to write,
and they are net-wise.
I have a web page for the class that always contains the most updated
version that I've made publicly readable:
http://www.cs.buffalo.edu/~goetz/prolog.html
(look for the links called "The adventure so far")
The assignment links from that page explain how the code works,
so they would be useful to look at if you decide you want to use it.
These don't have the planning code, or a lot of other niceties, because
I'm not assigning those to the class. Also, the class hasn't covered
parsing, save and restore, undo, or informational messages yet,
so the stuff you'll find there isn't ready to turn into a game.
There are some other things I don't like about that code, but it's a start.
If I ever write a book about this, I have a title already --
"Adventures in Prolog". :)
Phil
Andrew Plotkin
Carl Muckenhoupt (b...@max.tiac.net) wrote:
> Now this is an interesting line of thought. Anything that can make
> it easier to code NPC's with believable behavior is a Good Thing.
> Unfortunately, I know very little about Prolog other than its
> ideology. How feasable would it be to write a Prolog-to-Z-code
> compiler? I suggest it as a way do give any Prolog games you may
> write a widely-portable standard compiled format. (Mind you, this
> would be a different project from writing a Prolog interpreter in
> Inform, as someone has suggested.
The last time I used Prolog was, uh, 1990? But I think you're actually
incorrect; Prolog is a dynamic language (meaning that functions are built
and mangled as the program executes, not just at compile time. Rather
like, well, Lisp, to pick a common example.) You pretty much can't
translate a dynamic language program into source code for a procedural
language like Inform (or C.) I mean, you can compile parts of the program
as an optimization, but there will always be the interpreter core sitting
down at the bottom.
In fact, when I took that wacky computer language course back in
199-early, my conclusion was "Prolog is not a language; it's a unusually
funky database. You don't write programs, you create sets of data for the
database engine to process." Which tells you how much I enjoyed that part
of the course -- heh -- but the point is, there's no distinction between
a Prolog-to-Inform converter and a Prolog interpreter written in Inform.
Efficiency is another issue (which Phil Goetz raises in another post.)
Any interpreter running on the Z-machine is going to be miserably slower
than an interpreter written in native code. If the bottleneck is
computation, anyway.
John Hartnup
Andrew Plotkin (erky...@netcom.com) wrote:
: Efficiency is another issue (which Phil Goetz raises in another post.)
: Any interpreter running on the Z-machine is going to be miserably slower
: than an interpreter written in native code. If the bottleneck is
: computation, anyway.
Surely this is an issue with any program running under the Z-Machine? It's
just that most Inform programs aren't all that computationally intensive
at the moment.
Presumably if someone wrote some code for goal-driven NPCs, then whether
it was written in a prolog way or in some other way, it would take a
lot of CPU cycles.
Another thing to bear in mind: when would NPCs be allowed to "think",
"plan" etc... do these goal-analysis computations occur in normal
game computation time (i.e. between when you press "enter" and when
the game's response appears), or should they occur in the background,
calculating while the prompt is waiting for input?
If the player acts quickly (in real time or in turns?), does this
mean the goal-seeking system gets less time? Is there a way we can
force the NPC to act on an incomplete search?
I gather commercial games, particularly sports games and bead-em-ups,
employ some pretty serious AI to control NPCS (Electronic Arts publish
white papers on Genetic Programming). Presumably IF could employ GP,
neural nets... all sorts of alternatives to the rather mechanical
Prolog.
*I* don't fancy implementing them, mind you...
Fredrik Ekman
John Hartnup <sl...@ladle.demon.co.uk> writes:
> Another thing to bear in mind: when would NPCs be allowed to "think",
> "plan" etc... do these goal-analysis computations occur in normal
> game computation time (i.e. between when you press "enter" and when
> the game's response appears), or should they occur in the background,
> calculating while the prompt is waiting for input?
I don't think this is theoretically possible, unfortunately. For the
Prolog logic to work, it must have the complete game world clear in
memory.
This prompts another idea which has been laying in the back of my head
for quite a while. (I have played with deveoping Prolog IF, too.)
Perhaps the NPCs should not plan according to how the game world
actually looks, but rather to how they _perceive_ the world. This would
require the implementation of an entire sub-world of beliefs for each
NPC and would consequently require even more computational power, but I
think it would give much more believable reactions.
/F
Tom Emerson
In article <dwd8yb1...@tintin.lysator.liu.se>, Fredrik Ekman
<ek...@lysator.liu.se> wrote:
>I don't think this is theoretically possible, unfortunately. For the
>Prolog logic to work, it must have the complete game world clear in
>memory.
Well, it is theoretically possible that the complete game world would be
available to the planning engine: one could argue that it is required.
Whether this is practical is another matter.
For the NPCs to plan realistically, "they" must have knowledge of the
physics of the world which can result in a pretty large knowledge base in
and of itself. It would not make sense if an NPC stuck down in a cave for
the last n+1 years (think Golumn) would necessarily know about events
happening recently in another part of the world. Such global knowledge
would be unfair to the player.
>Perhaps the NPCs should not plan according to how the game world
>actually looks, but rather to how they _perceive_ the world. This would
>require the implementation of an entire sub-world of beliefs for each
>NPC and would consequently require even more computational power, but I
>think it would give much more believable reactions.
Exactly so. The Oz Project at Carnegie Mellon has been investigating this.
A good overview paper can be found at
<http://www.cs.cmu.edu/afs/cs.cmu.edu/project/oz/web/papers/loeffler.ps>
The Oz Project's home page is at
<http://www.cs.cmu.edu/afs/cs.cmu.edu/project/oz/web/oz.html>
I believe most of their work has been done in Lisp.
While Prolog may lend itself well to implementing a STRIPS-type planner
(predicates, back-tracking, and unification all for free) there is nothing
that says you can't implement the same thing in Lisp or Inform. The
Z-Machine is certainly capable of handling this type of problem providing
the language can represent the assertions.
Just my US$0.02 worth.
-tre
--
Tom Emerson Cambridge R&D
Senior Software Engineer Apple Computer, Inc.
<mailto:tr...@apple.com> <http://www.tiac.net/users/tree>
Brad O`Donnell
Phil Goetz wrote:
>
> TADS, Hugo, Inform, ALAN, Advsys, AGT --
>
> You're all wrong. :)
>
> My adventure language of choice, at the moment, is Prolog. Partly because
> it's easy to write an adventure in Prolog. Mostly because it's *necessary*
> to write huge parts of the game in a logical notation anyway so that
> non-player characters can reason about the gameworld and form plans.
>
If we want a real dynamic game-world, with active little mini-
AIs growing and thriving about (and I think we all would) What would
be really nice would be a _really_ dynamic language, something where
just about every part of every object, property, and function is
(possibly) manipulable. Put on top of that a library easily
modifiable functions geared at simulating and presenting the game
environment, and voila! Perfect game environment. Perhaps something
Prolog-like _is_ this language...
If not, well, I guess I better get cracking; see you in a few
years :)
--
Brad O'Donnell
Phil Goetz
Wow! I got responses! This is fun.
In article <DzoC...@ladle.demon.co.uk>,
John Hartnup <sl...@ladle.demon.co.uk> wrote:
>Another thing to bear in mind: when would NPCs be allowed to "think",
>"plan" etc... do these goal-analysis computations occur in normal
>game computation time (i.e. between when you press "enter" and when
>the game's response appears), or should they occur in the background,
>calculating while the prompt is waiting for input?
This is an excellent idea. It would be impossible to implement without
using operating-system-specific calls, I think. Prolog doesn't have
(at least not that I've seen) any way to check the keyboard for input,
and then return if nothing has been typed. Once you ask to read
the keyboard, you have to wait until someone types something.
How does Inform handle this? It must, because I saw Tetris in Inform.
Does it use machine-specific opsys calls?
RANT ON
This really annoys me -- I have never seen a programming language that
had a primitive for checking for keyboard input but not waiting for it.
This is an important operation, but language designers never put it in,
so it makes all realtime code un-portable because it has to use OS calls
to read the keyboard. X-Windows can do it, and I think curses (the C
library, not the game) can, but they don't count.
RANT OFF
>If the player acts quickly (in real time or in turns?), does this
>mean the goal-seeking system gets less time? Is there a way we can
>force the NPC to act on an incomplete search?
I wish. Not the way I've written it. Initially I wrote the planner
so it would construct incomplete plans, and expand them during plan
execution. But I had problems with replanning, then: When the plan
didn't work out, it would replan, and usually come up with the same
non-workable plan. I kept the planner so you can still provide an
NPC with a plan instead of a goal, and if your plan has steps like
"try to open the hatch", it will expand that step when it comes to it.
That gives you more control -- you can put in plans like
"wait 120 timesteps, then blow up the factory" that can't be derived.
But replanning won't always work correctly if you do that.
There was a revolution in planning systems in the 1980's that moved
away from designs like the one I implemented in Prolog, towards
reactive systems and "anytime" systems which work better in realtime.
But they don't, currently, handle complicated domains like an IF game
as well as the old ways (IMHO). They work great if you're designing
insects, but not NPCs.
>I gather commercial games, particularly sports games and bead-em-ups,
>employ some pretty serious AI to control NPCS (Electronic Arts publish
>white papers on Genetic Programming). Presumably IF could employ GP,
>neural nets... all sorts of alternatives to the rather mechanical
>Prolog.
GP is a learning technique only. One could use it to optimize planning,
say by re-ordering the rules in the database. One could use it to produce
plans for canned situations. But you would have to use
something else to do real-time, on-line planning.
Neural nets -- IMHO, they are mostly useful when you have some fuzziness
in your domain. They'd be great for games like football or military
operations. They can deal with uncertainty, nondeterminism, and
real-valued inputs, but they are slow and usually non-generative.
By non-generative I mean that a neural network takes an input of a
specific format and size, and gives an output of a specific format
and size. They're notably bad at, say, parsing and producing English
sentences, or planning, because parsers and planners have recursive,
syntactic rules. I have never seen a neural network that could handle
recursion. Feedback, but not recursion.
>John Hartnup | You can drink your weak lemon drink
>sl...@ladle.demon.co.uk| now, or you can save it 'til later.
Phil Go...@cs.buffalo.edu
Phil Goetz
>
>> Another thing to bear in mind: when would NPCs be allowed to "think",
>> "plan" etc... do these goal-analysis computations occur in normal
>> game computation time (i.e. between when you press "enter" and when
>> the game's response appears), or should they occur in the background,
>> calculating while the prompt is waiting for input?
>
>Prolog logic to work, it must have the complete game world clear in
>memory.
The world would be clear in memory. It would carry out your command,
then do planning while it waits for your next input.
>This prompts another idea which has been laying in the back of my head
>for quite a while. (I have played with deveoping Prolog IF, too.)
>Perhaps the NPCs should not plan according to how the game world
>actually looks, but rather to how they _perceive_ the world. This would
>require the implementation of an entire sub-world of beliefs for each
>NPC and would consequently require even more computational power, but I
>think it would give much more believable reactions.
Good point. It's pretty important. You don't want characters to
know everything, because then you could just type
>fred, rescue princess
at the game's first prompt.
Also, you want to have the characters do things differently depending
on who is present, as in Witness. The gangster shouldn't gun down
his competitor inside the courtroom.
Furthermore, you eventually want an NPC to be able to simulate another
NPC's reasoning processes, and say things like "Jim would flunk me from
the class if he knew I were cheating on the exam, but he won't know
because..."
There are some thoughts on this in my 1993 paper
"Notes on Using SNePS for Interactive Fiction", available via
http://www.cs.buffalo.edu/~goetz/if.html
My code hacks around this right now by saying that
characters know everything that is true, but eventually I want it to
keep track of what each individual character knows and sees.
This means, among other things, that whenever a character acts, you
have to check and see what all the other characters saw, and update
their knowledge bases.
You could get more sophisticated and think about blind characters,
deaf characters, schizophrenic characters.
Phil Go...@cs.buffalo.edu
Phil Goetz
In article <tree-ya02318000...@news.apple.com>,
Tom Emerson <tr...@apple.com> wrote:
>
>While Prolog may lend itself well to implementing a STRIPS-type planner
>(predicates, back-tracking, and unification all for free) there is nothing
>that says you can't implement the same thing in Lisp or Inform. The
>Z-Machine is certainly capable of handling this type of problem providing
>the language can represent the assertions.
Yes, there is. That's what my first post was about.
Basically, you can't run Inform or LISP programs backwards.
You can do STRIPS planning in LISP, but you can't treat your program
code as data and use that for planning, too. You can't read your
program code and compute an input that will give the desired output.
People have done so, but only by writing what amounted to
mini-Prolog interpreters in whatever language they were using.
It is theoretically possible to take a piece of, say, C code,
take the output you want from it, and come up with the set of all
inputs that will give that output. Humans do it. But I don't
think anybody knows how to write a computer program to do that.
Actually, you could run a pure LISP program backwards, as long as
you don't use loops or variable assignments. I once wrote a letter to
Lucid asking for a reversible LISP debugger. But I've never seen anyone
do this, and pure LISP is painful to program in.
>Tom Emerson Cambridge R&D
>Senior Software Engineer Apple Computer, Inc.
><mailto:tr...@apple.com> <http://www.tiac.net/users/tree>
Phil Goetz
Andrew Plotkin
Phil Goetz (go...@cs.buffalo.edu) wrote:
> In article <DzoC...@ladle.demon.co.uk>,
> John Hartnup <sl...@ladle.demon.co.uk> wrote:
> >"plan" etc... do these goal-analysis computations occur in normal
> >game computation time (i.e. between when you press "enter" and when
> >the game's response appears), or should they occur in the background,
> >calculating while the prompt is waiting for input?
> This is an excellent idea. It would be impossible to implement without
> using operating-system-specific calls, I think. Prolog doesn't have
> (at least not that I've seen) any way to check the keyboard for input,
> and then return if nothing has been typed. Once you ask to read
> the keyboard, you have to wait until someone types something.
> How does Inform handle this? It must, because I saw Tetris in Inform.
> Does it use machine-specific opsys calls?
No, it's portable. There's a variant of the "input" opcode which
basically says "input a line, but while you wait, call routine X every Y
milliseconds." (X can return a value which aborts the input process, too.)
> RANT ON
> This really annoys me -- I have never seen a programming language that
> had a primitive for checking for keyboard input but not waiting for it.
> This is an important operation, but language designers never put it in,
> so it makes all realtime code un-portable because it has to use OS calls
> to read the keyboard. X-Windows can do it, and I think curses (the C
> library, not the game) can, but they don't count.
> RANT OFF
Well, if you're going to check for key events, you might as well have a
general model for events, and that's better handled as a library than as
a language primitive. If you want it to be portable, make it a standard
library. That's exactly what X windows is, and why doesn't it count?
(Sometimes you get a general model for blocking and non-blocking streams,
instead of a interface event system. But it's still better handled as a
library.)
Tom Emerson
In article <54j7n2$1...@prometheus.acsu.buffalo.edu>, go...@cs.buffalo.edu
(Phil Goetz) wrote:
>Yes, there is. That's what my first post was about.
>Basically, you can't run Inform or LISP programs backwards.
>You can do STRIPS planning in LISP, but you can't treat your program
>code as data and use that for planning, too. You can't read your
>program code and compute an input that will give the desired output.
[...]
Your assumption is that the planning system uses the source to the game as
the knowledge base, and my personal viewpoint is that this is an overly
complex representation for the limited domain of NPC interactions. It isn't
necessary for an NPC to know about every action available to the player
(say in the Inform library). It is also possible to attach code to planning
tasks which would allow the NPCs to act out on their plans once
constructed.
Again, my point is that Strips doesn't force you to use Prolog, or to
implement a miniature Prolog in order to plan.
In any event, I'm not convinced that Strips would be the best algorithm for
IF... it is certainly interesting to ponder though.
-tre
--
Martin Frost
In article <baf.84...@max.tiac.net>, b...@max.tiac.net (Carl Muckenhoupt) writes:
>How feasable would it be to write a Prolog-to-Z-code
>compiler?
Well, since Prolog is at heart an interpreted language (yes I know you *can*
get compilers for it, but anything that allows you to modify the program
structure by both asserting and retracting statements is easiest to implement
as an interpreted system), you could write a Prolog interpreter in Z-code,
and proceed to run Prolog code on a Z-machine. It need not be huge (although
it could well make a dent in the 64k dynamic area), but it would be rather
slow. OTOH, if someone writes one, I'll give it a try.
I think, though, that the main advantage of doing this would not to be to
write whole games in it, but rather to just write those bits that Prolog does
well, such as 'intelligent' NPCs who can construct plans, and to use Inform
(or any possible other Z-code compilers which may appear) to write the
majority of the code.
When you have done this, there isn't quite as much point in keeping it pure
Prolog, and you may as well take just a subset of the language, or indeed a
totally new language (although that is probably not such a wise step). I
might one day do some work on ideas of this sort (a similar concept has been
going round inside my head for some time now), but for the moment I have many
other projects higher on my priority queue, such as finishing my Amiga
Z-interpreter (the one I first let on I was writing some time last year)
and doing some university work on the odd day off.
Martin
David Baggett
In article <erkyrathD...@netcom.com>,
Andrew Plotkin <erky...@netcom.com> wrote:
>Prolog is a dynamic language (meaning that functions are built and mangled
>as the program executes, not just at compile time. Rather like, well, Lisp,
>to pick a common example.)
[Since we're stumping for our favorite langauges...]
And what an apropos example Lisp is! In his book _On Lisp_, Paul Graham
essentially shows how to implement Prolog in Lisp. It's simplified for
purposes of explanation, of course, but I'm sure someone's got a fully
worked out implementation.
The great thing about Lisp is that you can make it be whatever language you
want. I think this is what makes it prefect for specialized problem
domains like IF, where you want the full power of a general-purpose
language, but want the syntax and semantics peculiarly customized.
A Lisp-based IF system could offer the data management facilities of a
procedural language like TADS or Inform, along with NPC planning like
Prolog provides. And perhaps something else totally different that you
dream up as well...
The hard part, of course, is gluing everything together in a a syntacticaly
and semantically pleasing way. But at least you have the option of trying!
[--End of Radio Free Lisp transmission--]
Dave Baggett
__
d...@ai.mit.edu
"Mr. Price: Please don't try to make things nice! The wrong notes are *right*."
--- Charles Ives (note to copyist on the autograph score of The Fourth of July)
John Hartnup
Phil Goetz (go...@cs.buffalo.edu) wrote:
: GP is a learning technique only.
...and...
: Neural nets -- IMHO, they are mostly useful when you have some fuzziness
: in your domain. They'd be great for games like football or military
: operations. They can deal with uncertainty, nondeterminism, and
: real-valued inputs, but they are slow and usually non-generative.
: By non-generative I mean that a neural network takes an input of a
: specific format and size, and gives an output of a specific format
: and size. They're notably bad at, say, parsing and producing English
: sentences, or planning, because parsers and planners have recursive,
: syntactic rules. I have never seen a neural network that could handle
: recursion. Feedback, but not recursion.
I was told that, given enough nodes, a NN is capable of reproducing *any*
algorithm. NNs are not slow - but they are slow to train.
However, you're right: the problems would be
o Mapping the world state to NN inputs
o Mapping the NN output to NPC reaction
o Training the NN in a reasonable amount of time... either by traditional
NN methods or by (bingo!) Genetic Programming...
Oh. And I guess I've drifted away from NPC planning, to NPC "reactions".
Drifting off-topic... always happens....
John
--
-----------------------------------------------------------
John Hartnup | You can drink your weak lemon drink
sl...@ladle.demon.co.uk| now, or you can save it 'til later.
-----------------------------------------------------------
Bruce Stephens
>>>>> "Fredrik" == Fredrik Ekman <ek...@lysator.liu.se> writes:
> Perhaps the NPCs should not plan according to how the game world
> actually looks, but rather to how they _perceive_ the world. This
> would require the implementation of an entire sub-world of beliefs
> for each NPC and would consequently require even more computational
> power, but I think it would give much more believable reactions.
I think the Oz project is doing this kind of thing. In a naive sense,
surely this is computationally much *less* expensive, because the NPC
has much less information to deal with? It probably requires
mechanisms for dealing with cases where inferences turn out to be
false (i.e., when the NPC thinks there might be a knife in the
kitchen, but goes there and finds there isn't one after all), and it's
surely harder in Prolog (it's easy to keep one database in prolog,
even a changing one, but it's more fiddly to keep multiple
databases).
--
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
Bruce Stephens
>>>>> "John" == John Hartnup <sl...@ladle.demon.co.uk> writes:
> I was told that, given enough nodes, a NN is capable of reproducing
> *any* algorithm. NNs are not slow - but they are slow to train.
NNs *can* be slow. In general, the more sophisticated the behaviour
you're trying to have the NN mimick, the larger the NN will have to
be, and large NNs can be expensive, both in memory to store the
weights and in time to evaluate them.
Phil Goetz
In article <Dzq1...@ladle.demon.co.uk>,
John Hartnup <sl...@ladle.demon.co.uk> wrote:
>
>I was told that, given enough nodes, a NN is capable of reproducing *any*
>algorithm.
Not quite. Given an algorithm, and an input size, you can construct a
neural network to approximate it to an arbitrary degree of precision.
But you have to decide ahead of time on the maximum input size you can
handle, whereas symbolic methods are generative and can handle any size
input.
A given neural network must use the same number of nodes for any
input. A symbolic method can parse the sentence
take inventory
very quickly, and recruit more computational power to parse
get three of the yellow balls from the cupboard and throw
them at the gnome who is charging me
A neural network responds to all input in constant time, and that means
it must always take as much time to respond as it would for the most
complex case.
>NNs are not slow - but they are slow to train.
If you have something which you can compute algorithmically,
like a logarithm, the neural network will be much, much slower
than the direct computation. You use them when you don't
know the function that you want to compute -- you want to implement
some sort of black box that maps from input to output, and you
have some way of telling how good an output is for a given input,
but you don't know how to compute it.
In the case of reacting, it might be good to take as input a set
of emotional values and a set of sensor inputs, and use a neural
network to "recognize" that state and produce an appropriate reaction.
But if you want planning that looks more than a few steps ahead,
I think you'll have to supplement any neural networks you use with
a GOFAI (good old-fashioned [symbolic] AI) planner.
Phil Go...@cs.buffalo.edu
Trevor Barrie
go...@cs.buffalo.edu (Phil Goetz) wrote:
>I've implemented an adventure engine in Prolog, and I spent last week
>adding a planning system to it. Now I can give my NPCs goals like
>"Get the babel fish" or "Kill Fred", and they can construct plans to
>accomplish them.
[Details deleted]
Well, it certainly sounds massively cool. Now hurry up and get a game out so
we can see how it works in practice.:)
Phil Goetz
>(Phil Goetz) wrote:
>
>>Yes, there is. That's what my first post was about.
>>Basically, you can't run Inform or LISP programs backwards.
>>You can do STRIPS planning in LISP, but you can't treat your program
>>code as data and use that for planning, too. You can't read your
>>program code and compute an input that will give the desired output.
>[...]
>
>Your assumption is that the planning system uses the source to the game as
>the knowledge base, and my personal viewpoint is that this is an overly
>complex representation for the limited domain of NPC interactions. It isn't
>necessary for an NPC to know about every action available to the player
>(say in the Inform library).
I think it is necessary. The NPCs should have the full range
of possible actions and consequences available to them, and they should
know how to go about doing things.
>Again, my point is that Strips doesn't force you to use Prolog, or to
>implement a miniature Prolog in order to plan.
Again, my point is that Strips doesn't force you to use Prolog,
but what I'm doing isa lot more powerful than Strips.
Maybe the best solution for now would be to use Inform, and just
duplicate information from the verb handlers in a logical scheme
to use in planning. If you had STRIPS planning plus a few plans
to achieve various preconditions, you could get pretty good coverage
of the things your NPCs want to do. The main problem, maybe, is
keeping the Inform code and the logic code synchronized, so they
actually do and say the same thing.
Phil
William Bryant
Dave Baggett writes of the advantages of using lisp as a potential
IF programming language. I would refer everyone back to AdvSys
(located in the archive) as a simple example of a IF language designed
with a lisp-like syntax and general organization.
It is still static, not dynamic, and has several limitations. The most
significant of which is its use of 16 bit integer data size which
limits (severly) the size of games that can be produced. But,
it is a nice, free and available introduction to lisp IF.
(BTW. I recently wrote to David Betz about releasing an updating AdvSys
that uses 32 bit data size increasing the game capacity and memory
size.
At this time, he prefers that AdvSys stay the way it is.)
John Francis
Phil Goetz wrote:
>
> RANT ON
> This really annoys me -- I have never seen a programming language that
> had a primitive for checking for keyboard input but not waiting for it.
> This is an important operation, but language designers never put it in,
> so it makes all realtime code un-portable because it has to use OS calls
> to read the keyboard. X-Windows can do it, and I think curses (the C
> library, not the game) can, but they don't count.
> RANT OFF
So read from the keyboard in one thread, and let it block.
Meanwhile do whatever else you want to do in another thread.
Several languages have thread synchronization primitives
(although I wouldn't generally recommend programming in ADA :-)
while Posix threads are available on a wide range of systems.
Erik Ostrom
go...@cs.buffalo.edu (Phil Goetz) wrote:
>John Hartnup <sl...@ladle.demon.co.uk> wrote:
>>Another thing to bear in mind: when would NPCs be allowed to "think",
>>"plan" etc... do these goal-analysis computations occur in normal
>>game computation time (i.e. between when you press "enter" and when
>>the game's response appears), or should they occur in the background,
>>calculating while the prompt is waiting for input?
>This is an excellent idea. It would be impossible to implement without
>using operating-system-specific calls, I think. Prolog doesn't have
>(at least not that I've seen) any way to check the keyboard for input,
>and then return if nothing has been typed. Once you ask to read
>the keyboard, you have to wait until someone types something.
>How does Inform handle this? It must, because I saw Tetris in Inform.
>Does it use machine-specific opsys calls?
I'm no Inform expert, but after a little digging in some manuals and
the Freefall source code, here's my educated guess:
* Inform doesn't provide any particular support for this, aside from
access to the Z-machine opcodes.
* Z-machine assembly language includes an opcode "@read_char",
which waits for a character to arrive, and reads it. Every so
often (as specified by a timeout parameter, in tenths of a
second), it calls a specified function if no input has yet
arrived. If this function returns true, @read_char exits without
having read a character. So you can implement roughly what you
want by writing a timeout function that sets a global variable and
then returns true. (The global variable is to indicate to the
rest of the program that no character was read.)
* Z-code interpreters implement this opcode in whatever way
their designers felt would be best. If they're using a language
that provides support for this sort of thing, they may use the
language facility. Otherwise, yeah, here's where the OS-specific
calls probably creep in.
I believe that if you write in Inform/Z-code, you _can't_ call any
OS-specific routines directly, even if you want to. Credit where it's
due: The mechanism described for doing this with the Z-machine
is lifted directly from Andrew Plotkin's _Freefall_, modulo
transmission errors on my part.
>RANT ON
>This really annoys me -- I have never seen a programming language that
>had a primitive for checking for keyboard input but not waiting for it.
>This is an important operation, but language designers never put it in,
>so it makes all realtime code un-portable because it has to use OS calls
>to read the keyboard. X-Windows can do it, and I think curses (the C
>library, not the game) can, but they don't count.
>RANT OFF
Offhand, I've got a few answers to this one:
* The Scheme standard includes a "non-essential" procedure,
"char-ready?", which indicates whether or not a character is ready
on a given input port. (The keyboard would be an obvious input
port for a Scheme implementation to provide.) Once your program
knows there's a character ready, it can call "read-char" to get a
character of input without blocking.
* In a language that provides threads, there's another solution:
Launch a separate thread whose only job is to read the keyboard
and store input in some buffer that the rest of the program can
get at. If your keyboard-reading thread blocks, it's no big
deal--it hasn't got anything _else_ to be doing. If another
thread wants to see if there's any input available, it just (with
some appropriate synchronization) checks the buffer and takes
a character if available. Modula 3 and Python are two of many
examples.
* Tcl allows you to specify a function to call whenever input is
available on a given I/O stream. With that, you can use the
same buffer strategy that you would use with the more general
mechanism of threads.
* Finally, I'm not sure why libraries don't count (it's so hard to
draw a line between language and library), but both Tk and
Java's AWT provide facilities similar to the Tcl model, but
for input events (keyboard and other) rather than I/O streams.
Of these, Scheme probably comes closest to what you asked for.
Threading might be better for the NPC computation problem, though.
--Erik
(not that you asked for this much detail)
William R Sherman
In article <...>, go...@cs.buffalo.edu (Phil Goetz) writes:
> If I ever write a book about this, I have a title already --
> "Adventures in Prolog". :)
>
> Phil
Except that you might want to choose a title that does more
to disambiguate it from Dennis Merritt's 1990 book "Adventure
in Prolog."
You might want to check this one out before you write your own.
I gather you're not familiar with it, which surprises me since
you're teaching a class on that very topic. Anyway, it's one
of the many books I own but have not yet read, so I can't
comment further. I'm sure that enough evolution has taken
place over the past 6-7 years in both Prolog and I-F that you
could write a new book that covers the topic better.
How about "Interactive Fictions in Prolog" ?
Bill
(posted & emailed)
/************************************************************************/
/* Bill Sherman (wshe...@ncsa.uiuc.edu) */
/* National Center for Supercomputing Applications */
/* University of Illinois at Urbana-Champaign */
/* */
/* "You want to do mankind a real service? Tell funnier jokes." */
/* Og */
/************************************************************************/
John Hartnup
go...@cs.buffalo.edu (Phil Goetz) wrote:
>RANT ON
>This really annoys me -- I have never seen a programming language that
>had a primitive for checking for keyboard input but not waiting for it.
>This is an important operation, but language designers never put it in,
>so it makes all realtime code un-portable because it has to use OS calls
>to read the keyboard. X-Windows can do it, and I think curses (the C
>library, not the game) can, but they don't count.
>RANT OFF
BBC BASIC had it. As I recall, there was a function INKEY - so you'd
go
IF INKEY(character you're testing for) THEN ...
...
END
... and if that key wasn't held down at the instant the command got
interpreted, the test would return false.
But then, BBC BASIC was (is) fab. Linux port, anyone?
Carl Muckenhoupt
go...@cs.buffalo.edu (Phil Goetz) writes:
>Threads are operating-system specific. There's no way around that.
>There is certainly no way I could write multi-thread code and have it
>run under Solaris, Linux, Windows, and MacOS.
Yes there is. It's called Java.
And, to get back on topic, I've been writing a text adventure framework
in Java during idle moments for a while now. (Not an adventure
language, just a set of classes to facilitate writing text adventures
in Java.) I had never considered making it multithreaded, but it would
be the obvious way to implement realtime components, as in Tetris or
Border Zone. However, for a system like mine, this entails no change -
threads are already supported implicitly.
--
Carl Muckenhoupt | Text Adventures are not dead!
b...@tiac.net | Read rec.[arts|games].int-fiction to see
http://www.tiac.net/users/baf | what you're missing!
Phil Goetz
In article <326F9D...@thuridion.com>,
John Francis <jo...@thuridion.com> wrote:
>Phil Goetz wrote:
>>
>> RANT ON
>> This really annoys me -- I have never seen a programming language that
>> had a primitive for checking for keyboard input but not waiting for it.
>> This is an important operation, but language designers never put it in,
>> so it makes all realtime code un-portable because it has to use OS calls
>> to read the keyboard. X-Windows can do it, and I think curses (the C
>> library, not the game) can, but they don't count.
>> RANT OFF
>
>Meanwhile do whatever else you want to do in another thread.
>
>Several languages have thread synchronization primitives
>(although I wouldn't generally recommend programming in ADA :-)
>while Posix threads are available on a wide range of systems.
Threads are operating-system specific. There's no way around that.
There is certainly no way I could write multi-thread code and have it
run under Solaris, Linux, Windows, and MacOS.
Phil Goetz
Jesse McGrew
John Hartnup (sl...@ladle.demon.co.uk) wrote:
[checking if therte's input waiting]
: BBC BASIC had it. As I recall, there was a function INKEY - so you'd
: go
:
: IF INKEY(character you're testing for) THEN ...
: ...
: END
Microsoft BASIC has a function INKEY$ such that if there is no waiting
character, it returns an empty string, else it pulls the first character out
of the input buffer and returns it. So this would get a string without
echoing it on the screen:
DO
ch$ = INKEY$
DO WHILE ch$ = ""
ch$ = INKEY$
LOOP ' wait for a character
IF ch$ <> CHR$(13) ' not a newline
str$ = str$ + ch$
END IF
LOOP WHILE ch$ <> CHR$(13) ' stop on newline
--
Jesse "Monolith" McGrew
http://www.concentric.net/~jmcgrew
Bruce Stephens
What's wrong with the old-fashioned approach of choosing a suitable
definition, wrapping it in a function, and implementing it for each
machine? You can do it the same way for Solaris and Linux (using
ioctl), so that's just three short variants you need to give?
Alternatively, use a library which you know is available on all the
relevant systems, and which provides what you want. An obvious choice
would be Tcl/Tk, which gives you nice widgets too.
John Hartnup
Carl Muckenhoupt (b...@max.tiac.net) wrote:
: go...@cs.buffalo.edu (Phil Goetz) writes:
: >Threads are operating-system specific. There's no way around that.
: >There is certainly no way I could write multi-thread code and have it
: >run under Solaris, Linux, Windows, and MacOS.
: Yes there is. It's called Java.
Or Ada. Must be others, too.
Matthew Crosby
In article <552o4u$o...@prometheus.acsu.buffalo.edu>,
Phil Goetz <go...@cs.buffalo.edu> wrote:
>In article <326F9D...@thuridion.com>,
>John Francis <jo...@thuridion.com> wrote:
>>>
>>> RANT ON
>>> This really annoys me -- I have never seen a programming language that
>>> had a primitive for checking for keyboard input but not waiting for it.
>>> This is an important operation, but language designers never put it in,
>>> so it makes all realtime code un-portable because it has to use OS calls
>>> to read the keyboard. X-Windows can do it, and I think curses (the C
>>> library, not the game) can, but they don't count.
>>> RANT OFF
>>
>>So read from the keyboard in one thread, and let it block.
>>Meanwhile do whatever else you want to do in another thread.
>>
>>(although I wouldn't generally recommend programming in ADA :-)
>>while Posix threads are available on a wide range of systems.
>
>There is certainly no way I could write multi-thread code and have it
>run under Solaris, Linux, Windows, and MacOS.
>
the language spec that are redily portable. Don't think that the
entire world is C and C++.
--
Matthew Crosby cro...@cs.colorado.edu
Disclaimer: It was in another country, and besides, the wench is dead.