21 January 2009

Modeling reality with code: Nethack

One of my secret vices is Nethack, a classic dungeon-crawl game with an ASCII user interface, in the tradition of Rogue and Angband.  (The name "nethack" refers to the game's development as a hacking project by people distributed over the Internet, and has nothing to do with the game's content.)  Nethack is a great game, despite its ludicrously primitive graphics by modern standards, for the following reasons:
  • Game play is rich and complex, but intuitive.  Rules make sense (especially if you catch the allusions to myth and modern storytelling) and actions have consequences.  Almost any object or creature can and will interact with anything else. 
  • Intelligent humor makes the perverse and random ways to suffer and die (almost) bearable.
  • The game is so challenging that even if I skim the spoilers and play with infinite lives, I can get myself into apparently inextricable situations.  Yet, it's still enjoyable without cheats and spoilers.
  • The display is stripped-down but suggestive.  For example, line of sight and memory interact intuitively -- both are combined into one map, which lets you fit more of the map on one screen (unlike, say, a first-person shooter, which keeps the map separate from the view). 
Nethack also makes a good motivating example for teaching new programmers how to model reality with code.  The game has some elements which are representative of real-life situations:
  1. Agents have limited information, and may even forget things.
  2. Things happen beyond agents' awareness.
  3. Attempted actions may not succeed: luck (which may improve with skill) plays a role.  (Nethack, like most games, models luck probabilistically.)
  4. Actions usually change the world state irreversibly.
  5. Object interactions depend on the properties of all the objects involved.  (In terms of object-oriented programming, your object system needs mixins.)
  6. Some items and creatures are unique and irreplaceable.
 It also has properties which are not representative of reality:
  1. Turn-based: there is no need to manage simultaneous attempts to change the world's state.
  2. Rule-based: interactions are modeled simply, with little resort to a priori physical modeling (e.g., Newton's laws).  This means interactions are not usually computationally intensive.
  3. Very simple graphics.
These three properties make Nethack fit into a natural progression of increasingly complex situations to model.  The game belongs after explaining object-oriented programming (OOP), but before explaining concurrency.  The simple graphics let students concentrate on the algorithmic interactions (and save teaching assistants and graders a lot of trouble writing a GUI framework for them!).  These interactions are rich enough to exercise many OOP lessons, such as member and class methods, inheritance, generic (a.k.a. virtual) methods, and object factories (for uniqueness).  However, they are not generally computationally expensive, so complicated algorithms are not necessary.

The chosen programming model affects the teaching approach.  For example, probabilistic success requires pseudorandom number generation, but if the programming model is functional, the novice's mental model ("rolling a die") differs from the usual stateful implementation.  Also, the lessons learned at this stage may require correction when the model is generalized to handle real-time (instead of turn-based) interactions, since multiple agents will need to draw random numbers simultaneously (parallel pseudorandom number generation). In addition, the programming language's version of OOP may make it more or less difficult to explain how to implement object interactions.  Some (such as Common Lisp) handle mixins trivially, whereas others (Java, C++) do not.  Reliance on "design patterns" to cover the programming language's deficiencies can help students deal with languages used in industry, but may also limit their flexibility with programming languages and models.  This doesn't mean a dogmatic insistence on "the one true programming language."  It's better to understand the deficiencies of one's chosen language, and learn how to work around them, than not to recognize deficiencies at all.

Nethack offers another useful pedagogical feature:  it's well-crafted and balanced.  Playing it teaches students that making an application good comes not so much from learning new programming tricks, as from careful and laborious design and testing.   "Testing" here means both correctness ("It didn't crash"), which students experience by necessity, as well as user experience testing ("It's fun to play"), which few students experience much in an undergraduate computer science curriculum.


John said...

Well put. I've never played nethack myself, but I've read enough to know it sounds quite engaging (which is one reason I've never started!).

It makes me wonder why CS programs don't try to build up a patina of software systems that students can then plug into, and that can work as platforms for projects, even between classes. For example, extending the local adventure game to allow for plausible concurrent actions.

I remember talking with Sameer about temporal model checking of developing programs, so that he could (as a TA) intervene before a student spent days on a bad assumption.

HilbertAstronaut said...

Yes, Nethack is an effective time sink ;-)

Your second paragraph reminds me of the typical undergraduate operating systems course, where students spend their time filling out components of a partially written OS framework. TAs for the more introductory programming courses seem to spend a lot of time developing and maintaining ad hoc frameworks for the homework exercises, but I haven't seen a more comprehensive approach at that level (with "real" apps like Nethack used as examples). Maybe that's because CS majors don't actually get time to learn how to program, with all the classes they have to take ;-P

I like that idea of using some kind of verification on student programs to save them lots of pain -- they might be too hard for students to use themselves but great for supervised debugging.

John said...

This is exactly what I was thinking of when I wrote the example, was the difference between some of the walled garden frameworks used in homework, the simulators used in hardware research, and some really great top-to-bottom simulators that, sadly, I can't remember right now.

I do think that computer programming, for all it's been compared to various fields, has many similarities to design, and that a design-studio/critique-driven environment would really do much for the field. I'm not sure how computer science fits into it, although my theory classes were some of the most collaborative I've taken, so it's possible.

HilbertAstronaut said...

CS curriculum design is hard ;-P

I like the design studio idea. I wish there was more of that required and less of classes around specific "CS topics" (like databases and OS), or at least a "theory track" (with more topics courses) and a "design track" (with more of what you're talking about).

Watching the undergrads here, the "software engineering" / advanced practica courses seem more about the last-minute cram and less about picking apart code and discussing it. Good prep for how most code gets written, I guess ;-P but it's just a waste of time to expose them to that before the "real world."

John said...

I'm kind of skeptical about the track pipeline. I think that you can discuss an algorithm, a proof, code, software specs, and hardware designs all as designs with design criteria.

I think you are entirely right about the problems of software engineering classes, but again I think that comes from a lack of critical work, and being graded on critical ability.

The most major problem is that such an approach is so radically different than the way it has worked. It's then a critical question if the temperament of going to your desk and cranking code by yourself for ten hours a day wouldn't want to participate in these kinds of programs.

HilbertAstronaut said...

Re: "It's then a critical question if the temperament of going to your desk and cranking code by yourself for ten hours a day wouldn't want to participate in these kinds of programs."

One part of our Parallel Computing Laboratory effort is to write and apply design patterns for parallel programming. I attended a couple sessions of a seminar on this topic but it felt like a strange combination of formality (a design pattern has a specific format) and vague impracticality (e.g., it wasn't clear that a definition of the "dense linear algebra" parallel motif could offer much problem-solving insight). Like Nethack, it was a time sink, but unlike Nethack, it was not fun, so I left ;-)

The two people (one prof and one industry expert) who ran the seminar last time are offering the seminar again, but this time they plan to make the design patterns practically grounded by making participants use/apply them to an application (with actual code). I don't have time to attend this semester but I think their approach has a lot more potential.

Most programmers fall between the "wannabe manager" and "10-hour-a-day code cranker" extremes, but I do think even code crankers can benefit from being forced to discuss their code, communicate their ideas, and work at a "meta" level. It's just that the class needs to be practically grounded in order to interest such people. Any decent programmer, even as a student, has an aesthetic of design. It's good to tap into that aesthetic and bring it into the open so that students can learn that design isn't purely subjective, nor is it purely imposed from outside.

John said...

While on one hand that's true, I think it's worth reflecting on where that tendency came from, where people get involved with computing in their teens, in which a lot of programming is "taking my time to do what I want to do." It strikes me that suddenly turning this into a collaborative critiqued activity could be profoundly decentering, particularly given the time of transition in college. On the other hand, it could be argued that the formative art experience is the individual drawing for many hours alone. But, of course, that is a discipline that already has its institutional weight behind a critical practice. Here, the students and practitioners can say: it's not the way it was done, it's not the way I did it, it's not the way I do it, and therefore it's not the way it's done.

HilbertAstronaut said...

Re: "It strikes me that suddenly turning this into a collaborative critiqued activity could be profoundly decentering, particularly given the time of transition in college."

I think if it's done nonjudgmentally and in alternation with "10 hours of code cranking," it could be both beneficial and natural. But there is a risk of turning it into an alienating vague formality.

Real programmers do both kinds of work -- intensely solving a problem alone, and negotiating with others over design and requirements. Maybe it's good to begin a CS curriculum with lots of the former, and gradually transition to the latter to get students ready for industry.

John said...

I suppose I shouldn't argue too hard about something I believe is a good thing. What I was merely trying to show that there are many reasons, despite that, that a design-critique approach might be resisted.

My friend Dave L. noted that in the early days of personal computing, many programs flowed through magazines, from which you then typed in the code yourself. He credits this experience with his ability to read code.