NAIL v1.5

Authoring Inform 6
1

I created a system for writing very small Z-code games. It’s derived from PunyInform, and it works a lot like PunyInform, except it (a) produces smaller story files, and (b) has a much simpler parser, lacks some nice features, requires Ruby for the build process, and is all-around less convenient to work with.

It’s not really a library, but more a build environment, and a source code template for a game. Start editing the template, build, test, repeat until happy.

An absolutely minimal game in PunyInform is about 23 KB. In NAIL, it’s 11 KB. Cloak of Darkness is 12.5 KB, unless you start removing verbs/actions which aren’t strictly necessary for the game.

I expect this to come in handy for projects targeting tiny 8-bit machines, possibly without a disk drive. E.g. on a 48K Spectrum, it should be possible to run a 29 KB Z-code game, using Vezza.

12 Likes
2

Using checksums for dictionary words is really clever!

Though I’d worry that a game might not have a encoding factor that makes all words unique.

I feel that lacking multiple commands per input line might be a deal breaker for many people. Being able to type stuff like s.e.e.w is something people take for granted.

1 Like
3

Whoah, I didn’t even know you could do that. ( I’m just getting into the genre :slight_smile: )

3 Likes
4

Thanks for your comments!

The build script will write comments in generated_dictionary.inf, noting any collisions. In some cases it may be okay, e.g. if a verb has the same checksum as a noun or a preposition, that will never be a problem, or if synonyms for two objects that will never be in scope at the same time have the same checksum, that’s not a problem.

If you do find that there’s a collision that will cause problems, you can consider renaming an object. Maybe a stone can be named a rock, etc. If you aren’t interested in making compromises, this just isn’t the system you’re looking for.

I can’t easily run a test on all Infocom games, as I’d need to go through the dictionary of each game and figure out what characters are missing for words that have been cut off.

I have tried to do this for Zork I (690 words) and PunyInform Adventure (740 words), and at least for these games, I could find factors causing no collisions.

I also tried this for Trinity (2100+ words), and got something like 15 words with non-unique checksums. That’s a much bigger game than what NAIL is meant for though.

There’s a lot that people take for granted that isn’t supported by NAIL. You can’t take a library that’s been heavily optimized for size, such as PunyInform, reduce the size by 50%, and still have support for everything that’s nice to have.

Note that NAIL isn’t meant to supersede PunyInform. It’s a lot cruder, but may be good enough for some kinds of games, where both authors and players accept cutting some corners in order to get a small enough game.

I may have a look at this particular feature, to see if it can be implemented cheaply enough. If it’s 50 bytes, then sure. If it’s 500 bytes, it’s not happening.

5

The ZIL parsing I’ve done for Visible Zorker makes this tractable. E.g. for Zork 1 I get:

Summary

