Seeing the Snakes

A contest update, and a follow-up to Hunting Zombies: what static code analysis finds that tests miss.

A contest update: twelve new held-out sessions

The teleport challenge has been running for almost six months! Porting NetHack to JavaScript is hard indeed, even for our superhuman AI code assistants. None of the contestants so far have been able to perfectly reproduce all the sessions, including the transpilers, which translate the C mechanically instead of porting it "by hand". But several of you have gotten very close, with scores in the high 90 percent! In particular, the transpiled entry from NoahBPeterson matches 99.996% of screens, only one screen short of perfect parity on the original 88 sessions.

Remember that the contest remains open to all comers. And remember that in a month, I will snapshot your code and announce a phase 2 challenge that will challenge you to develop a new revision of the code that pursues a new objective, to test the flexibility and maintainability of your code. Before phase 2, it will be helpful for your phase 1 ports to be as perfect and as well-structured as possible.

So as we enter the last month of phase 1, I am adding 12 new sessions to the held-out set, bringing the total to 100 sessions (44 public and 56 held out). These gameplay sessions exercise a few more scenarios, events, and actions in the game, and they give a slightly more complete view of how accurate each implementation is. Every contestant has some new blind spot among them, so they should help serve as a guide to perfecting the ports. On a preview scoring run today, no entry matched every screen of the twelve new sessions:

The two leading transpilers have the most perfect new sessions, serteal with 9/12 and NoahBPeterson with 7, but neither gets everything here. And several of the other ports are very very strong. I am impressed at how well the ports are doing in completely novel sessions that none of you have had any exposure to before.

How did all the contestants get so strong?

This is a good moment for a code review of the submissions. This time, let's look beyond the code and into the development processes you've been using.

Two ways to hunt

Last time I wrote about Hunting Zombies, and pointed out that testing is much stronger if it goes beyond visible outcomes and looks at the hidden variables. Now many contestants have taken up the zombie-hunting approach, with lots of clever ideas that I will write about in the future. Many of the contestants are taking measures to make hidden state observable, compare it after every keystroke, and fix any internal state that disagrees.

But now another trend has emerged among the contestants: static code analysis. Instead of only looking at tests of gameplay, many of you have been analyzing the structure of your code directly, looking for places where the JavaScript, structurally, cannot possibly be doing what the C does.

Unlike zombie hunting, code analysis can find a bug that no recorded game has reached yet. That helps explain how you can do so well on a deeply held-out test set like the new test sessions, where you have no idea what corners of the code new hidden sessions might exercise.

Transpilation is the most extreme version of code analysis, since all the transpiled JavaScript is the output from a detailed compiler analysis of the original C code. But the agentic contestants have also been developing code analysis methods to supplement their work. Some of these are very simple but powerful.

Reading code to find hidden snakes and eels

Let's consider a simple approach used by richie3366, the hand port with the highest screen score on the new never-seen-before held-out sessions.

In NetHack, some monsters can hide. An eel lurks under the water, and a snake can hide under a pile of stuff on the floor. But if you try to move onto a square where one is hiding, the game does not let you blunder into an ordinary attack. Kindly, it stops you and reveals the monster. Here is the code, in attack_checks() in uhitm.c:

if (mtmp->mundetected && !canseemon(mtmp)
    && !glyph_is_warning(glyph)
    && (hides_under(mtmp->data) || mtmp->data->mlet == S_EEL)) {
    mtmp->mundetected = mtmp->msleeping = 0;
    newsym(mtmp->mx, mtmp->my);
    ...
    else if (Blind || (is_pool(mtmp->mx, mtmp->my) && !Underwater))
        pline("Wait!  There's a hidden monster there!");
    else if ((obj = svl.level.objects[mtmp->mx][mtmp->my]) != 0)
        pline("Wait!  There's %s hiding under %s!", ...);
    return TRUE;
}

