RSS

Daily Archives: January 3, 2012

Zork on the PDP-10

One distinguishing trait of hackers is the way they never see any program as completely, definitively done; there are always additions to be made, rough edges to be smoothed. Certainly Adventure, impressive as it was, left plenty of room for improvement. On top of all that, though, one also has to consider that Adventure came to MIT from Don Woods of Stanford’s AI Lab, perhaps the only computer-science program in the country with a stature remotely comparable to that of MIT. MIT students are fiercely proud of their alma mater. If Stanford had done the adventure game first, MIT’s Dynamic Modeling Group could still do it better. And it didn’t hurt that the heritage of Project MAC and the Laboratory for Computer Science, not to mention the DMG itself, gifted them with quite some tools to bring to bear on the problem.

Adventure had been implemented in FORTRAN, a language with no particular suitability for the creation of a text adventure. Indeed, FORTRAN wasn’t even natively designed to handle variable-length strings, leaving Crowther and Woods to kludge their way around this problem as they did plenty of others. Both were of course very talented programmers, and so they made the best of it. Still, the hackers at DMG, whose opinion of FORTRAN was elevated about half a step above their opinion of BASIC, couldn’t wait to design their own adventure game using their own pet language, MDL. Not only did MDL, as a language at least partially designed for AI research, boast comparatively robust string-handling capabilities, but it also offered the ability to define complex new data types suitable to a specific task at hand and even to tie pieces of code right into those structures. Let me try to explain what made that so important.

We’ll start with the opening room of Zork, the game the DMG eventually produced in response to Adventure. Its description reads like this to the player:

West of House
This is an open field west of a white house, with a boarded front door.
There is a small mailbox here.
A rubber mat saying 'Welcome to Zork!' lies by the door.

Here’s the original MDL source that describes this room:

<ROOM "WHOUS"
"This is an open field west of a white house, with a boarded front door."
"West of House"
<EXIT "NORTH" "NHOUS" "SOUTH" "SHOUS" "WEST" "FORE1"
"EAST" #NEXIT "The door is locked, and there is evidently no key.">
(<GET-OBJ "FDOOR"> <GET-OBJ "MAILB"> <GET-OBJ "MAT">)
<>
<+ ,RLANDBIT ,RLIGHTBIT ,RNWALLBIT ,RSACREDBIT>
(RGLOBAL ,HOUSEBIT)><

Just about everything the program needs to know about this room is nicely encapsulated here. Let’s step through it line by line. The “ROOM” tag at the beginning defines this structure as a room, with the shorthand name “WHOUS.” The following line of text is the room description the player sees when entering for the first time, or typing “LOOK.” “West of House” is the full name of the room, the one which appears as the header to the room description and in the status line at the top of the screen whenever the player is in this room. Next we have a list of exits from the room: going north will take the player to “North of House,” south to “South of House”, west to one of several rooms that make up the “Forest.” Trying to go east will give a special failure message, saying that the player doesn’t have a key for the door, rather than a generic “You can’t go that way.” Next we have the items in the room as the game begins: the front door, the mailbox, and the welcome mat. Then a series of flags define some additional properties of the room: that it is on land rather than overrun with water; that it has light even if the player does not have a lit lantern with her; that (being outdoors) it has no walls; that it is “sacred,” meaning that the thief, a character who wanders about annoying the player in a manner akin to the dwarfs and the pirate in Adventure, cannot come here. And finally the last line defines this room as being associated with the white house, or if you will a part of the house “region” of the game’s geography.

Each item and character in the game has a similar definition block explaining most of what the game needs to know about it. Notably, even the special abilities or properties of these are defined as part of them, via links to special sections of code crafted just for them. Thus, once the scaffolding of utility code that enables all of this was created (no trivial task, of course), adding on to Zork largely involved simply defining more rooms, items, and characters, with no need to dive again into the engine that enables everything; only special capabilities of items and characters needed to be coded from scratch and linked into their hosts. In forming their world from a collection of integrated “objects,” the hackers at DMG were pushing almost accidentally toward a new programming paradigm that would first become a hot topic in computer science years later: object-oriented programming, in which programs are not divided rigorously into code that executes and the data it manipulates, but are rather built out of the interaction of semi-autonomous objects encapsulating their own code and data. Regarded for a time as the ideal solution to pretty much everything (possibly including the attainment of world peace), there is today a (probably justified) push-back in some quarters against the one-size-fits-all imposition of OOP theory found in some languages, such as Java. Be that as it may, OOP is pretty much ideal for crafting a text adventure. To show what I mean, let’s look at the alternative, as illustrated by the very non-OOP FORTRAN Adventure.