$ A ACROSS ACTIVATE ADVENTURER ADVERTISEMENT AGAIN AIR AIR-PUMP ALL ALTAR AN ANCIENT AND ANSWER ANTIQUE APPLY AROUND ART ASK AT ATTACH ATTACK AVIATOR AWAKE AWAY AX AXE BACK BAG BANISH BAR BARE BARF BARROW BASKET BAT BATHE BAUBLE BEAUTI BEETLE BEGONE BEHIND BELL BELOW BENEATH BIRD BIRDS BITE BLACK BLADE BLAST BLESSINGS BLOCK BLOODY BLOW BLUE BOARD BOARDED BOARDS BOAT BODIES BODY BOLT BONES BOOK BOOKLET BOOKS BOTTLE BOX BRACELET BRANCH BRANDISH BRASS BREAK BREATH BRIEF BROKEN BROWN BRUSH BUBBLE BUG BUOY BURN BURNED BURNING BUT BUTTON CAGE CANARY CANDLES CANVAS CARPET CARRY CARVED CASE CASKET CAST CATCH CHALICE CHANT CHASE CHEST CHESTS CHIMNEY CHOMP CHUCK CHUTE CLEAN CLEAR CLIFF CLIFFS CLIMB CLOCKWORK CLOSE CLOVE COAL COFFIN COIL COINS COLONI COME COMMAND CONSUME CONTAINER CONTROL COUNT COVER CRACK CRAWLWAY CRETIN CROSS CRYSTAL CUP CURSE CUT CYCLOPS D DAM DAMAGE DAMN DARK DEAD DEFLATE DERANGED DESCRIBE DESTROY DIAGNOSE DIAMOND DIG DINNER DIRT DISEMBARK DISENCHANT DISPATCH DIVE DONATE DOOR DOUSE DOWN DRINK DRIP DRIVE DRIVER DROP DRYER DUMBWAITER DUSTY E EAST EAT ECHO EGG EGYPTIAN ELONGATED ELVISH EMERALD ENAMELED ENCHANT ENCRUSTED ENGRAVINGS ENORMOUS ENTER EVIL EXAMINE EXCEPT EXIT EXORCISE EXQUISITE EXTINGUISH EYE FALL FANTASIZE FASTEN FCD#3 FEAR FEEBLE FEED FEEL FENCE FERMENT FIENDS FIERCE FIGHT FIGURINE FILCH FILL FIND FINE FINEPRINT FIREPROOF FIX FLAMING FLATHEAD FLIP FLOAT FLOOR FLUORESCE FOLLOW FOOD FOOTPAD FOR FORBIDDING FORCE FORD FOREST FORK FREE FREEZE FRIGID FROBOZZ FROM FRONT FROTZ FRY FUCK FUDGE FUMBLE G GARLIC GATE GATES GAZE GET GHOSTS GIANT GIVE GLAMDRING GLASS GLUE GO GOLD GOLDEN GOTHIC GRAB GRACES GRANITE GRATE GRATING GREASE GREEN GROUND GROUP GRUE GUIDE GUIDEBOOKS GUNK H2O HAND HAND-HELD HANDS HATCH HEAD HEAP HELLO HEMLOCKS HEMP HER HERE HI HIDE HIM HIT HOLD HOP HOT HOUSE HUGE HUNGRY HURL HURT I IGNITE IMBIBE IMPASSABLE IN INCANT INCINERATE INFLAT INJURE INSCRIPTION INSERT INSIDE INTNUM INTO INVENTORY INVISIBLE IS IT IVORY JADE JEWEL JEWELED JEWELS JUMP KEY KICK KILL KISS KITCHEN KNIFE KNIVES KNOCK L LABEL LADDER LAMP LANTERN LARGE LAUNCH LEAF LEAFLET LEAK LEAN LEAP LEATHER LEAVE LEAVES LEDGE LETTERING LID LIFT LIGHT LIQUID LIQUIFY LISTEN LOCK LONG LOOK LOSE LOWER LOWERED LUBRICATE LUNCH LUNGS LURKING MACHINE MAGIC MAIL MAILBOX MAKE MAN MANGLED MANUAL MAP MARBLE MASSIVE MATCH MATCHBOOK MATCHES MATERIAL ME MELT METAL MIRROR MOLEST MONSTER MOUNTAIN MOUTH MOVE MUMBLE MURDER MYSELF N NARROW NASTY NE NEST NO NORTH NORTHE NORTHWEST NUT NW ODYSSEUS OF OFF OFFER OIL OLD ON ONE ONTO OPEN ORCRIST ORIENTAL OUT OVER OVERBOARD OWN OWNERS OZMOO PAGE PAINTING PAIR PANEL PAPER PARCHMENT PASSAGE PASTE PAT PATCH PATH PDP10 PEAL PEDESTAL PEPPER PERSON PET PICK PIECE PIERCE PILE PINES PIPE PLACE PLASTIC PLATINUM PLAY PLUG PLUGH POKE POSEIDON POT POUR PRAY PRAYER PRESS PRINT PROCEED PULL PUMP PUNCTURE PURSUE PUSH PUT Q QUANTITY QUIT RAFT RAIL RAILING RAINBOW RAISE RAMP RANGE RAP RAPE READ RED REFLECTION RELEASE REMAINS REMOVE REPAIR REPENT REPLY RESTART RESTORE RICKETY RING RIVER ROBBER ROCKY ROLL ROPE RUB RUG RUN RUSTY S SACK SAILOR SAND SANDWICH SAPPHIRE SAVE SAY SCARAB SCEPTER SCEPTRE SCORE SCREAM SCREW SCREWDRIVER SCRIPT SE SEARCH SEAWORTHY SECURE SEE SEEDY SEEK SELF SEND SET SHADY SHAKE SHARP SHEER SHIT SHOUT SHOVEL SHUT SIGH SILENT SILVER SINISTER SIT SKELETON SKIM SKIP SKULL SLAG SLAY SLICE SLIDE SMALL SMASH SMELL SMELLY SNIFF SOLID SONG SONGBIRD SOUTH SOUTHE SOUTHWEST SPILL SPIN SPIRITS SPRAY SQUEEZE STAB STAIRCASE STAIRS STAIRWAY STAND STARE STARTLE STAY STEEP STEP STEPS STILETTO STONE STORM STRANGE STRIKE STUFF SUPER SUPERBRIEF SURPRISE SURROUNDING SUSPICIOUS SW SWALLOW SWIM SWING SWITCH SWORD TABLE TAKE TALK TAN TASTE TAUNT TEETH TELL TEMPLE THE THEM THEN THIEF THIEFS THROUGH THROW THRU THRUST TIE TIMBERS TO TOMB TOOL TOOLCHESTS TOOLS TOOTH TORCH TOSS TOUCH TOUR TRAIL TRAP TRAP-DOOR TRAPDOOR TREASURE TREE TREES TRIDENT TROLL TROPHY TRUNK TUBE TUG TURN TWISTING U ULYSSES UNATTACH UNDER UNDERNEATH UNFASTEN UNHOOK UNLOCK UNRUSTY UNSCRIPT UNTIE UP USELESS USING VALVE VAMPIRE VERBOSE VERIFY VERSION VICIOUS VISCOUS VITREOUS W WADE WAIT WAKE WALK WALL WALLS WATER WAVE WEAR WEST WHAT WHATS WHERE WHITE WIN WIND WINDING WINDOW WINNAGE WISH WITH WOODEN WRENCH WRITING XYZZY Y YANK YELL YELLOW YES Z ZORK ZORKMID ZZMGCK , .