The problem with this chunk of code is it describes a slightly rare event, one that is never exercised by any of the 44 public test sessions. How many games would you have to play to run into an undetected eel in a pool of water? By the time September came around, richie3366 had never tested this situation and their JavaScript code was totally missing these branches.

On the other hand, the gap is easy to see on a quick code inspection. The string literal "Wait! There's a hidden monster there!" appears clearly in the C source, and if that string never appears in your JavaScript codebase, you know that you're missing something.

So if you can make a list of all gameplay strings in the C that do not appear in the JS, they will give you a map of potentially unimplemented pathways in the code! Finding all these pathways through exhaustive testing could take months. But compiling the list of strings takes a few seconds.

A map of missing strings

richie3366 wrote exactly this tool, which they called c-literal-coverage.py. It takes every string of 14 or more characters on a line of the C source that prints a message, and looks for its longest fixed piece (slicing out the C-style % format codes) in the JavaScript. Running a corrected version of it retroactively over their history shows how well this strategy tracked the progress of their port.

As you can see, the day after richie3366 scored perfect on public tests, they were missing more than 2000 strings in the JS, an excellent map of code paths their tests had never visited.

But as clever as this idea was, richie3366 did not actually devise and use the string-comparison tool until very late in the process. It was committed on October 13, as one line item in an overhaul of their rules after their held-out score had been stuck at 22 for two days. The same overhaul required complete data tables, and with this tool in hand, they were able to go from 22 to 35 held-out sessions correct. By then the port was already down to about a hundred missing messages: months of porting, including the breadth phase described below, had closed nearly all of the gap before the tool was used.

The Massive Middle

Before that, richie3366 spent many weeks dealing with an interesting problem that all the contestants faced. In July, they had exhausted the public tests with a perfect 44/44, and yet the NetHack codebase, with more than 5,000 C functions, was too massive to review and port all at once.

What to tackle first? I found it interesting to see the contestants try several ways of choosing what to port next. Here is the path richie3366 took.

July. Public sessions: 44/44 by July 21. They worked from the public sessions, fixing the code at the first point where a session diverged from C. Commits read like "so seed0002 RNG matches through music".

August to mid-September. Held-out: 6/44 on September 3, 11/44 by September 17. With the public sessions exhausted, they walked a function-by-function map of the C against their JS and ported whatever it listed as missing, with a second model reviewing each commit against the C. They also recorded hundreds of private C sessions and chased those divergences one at a time. But the approach stalled: their private corpus passed 91.7% while their official held-out score sat at 11/44.

September 18 to October 6, "breadth". Held-out: 11 → 16. Screens: 50% → 64%. Missing C messages: 677 → 121. Here is the interesting turn. richie3366 decided to port the game as completely as possible first, using a hybrid of code analysis and agentic coding. They ranked unported C functions by the call graph: how few calls separate each one from the main turn loop, how many callers it has, how often it rolls dice or prints, and whether the functions it calls exist in their JS at all. That gave a top-down ordering, and they walked through the codebase in that order, first porting the top functions whole, and later whole C files of 40 to 100 functions at a time. They wrote a huge amount of code, but the held-out score rose only modestly, and then sat flat for about 50 iterations.

The modest gain seems to come from how they checked the work. After porting a function, their loop re-ran the passing sessions whose C trace went through it, and rejected the change if any of them broke. That catches regressions, but it cannot tell you whether the new code is right, and if no session reached a function, nothing checked it at all. Breadth was, by design, a code analysis approach. It was about porting exactly the parts of the code their tests did not touch.

October 6 to 13, "cliffs". Held-out: 16 → 22. They went back to divergences, now in a private test corpus they had grown to about 950 sessions aimed at the areas their tests had missed, and they worked first on the divergences that threw away the most dice rolls.

October 13 onward. Held-out: 22 → 35 by October 20. After two days stuck at 22, they generated complete data tables from the C data files and wrote the string-coverage tool.

