From the article: [...] [...] [...] [...] [...] [...]
From the article:
In the years that followed, NetHack continued to inspire and challenge us. The first Antithesis VCS repo (long since deleted) was called “fuzzhack” because it was a fuzzer for NetHack. Before we built our deterministic hypervisor, we tried Hermit-style deterministic Linux userland because it’s the bare minimum you need to beat NetHack. NetHack inspired our thinking about the importance of strategy, about the importance of code coverage and also about its inadequacy, and about why you need intrinsic curiosity rewards to have any hope of applying AI to this problem. NetHack inspired many of our early experiments in visualization. Wanting to interactively explore NetHack performance and coverage maps is why we wrote the first version of the reactive notebook that now powers our UI. Processing reams of NetHack data that wouldn’t fit in memory was why we decided to put a GCP subscription on my credit card so we could crunch the data in BigQuery, which later led us to invent skip trees, and finally Pangolin.
All of this is because it was a worthy adversary – perhaps even what my colleague David MacIver likes to call a “dragon problem.” NetHack is famously difficult for human beings because it combines permadeath, extreme information scarcity (reading the source code of the game to figure out how to beat it is practically a rite of passage for aficionados), and a brutal intolerance for error. But it’s also very difficult for autonomous systems like fuzzers and AI agents due to its sprawling state space and to the need for long-horizon planning to make any real progress. People have written bots that have successfully beaten the game, but despite Meta’s investment in the NetHack Learning Environment, AI agents have struggled with it. The wins that both the hardcoded bots and the AIs (most recently GPT-6 Astra) have eked out have been skin-of-their-teeth affairs involving lucky seeds and “beginner-friendly” roles. Nobody has produced a system that can reliably and quickly beat the game over and over again as any character build.
[...]
Antithesis can now find a path to victory within 5 wall-clock minutes on nearly 80% of NetHack seeds. Moreover, the median time to victory within the seeds that finish is under 2 minutes. To explain how we did this, we need to let you in on a secret: Antithesis is not just a system for unopinionated state space exploration, it is also something akin to a probabilistic programming language, a new computing paradigm for partially describing tests or other tasks and letting search and optimization fill in the rest. When you put this tool in the hands of capable AI agents, they can do things like beat NetHack in 30 seconds. But first… back to our story.
[...]
This is a common class of bug in video games. Let’s call them distribution bugs: in any timeline where you see the bug, it’s impossible to see that there is a bug, because the observed outcome could just come down to luck. The Gen 1 same-type bug is my favorite example of this, because it shows just how hard it is to notice distributional bugs – every simulator and every player’s model of the game was wrong for 16 years! – but there are many others. The Pokemon series also had the catch rate bugs, where claimed multipliers to success chances were never applied, and the Focus Energy bug, where a move intended to quadruple the likelihood of a critical hit instead divided it by 4. In the first Final Fantasy game for the NES, the routine to roll for a critical hit looked at the wielded weapon’s index number instead of its critical hit chance, and the Thief’s bonus to the success rate of fleeing from battle was never applied. More recently, a prerelease of Slay the Spire 2 was found to have such extreme RNG correlation that certain items intended to be obtainable as drops were impossible to get in normal play.
[...]
What does it take to find a distribution bug? Once you suspect you have a distribution bug, you can perform a statistical analysis of many simulated timelines – but you first have to suspect you have a distribution bug. For this reason, distribution bugs are often discovered by close analysis of code (as with the Body Slam paralysis chance bug) or mass computation of simulated timelines by other means (as with the Slay the Spire 2 RNG correlation) rather than observation. Finding a distribution bug isn’t hard once you suspect you have one, but to get to the point where you suspect you have one, you first have to stop believing that you were just unlucky.
[...]
After seeing this tweet, Will offhandedly mentioned that it might not be much effort for our research platform to support NetHack. I bit. Soon after it was up and running, Paul found the config overflow. Right after that, GPT-6 Astra beat NetHack.
Beating NetHack was still not exactly the company’s top priority. But we were so close! I decided to see what I could do.
The super-fast iteration loop is nice for humans. But it’s pretty much a necessity for effective LLM use. And since I’ve never played NetHack, and Paul was preoccupied with real work, we weren’t going to ascend without relying heavily on Claude. Custom strategies leverage domain knowledge, and I had none.
[...]
At the start of this post, we said Antithesis is something like a probabilistic programming language: a way to partially describe a task and let search and optimization fill in the rest. Here’s what we meant. Player’s plan for the early game fits in a sentence: sit on thrones and drink from fountains until you have all the wishes you need. It doesn’t say how to get the wishes. Nothing could – a sit on a throne only grants a wish one time in 39, and if it doesn’t, it can curse you, surround you with enemies, or vanish. But we can throw those other 38 timelines out. We tell the fuzzer how to sit on a throne, we tell it that a moment with one more wish beats the one before, and we tell it how to shake the dice. The fuzzer does the rest.
[...]
This partial specification paradigm has three advantages.
First, it lets you do less work. Any bot needs three kinds of knowledge. The first is how to act: how to turn “put seven candles on the Candelabrum” into keystrokes. These are the tactics. The second is a vision of the good: high health, great strength, alignment with your god, and a magic silver saber. This is the strategy. The third is foresight: knowledge of the paths from here to there, and of how to recover from a misstep. This is what search replaces. BotHack needed 16,000 lines of Clojure and Astra needed a trillion or so dollars of CapEx; our fuzzer ascended with a short config file, and I hear Antithesis has received a tiny bit less funding than OpenAI.
Second, it’s more robust to evolution of the system under test. If you move a block in Super Mario Bros., your scripted run might fail, but partial specification doesn’t care. If you change the CSS of your website, your scripted tests won’t know where to click, but Bombadil will. And if your partial specification can ascend a Valkyrie, it can probably ascend a Wizard.
And finally, it can find unknown unknowns. The usual way to gain confidence in a program is to understand it: to read the code really hard, reason through the logic, and try to consider each case. Few programs have been read harder than NetHack. Its players have been source-diving for decades, and there’s extensive documentation for nearly every mechanic. We read it too. Reading is how we found the 1-in-39 wish chance and the Grimtooth naming trick. But years of reading never turned up the del_light_source bug. The fuzzer found it by wandering into it. So did its eventual reporter.
Every piece of that bug was known. A quest artifact blasts a hero whose alignment is negative, even its rightful owner. A player’s polymorph is an opportunity for artifacts to blast. A polymorphed hero who runs out of hit points returns to normal form. A yellow light gives off light. What nobody had read about was the moment where all four combine: a Valkyrie at -70 alignment turning into a yellow light, blasted by her own Orb for all the light’s HP before her new body had started to glow. Once the reporter had stumbled into it, AI-assisted testing found related bugs in the same code. Reasoning, whether human or machine, is great at checking a bug’s vicinity. It’s much worse at telling you where to look.
From the article:
[...]
[...]
[...]
[...]
[...]
[...]