That’s approximate – I’m sure I missed some parsing details – but it gives you an idea.

2 Likes
6

Thanks!

I think I’m just missing these words (which I found in R88) :

‘$verify’
‘.//’
‘,//’
‘#command’
‘#random’
‘#record’
‘#unrecord’
‘~//’

If you have this data for more games, or can produce it without too much inconvenience, I’d love to have a copy.

7

I’ll see if I can rig up a decent dump function. What I did above isn’t really good. (E.g. it includes FROTZ OZMOO which are only compiled into Zork 3.)

EDIT: I thought they weren’t, but infodump says I’m wrong. That’s odd. Oh, I see – they’re in the BUZZ list.

1 Like
8

That’s fair enough.

BTW I tested the algorithm (using my own code) on the dictionary words of my game All That Shimmers, which has around 687 words (including ones from PunyInform). The were only 4 clashes in the best case, really surprising! That wouldn’t be much burden to work around.

9

I have a long-running/frequently-dormant project where I’m attempting to fit a good text adventure engine on a PDP-8, and I went with almost the same approach. I ended up with Soundex, which is a First-World-War-era hashing scheme for family names invented by genealogists and census-takers. I actually read about it in Knuth back in the 90s, which makes this probably the only time I have ever directly taken an idea from TAoCP and put it into my code.

One advantage to Soundex is that it clusters words by how they actually sound to an English-speaker’s ear. It makes input extremely typo-forgiving, and kind of broadens the acceptable input available to the player.

The drawback is that there are some notable collisions in the standard I6/Puny verb lists, such as ATTACH and ATTACK. This is easily worked around in your grammar system to get the other benefits, as few games would have trouble distinguishing ATTAC* TROLL WITH SWORD from ATTAC* CHAIN TO ELEVATOR. We already tend to use the grammar patterns to hack around the fact that GET OUT means EXIT, not “take”.

My Soundex code only hashes words that are too long to fit into the native word size of the machine (in my case, that’s 12 bits, but the examples under discussion here are largely talking 16). So you could have a 14-bit Soundex hash (5 bits for the initial letter, and three for each subsequent digit) iff the most-significant bit is high, and packed five-bit text otherwise.

This lets you easily handle NW and NE (which encode to the same hash in Soundex) as raw input, while storing DEPUTISE in a way that won’t break if someone uses Oxford spelling conventions. And in a 16 bit system, you’d also trivially distinguish GET FISH from GUT FISH in a way my 12-bit version can’t.

2 Likes
10

Also you managed to release 1.0 just as we recorded an OPEN MAILBOX episode talking about your 0.3 release!

1 Like
11

So is every dictionary word reduced to a single 16 bit integer? Does that include any “part of speech” information that would ordinarily be in the payload for V3?

On V3 dictionary words are already only 5 bytes each (six packed letters and a payload byte) and the interpreter handles the binary search during parsing so that seems like a lot of work to save a few bytes per word. I’d also be worried about random words mis-identifying as some completely unrelated word with only a 16 bit hash, leading to some really confusing user experiences.