What worked was not giving up on breadth but building tests to go along with it. Breadth was something richie3366 needed to create a comprehensive implementation, but it did not get them to high accuracy on its own. Each branch still had to be ported correctly, and for that, they did need tests.

Reading the C without a test

daoa0601 also ran the purest form of code analysis in the contest. Once their local pool of 2,500 generated sessions was passing, they assigned agents to "C-source audits of files the corpus barely runs".

Each of daoa0601's audits reads one C file (trap.c, zap.c, role.c, the quest arrival code in do.c), comparing it against the port, and fixes what differs based on the code inspection. A second model reviews each fix against the C. Meanwhile, every fix must come with a test that fails before it.

This discipline paid off handsomely on hidden test performance. On October 24 when they made a rapid gain of six held-out sessions, three of the wins came directly from these audits:

• two from an audit of quest text and arrival order. It found that C prints the familiar-level message before the quest leader's summons, so the random draws happen in a different order;
• one from an audit of role.c.

Two more came from another insight.c port (the attributes shown when the game ends), and one from a character-creation menu fix.

What remains missing

Several of the contestants have been using code analysis the way richie3366 and daoa0601 do, to set the agenda for the coding agents to prioritize or review their work.

But I think that there is still room for all the ports to benefit more from detailed static code analysis. It only takes seconds to extract a call graph, to pull the constants, to analyze and compare the C and JS code to identify structural differences. It is, potentially, much faster and cheaper than trying to guess at missing test sessions.

Running a corrected version of richie3366's string-literal comparison script over the current code of the six strongest agentic ports gives the following stats:

(The second column leaves out files that are mostly error handling, options parsing, file I/O and debugging output.)

All the ports are missing a little something, but each port is different. Few of the missing pathways are shared by more than two ports. They cluster by subsystem: one port is thin on sinks, another on drawbridges, another on kicking objects or on engulfing.

That matches what the new held-out sessions show. Every contestant has blind spots, and they are mostly not the same blind spots. But a simple static code analysis can give you quick insights.

What else the contestants are analyzing

The string map is one of several static analyses running in the contest. A quick tour:

Missing await. In a JavaScript port of a single-threaded C game, every function that can wait for a key has to be async, and every call to it must be awaited. A call without await runs only until its first pause. Everything after that happens later, after the caller's next dice roll or message. rohitgandikota's tools/unawaited.mjs lists every statement-level call of an async function that lacks await. Its header records the bug that prompted it: a demon's cuss() left its neighbours asleep. daoa0601 gets the same check from the type checker, with no-floating-promises and no-misused-promises as errors. NoahBPeterson's transpiler has to solve the same problem from the other direction. It computes, over the call graph, which functions can reach a keystroke read. It computes this once on the C syntax tree and again on the generated JavaScript, and fails if the two disagree.

Type checking. daoa0601 wrote their port in strict TypeScript, with noImplicitReturns, exactOptionalPropertyTypes and an exhaustive-switch check, and with any and @ts-ignore banned. A function that C declares as returning a value cannot quietly fall off its end. (Our own reference port found eight commands doing exactly that this week. They returned undefined where C returns ECMD_OK.) Others get part of the benefit without a type system. vtjeng checks that every ns.NAME read on an imported module names something the module actually exports, because otherwise it silently evaluates to undefined. rohitgandikota checks for unbound names and missing exports, and an audit pass of richie3366's loop found ten latent ReferenceErrors the same way.

One copy of each function. vtjeng's check-duplicate-symbols.mjs looks for C functions ported more than once. It found 13. Three of them disagreed with each other, and artifact_light() had five copies whose null checks differed.

The C compiler as a checker. rohitgandikota generates a C file with a _Static_assert(NAME == value) for every constant the JavaScript uses, and compiles it against the real headers. They report that it found 45 wrong values among 1,661 names. Nearly every strong entry extracts its tables with the real C preprocessor or a small C program, never with regular expressions.

