Synchronizing with NetHack

One of the nastiest problems TAEB has to solve is also one of the most mundane. If you've ever played a game over a network or on a heavily loaded computer, you are probably familiar with lag and the problems it creates. While NetHack, as a turn-based game, does not suffer from directly lag-caused deaths, it is still very difficult to make moves sensibly when the responses are delayed.

Bots like TAEB also suffer from lag, indeed much worse than people do. Twenty milliseconds is quite unnoticeable for a human but is an eternity for a bot, and even at that timescale issues of finding the end of a turn are normal. Furthermore, bots are much less able to recover from partial updates than people are, due to the lack of sensible error-recovery.

Presumably, the player just exited a full-screen menu or changed dungeon level. A full screen redraw for NetHack is larger than the MTU of most networks, and due to lag, the second packet has been delayed significantly. (This doesn't require weird conditions; TCP normally waits until data has been successfully received before sending more.) As a result, the lower half of the current frame is black. TAEB, on seeing this frame, makes a couple of damaging inferences:

• The lower half of the level has turned into solid rock. This is an especially nasty case if the redraw was caused by stairs, as TAEB interprets large areas of new stone to indicate a brand new unexplored level, corrupting the dungeon graph.
• The bottom line is all spaces and unparsable, resulting in error spam and no stats.

Clearly, bots need a reliable way to tell when NetHack is done sending output for the turn. There have been several approaches to this problem over the years.

Consistently slow

One of the oldest and simplest approaches is simply to sleep for one second or so after every move, to wait for NetHack. This works, most of the time. It has two major flaws; first it is very slow, second it is unreliable - if lag spikes above 1 second, the bot may see an incomplete frame. Nevertheless, it is very simple to implement and has been used in several efforts.

Avoiding the issue

Another approach which has been historically used, most famously by the Angband Borg and Rog-o-matic, is to link the bot into the game's input routines. In theory, this is foolproof, but it carries dangers of a different sort, in addition to the obvious restriction to local games.

If done incautiously, the linking can affect game mechanics or leak information, thus compromising the validity of the bot effort. Modifying the game requires a very in-depth knowledge of NetHack's implementation, which is very unclean and non-transparent in places. Furthermore, requiring the bot to be linked into NetHack greatly complicates the build process; the bot cannot be built or distributed as a self-contained object unless all of NetHack is duplicated, prohibitive effort for many starting projects. As such, the linking approach is very rarely used.

We want TAEB to play in tournaments on public servers, which precludes linking.

Inline pings

One approach which is often proposed, but sadly does not work, is the inline ping. Simply send an invalid command after every real command, and wait for the error. Unfortunately, there is no command which is invalid in every context in NetHack. Not even control-r to redraw the screen; it fails in prompts and menus.

Telnet ping/pong

Invented by Sartak for NetHack fairly early on, and the most common method in use today (in particular, TAEB uses this), this relies on telnet as a side channel. A bot connects to a telnet server using a raw TCP socket, and implements the protocol itself; after every command is sent, the bot attempts to negotiate an invalid telnet stream option (DO 99).

When a telnet daemon receives the packet containing the command, it sees an option it does not support and responds in failure (WONT 99), then passes the command off to NetHack. Shortly afterward, NetHack's response is responded to the bot. Thus, the bot receives NetHack's response very shortly after the "pong". In effect, the telnet options are used as a side channel to dynamically measure network lag. Since under normal conditions network lag is the dominant component of total lag, this gives the bot a very good idea of when the output should be expected.

The reliability of this approach is improved by kernel packet coalescing, also known as Nagle's algorithm. When the pong is sent, the network implementation at the server waits a short time to potentially send a larger packet; if packet sending is low-priority, this will additionally tend to be delayed until NetHack is done calculating. With the pong and the response generally in the same packet, they are guaranteed to arrive at the bot at exactly the same time.

While good enough for bots, this approach is not quite foolproof. If NetHack takes a long time to reply to a command, due to system load, slow execution (there are several quadratic algorithms in the game, most notably monster movement and item stack sorting), or simply being swapped out, it is possible for the kernel to time out the attempt to coalesce, and the pong will arrive significantly before the output. This has been the source of several unreproducible errors in TAEB.

This approach is also limited to telnet servers. It does not help at all with lag as it occurs on heavily-loaded local systems, and does not work well with other network protocols. In principle SSH could be used, however the vastly higher complexity of the SSH protocol makes a custom implementation prohibitively difficult.

Expectations and Confusion

Will Noble (futilius)'s bridey works on an entirely different principle from the other bots. Instead of relying on out-of-band data to find complete frames, bridey is more like a human in that it waits for a frame that looks complete. The code which generates actions also provides a predicate for a sensible-looking result; fully filled bottom line, cursor on the character, etc. When an action is run, bridey waits for a frame that satisfies the predicate. To guard against programming oversights, the predicates are made partially dependant on wait time, and become more lenient as more data has had a chance to arrive.

Actually, bridey combines this with other mechanisms above; the time, as it is used in predicates, is measured in telnet ping/pong cycles. For instance, the move action has a final timeout of 4 cycles. This allows the reliability of the expect system to partially stack on the reliability of ping/pong. bridey, like TAEB, uses simple sleeps on the local interface.

Abusing POSIX Job Control for Fun and Profit

In 2008 I developed a novel method, which is currently being adopted by TAEB for the local interface. NetHack is single threaded and makes very little use of asynchronous calls, so when it is blocked on tty input it cannot possibly generate output until more keys arrive. So, if we could somehow find out when NetHack blocks, we would solve the synchronization problem permanently - unlike the methods above, this is immune to system load.

On the surface, finding out when a process blocks would seem to require low-level, privileged, and generally highly nonportable code. However, we are not the first user of the information. It is possible in UNIX to move processes between the foreground and background at will; if it were possible for background processes to read keyboard input, chaos would result. The traditional solution is for the kernel to stop any process when it attempts to read in the background. Stops, like deaths, result in wait() events; this is necessary in order that the shell may continue them.

With this insight, the solution seems fairly obvious - simply put NetHack in the background, then when it stops, let it read. There are a few complications in this, though. First, it's not possible to simply shovel data into a stopped reader; it has to be briefly continued in the foreground. How long is briefly? Depends on... system load. Fortunately, there is a trick we can use to eliminate inaccuracy - check for data on the virtual keyboard, with ourselves in the foreground. If we see anything, the slave needs to read more, and we re-continue it, using exponential backoff. Of course, data typed is not always immediately available due to line-buffering and various forms of special-key processing - but that applies to us too, so we still get the right answer.

Even with that settled, POSIX only allows a process to use job control if it lives inside the pseudo-terminal. That means, we need to fork a slave in order to do the actual manipulation, and communicate using pipes.

This is very unusual activity terminal driver, and it has exposed two bugs in the BSD kernel so far. First, in all known versions of BSD, a process which reads in the background does not actually receive the stop signal until it returns to user mode; but it returns to user mode only once the wait for terminal data completes! In regular usage, this is masked, because when you type bg all waiting threads are woken, but it was a killer for us; the eventual workaround I found was to briefly change the terminal blocking mode, thus forcing the kernel to reconsider all active blocks. Finding this bug, and the workaround for it, took an annoyingly long amount of time.

Another bug the project found was that the BSD kernel does a one-second sleep whenever a process that is already in the background tries to read. The reasons for this are quite unclear, but it has the effect of killing performance of this approach. Fortunately, recent versions of Darwin (OS 10.5.7 is known to work) have a rewritten sleep system, and this call is no more.

A comparatively minor issue was found in Linux; attempting to read from an idle psuedoterminal master fails with a "No such device" error, instead of the EOF return that would be expected of devices with pipe semantics. I'm not sure if this is a bug, but it did require workaround code.

This method is implemented in the IO::Pty::HalfDuplex perl module.

Variations on the theme

Job control abuse works pretty well on Linux and Darwin, but what if you're on a different platform? Well, there's always low-level, privileged, and generally non-portable code. As seems to often be the case with hacks like this, it usually takes the form of a debugger API abuse; set breakpoints on the functions that can read from the terminal, and arrange to capture output somehow. These approaches share a common liability; debugger interfaces are highly security-sensitive and are often in some way disabled.

• On most UNIXes (including the BSDs) there is a system call ptrace which fits the bill perfectly. Unfortunately, while the style of ptrace is virtually identical everywhere, no two UNIXes implement the call in exactly the same way. ptrace implements security by refusing to trace processes of other users and denying user and group changes while active; this is a real bother for us, as NetHack is normally installed setgid - it escalates its group to one that can write to the saves and scoreboard.
• Windows has a debugger interface which is well documented and consistent across versions. Nice? Well, Windows also has, last time I counted, 30 different documented ways to read from the console. Writing the correct traps to catch them all would be interesting, to say the least.
• Ironically, the best chances seem to exist on DOS. Programs are debugged by directly hooking the operating system, allowing for a fully consistent interface, and there are very few paths for keyboard reading. Unfortunately, CPAN on DOS is non-functional, and installing any large Perl system without it is extremely tedious.
• Departing from the trend of debuggers, it is also possible on the BSDs to simply read the process status. Compared to the ptrace method, this has the advantage of working on segid processes, but requires polling.

I plan to implement most of these in IO::Pty::HalfDuplex.

Conclusion

In the field of bot writing, even the simplest things can prove almost insurmountably complex. This is very evident in dealing with lag, both network and loading. Lag-related problems are a major cause of unreproducable faults in even the most sophisticated NetHack bots. Many of the simplest approaches to controlling lag are deeply flawed and will make debugging difficult. Let this be a lesson to everyone who wants to start from scratch. Fortunately, you don't have to; TAEB is designed to be a framework, to support additional AIs easily.

Anatomy of a Step

Several people have asked to see more articles about TAEB's architecture. Even after working with the codebase for a year and a half, I am still very happy with the design. My previous attempts at writing a NetHack bot lasted only a month or two before collapsing under their limitations. However, I think we finally got it right with TAEB, so I enjoy sharing what we have created.

To introduce the important components of TAEB, I am going to walk through TAEB's "main loop". We call each iteration of the main loop a "step". Each step vaguely resembles iterations of NetHack's own main loop. Note that this is completely unrelated to NetHack's turn counter. Due to the speed system, command repetition ("search for twenty turns"), and even paralysis, steps do not correspond with turns. The only similarity is that both counters increase monotonically. Today, we care only about steps, not turns.

Input

The first thing TAEB does is read input from NetHack. This can involve reading from a socket (as in TAEB::Interface::Telnet) or reading from a pseudo-terminal (as in TAEB::Interface::Local). I will eventually write a post about the mechanics of simply deciding when NetHack is done sending data. It is not at all trivial. (update: here's that post)

NetHack prints a stream of characters. Since it provides a full text user interface with two-dimensional maps and colors, NetHack prints escape sequences. These escape sequences encode commands such as "change the pen color to red" (\e[31m) or "go to cell (5, 12)" (\e[12;5H). We run all input through Term::VT102 to parse and handle these escape sequences. Term::VT102 then lets us ask high-level questions like "what is the text of row 23?" or "what color is cell (59, 6)"? We have a subclass TAEB::VT that lets us ask additional questions, such as "is the text 'Hit return to continue:' present on the terminal?"

We now have something resembling what the player would see (a two-dimensional, colored block of text). The next task is to understand what is on the screen. Consider the following NetHack terminal:

As a human, you can figure out a lot of what is going on, even if you have never played NetHack. You can see that the player is in combat with a goblin. From the bottom lines, you can guess that the player is stuffed with food, and probably the character's name. If you have played NetHack, you can recognize several more things. The character is a wizard (evidenced by the Evoker title). There is a general store in the top left room. The character is currently on the bottom of the screen, with a goblin just north of him. You can identify the seven rooms of the level, and the features of the dungeon (like stairs, a fountain, and many doors).

Such analysis is the job of two components, TAEB::ScreenScraper and TAEB::World::Cartographer. The Cartographer analyzes the map to populate internal level and tile information, while the ScreenScraper handles other input (mostly English text). The ScreenScraper runs first, parsing messages to publish announcements. The rest of the system does not have to worry about the content of messages, each component just listens for particular high-level events.

Thankfully, English text appears in fixed places on the screen; TAEB never has to guess which text is prose and which represents the map. Most of the time, text only appears on the top and bottom lines. However, menus can appear in more places on the screen.

Here we have an "identify" menu. The ScreenScraper can detect that there is a menu by looking at the text preceding the cursor. If it is "(end)" or "(# of #)" then TAEB knows a menu is on the screen.

Menus are interesting because they demand input from the rest of the system. The ScreenScraper does not know what items should be identified — it has to ask the AI component. Since there can be many menus in a particular step (such as identifying several items, one at a time), the ScreenScraper has its own loop for parsing different kinds of input. The various kinds of input include menus, prompts ("Eat what?"), location requests ("To what position do you want to be teleported?"), and ordinary top-line messages.

The ScreenScraper and NetHack may communicate several times before the next step is started. What is vital is that the ScreenScraper leaves NetHack in "action mode". There are no unresolved prompts, menus, --More-- messages, etc. This means that the Cartographer can assume that the cursor is on TAEB. This invariant makes TAEB cope perfectly with having a different character glyph due to polymorph or invisibility. Other bots (such as "moomaster") have struggled with this, since they guessed that the white @ on the screen was the character.

Since the ScreenScraper leaves NetHack in action mode, the Cartographer knows that every character between lines 2 and 22 inclusive are the map. If there were a menu on screen, TAEB would get massively confused, thinking there are suddenly hundreds of monsters floating in a void on the right side of the screen.

The Cartographer looks at each cell on the virtual terminal to update each tile in TAEB's internal map. It uses cell glyph and color to determine what is on each tile. For example, a gray { is a sink.¹ The sink is mapped to a TAEB::World::Tile::Sink object. This sink object of course knows things every tile knows, such as how many times it has been stepped on by the character, what items are on the tile, and what engraving is on the tile. In addition, sinks know whether they have produced a black pudding, ring, or foocubus through kicking.

One curiosity is that the map is updated after we publish messages from the ScreenScraper. If TAEB moves and receives the message "You see here an opal ring", the ScreenScraper sees that and announces that there is an opal ring on the current tile. However, since the Cartographer has not run, the current tile has not been updated yet, so the item would be incorrectly added to the previous tile. The crude solution we currently use is to freeze the publisher until after the map has been updated. We are not yet sure of a better solution to this.

Output

At this point, the map has been updated, all input from NetHack has been parsed, and the appropriate announcements have been published. We then redraw the screen for the users watching the bot play. We also check if the user typed a key. TAEB has many debug commands, such as ~ to open up an interactive REPL to inspect and change TAEB's internal state.

Finally, it is time to involve the AI. TAEB simply asks the AI "what now?" This can involve arbitrarily complex calculations. One of my favorite features of TAEB's design is that its AI is pluggable. TAEB requires only a few methods be implemented by the AI, and we are working to trim that down to just "what now?"

There are currently two AIs being developed: Behavioral (by most of the core team) and Planar (by ais523). Both are worthy of many posts. We hope to entice more developers to work on TAEB AIs! One of our future projects will be Interhack on top of TAEB. The intelligence of a TAEB::AI::Interhack would not actually be "artificial", of course.

Since TAEB is a framework, the AI will inevitably be tightly-bound to TAEB (though, as explained, the converse is not true). The AI is expected to call all sorts of methods on TAEB objects, such as "am I currently blind?" (TAEB->is_blind), "do I know the identify spell?" (TAEB->find_spell("identify")), "is there a fountain on this level?" (TAEB->current_level->has_type("fountain")), and so on. We think this is a huge boon to developers seeking to write NetHack bots — they can focus solely on the interesting bits of artificial intelligence. We handle the programmatic NetHack.

The AI tells TAEB what to do each step through TAEB::Action objects. These abstract away the details of interacting with prompts and menus. The AI can say:

    sub next_action {
        # ...
        if (my $lizard_corpse = TAEB->find_item("lizard corpse")) {
            return TAEB::Action::Eat->new(
                food => $lizard_corpse,
            );
        }
        # ...
    }

The action will take care of responding to the "Eat what?" prompt with $lizard_corpse's inventory letter. The action will also respond to unexpected prompts, such as "There is a fox corpse here; eat it?". This declarative nature pervades TAEB's design to great effect.

Finally, we send the keystrokes for the current action (such as "e" for eat) to NetHack.

The action will participate in the next iteration of the main loop to respond to prompts and listen for events caused by the action. For example, if TAEB receives the message "You stop eating the lizard corpse", then the action will know not to remove the lizard corpse from the inventory.

Conclusion

The design of TAEB's main loop has had a significant impact on its (relative) longevity. The design of handling all of the input from NetHack as soon as possible drove much of the system's design in very positive ways. It encouraged the reification of Actions, which has been immeasurably useful. It even encouraged the addition of the pubsub system and its later enhancement to announcements. Though there are still some lingering quirks caused by this main loop design (such as teleportation traps), none seem insurmountable.

---

Footnotes

1. TAEB remaps some dungeon features to avoid conflicts; in core NetHack, sinks are gray #, but so are corridors. Eventually we may be able to remove some remappings due to increasing Cartographer sophistication, but there's no rush. TAEB does not change too many characters as to render its NetHack screens unfamiliar. (back)

TAEB 0.03

registering upload with PAUSE web server
POSTing upload for TAEB-0.03.tar.gz
PAUSE add message sent ok [200]

This is the first version that is actually going to be on the CPAN. I decided to put up with Module::Install for a little while longer. :)

TAEB, pubsub, and announcements

TAEB is a decently-sized, componentized program. Components need to be able to communicate with each other. For example, the Senses component (which tracks the state of TAEB's character) needs to know when we are indebted to a shopkeeper so that it can respond to the AI when it asks if TAEB is in debt, and for how much. The Cartographer component (which tracks the state of the dungeon map) needs to know when TAEB becomes indebted so it can mark the current room as a shop. In general, we want any component to be able to listen for any update. This will let us remain flexible and extensible; the completely-separate AI can listen for any update that the framework can.

We use the publish-subscribe pattern to control this complexity. Pubsub decouples those who generate updates (publishers) from those who listen for updates (subscribers). TAEB has been using pubsub for a long time now (since 2008-01-06, according to darcs trackdown). To publish a message, anything in the program can call TAEB->enqueue_message("foo" => @arguments). This will call the msg_foo method on all subscribers with arguments @arguments. We have a component, Publisher, that acts as message broker.

Pubsub has been a great tool for letting TAEB understand messages from NetHack. We have a component that is devoted entirely to figuring out what the current state of the screen is telling us: the ScreenScraper. The ScreenScraper deals mostly with transforming characters on the screen into published messages. For example, when the NetHack prints the message "You owe (somebody) (some amount of) zorkmids.", the ScreenScraper publishes a debt message with one argument: the number of gold pieces TAEB owes. The Senses has a msg_debt method that stores this amount of debt in an attribute. The Cartographer has a msg_debt method that floodfills the current room's tiles with the shop bit. The ScreenScraper does not need to know who cares about debt. The ScreenScraper publishes a lot of messages that no component subscribes to yet, and that's okay!

I'm happy with this, but there is room for improvement. Simple methods are not great message handlers. There are painful bugs lurking when subscriptions interact with inheritance. Suppose the AI defines a generic "go to a specific tile" behavior. This behavior would need to handle walked so it can track TAEB's progress. This GotoTile behavior is then subclassed to produce behaviors such as GoUpstairs and GotoCorpse. GotoCorpse might need to handle walked so it can age the corpse (so that TAEB doesn't eat rotten corpses). When the publisher sends the walked message to the GotoCorpse behavior, it does not invoke GotoTile's msg_walked method, because GotoCorpse didn't invoke it. While you may argue that GotoCorpse should have known to invoke GotoTile's msg_walked as that is part of its public interface, it certainly sucks for usability. It's especially painful when GotoTile begins subscribing to walked months after GotoCorpse is written!

The potential fixes for this are easy. The one I like best is providing some "subscribe to a message" sugar. Where we previously wrote sub msg_walked { ... }, we would now write message walked => sub { ... }. This sugar would handle publishing to parent classes if there are any. It would still use method calls behind the scene; message would install a msg_walked method. This gives us maximum flexibility. A subscriber could define an unusual message that would only conditionally be published to its parents.

The arguments we pass to each method could be improved as well. It's not immediately apparent what arguments the msg_debt method would receive. Currently we pass the amount of debt. However, we should also be providing the name of the shopkeeper TAEB is indebted to. This would help the Cartographer resolve ambiguities when there are multiple rooms and shops in sight. Should we rewrite every msg_debt method (including those potentially written by third-party, unknown AI hackers) to take named parameters? Should we pass in the shopkeeper's name as the second parameter? Should we pass in the name as the first parameter? After all, the name does come first in the message NetHack prints. We could provide one positional parameter (amount) and one named parameter (shopkeeper). Hey wait, it would be useful to also pass which items we're buying as well...

The best answer is to make each message an object. We would have a TAEB::Message::Status::Debt class with attributes amount and shopkeeper. This class could have a method to ask the inventory what items are currently in TAEB's shopping cart. If we're feeling cute, we could even overload this message to stringify to the amount of debt.

Pubsub with objects as messages is generally called Announcements. The concept of announcements is more general than pubsub. Announcements lets subscribers of a message communicate with the other subscribers, and even with the publisher.

Currently, when NetHack presents TAEB with a menu to select which items to pick up, TAEB will ask the AI whether it wants to pick up each item. The AI is asked about the item without the context of the other items that it can pick up. This really sucks! If TAEB is toeing the burden line, it needs to be pretty strict about what items it will pick up. This means it may refuse to pick up a useful item because there just might be an even more useful item further down the list.

Instead, TAEB should publish a "pick up items" announcement. This announcement, TAEB::Message::Query::PickupItems, would have the list of items. Subscribers would select which items they want by invoking methods on the announcement. When all subscribers have had a chance at it, the ScreenScraper would select the items in NetHack's menu accordingly. The selection doesn't have to be binary either; each subscriber could assign a numeric "desire" to each item. The ScreenScraper would then select items that have a sum desire greater than some cutoff (which would be another decision that some subscriber could set). Using announcements would better decouple the AI from the framework.

This is not the first time that turning plain strings into classes has been a major improvement for TAEB. Previously, the AI would return a string, a NetHack command, as the action to perform next. We then reified actions into classes. Letting the current action subscribe to messages, and respond to NetHack prompts, vastly improved TAEB's interactions with NetHack. Problems with unexpected prompts (such as "Eat this corpse on the ground?") quickly and completely vanished. Actions subscribing to messages lets us handle ambiguous messages better; if we just applied a unicorn horn, then we can figure out that "You feel sick." means the unicorn horn was cursed and TAEB can mark it so.

TAEB does not have announcements yet, but that's my next big project. I'm excited by the many possibilities here.

Predicting and controlling NetHack's randomness

NetHack, being a single-player game of imperfect knowledge, incorporates a large element of randomness. Random numbers control how much damage that minotaur will deal you, what the identity of each purple-red potion is, whether dipping into that fountain will net you a wish, etc. To generate random numbers, NetHack employs a pseudorandom number generator. Wikipedia says:

A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's [seed].

Because NetHack uses a PRNG, providing identical input to two separate games, sharing the same seed and PRNG algorithm, will lead to the same results in each game. This should not be surprising as this is a property fundamental to PRNGs. The input must be identical for both games, otherwise the games will diverge; on the same turn, casting a spell in game A will do a different amount of damage than simple melee in game B. Since the two actions use a different amount of random numbers, it would be annoying (but not difficult) to reconcile the two games.

NetHack uses the current time (specifically the number of seconds since midnight, January 1st, 1970) as the seed for its PRNG. Thus, two games started in the same second will have the same seed. You can verify this by typing "nethack" into two separate terminals, then quickly hitting enter in each. Once you select the same characters, you should be greeted with the same map and stats. If not, your clock may have ticked between starting the two games, so just try again. If you play both games identically you'll see that you obtain the same results in both games. You can, of course, diverge once you experience very unfavorable results in one game, such as death.

That's a lot of work just to fool the game. If you're going to those lengths, you're better off playing in the immortal "explore mode", or changing the code so that it's easier to win. These are some of the reasons that "public server ascensions" are more highly valued than local ascensions. You can't change the code on the server, or play in god mode, so everyone knows that your server ascensions are legitimate.

However, public NetHack servers still use PRNGs, so there still exist some serious exploit vectors. On the nethack.alt.org public server, I abused the PRNG for demonstrative purposes (though never for actual ascensions). On the WowDeath account, I killed myself by kicking wands of wishing on the first level — three times in one day.

Though NetHack uses the current time for its seed, it's very easy to change that to be, say, an option to NetHack. You can tell NetHack to start a game in advance, fooling it into thinking it's 11:00:00. If that game doesn't work out so well (perhaps you got a lame starting inventory), you can try again, using a seed 11:00:01. Repeat until you find a great starting haul, then start a game on the server at that exact time. I went one step further, generating thousands of starting levels until a wand of wishing was created as part of the initial level. paxed, one of the admins of nethack.alt.org, patched nethack to use a truly random seed so that this specific exploit can no longer be used on that server.

The trickiest part, which was the only point of failure, was in starting a game on the server at some exact second. Due to clock skew, the server could think it is several seconds (or even minutes) earlier or later than your clock does. The server doesn't broadcast what it thinks the current time is, either. One way to actually figure out the current time is through the random seed! Start a game on the server, noting the current time on your clock. Then generate NetHack games for that time, that time plus a second, that time minus a second, plus two seconds, and so on until you get the same starting map and stats. The offset you used is the number seconds between your machine and the server, so you can use it to know exactly when to start a server game. It's still not as exact as I would like, since you only get resolution of a second.

That method actually describes a distinct avenue of exploitation. Since you now have a server game and a local game with the same seed, you can play the local game (remembering to mirror the input to the server game as well) until you get to some point at which you want to diverge. It's actually more powerful than even that, because you can modify your local nethack to display object identities instead of appearances, or not require exploration for the map. You will appear to have x-ray vision or prescience to the audience of your server game.

This was actually how I was introduced to practical methods of exploiting nethack's PRNG. A nethacker named switch told me to start up a game and wait. He then said "See that gold in the upper right corner of the room? It has 70 gold pieces in it." That was viciously consternating. What he had done is what I described in the previous paragraph. He found my game's seed then looked at the pile of gold before I did: prescience.

nethack.alt.org has patched the initial seed calculation, but as nethacker Adeon has demonstrated, it's still feasible to figure out the game's seed by observing random effects. Being able to observe random effects without advancing the game's state is very helpful in sussing out the game's seed, since monsters moving, level messages, and many more per-turn effects use an unknowable amount of random numbers. By using something similar to the artifact naming exploit, you can observe the effects of a knowable amount of random numbers. Adeon has code that will do exactly this for server games. Once you have the seed, you're in control of the random number generator. You can trash as many random numbers as you want by using the same actions you used to figure out the seed. This will let you make every fountain quaff produce a wish by throwing out every random number that wouldn't produce a wish.

The fix for this would be to re-seed the PRNG every n (say, 100) random numbers. That way, well before you have a chance figure out the current seed, a new one takes its place. Re-seeding must use true random numbers. If not, the re-seeding is useless; pseudorandom seeds fall victim to the same exploits. [Update March 3rd: paxed has patched this fix into nethack.alt.org as well]

You might wonder why we use PRNGs at all; why not use a truly random source for every number? Unfortunately, a computer's pool of truly random numbers is very limited; it has to build up by measuring minute temperature changes or internal timing variations. NetHack, especially being played by fifty people on a public server, would keep that pool empty and harm the game's playability.

This type of exploit could affect many single-player games like NetHack, but I don't think there would be value in doing this for other games, since one of the preconditions is that server play is more highly valued than local play. Commercial games use closed-source servers anyway. The real applicability of these techniques is in cryptanalysis. Use truly random numbers for your keys!

Where's 0.01?

Due to an issue with Module::Install, the 0.01 tarball I uploaded to CPAN last night was empty. I've long disliked Module::Install, so I'm going to get rid of it in favor of a plain ExtUtils::MakeMaker or something.

Update June 3rd, 2009: The issue with Module::Install was that it generates an empty tarball when there's no MANIFEST. More recent versions of MI are thankfully very reluctant to do that.

0.01

registering upload with PAUSE web server
POSTing upload for TAEB-0.01.tar.gz
PAUSE add message sent ok [200]