But it’s still a cool idea! Reminds me of how the ancient Unix spell utility just remembered the hash codes of valid English words instead of the actual words themselves.

-Dave

12

You don’t need a dictionary at all, so for 500 words you are saving 3000 bytes.

Another advantage is that words can be any length, with Z3 you are limited to 6-ish characters and anything longer cannot be distinguished.

You’re right about the potential for miscontruing words. My feeling is that would be happen too rarely to be an issue.

13

Most examples on the web don’t go any lower than 32 bit hashcodes, so I had to ask google for specifics:

Entry Count vs. Collision Probability

The table below tracks how the probability grows as you add entries to your 16-bit space:

Number of Entries Exact Collision Probability Risk Level / Notes
10 0.07% Extremely low
50 1.85% Noticeable risk
100 7.27% High risk for production systems
300 49.56% Roughly a 50/50 coin flip
500 85.10% Collision is highly likely
1,000 99.95% Collision is practically guaranteed
14

I don’t mean the risk of a collision is rare, I mean that people playing interactive fiction will mostly be typing about things which are mentioned (and not words at random), so the risk of a command like “eat hamburger” displaying “you can’t see the spaceship here” is small, especially when “hamburger” is never mentioned anywhere.

15

I’m actually using a 15-bit checksum, so the risk of a collision should be higher than this, if the numbers are indeed correct. However, my build process chooses between ~10K different parameter values, and picks the one with the least number of collisions, which may mean that the risk is lower than what your AI friend figures.

I’m actually interested in alternate ways of computing the checksum. Right now, this is how it’s calculated:

checksum = 0
for each character of the word:
  checksum = (k * checksum) AND $7FFF
  checksum = (checksum + ZSCII_CODE) AND $7FFF

This gives me a 15-bit checksum. The reason for doing AND $7FFF is to make the checksum positive before the next operation. I’m relying on the Z-machine to hand me the bottom 16 bits of the result, when making a multiplication or addition that overflows. This behaviour isn’t specified in the standard, but it works this way in all the interpreters that I’ve tried. If I start doing multiplications with negative numbers, I’m afraid this would increase the risk of different interpreters behaving in different ways, so I avoid that.

I tried using division and mod instead of multiplication, since they can’t overflow. It got a lot more complicated, and I didn’t quite manage to get results on par with what I get with multiplication.

The perfect candidate for a checksum algorithm would meet these criteria:

  • Typically produces fewer collisions than the current algorithm.
  • Requires little code in Z-code version 3 (my current solution is 112 bytes).
  • Is reasonably fast, in Z-code version 3.
  • Only relies on behaviour that is well-defined in the Z-machine standard.
  • Finding the best parameter values, in Ruby, is reasonably fast

Note that while Z-code version 3 has support for multiplication, division and mod, it lacks shift operations, exclusive or, and integer arithmetic for anything except 16 bit integers (which are always treated as signed for +, -, *, / and % (mod)).

2 Likes
16

If you don’t trust Google’s AI (and why should you), you can either follow the math on the Wikipedia page for Birthday Paradox, or use this applet:

It claims that for 15 bits, 500 items has a 97.8% of there being at least one collision.

As far as how to compute the hash – yeah, most hash functions I’ve used in my day job have a bunch of xors and shifts in them, neither of which Z3 is great at.

1 Like
17

Corollary: If you have 10000 different ways to do the encoding (by setting the multiplication factor to different values), the chance that all of them cause collisions for a given set of 500 items is 0.978 ^ 10000 = 0.000% (correctly rounded).

This is all true, if the algorithm produces a perfect pseudo-random number, and if changing the factor produces something that can be considered as a completely different set of checksums. Neither of this is true. However, the above reasoning goes to show that the 97.8% chance of collision isn’t the whole story.

3 Likes
18

True. When I’ve used perfect hashing (modifying the hash coefficients until there are no collisions in a specific fixed data set) I’ve kept the actual result in the table as well to double check it.

My concern here is that user input is unconstrained and they might guess a verb you didn’t include or picked some word in a description that didn’t get hashed.

But it’s still better than the three letters of precision in the early Scott Adams games!!

Dave

1 Like
19

Actually, you can see how this works in practice, since the first NAIL game has already been released: https://microheaven.com/schooladventure/

1 Like
20

I have now added this, at a cost of 72 bytes.

3 Likes