The NetHack Challenge: Dungeons, Dragons, and Tourists (2021) | Hacker News Reader

The NetHack Challenge: Dungeons, Dragons, and Tourists (2021)

nethackchallenge.com

122 pointscpeterso70 comments

No human has ever beaten NetHack without being "spoiled". That is, in NetHack culture, reading how-to guides or the game's source code to understand what process to follow to identify unknown objects or to navigate tricky situations. It is unsurprising that with training rules that prohibit AI's from similarly being spoiled no AI has beaten the game.

Where can you see "training rules that prohibit AI's from similarly being spoiled"? It says "We imposed no limits upon how teams would design or train (if relevant) their agents" so seems they do allow spoiled AI.

Even spoiled, when it's achieved, an ability to complete a task like ascending in NetHack seems more world changing to me than the LaMDA conversations.

I'd be completely flabbergasted if they trained an AI to parse source code while playing a game. I think it's the "lack of addition" rather than the "expressly disallowed" training rules that are being referred to.

The AI doesn't need to parse the source code. I haven't played Nethack, but based on the example given of writing ELBERETH in the dirt, the person training the model could add that to the potential actions being considered at each step and the model learns what it does by playing a million games.

They wouldn't necessarily need to parse the source code. E.g. initially training a neural network on replays of human runs (AlphaGo style, as opposed to AlphaZero) would probably be considered "spoiling" in the Nethack community, but it's a plausible approach assuming you can somehow obtain a training dataset.

I used to read the source code before I managed to find a guide and I never won the game. That could be Hack, not Nethack, too many years passed by.

By "training rules" are you referring to the way machine learning systems are traiend? In that case, you're right.

The Challenge highlights an important limitation of modern machine learning systems, that they can only learn from their training data and have only a very, very limited ability to incorporate "background knowledge".

"Background knowledge" in this case is the "spoiling" you're refering to. There is virtually no way to teach a neural net system how to play Nethack, other than to let it try, and fail, and fail again, at ascending. You can't explain to it for example, how writing "ELBERETH" in the dirt with your finger will scare monsters away (which is important background knowledge about the game that is very hard to learn just by trial and error).