Each room in Adventure is given a number, from 1 (the starting location outside the small brick building, naturally) to 140 (a dead end location in the maze, less naturally). To find the long description of a room, shown when the player enters for the first time or LOOKs, the program digs through the first table in an external data file, matching the room number to the entries:

1
1	YOU ARE STANDING AT THE END OF A ROAD BEFORE A SMALL BRICK BUILDING.
1	AROUND YOU IS A FOREST.  A SMALL STREAM FLOWS OUT OF THE BUILDING AND
1	DOWN A GULLY.


Another table defines the short description shown upon entering an already visited room:

1	YOU'RE AT END OF ROAD AGAIN.


And now it gets really fun. Another table tells us what lies in what direction:

1	2	2	44	29
1	3	3	12	19	43
1	4	5	13	14	46	30
1	5	6	45	43
1	8	63


The first line above tells us that when in room 1 we can go to room 2 by typing any of three entries from yet another table, this time of keywords: “ROAD or HILL” (entries 2); “WEST” or “W” (entries 44); or “UPWAR” (pattern matching is done on just the first 5 characters of each word), “UP,” “ABOVE,” or “ASCEN” (entries 29). Definitions for items are similarly scattered over multiple tables within the data file. Thus, while Adventure does make some attempt to abstract its game engine from the data that makes up its world (placing the latter as much as possible within the external data file), modifying the world is a fiddly, error-prone process of editing multiple cryptic tables. Early adventuring engines created on microcomputers, such as those of Scott Adams, work in a similar fashion. Although it is of course possible to develop tools to ease the burden of hand-editing data files, the MDL Zork system is flexible and programmable in a way that these systems are not; with no ability to build code right into the world’s objects, as it were, crafting non-standard objects in Adventure or a Scott Adams game generally required hacking on the engine code itself, an ugly proposition.

So, MDL was just better for writing an adventure game, capable of cleanly representing a huge world in a readable, maintainable way. It was almost as if MDL had been designed for the purpose. Indeed, if you’ve used a more modern IF programming language like Inform 6, you might be surprised at how little their approach to defining a world has changed since the days of MDL Zork. (Inform 7, one of the latest and greatest tools for IF development, does drift away from the OOP model in favor of a more human-readable — even “literary” — rules-based approach. Suffice to say that the merits and drawbacks of the Inform 7 approach is a subject too complex to go into here. Maybe in 20 years, when the Digital Antiquarian finally makes it to 2006…)

And the DMG hackers had still another ace up their sleeve.

MIT had a large body of research into natural-language understanding on the computer, stretching back at least as far as Joseph Weizenbaum and his 1966 ELIZA system. If that program was ultimately little more than an elaborate parlor trick, it did inspire other, more rigorous attempts at getting a program to parse plain English. Most famously, between 1968 and 1970 Terry Winograd developed a program he called SHRDLU, which simulated a model world made up of blocks. The user could ask the program to manipulate this world, shifting blocks from place to place, placing them on top of each other, and so on, all by typing in her requests as simple imperative English sentences. She could even ask the computer simple questions, about what was placed where, etc. Rather overvalued in its time (as so much AI research tended to be) as a step on the road to HAL, SHRDLU nevertheless showed that when held within a very restricted domain it is very possible for a program to parse and genuinely “understand” at least a reasonable subset of English. Working from the tradition of SHRDLU, the DMG hackers crafted an adventure-game parser that was arguably the first to be truly worthy of the term. While Adventure got by with simple pattern matching (as betrayed by the fact that “LAMP GET” works as well as “GET LAMP”), Zork would have a real understanding not only of verb and direct object, but also of preposition, indirect object, conjunction, punctuation, even article. Helping the process along was once again MDL, which as a language designed with AI research in mind had superb string-manipulation capabilities. The parser they ended up with is a remarkable creation indeed, one that would stand alone for several years — then as now an eternity in the world of computer science. But now we’re getting ahead of ourselves.

