static analysis of inform / z-machine games
Chris Pickett
I'm interested in analysing games statically, and computing things like:
-- a walkthough (including whether dead ends exist)
-- a hint system
-- difficulty / complexity
etc. etc.
I have experience writing compilers and virtual machines. I'd like to
start with the Infocom games.
My questions are:
1) Has anyone tried stuff like this before, and if so where can I read
about it?
2) Is there a specific Inform developer mailing list (I looked ...)? Is
this the best place to discuss its internals? I'm subscribed to the
Z-machine list but it has relatively low traffic.
3) Is it better to do this using a series of passes in Inform, or write
my own Z-Machine story file analyser? On related note, can I get back
and forth between Z-machine games and Inform perfectly with existing
tools on the Inform website?
4) Any neat metrics you'd like to compute for games?
5) What are the technical difficulties to overcome here?
Cheers,
Chris
--
Chris Pickett
Sable Research Group
McGill University
http://www.sable.mcgill.ca/~cpicke/
Michael Chapman Martin
> 1) Has anyone tried stuff like this before, and if so where can I read
> about it?
I poked around a bit but haven't really seen it -- other than dynamic
tools for exploring maps and the like.
> 3) Is it better to do this using a series of passes in Inform, or write
> my own Z-Machine story file analyser? On related note, can I get back
> and forth between Z-machine games and Inform perfectly with existing
> tools on the Inform website?
I'd definitely use the Inform source, if your goal is "static analysis
of Inform". There's a lot of OO structure in Inform that isn't directly
in the Z-Machine format.
txd will give you string tables and assembler source, which is probably
the best one can hope for when dealing with the old Infocom games.
Inform was *not* the language used by Infocom, so you can't get Inform
code for them -- and the decompilers I've worked with don't permit
transformations.
The Z-Machine is by no means the JVM, so there's no real convenient
equivalent to Soot or Joeq or really even BCEL. TXD's options imply
that Inform 6 includes some symbolic information, but there's no
such concept in the older works. (And I haven't seen much of a
difference between the listings even with it on.) If you operate
on the binaries, it'll be like analyzing binaries.
With respect to question 4 (fun metrics), degree of code reuse between
Inform games and Infocom originals might be amusing. I think that
Inform has a tighter library (and it's known that Infocom did not have
a core library from game to game) and so Inform's reuse would be
higher. It might be entertaining to see by how much.
--Michael
Chris Pickett
I'm interested in analysing games statically, and computing things
like:
-- a walkthough (including whether dead ends exist)
-- a hint system
-- difficulty / complexity
etc. etc.
I have experience writing compilers and virtual machines. I'd like to
start with the Infocom games. I'm at the stage of assessing the
feasibility of such a study.
My questions are:
1) Has anyone tried stuff like this before, and if so where can I read
about it?
2) Is there a specific Inform developer mailing list (I looked ...)?
Is
this the best place to discuss its internals? I'm subscribed to the
Z-machine list but it has very low traffic.
3) Is it better to do this using a series of passes in Inform, or
write
my own Z-Machine story file analyser? On related note, can I get back
and forth between Z-machine games and Inform perfectly with the
existing
tools on the Inform website?
4) Any neat metrics you'd like to compute for games?
5) What are the technical difficulties to overcome here?
Cheers,
Chris
--
Chris Pickett
Sable Research Group
McGill University
http://www.sable.mcgill.ca/~cpicke/
P.S. I already posted this message via my ISP instead of Google but
it doesn't appear to have shown up. Apologies for duplicates if they
exist.
Andrew Plotkin
>
> With respect to question 4 (fun metrics), degree of code reuse between
> Inform games and Infocom originals might be amusing. I think that
> Inform has a tighter library (and it's known that Infocom did not have
> a core library from game to game) and so Inform's reuse would be
> higher. It might be entertaining to see by how much.
Inform has a much larger and more feature-heavy library, but then most
Inform games don't make use of every feature in it. So the level of
code re-use is... a bit arbitrary. What do you count as "real" re-use?
Infocom copied parser code from game to game. De facto it was a
library. Inform's library has been much more stable over time -- many
games hack the library to some extent, but the changes don't propagate
much. (I re-use library hacks from one Inform game to another, but
they're small.)
--Z
"And Aholibamah bare Jeush, and Jaalam, and Korah: these were the borogoves..."
*
* Make your vote count. Get your vote counted.
Adam Thornton
Chris Pickett <chrisDOTpickett@mailDOTmcgillDOTca> wrote:
>I'm interested in analysing games statically, and computing things like:
> -- a walkthough (including whether dead ends exist)
> -- a hint system
> -- difficulty / complexity
>5) What are the technical difficulties to overcome here?
Combinatorial Explosion.
Adam
RootShell
news:PFZcd.63853$ct3.1...@wagner.videotron.net...
> Hi,
>
> I'm interested in analysing games statically, and computing things like:
> -- a walkthough (including whether dead ends exist)
> -- a hint system
> -- difficulty / complexity
>
> etc. etc.
Funny You should mention this... since even last night i was talking to a
friend of mine about the existance (or not) of what we call in FPS (First
Person Shooters) games, a BOT.
The idea is simple, we launched the bot in a IF game, and see if he could
end the game, walk around the rooms, pickup objects, use objects, etc etc...
(maybe this could also be applied to a beta-tester NPC???).
All this to try and check if the game as loose ends, dead ends, it's
finishable (or not), it's not buggy...
Of course the whereabouts of the bot would need to be loged, so that one
could check what the bot tryed and where it did (or not) successed, and
eventually get a solution transcript.
That would not replace beta-testers, but it would in fact show (at least)
mapping errors faster, and report on number of ingame object, npcs, rooms,
etc etc.
A strange, maybe not even aplicable idea, nevertheless, yours seems to be in
the same direction or did i missunderstood your questions?
Regards,
RootShell
PS: as always if i am on the wrong side of this, please ignore ;)
dgr...@cs.csbuak.edu
> Hi,
> I'm interested in analysing games statically, and computing things like:
> -- a walkthough (including whether dead ends exist)
> -- a hint system
> -- difficulty / complexity
Page 381 of the Inform Designer's Manual has directed graph of sorts that
illustrates what needs to be done before something else can be done. This
is a way to prove or disprove a game's winnability.
--
David Griffith
dgr...@cs.csbuak.edu <-- Switch the 'b' and 'u'
Chris Pickett
> Chris Pickett <ch...@videotron.ca> wrote:
>
>>Hi,
>
>
>>I'm interested in analysing games statically, and computing things like:
>> -- a walkthough (including whether dead ends exist)
>> -- a hint system
>> -- difficulty / complexity
>
>
> Page 381 of the Inform Designer's Manual has directed graph of sorts that
> illustrates what needs to be done before something else can be done. This
> is a way to prove or disprove a game's winnability.
>
Yes, I should have said that my supervisor already did something along
these lines. I would be interested in taking his formalism, building on
it, and applying it within a compiler framework. Inside you'll find a
hand-analysis for the beginning of The Count by Scott Adams.
Clark Verbrugge. "A Structure for Modern Computer Narratives.". in
CG'2002: International Conference on Computers and Games." LNCS 2883.
pp. 308-325. July 2002 (nb: publish date is 2003).
http://www.sable.mcgill.ca/~clump/papers/narrative.ps
Cheers,
Chris
Chris Pickett
> "Chris Pickett" <ch...@videotron.ca> escreveu na mensagem
> news:PFZcd.63853$ct3.1...@wagner.videotron.net...
>
>>Hi,
>>
>>I'm interested in analysing games statically, and computing things like:
>> -- a walkthough (including whether dead ends exist)
>> -- a hint system
>> -- difficulty / complexity
>>
>>etc. etc.
>
>
> Funny You should mention this... since even last night i was talking to a
> friend of mine about the existance (or not) of what we call in FPS (First
> Person Shooters) games, a BOT.
>
> The idea is simple, we launched the bot in a IF game, and see if he could
> end the game, walk around the rooms, pickup objects, use objects, etc etc...
> (maybe this could also be applied to a beta-tester NPC???).
Like a bot, but it would be static, not an external module interacting
with the game at runtime. It's not an artificial intelligence kind of
proposal (although that also sounds neat).
Chris
Andrew Plotkin
> RootShell wrote:
> > "Chris Pickett" <ch...@videotron.ca> escreveu na mensagem
> > news:PFZcd.63853$ct3.1...@wagner.videotron.net...
> >
> >> -- a walkthough (including whether dead ends exist)
> >> -- a hint system
> >> -- difficulty / complexity
> >
> >
> > friend of mine about the existance (or not) of what we call in FPS (First
> > Person Shooters) games, a BOT.
> >
> > The idea is simple, we launched the bot in a IF game, and see if he could
> > end the game, walk around the rooms, pickup objects, use objects, etc etc...
> > (maybe this could also be applied to a beta-tester NPC???).
>
> Like a bot, but it would be static, not an external module interacting
> with the game at runtime. It's not an artificial intelligence kind of
> proposal (although that also sounds neat).
Static analysis of an executable, or even of source code, *is* an
AI-like problem.
Chris Pickett
> Here, Chris Pickett <chrisDO...@mail.mcgill.ca> wrote:
>
>>RootShell wrote:
>>
>>>"Chris Pickett" <ch...@videotron.ca> escreveu na mensagem
>>>news:PFZcd.63853$ct3.1...@wagner.videotron.net...
>>>
>>>
>>>>I'm interested in analysing games statically, and computing things like:
>>>> -- a walkthough (including whether dead ends exist)
>>>> -- a hint system
>>>> -- difficulty / complexity
>>>
>>>
>>>Funny You should mention this... since even last night i was talking to a
>>>friend of mine about the existance (or not) of what we call in FPS (First
>>>Person Shooters) games, a BOT.
>>>
>>>The idea is simple, we launched the bot in a IF game, and see if he could
>>>end the game, walk around the rooms, pickup objects, use objects, etc etc...
>>>(maybe this could also be applied to a beta-tester NPC???).
>>
>>Like a bot, but it would be static, not an external module interacting
>>with the game at runtime. It's not an artificial intelligence kind of
>>proposal (although that also sounds neat).
>
>
> Static analysis of an executable, or even of source code, *is* an
> AI-like problem.
What I meant by that is that I would not be using heuristics trying to
solve a game, or using an English generator to interact with the parser.
Chris
Chris Pickett
I was thinking about some system to collapse equivalent series of
actions (esp. movement, dropping and picking up objects). It seems like
some concept of forward progress would also be necessary.
Chris
Chris Pickett
> Chris Pickett <ch...@videotron.ca> wrote:
>
>>1) Has anyone tried stuff like this before, and if so where can I read
>>about it?
>
>
> I poked around a bit but haven't really seen it -- other than dynamic
> tools for exploring maps and the like.
>
>
>>3) Is it better to do this using a series of passes in Inform, or write
>>my own Z-Machine story file analyser? On related note, can I get back
>>and forth between Z-machine games and Inform perfectly with existing
>>tools on the Inform website?
>
>
> I'd definitely use the Inform source, if your goal is "static analysis
> of Inform". There's a lot of OO structure in Inform that isn't directly
> in the Z-Machine format.
>
> txd will give you string tables and assembler source, which is probably
> the best one can hope for when dealing with the old Infocom games.
>
> Inform was *not* the language used by Infocom, so you can't get Inform
> code for them -- and the decompilers I've worked with don't permit
> transformations.
So, I've looked at the readme for Disinformation, which says:
For the moment, it will only de-compile the source code, and rather
rudimentarily. However, sometime in the near-distant future, it will
also print out all the objects, their arrays, objectloops, attributes,
classes and properties, in an Inform syntax. And everything will be
compilable. But not yet.
> The Z-Machine is by no means the JVM, so there's no real convenient
> equivalent to Soot or Joeq or really even BCEL. TXD's options imply
> that Inform 6 includes some symbolic information, but there's no
> such concept in the older works. (And I haven't seen much of a
> difference between the listings even with it on.) If you operate
> on the binaries, it'll be like analyzing binaries.
Yeah ... I'll have to read the docs in detail and see what can be done
with Z-machine code / assembly / Inform source / any IR's that might
exist for Inform. It would be nice to get between Z-Machine bytecode or
Inform source and some stackless 3-address IR, and analyse that (based
on my experience with Soot's Jimple intermediate representation).
Anyway, thanks for the feedback, it gives me some idea of the problems,
and suggests strongly that I should start from Inform source, were I
actually to embark upon this fool's errant.
Cheers,
Chris
Carolyn Magruder
actually work very well. For mapping areas, it would be fairly
effective, but so many games have their own little peculiarities
(added commands, varying conversational systems, directions changed to
left/right/ahead/back, intricate puzzles, nonstandard responses to
standard commands, etc.) that it seems as though only the most basic
of games would be winnable via bot.
A bot might do fairly well on "Pick Up The Phone Booth and Die",
though. (After some experimentation, that is!) If anyone does try
writing an IF bot, I'd be quite curious to see how well (or poorly) it
worked out.
If I ever see a bot win "Jigsaw" without being specifically programmed
for the game, then I'll... well, I don't know what! --but it doesn't
seem very likely to happen....
Carolyn
"RootShell" <root...@netcabo.pt> wrote in message news:<4174de2b$0$12623$a729...@news.telepac.pt>...
Michael Chapman Martin
> Static analysis of an executable, or even of source code, *is* an
> AI-like problem.
McGill in particular is pretty well known for its static-analysis group,
so I imagine the OP has some idea of what he'd be getting into on the
"solving the problem" end.
--Michael
Michael Chapman Martin
> I was thinking about some system to collapse equivalent series of
> actions (esp. movement, dropping and picking up objects). It seems like
> some concept of forward progress would also be necessary.
Or, in the best static-analysis vein, drop the level of complexity to
something a bit more managable. A TXD disassembly will show a number of
"interesting" strings. This could give the question "So, which verb on
which object may produce this message," but even that may require some
degree of context-sensitivity to be reasonably accurate.
--Michael
RootShell
news:ad17d854.04101...@posting.google.com...
> The idea of an IF bot is interesting, but I don't think it would
> actually work very well. For mapping areas, it would be fairly
> effective, but so many games have their own little peculiarities
> (added commands, varying conversational systems, directions changed to
> left/right/ahead/back, intricate puzzles, nonstandard responses to
> standard commands, etc.) that it seems as though only the most basic
> of games would be winnable via bot.
A Bot would have access to the game data file (.z5 or whatever) thus if the
interpreter recognizes the new comands programmed by the game's author then
the bot also would. as for the complex of the puzzles (same thought)...
Meaning that if a human reads the source file and knows the correct solution
for a given puzzle, i guess it would be that impossible to do it also in a
bot (ie AI).
AI in computer games (such as FPS) as evolved greatly, i wouldnt be that
suprised if i saw on on the IF world.
> A bot might do fairly well on "Pick Up The Phone Booth and Die",
> though. (After some experimentation, that is!) If anyone does try
> writing an IF bot, I'd be quite curious to see how well (or poorly) it
> worked out.
Been looking for it all over the web, and nothing :( yet!
> If I ever see a bot win "Jigsaw" without being specifically programmed
> for the game, then I'll... well, I don't know what! --but it doesn't
> seem very likely to happen....
Dont know if it would be possible, but the bot (as i see it) would have
access to the same information the interpreter has, so the solution to
puzzles and mind twisting commands would also be available to him (as stated
earlier).
I GUESS that the best thing to do would be "transform" a interperter into a
IfBot... So that it reads the game file, and then acts according to all the
possibilities inside that game file (objects, rooms, npc, etc). The
interperter knows every single command combination possible to win the game,
so the IFBot would also know it? wouldnt it? As said im just guessing
here...
Regards,
RootShell
Kevin Venzke
"Chris Pickett" <chrisDO...@mail.mcgill.ca> wrote in message
> > Page 381 of the Inform Designer's Manual has directed graph of sorts that
> > illustrates what needs to be done before something else can be done. This
> > is a way to prove or disprove a game's winnability.
>
> Yes, I should have said that my supervisor already did something along
> these lines. I would be interested in taking his formalism, building on
> it, and applying it within a compiler framework. Inside you'll find a
> hand-analysis for the beginning of The Count by Scott Adams.
>
> Clark Verbrugge. "A Structure for Modern Computer Narratives.". in
> CG'2002: International Conference on Computers and Games." LNCS 2883.
> pp. 308-325. July 2002 (nb: publish date is 2003).
I'm very interested in anything to do with The Count... Embarrassingly
I can't read .ps files.
I take it you are saying that this paper simply describes what things
must be done before other things, in The Count? If it's much more
than that, I'll have to look for a way to read it...
Kevin Venzke
Dave Holland
>I take it you are saying that this paper simply describes what things
>must be done before other things, in The Count? If it's much more
>than that, I'll have to look for a way to read it...
It's *much* more than that.
I've put a PDF version at http://www.biff.org.uk/dave/narrative.pdf
temporarily. I hope that's more accessible. Goodness knows if that's
"fair use" or not, but I'll leave it there for a while.
Dave
Ben Rudiak-Gould
> Hi,
>
> I'm interested in analysing games statically, and computing things like:
> -- a walkthough (including whether dead ends exist)
> -- a hint system
> -- difficulty / complexity
>
> etc. etc.
>
> I have experience writing compilers and virtual machines. I'd like to
> start with the Infocom games.
Go for it! I've always thought this would make a great CS research project.
> My questions are:
>
> 1) Has anyone tried stuff like this before, and if so where can I read
> about it?
I don't think anyone's tried it before. It's been discussed before on this
group, though at a very high level (or low level, depending on how you look
at it). The following Google search should find those discussions (notice my
clever choice of query term):
http://groups.google.com/groups?q=group:rec.arts.int-fiction+halting+problem
> can I get back
> and forth between Z-machine games and Inform perfectly with existing
> tools on the Inform website?
No. The Z-machine is mostly untyped -- it's closer to a typical hardware
architecture than a typical VM architecture. The state of the art last I
checked is my decompiler "Reform" [1], which can do a good job if you spend
a lot of time assisting it. It comes very close to producing recompilable
source code for Zork I release 88; the biggest obstacle right now is
Inform's lack of support for Infocom-format verb tables.
[1] http://www.darkweb.com/~benrg/if-decompilers/
> 5) What are the technical difficulties to overcome here?
Combinatorial explosion, as Adam Thornton said. Determining whether an IF
game is winnable is like determining whether chess is a first-player win:
it's easy enough to write the program, but the sun will go nova before it
completes (even assuming Moore's Law continues to the limit of physical
laws). The hard part is coming up with effective heuristic methods of
reducing the search space.
(I'm still hoping that P will turn out to be equal to NP, but I'm not
holding my breath.)
-- Ben
Matthew Russotto
RootShell <root...@netcabo.pt> wrote:
>
>Dont know if it would be possible, but the bot (as i see it) would have
>access to the same information the interpreter has, so the solution to
>puzzles and mind twisting commands would also be available to him (as stated
>earlier).
>
>
>I GUESS that the best thing to do would be "transform" a interperter into a
>IfBot... So that it reads the game file, and then acts according to all the
>possibilities inside that game file (objects, rooms, npc, etc). The
>interperter knows every single command combination possible to win the game,
>so the IFBot would also know it? wouldnt it? As said im just guessing
>here...
I think the problem's clearly intractable using that method. Formally: the
number of steps required to find a solution grows exponentially with
the size of the game.
Even if it grows only polynomially (e.g. if you can model the game as
a DFA), the exponent is going to be huge.
Chris Pickett
I'm sure that's fine. Eventually I'll get him to put one up with the
fonts properly embedded (assuming you didn't bother). Thanks for
reading it and doing that.
Chris
P.S. You can get ghostscript and gsview from
Chris Pickett
Last night, after seeing that KG's program is decidedly non-free, and
discovering a bushel of holy wars testifying to this effect, I readied
myself for YAGWAD. It doesn't help that the bloody thing is a
ribosome. I got through Chapter 4 okay, but after Chapter 5 I had a
splitting headache (I still have it) -- I possess no vorpal blade
(LL(5)) of disambiguation, and I'm not sure I want to hunt for it.
There must be an easier way.
So today (and the next day, and possibly the day after that, and even
then for probably quite some number of days further), I'm going to
take your new advice and seek out a hidden passage for the Lower
Halls, pondering the utility of Zimple on my trek, rather than try to
bash down the Front Gate.
Chris
Chris Pickett
> Chris Pickett wrote:
>
>>Hi,
>>
>>I'm interested in analysing games statically, and computing things like:
>> -- a walkthough (including whether dead ends exist)
>> -- a hint system
>> -- difficulty / complexity
>>
>>etc. etc.
>>
>>I have experience writing compilers and virtual machines. I'd like to
>>start with the Infocom games.
>
>
> Go for it! I've always thought this would make a great CS research project.
>
>
>>My questions are:
>>
>>1) Has anyone tried stuff like this before, and if so where can I read
>>about it?
>
>
> I don't think anyone's tried it before. It's been discussed before on this
> group, though at a very high level (or low level, depending on how you look
> at it). The following Google search should find those discussions (notice my
> clever choice of query term):
>
> http://groups.google.com/groups?q=group:rec.arts.int-fiction+halting+problem
>
I'm not sure that what I want to do reduces to the halting problem, but
those discussions are always fun.
>
>>can I get back
>>and forth between Z-machine games and Inform perfectly with existing
>>tools on the Inform website?
>
>
> No. The Z-machine is mostly untyped -- it's closer to a typical hardware
> architecture than a typical VM architecture. The state of the art last I
> checked is my decompiler "Reform" [1], which can do a good job if you spend
> a lot of time assisting it. It comes very close to producing recompilable
> source code for Zork I release 88; the biggest obstacle right now is
> Inform's lack of support for Infocom-format verb tables.
>
> [1] http://www.darkweb.com/~benrg/if-decompilers/
>
Thanks for making it free, I will look. As I said in other posts, some
intermediate representation is what I'm looking for; converting back to
Inform doesn't really get me anywhere.
>>5) What are the technical difficulties to overcome here?
>
>
> Combinatorial explosion, as Adam Thornton said. Determining whether an IF
> game is winnable is like determining whether chess is a first-player win:
> it's easy enough to write the program, but the sun will go nova before it
> completes (even assuming Moore's Law continues to the limit of physical
> laws). The hard part is coming up with effective heuristic methods of
> reducing the search space.
So, I don't want any approximations, but I do believe that it's possible
to simplify without losing meaning. What I want is to construct a
narrative flow graph (NFG), see above posted .ps and .pdf files, and
then analyse that.
> (I'm still hoping that P will turn out to be equal to NP, but I'm not
> holding my breath.)
I'm just hoping that the inputs here are/can be made small enough :)
Chris
Chris Pickett
> Ben Rudiak-Gould wrote:
>
>>Chris Pickett wrote:
>>
>>
>>>Hi,
>>>
>>>I'm interested in analysing games statically, and computing things like:
>>> -- a walkthough (including whether dead ends exist)
>>> -- a hint system
>>> -- difficulty / complexity
>>>
>>>etc. etc.
>>>
>>>I have experience writing compilers and virtual machines. I'd like to
>>>start with the Infocom games.
>>
>>
>>Go for it! I've always thought this would make a great CS research project.
>>
>>
>>
>>>My questions are:
>>>
>>>1) Has anyone tried stuff like this before, and if so where can I read
>>>about it?
>>
>>
>>I don't think anyone's tried it before. It's been discussed before on this
>>group, though at a very high level (or low level, depending on how you look
>>at it). The following Google search should find those discussions (notice my
>>clever choice of query term):
>>
>>http://groups.google.com/groups?q=group:rec.arts.int-fiction+halting+problem
>>
>
>
> I'm not sure that what I want to do reduces to the halting problem, but
> those discussions are always fun.
Note that I'm not trolling here. I don't really care either way: if I
can analyse a subset of games it's a start and I'll be happy.
Chris
Ben Rudiak-Gould
> Ben Rudiak-Gould wrote:
>> discussions (notice my clever choice of query term):
>>
>> http://groups.google.com/groups?q=group:rec.arts.int-fiction+halting+problem
>
> I'm not sure that what I want to do reduces to the halting problem, but
> those discussions are always fun.
I don't think it does either, but when these discussions come up, someone
tends to mention the halting problem sooner or later (sort of like flame
wars and Hitler). In this case it was me. :-)
>> The hard part is coming up with
>> effective heuristic methods of reducing the search space.
>
> So, I don't want any approximations, but I do believe that it's possible
> to simplify without losing meaning.
Well, that doesn't necessarily mean you can't use heuristics (look at A*),
but I see what you mean.
> What I want is to construct a
> narrative flow graph (NFG), see above posted .ps and .pdf files, and
> then analyse that.
This seems a very nice model, but there are still some hurdles if you want
to represent the entire state space of a real game. Anything that involves
numeric calculation, as opposed to boolean tests, is going to be difficult
-- e.g. a lamp running out, or Zeno's bridge in Beyond Zork. The latter is
an example of state that you might be better off ignoring if you can.
-- Ben
Kevin Venzke
Thanks very much, I got it.
Kevin Venzke
samwyse
> No. The Z-machine is mostly untyped -- it's closer to a typical hardware
> architecture than a typical VM architecture. The state of the art last I
> checked is my decompiler "Reform" [1], which can do a good job if you
> spend a lot of time assisting it. It comes very close to producing
> recompilable source code for Zork I release 88; the biggest obstacle
> right now is Inform's lack of support for Infocom-format verb tables.
Do you mean the dictionary or the grammar tables, or maybe something
else? I would be interested in any information on the format of either
or both in non-Inform storyfiles.
Ben Rudiak-Gould
> Do you mean the dictionary or the grammar tables, or maybe something
> else? I would be interested in any information on the format of either
> or both in non-Inform storyfiles.
I meant the grammar tables, but only because I'd forgotten that the
dictionary has the same problem.
As far as I know the only documentation on these formats is the InfoDump and
Reform source code (and the parsers embedded in the story files themselves).
I had to work from InfoDump when writing Reform. I think the Reform code
(Reform_grammar.hs) is easier to understand than InfoDump, but only if you
know Haskell.
I volunteer to write a description of the formats in English if someone else
will volunteer to get them published in an appropriate place (e.g. as a new
appendix to the Z-machine specification).
-- Ben
RootShell
the
> number of steps required to find a solution grows exponentially with
> the size of the game.
>
> Even if it grows only polynomially (e.g. if you can model the game as
> a DFA), the exponent is going to be huge.
I dont know, but maybe the power of today's computers as opposed to older
might just justify a try?
If the player sends "comands" to the game parser to analyze why cant the bot
do the same thing, only a huge number of times faster?
samwyse
> samwyse wrote:
>> Do you mean the dictionary or the grammar tables, or maybe something
>> else? I would be interested in any information on the format of
>> either or both in non-Inform storyfiles.
>
> I meant the grammar tables, but only because I'd forgotten that the
> dictionary has the same problem.
>
> As far as I know the only documentation on these formats is the InfoDump
> and Reform source code (and the parsers embedded in the story files
> themselves). I had to work from InfoDump when writing Reform. I think
> the Reform code (Reform_grammar.hs) is easier to understand than
> InfoDump, but only if you know Haskell.
I just looked at the source to both. It's been years since I looked at
anything to do with Haskell (and I've never actually programmed in it),
so unsurprisingly I found Infodump a bit easier to decypher.
> I volunteer to write a description of the formats in English if someone
> else will volunteer to get them published in an appropriate place (e.g.
> as a new appendix to the Z-machine specification).
I'll see what I can do. There's a lot of Z-machine stuff that didn't
make it into the specs, but that shouldn't be lost either. If nothing
else, it could be put into the if-archives alongside of the specs.
Chris Pickett
> Chris Pickett
> > to simplify without losing meaning.
>
> Well, that doesn't necessarily mean you can't use heuristics (look at A*),
> but I see what you mean.
Actually I want to use BDD's to search the state space.
> > What I want is to construct a
> > narrative flow graph (NFG), see above posted .ps and .pdf files, and
> > then analyse that.
>
> This seems a very nice model, but there are still some hurdles if you want
> to represent the entire state space of a real game. Anything that involves
> numeric calculation, as opposed to boolean tests, is going to be difficult
> -- e.g. a lamp running out, or Zeno's bridge in Beyond Zork. The latter is
> an example of state that you might be better off ignoring if you can.
Over the weekend I hacked together a grammar and Java interpreter for
narrative flow graphs, and implemented the trivial Cloak of Darkness
game. It actually wasn't so trivial (1000 lines), and it made me
realize that NFG's are extremely low level. At the same time, I think
this makes the representation powerful.
You can download it and play, or browse the sources (currently
unlicensed, will be LGPL) at my homepage. I'm calling it nfg-0.0.1
for now, but I don't know if I want nfg as the project name. We'll
see. I just realized that it's a pretty funny acronym, which is a
plus (think about it).
http://www.sable.mcgill.ca/~cpicke/
You can get arbitrary arithmetic using Petri nets if you let places be
bits in a register. I didn't implement this in the example game
(which is grossly redundant in many places and also lacks a parser,
but hey, it works).
I think all that's missing is randomness. This could be accomplished
by saying that when faced with a choice between enabled transitions,
it is random which one will fire (yes, I know, sometimes you want it
to be repeatedly random, that isn't much of a problem either).
Anyway, comments are very welcome. At this point, I want to focus on
formal verification using BDD's, since the cloak.nfg game is a good
enough benchmark (maybe not for speed, but definitely for other
properties). Obviously I realize that as it stands it's not much good
for serious writing, but personally I think it's already pretty fun to
play around with.
Cheers,
Chris
P.S. The grammar could do with constructs like exclusive-or '|' and
not '!', but at this point it's usable so I'm not going to bother.
samwyse
> Over the weekend I hacked together a grammar and Java interpreter for
> narrative flow graphs, and implemented the trivial Cloak of Darkness
> game. It actually wasn't so trivial (1000 lines), and it made me
> realize that NFG's are extremely low level. At the same time, I think
> this makes the representation powerful.
>
> You can download it and play, or browse the sources (currently
> unlicensed, will be LGPL) at my homepage. I'm calling it nfg-0.0.1
> for now, but I don't know if I want nfg as the project name. We'll
> see. I just realized that it's a pretty funny acronym, which is a
> plus (think about it).
>
> http://www.sable.mcgill.ca/~cpicke/
OK, I'm having some problems running it under WinXP. Also, you may want
to think about putting just the .class files into a JAR and running
everything from there.
C:\Temp\nfg-0.0.1>java -version
java version "1.4.1_02"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_02-b06)
Java HotSpot(TM) Client VM (build 1.4.1_02-b06, mixed mode)
C:\Temp\nfg-0.0.1>java nfg.Main cloak.nfg
Exception in thread "main" java.lang.NoClassDefFoundError: nfg/Main
C:\Temp\nfg-0.0.1>dir nfg\Main.*
Volume in drive C is C_DRIVE
Volume Serial Number is 20DF-E57E
Directory of C:\Temp\nfg-0.0.1\nfg
10/26/2004 12:36 AM 4,500 Main.class
10/26/2004 12:36 AM 4,276 Main.java
2 File(s) 8,776 bytes
0 Dir(s) 28,587,388,928 bytes free
Chris Pickett
> On or about 10/26/2004 1:19 AM, Chris Pickett did proclaim:
>
>
>>Over the weekend I hacked together a grammar and Java interpreter for
>>narrative flow graphs, and implemented the trivial Cloak of Darkness
>>game. It actually wasn't so trivial (1000 lines), and it made me
>>realize that NFG's are extremely low level. At the same time, I think
>>this makes the representation powerful.
>>
>>You can download it and play, or browse the sources (currently
>>unlicensed, will be LGPL) at my homepage. I'm calling it nfg-0.0.1
>>for now, but I don't know if I want nfg as the project name. We'll
>>see. I just realized that it's a pretty funny acronym, which is a
>>plus (think about it).
>>
>>http://www.sable.mcgill.ca/~cpicke/
>
>
>
> OK, I'm having some problems running it under WinXP. Also, you may want
> to think about putting just the .class files into a JAR and running
> everything from there.
Yes, the packaging could be better.
> C:\Temp\nfg-0.0.1>java -version
> java version "1.4.1_02"
> Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_02-b06)
> Java HotSpot(TM) Client VM (build 1.4.1_02-b06, mixed mode)
>
> C:\Temp\nfg-0.0.1>java nfg.Main cloak.nfg
> Exception in thread "main" java.lang.NoClassDefFoundError: nfg/Main
I don't know if this is a Windows problem or not (I only have access to
*nix machines). Is "." on your CLASSPATH? IIRC, you have to set it via
some system property (wherever you set PATH). What about trying:
C:\Temp\nfg-0.0.1>java -cp . nfg.Main cloak.nfg
Cheers,
Chris