Formal proof. daoa0601 is the only entry attempting real formal verification. A symbolic executor for C (working from clang's syntax tree) and one for JavaScript share an abstract random stream, and Z3 proves the two sides equal for every input in a stated domain and every random sequence: the same return value, the same draws consumed, the same log entries. So far it covers ten small functions: the RNG wrappers (rn2, rnd, rn1, rnl, d, rne, rnz, the display RNG) and two distance functions. Mutated versions must fail the proof, which guards against proofs that pass for the wrong reason. A companion pass uses the TypeScript checker to find every call site of an RNG function, about 2,353 by their count, and asks the solver whether each argument stays inside the proved domain.

Assigning a screen to its C function. richie3366's held-out proxy matches the first differing line of a screen against every C string literal, so that a screen-only divergence is charged to the C function that prints it, the way an RNG divergence is charged to the function that rolls.

What nobody is doing yet: the call graph

Code analysis is a powerful technique, and I do not think the contestants have yet gotten all the benefit out of it.

Most of the analyses above look at nodes: does a function exist, does a string exist, does a constant have the right value. Several entries keep lists of C functions and mark each as ported. richie3366's ledger even extracts the C call graph, but it uses the edges only to rank work by how reachable a function is. xeophon's C inventory says the limitation plainly in its first line: "A JavaScript symbol with the same name says nothing about its missing branches or callers."

The next step is to compare the edges. Tally the static call graph of the C, tally the static call graph of the JavaScript, and line them up function by function. Every edge that C has and JavaScript lacks is a specific place to audit. Every edge JavaScript has and C lacks is another.

Here is that comparison for one function, mount_steed(), which runs when you try to climb onto a saddled pet with #ride. Knights start the game with a saddled pony, so it is an ordinary thing to do. The C function is about 190 lines and calls about 45 different functions, most of them checks that stop you from mounting: you are hallucinating, your legs are wounded, the pony is trapped, your armor is rusty, and so on.

For each strong hand port, I listed the functions C's mount_steed() calls that the port's mount_steed() never reaches, then read the code to throw out renames. Six calls are left; here are four of them. richie3366, lockwo and daoa0601 make every one of these calls, so only the other three ports appear:

Each of these three has a different blind spot:

• jon-bell goes straight from the tameness check to the saddle check, skipping the underwater test, so you can mount a non-swimming steed while underwater.

• vtjeng prints "You touch the cockatrice." and then calls note_unported('trap.c instapetrify'). That is an honest label for an unfinished branch: the hero should turn to stone, and does not.

• rohitgandikota, whose fork last changed on September 12, is missing all four. The quietest is the tameness rule. In C, every time a non-Knight tries to mount, the steed loses a point of tameness:

  if (!force && !Role_if(PM_KNIGHT) && !(--mtmp->mtame)) {
      /* no longer tame */
      pline("%s resists%s!", Monnam(mtmp),
            mtmp->mleashed ? " and its leash comes off" : "");

  Without that line, a Valkyrie who tames a pony and tries to ride it a few times leaves its tameness unchanged. Nothing on screen changes until much later, when the pet behaves differently. This is a zombie in the sense of the last post: hidden state that the screens do not show. A call-graph diff finds it without a single recorded game.

  The missing test_move() is the more ordinary bug. Without it, a hero standing in a doorway can mount a pony on the diagonal, which C forbids. rohitgandikota checks Fumbling in its place. C does test Fumbling, but later, as one of the reasons you slip while mounting.

Many of these gaps are invisible to the string map. I compared these few functions with a hundred-line script. Over the whole program the raw diff is large. A crude version that ignores helpers reports between 2,800 and 6,600 missing C edges per hand port. But there are many mismatched names, macros, and moved code that make it tricky. So the work is in making the comparison precise.

When code becomes too large to read, the code itself can still be read by a program.