Nethack is full of such things, that would be meaningless in many other games, and AI developers would probably not look at in other games... eg. what your pet stops on (or doesn't step on/pick up) and its curse status. If you don't track the dog, remember the status, and then notice the un/cursed status in the end, you never find out stuff like that.

Yes. Some of those things can be discovered by trial-and-error (exploration in Reinforcement Learning, I guess?) but some others are much more of a tall order. One classic problem is that the things one does in early levels affect the progress of the game at higher (lower) levels but it's not clear how before getting there. So while I think that, ultimately, a big neural net should be able to learn all those tricks that human players have learned over the years, it would take an exhorbitant amount of data and training time, that perhaps few companies would want to spend on something obscure and esoteric like nethack.

Actually this is false and probably have occurred more than what’s recorded. The guidebook is enough information (although if there’s an AI who can comprehend the nethack guidebook that’s far more impressive than being able to play nethack).

https://groups.google.com/g/rec.games.roguelike.nethack/c/wc...

A sufficiently large GPT model could probably comprehend the guidebook, in some sense, assuming they manage to increase the input size enough to ... I guess, let it condense the guidebook to some kind of internal language and then make use of that and now I'm just speculating wildly. ^^;

If I had the GPUs, it would be an interesting thing to experiment with.

However, having comprehended the guidebook, it then needs to also comprehend the nethack terminal client. The pile of obstacles does not cease to grow.

It's worth noting that even people who have been spoiled still usually find it _extremely hard_ to beat NetHack.

I started playing when I was 12 and have gone relatively spoiler free.

I have ascended once. (I was 25 at the time)

I got stuck on the vibrating square many times, the castle many times, and have died on the elemental planes many times. Because I had no idea to do what was expected to me. The first I got to Medusa I died instantly.

Yes, I think some of the final puzzles are a bit too obscure... But I think you can beat it without spoilers.

But I would spend entire days to learn mechanics... IE: day of kicking sinks is a day I remember fondly in my childhood.

I am sure there is tons I don't know. But I have never used explore mode, and I have never looked up spoilers before ascending.

Note, I had some word of mouth friends, and it took me 3 years alone to figure out altars.

>>> NetHack benefits ‘strategic’ play — good play often involves executing a series of actions with a well-defined, expressible sub-objective, eg: “Find Sokoban” or “Apply a Unicorn Horn to Cure Poison”. Symbolic bots found it easy to define ‘strategy’-like subroutines and to decide when to deploy them based on rich, human-legible representations of the game state.

This feels akin to Classic Game AI vs Modern AI debates that happen all the time. And even in 2022, with desktop GPU capabilities nearing supercomputing levels, it feels like rules-based, goal-oriented planning still dominates NPC & Enemy AI in games. The question really becomes, why did symbolic ai research die when it's so effective at specialization? Rather, the research obsession is solving generalization. And the problems always seem to stem around the black box itself, the lack of "human-legible representations" of its latent spaces ;)

> rules-based, goal-oriented planning still dominates NPC & Enemy AI in games.

I think this is largely because the goal of most game AI is not to win per se, but rather to provide an engaging experience to the player. To that end, a game designer wants to be able to purposefully craft the experience, and explicit rule/goal based systems allow that.

Also because rule-based AI is typically much less computationally expensive to execute than ML-based AI. This matters in games because they often have other things to do with the available computational resources on the target hardware.

And, in particular, most players enjoy AI that is just smart enough to be challenging, but no smarter. Players feel OK losing to an enemy player that outguns them or gets lucky, but very few enjoy feeling stupid because they were outsmarted by a program that had fewer resources than them but played better.

"The question really becomes, why did symbolic ai research die when it's so effective at specialization?"

I think we want "AI" that scales faster than humans can implement. Game "AI" looks nothing like machine learning and looks a lot more like some programmer just smashing out some code and trying it out for a while. Some autotuning can be done, of course, but it's largely a program being written. Who has time for that?

Because Nethack and video games remove most of the reasons that GOFAI failed; for example, everything hard about perception from pixels is removed when you have a little parsed text grid of cells presented to you or are hooked into the game engine and query objects directly. (The real world is not made of a clean little grid of discrete high-level objects like 'dragon' or 'black jelly'.)

Moravec's paradox again: humans find perception easy but things like Sokoban hard, while GOFAI approaches find Sokoban so trivial that it's common to use it (or Sudoku) as a toy problem introduction to constraint solving. Nethack literally has levels which are just Sokoban and which are important to solve; GOFAI can push the boulders around perfectly, even though it would be unable to recognize a photograph of 'a boulder' or use the word 'boulder' in a story.

Then you have the extensive hand-engineering of expert knowledge which goes into ascension agents and the symbolic winners, above and beyond merely plugging in a Sokoban solver. There are increasing experiments in making DRL agents exploit or initialize from pretrained language models (https://arxiv.org/abs/2005.07648#google https://arxiv.org/abs/2201.12122 https://arxiv.org/abs/2204.01691#google https://ai.stanford.edu/blog/DrRepair/ https://arxiv.org/abs/2005.07648#google https://arxiv.org/abs/2009.03393 https://arxiv.org/abs/2204.00598 come to mind) or reading manuals (https://arxiv.org/abs/1401.5390 all the way back in 2012!), and of course, a DRL agent can learn a tremendous amount without actually doing any playing by offline and off-policy and imitation learning, but while it is exciting and things like Gato look like the future, there is a long way to go from feeding in a dump of the Nethack wiki which mentions offhandedly "you can do X" to an agent recognizing an opportunity for X in the wild and executing it. (Which is something that symbolic approaches also don't come anywhere close to doing, because they just cheat by the capability being given to them by hand-engineering rather than having to autonomously read, understand, and apply.)

Probably the biggest thing for Nethack DRL will be when datasets of human games allow for imitation-learning initialization, rather than learning from tabula rasa (which even humans can't do). I asked them about that and apparently the existing telnet server datasets aren't usable but they have been working on getting usable game logs in the future: https://www.reddit.com/r/MachineLearning/comments/p88v9w/d_w... As sessions pile up fast from all the active players, I expect at some point they'll be able to dump 50 or 100k human games, including by expert players, and that'll lead to a huge boost for DRL perf.

And especially with those logged games, language models with retrieval will be useful: https://arxiv.org/abs/2206.05314#deepmind

Right now, Junethack, the NetHack Cross-Variant Summer Tournament (aka the tournament that is abusing players for finding bugs in nethack forks tournament) is running.

This year, I don't think there are any obvious bots running. The only time a bot clan was participating AFAIK was 2015.

https://junethack.net/archive/2015/scoreboard.html

And it didn't do badly (it did score 2 of the 5 clan trophies) but also not particularly well. That's mostly due to the tournament including lots of NetHack forks and the clan trophies being special side achievements that aren't necessarily needed for winning the game. So a generic bot that is trained to win the game isn't best at getting those.

And for today, I think there is no bot that can win the game for the newer versions or any forks. The bots from the NetHack Challenge also can't participate as they need a custom NetHack binary that outputs the game data in a machine parsable way whereas the tournament requires you to play on existing public servers.

One interesting result from this challenge that could stoke debate is that symbolic (rules-based) agents are clearly achieving better results than neural (machine-learning-based) agents.

Maybe that's related to the nature of NetHack itself, compared to other games where ML has seen (often overwhelming) success?

Will rules-based systems continue to succeed for NetHack, or is this a temporary condition until the state-of-the-art in machine learning improves?

Consider that the existing MVP for ascension is a neutral network.

I wasn't able to find out about that, from a quick scout around - could you share a link to it?

(I did find BotHack[1] and a video of its' first ascension[2], both of which are cool)

[1] - https://github.com/krajj7/BotHack

[2] - https://www.youtube.com/watch?v=unCQHAbGsAA

Human brain.

Hehe, ah, of course :)

I think neurosymbolic ai could do better here. It seems to be an interesting field and this might be a cool application.

Nethack is notorious for being utterly unwinnable without spoilers. There are a few claims of people who have done it, they don't hold up very plausibly: at the very least those people got indirect spoilers from talking with people who were spoiled.

So it's not really surprising that hard-coded rules based bots incorporating spoiler knowledge beat learning bots trying to learn the game directly from the interface.

But we have neural networks for NLP, who could read the spoilers.

DCSS might be a better target, in that it doesn’t reward hanging around on one level, and has far fewer things you need to be spoiled on (you need to know that picking up runes is good, and how to kill hydras, that’s about it) But it has a steady stream of qualitatively different challenges on different floors, forcing a lot of contextual behaviour. And there’s a little bit of long term strategy that can really mess up an AI.

DCSS has been beaten by a handcrafted Lua bot, written by the (at the time) indisputably best player in the game. Unlike the approach here, it got to benefit from human expertise, and also it can only win with a very narrow set of characters. Learndb entry:

qw: A fully automated lua bot written by elliptic, with some code borrowed from parabolic and xw. The first DCSS bot to ever achieve an uninterrupted and unassisted win (see '!lg qw won 2'). Now maintained at https://github.com/crawl/qw by the DCSS devteam. See qw[2] for a summary of results.

As of 0.29-a, qw has a 0.36% winrate with GrBe with 1 win in 276 attempts. See https://crawl.dcss.io/crawl/morgue/qwqw/morgue-qwqw-20220613... and games are sometimes played on cdi. Historically its best 3-rune winrate was 15% DDFi^Makhleb, and, for 15 runes, about 1% with GrFi^TSO before the 0.28 hell rework.

Branch order: D -> Lair:8 -> Orc:3 -> D:15 -> S:5 -> Vaults:4 -> Depths:5 -> S:5 -> Vaults:5 -> Zot

On the online servers, qw plays with an extra added delay so that it doesn't use too much server CPU. Playing locally without this delay, qw is much faster.

DCSS is just a much simpler game than Nethack, so a bot would likely do well.

It's questionable if it's simpler (notwithstanding all the things they've cut from dcss over the years). The main obstacle for bots is that to win nethack you need to know lots of things you're unlikely to find out by trial and error. Like how eating a lizard corpse can prevent stoning from a cockatrice's hissing, or hallucination can prevent a Lich's touch of death, how you can apply a towel to wipe your face if you've been blinded by a thrown cream pie etc. Know all the tricks, and the game becomes much easier.

You need a lot of knowledge to win DCSS, too, but it's more about wise use of limited resources, playing the hand you're dealt, and the dangers of various locations. It's much harder to codify as spoilers, but you will learn by trial and error.

I imagine you'd at least have to inject domain knowledge into the model, the ruleset isn't as simple as chess or go, and all the places where a bunch of actions have to be strung together just so will lead to a very spiky parameter space where gradient descent struggles.

I used to play NetHack a lot and the only thing that bothered me in the gameplay was the monsters' AI. They were basically a huge heap of mindless creatures that lived with a single objective in mind: to destroy you.

I think there is a lot of opportunity to make NetHack even more amazing by having smarter monsters that come up with new strategies, often as a group, to beat the player.

On the topic of what's next, I'd really like to see an AI tackle a 4X strategy game like Civilization. AlphaStar is the closest we've seen, but I think it relied on superior control ("micro") more than good decision making, and the Dota AI was similar. I want to see an AI succeed in a strategy game via pure decision making in a turn-based game.

I'd be much more interested in watching an AI play the board game Diplomacy, charades, or see one LARP.

I'd like to see an AI tackle 4X because Firaxis' AI is famously miserable at its own game.

Firaxis iirc has never shipped an iteration of civilization where the AI could compete on a level playing field with even quite mediocre humans.

Tangentially related, but I wish the Tourist class would let me talk my way out of adversarial encounters by explaining that I'm merely a tourist and unfamiliar with local customs. Like Twoflower in The Color of Magic.

That could be counterbalanced by shopkeepers making them pay inflated prices and some cop fining them for nothing.

I just checked on nethack.alt.org high score in the last 60 days

https://alt.org/nethack/top60d.html

5000 points is still a relatively low score, it corresponds to reach Dungeon level between 5 and 7, which is quite early in the game.

To those not that familiar with NetHack, it's possible to run up arbitrarily high scores by doing activities within the game such as pudding farming. This is essentially a risk-free way (when done correctly) to get an unbounded number of kills, and as each kill is worth points, an unbounded score as well. I believe the score maxes out at 2 billion something, i.e. the maximum value of a signed int. So you may as well consider all 7 digit and up scores for ascended characters to belong to one single group, as any of these characters could have arbitrarily inflated their score, they just chose not to, as it's relatively uninteresting/boring to do.

What's more interesting is a low score ascension. That is insanely hard to pull off as it means you're taking a very fragile character into the endgame, and yet somehow pulling through.

Various farming strategies have been severely restricted in recent versions of the game; puddings don't even drop real corpses now. There are definitely still plenty of ways to loiter around and boost your score, though.

I'm showing my age here then. I mostly played version 3.3.1, then some of the 3.4.* versions. I haven't played 3.6.*.

Oh man, this takes me waaay back to my time spent on rec.games.roguelike.nethack about two decades ago. It literally took me a couple years of off-and-on effort (and hundreds of deaths) until I ascended for the first time. But once you put that much actual effort into getting good at it, you stay good, and I ended up doing multiple back-to-back ascensions, ascending with every class, and doing some high conduct runs, including one that was vegetarian, weaponless, genocideless, self-polymorphless, and artifact-wishless.

It's definitely a hard nut to crack, and I can see why the machine learning attempts would've struggled so much, but honestly I'm surprised that the best symbolic logic bots only achieved a few thousand points on average. That's really not even getting very far into the game.

I guess NetHack is a harder game than StarCraft II, as with SC, the best bots are competitive with the best humans (albeit they have advantages in inputs/attention and disadvantages in grand strategy). NetHack though is literally turn-based (like Chess), so there's no advantages to be had here, and clearly they're struggling for it.

> it literally took me a couple years of off-and-on effort (and hundreds of deaths) until I ascended for the first time.

> But once you put that much actual effort into getting good at it, you stay good

I had the same experience, but I don't think it's a matter of being "good" at the game so much as having memorized all of the stupid ways to die (many of them insta-deaths ) plus how to avoid them, and knowing the mechanics of how to win (I think you're supposed to figure out the invocation ritual by giving tons of money to the Oracle, but it's been decades and I can't recall if I learned it that way or just read spoilers). edit: just remembered the whole vibrating square thing and that there are a few ways of making a run unwinnable, which is a kick in the teeth when you have a promising @ going.

Maybe that's just splitting hairs (is that just becoming "good"?) but in retrospect, I don't think that getting good at nethack was worth the investment in time and frustration. I will say that playing nethack improved my vocabulary.

Yeah, I do think that's splitting hairs. A large part of that is what being good at the game actually entails. Also, you're underselling it -- it's not memorizing specific ways to die per se, it's learning a large number of different strategies to deal with a large number of different problematic situations. If it were just simple memorization the programs would be better at playing it. Ironically, the vibrating square is one thing that a program would do much better at than a person (also Sokoban) -- it's mind-numbingly boring for a person to do, and you can easily mess it up and frustrate yourself to no end, but a program will execute a perfect sweep to find it in no time at all.

A large part of becoming good at NetHack ends up being learning to be patient, playing conservatively, and taking lots of time to think before acting. And there are plenty of mini-games within the game (such as Sokoban, potion/scroll IDing, pudding farming setup) that you need to learn well too.

What helps most of all is being resourceful. There are so many different systems in the game that can all be used in the right situations to give you an advantage (e.g. Elbereth, wielding cockatrice corpses), so you just need to play slowly and cautiously and continuously think about every single possible action of the dozens available at any one point that you can use to maximal effect in any specific hairy situation.

> And there are plenty of mini-games within the game (such as Sokoban, potion/scroll IDing, pudding farming setup) that you need to learn well too.

I'm with you on the ID minigame, but Sokoban is very skippable: winning it gives you one of two valuable items, but it's not the only chance to get them. And I've ascended every class without ever once pudding farming. Your overall point stands, though.

Your chance of ascension definitely increases if you learn how to do Sokoban well, though. It's a pretty simple way to get an excellent reward that definitely helps you substantially. The Sokoban levels are also a good source of randomly spawned items at depths that aren't too deep. I'd always do the mines and Sokoban before going too deep in the main dungeons, as without getting geared up well enough first you would quickly start encountering monsters at lower levels that would pose serious problems. Going through all the low-depth branches first kits you out with more gear (and more experience points), without risking running out of food which is what might happen if you only stuck on the main branch and farmed those levels for EXP.

Amen. Once I understood the game and started being able to play rationally, the main threat was always my own impatience. How many times I lost fights just because I forgot to stop and check my inventory for useful stuff. Or ran right into a floating eye in a dark corridor...

SC2 has an important real time dexterity requirement, so I don't think they are really comparable challenges.

There’s a good reason for putting computation restrictions on the bots. Turns out without it, it’s already pretty solved: https://pellsson.github.io/

You can easily avoid that by replacing the RNG with a proper secure one.

Then it wouldn't be Nethack.

Nethack is not a game where the dice are fair. Nethack is a game where the phase of the moon has real influence.

Nethack is, though not originally designed for that purpose, a game which encourages players to learn to read the source code and familiarize themselves with text files, editing, and searching.

You could build a nice first-year CS class around Nethack, taking people from "this is a fun game" to "I have a tenuous grasp on programming" in a semester.

> Then it wouldn't be Nethack.

Hard disagree. No human player would remotely detect a difference if the exploitable pseudorandom seed were replaced with a truly random source.

> Nethack is not a game where the dice are fair. Nethack is a game where the phase of the moon has real influence.

The phase of the Moon _is not random_! It is deterministic! You're arguing against yourself here.

> Nethack is, though not originally designed for that purpose, a game which encourages players to learn to read the source code and familiarize themselves with text files, editing, and searching.

Entirely orthogonal to the issue of using a better random number source. Indeed, a good class project might be improving the source of randomness used by NetHack.

A pseudorandom number generator

  - is necessary for technical reasons
  - is easily distinguishable from a different one by players 
  - can (and since it is Nethack, should) include the phase of the moon as a seed

Can't you have a secure random number generator and on top of that add in biases for the phase of the moon, etc? League adjusts crit chance so smooth out the likelyhood of two in a row for example.

The Moon phase adjustments are really trivial. E.g. luck is increased by 1 during a full Moon (and you already need to handle luck anyway; basically your total luck is setting a modifier on how likely good/bad events are to happen). Or a cockatrice will always turn you to stone when it attacks on a new Moon instead of having a 10% chance of doing so (this can trivially be implemented on top of any kind of source of random numbers).

You need to explain these in further detail then, because I don't see how any of them are true.

https://www.reddit.com/r/nethack/comments/adbgzd/yaap_swaggi...

> Fountains have a 1/30 chance of summoning a Water Demon when quaffed, this demon has a (80+DL)/100 chance of being hostile. If not hostile, it grants a wish and vanishes.

> every time the character attempts to walk into a wall, it calls random() without wasting any in-game time

> So it is advancing the RNG millions of times (or whatever is necessary, maybe not that many times) for each "real turn" until it reaches a favorable point in the RNG as tested in parallel offline (e.g., find a spot in the RNG such that a quaff 1) gets a demon that 2) grants a wish and 3) the fountain stays... advance the RNG as many times as it takes to repeat that... again and again, for 90 wishes)?

This is not solving nethack, this is just save scumming / cheating.

I agree that it’s a fairly uninteresting way of beating the game (except for the sheer hilarity that it’s possible) but trying out various scenarios and backtracking in your own head is exactly what the average chess player does.

The difference, of course, being that chess doesn't have an RNG. Manipulating a pseudorandom stream of bytes to get an exact unlikely desired outcome doesn't have a parallel in chess. Chess has no random or hidden state.

What's described in your link is not a game without restrictions. It's a game where the RNG was reverse-engineered so that the bot could get 90 wishes and ascend easily. So it's hacking the game, rather than playing the game.

The tournament in the NetHack Challenge is a bunch of bots playing the game in an ordinary manner. There is no comparison between the two things.

Who gets to define hacking vs playing? The bot is executing the game code with exactly the same behavior as a human would experience.

Yes, the bot is taking advantage of hidden state with the RNG... but there's nothing stopping a human from doing the same. It's possible for a human to take enough RNG-based actions and observe the outcomes to derive the current state of the RNG seed. Maybe that number is in the thousands or millions of actions, but a human could do it the same as a bot, we just don't choose to try.

To be honest I don't find splitting hairs about hacking vs. playing interesting. The OP specifically wrote that without restrictions Nethack is solved. In truth it isn't because the bot in their article has to know the RNG seed to ascend. Without knowledge of the RNG seed the bot can't ascend. So it's not removing restrictions that helps the bot ascend but giving it an advantage by revenging the RNG seed.

OP here: if you read the article, their big insight is that the RNG is completely computable. So with unrestricted computation/storage, you can deduce the RNG seed and proceed from there. Strictly speaking you still need to build something smart enough to get to a fountain, but that’s a significantly smaller challenge.

Right, that was my point. The RNG is completely computable, by either a bot or a human player, even without directly observing the hidden state, if you could do enough actions and observe the results to deduce the hidden state of the RNG seed from that.

There's an argument that would call this cheating, but I don't think so. There's plenty of hidden state in Nethack (unidentified items, anything out of your field of view at the moment) and playing the game is largely an exercise in deducing that. The so-called RNG is no different, it's just another piece of hidden state, as far as the program is concerned.

Does this website somehow prevent smooth scrolling on the iPhone?

This reminds me of Zebulon (sp?) which I think was run by Packetstorm Security - although it was more geared towards infosec than AI. Does anyone else remember that?

Is symbolic just a fancy way of saying hand coded rules, or is it “trained” in some way, just not via neural net?

Reply on news.ycombinator.com