The road to Zork began in late May of 1977, when Dave Lebling put together a very simple parser and game engine quite similar to Adventure‘s, from which Marc Blank and Tim Anderson built their first four-room game as a sort of proof of concept. At this point Lebling went on vacation for two weeks, while Blank, Anderson, and Bruce Daniels hacked like crazy, crafting the basic structure of Zork as we know it to this day. The name itself was a nonsense word floating around MIT that one might use in place of something, shall we say, stronger in stressful situations: “Zork the bloody thing!” when a piece of code just wouldn’t work correctly, etc. The file holding the game-in-progress got named “Zork” as a sort of placeholder until someone came up with something better. Every programmer tends to have a few names like this which she uses for programs, variables, functions, etc., when she’s just experimenting and can’t be bothered to come up with something better. (My own go-to placeholder, for reasons too embarrassing and idiosyncratic to elaborate on here, has been “fuzzy” for the last 25 years.) In the case of Zork, though, a proper name was slow in coming. And so Zork the game remained for the first six months of its existence.

By the time Lebling returned from that vacation to resume working on the game, a solid foundation was in place. Everything about the design was modular, meaning not only that (as demonstrated above) it was easy to add more rooms, items, and puzzles, but also that parts of the underlying technology could be easily removed, improved, and inserted again. Most notably, the parser gradually progressed from a two-word job “almost as smart as Adventure‘s” to the state-of-the-art creation it eventually became, mostly thanks to the efforts of Blank, who obsessed over it to the tune of “40 or 50” iterations.

In later years Infocom would develop an elaborate if comedic history and mythology around Zork and its “Great Underground Empire,” but in these early days they were interested in the game’s world only as a setting for cool if ridiculously disparate scenery and, of course, puzzles to solve, very much in the tradition of Don Woods’s approach to Adventure. In fact, Zork‘s world paid homage to Adventure almost to the point of initially seeming like a remake. Like in Adventure, you start above ground next to a small house; like in Adventure, there is a small wilderness area to explore, but the real meat of the game takes place underground; like in Adventure, your goal is to collect treasures and return them to the house that serves as your base of operations; etc., etc. Only deeper in the game did Zork diverge and really take on its own character, with imaginative locations of its own and much more intricate puzzles enabled by that magnificent parser. Of course, these parts were also crafted later, when the development team was more experienced and when said parser was much better. I’ll be having a detailed look at Zork the game in its microcomputer rather than its PDP-10 incarnation, but if you’re interested in learning more about this original shaggy-dog implementation I’d encourage you to have a look at Jason Dyer’s detailed play-through.

Like Adventure, Zork ran on a DEC PDP-10. Unlike Adventure, however, it ran under the operating system which also hosted the MDL environment, the Incompatible Timesharing System (named with a bit of hacker humor as a sarcastic response to an earlier Compatible Timesharing System; once again see — sorry to keep beating this drum — Levy’s Hackers for a great account of its origins). ITS was largely unique to MIT, the institution that had developed it. There was something very odd about it: in extravagant (some would say foolhardy) tribute to the hacker tradition of total openness and transparency, it had no passwords — in fact, no security whatsoever. Absolutely anyone could log on and do what they pleased. This led to a substantial community of what the MIT hackers came to call “net randoms,” people with nothing to do with MIT but who were blessed with access to an ARPANET-connected computer somewhere who stopped by and rummaged through the systems just to see what all those crazy MIT hackers were up to. DMG’s machine had collected quite a community of randoms thanks to the earlier Trivia game. It didn’t take them long to find Zork, even though it was never officially announced anywhere, and get to work adventuring. Soon the game-in-progress was developing a reputation across the ARPANET. For the benefit of this community of players the development team started to place a copy of U.S. News and Dungeon Report in one of the first rooms, which detailed the latest changes and additions to this virtual world they were exploring. The randoms as well as other, more “legitimate” MIT-based users (John McCarthy, the father of AI, among them) served as a sort of extended beta-testing team; the implementers could see what they tried to do, not to mention what they complained about, and adjust their game to accommodate them. Many of the parser improvements in particular were undoubtedly driven by just this process; anyone who’s ever put a text adventure through beta testing knows that you just can’t predict the myriad ways people will try to say things.

Still, Zork‘s growing popularity raised obvious concerns about overloading the DMG’s PDP-10 system — which was funded by the Defense Department and theoretically needed for winning the Cold War, after all — with all of these gamers. Meanwhile, others were asking for their own copies of the game, to install on other machines. Although developed and used primarily under ITS, there was as it happened a version of the MDL environment that ran on yet another PDP-10 operating system, TOPS-20, first released by DEC in 1976 and positioned as a more advanced, user-friendly version of TOPS-10. Unlike ITS, TOPS-20 was widely used outside of MIT. The DMG hackers therefore modified Zork as necessary to run on TOPS-20 and began distributing it to any administrator who requested a copy. By that fall, machines all over the country were hosting Zork, and the maintainers had even set up an electronic mailing list to keep administrators aware of expansions and improvements.

The DMG hackers were generous, but not quite so generous as Don Woods had been with Adventure. They distributed Zork only as encrypted files that were runnable in an MDL environment but were not readable (and modifiable) as source code. They even went so far as to patch their famously insecure ITS development system, adding security to just the directory that stored the source. Hackers, however, won’t be denied, and soon one from DEC itself had penetrated the veil. From Infocom’s own official “History of Zork“:

[The security] was finally beaten by a system hacker from Digital: using some archaic ITS documentation (there’s never been any other kind), he was able to figure out how to modify the running operating system. Being clever, he was also able to figure out how our patch to protect the source directory worked. Then it was just a matter of decrypting the sources, but that was soon reduced to figuring out the key we’d used. Ted had no trouble getting machine time; he just found a new TOPS-20 machine that was undergoing final testing, and started a program that tried every key until it got something that looked like text. After less than a day of crunching, he had a readable copy of the source. We had to concede that anyone who’d go to that much trouble deserved it. This led to some other things later on.

About those “other things”:

At some point around the fall of 1977, the DMG hackers had decided that their creation really, really needed a “proper” name. Lebling suggested Dungeon, which excited no one (Lebling included), but no one could come up with anything better. And so Dungeon it was. It was shortly after this that the security breach just described took place — thus, the game that that DEC hacker recovered was not called Zork, but rather Dungeon. Shortly after that, MIT heard legal rumblings from, of all places, TSR, publishers of Dungeons and Dragons — and of a dungeon-crawling board game called simply Dungeon! TSR was always overzealous with lawsuits, and the consensus amongst the MIT lawyers that the DMG hackers consulted was that they didn’t have a legal leg to stand on. However, rather than get sucked into a lengthy squabble over a name none of them much liked in the first place, they decided to just revert to the much more memorable Zork. And so by the beginning of 1978 Dungeon became Zork once more, and retained that name forevermore.

Almost. Remember that source that “Ted” had liberated from MIT? Well, it made its way to another hacker at DEC, one Robert Supnik, who ported the whole thing to the more common and portable (if intrinsically vastly less suitable for text adventures) FORTRAN — a herculean feat that amazed even the DMG hackers. Since the game described in the MDL source he had access to was called Dungeon, Dungeon this version remained. Supnik originally did the port with an eye to getting Dungeon running on the DEC PDP-11 (not, as its name might seem to imply, a successor to the PDP-10, but rather a physically smaller, less powerful, less expensive machine). With Supnik’s FORTRAN source free distributable, however, it was a short hop from the PDP-11 to other architectures. Indeed, during these early years Supnik’s Dungeon was probably more widely distributed and thus more commonly played than the DMG’s own Zork. When PCs appeared that could support it, Dungeon inevitably made its way there as well. Thus by the latter part of the 1980s the situation was truly baffling for those without knowledge of all this history: there was this free game called Dungeon which was strangely similar to the official commercial Zork games, which were in turn very similar to this other game, Adventure, available by then in at least a dozen free or commercial versions. To this day Supnik’s Dungeon is available alongside the free-at-last MDL source to the PDP-10 Zork.

Back at MIT, development continued on Zork proper, albeit at a gradually diminishing pace, through 1978. Apart from some minor bug fixing that would go on for another couple of years, the last bits of Zork were put into place in February of 1979. By this point the game had grown to truly enormous proportions: 191 rooms, 211 items, a vocabulary of 908 words including 71 distinct verbs (not counting synonyms). The implementers were just about out of new puzzle ideas and understandably a bit exhausted with the whole endeavor, and, as if that weren’t justification enough, they had completely filled the 1 MB or so of memory an MDL program was allowed to utilize. And so they set Zork aside and moved on to other projects.

The story could very well have finished there, with Zork passing into history as another, unusually impressive example of the text adventures that flourished on institutional machines for a few brief years after Adventure‘s release; Zork as another Mystery Mansion, Stuga (UPDATE: not quite; see Jason Dyer’s comment below), or HAUNT. It didn’t, though, thanks to the DMG’s very non-hackerish director, Al Vezza, who decided a few months later that the time was right to enter along with his charges the burgeoning new frontier of the microcomputer by starting a software company. Little did he realize where that decision would lead.

Update, July 27, 2023: The full source code of the PDP-10 Zork is now available for the dedicated and curious!

 
 

Tags: , , ,