NetHack beaten in 7 minutes 15 seconds real time | Hacker News Reader

NetHack beaten in 7 minutes 15 seconds real time

pellsson.github.io

417 pointsUser2389 comments

When I saw the previous submission of this as https://news.ycombinator.com/item?id=18853508 (which describes it as a "tool-assisted speedrun" of NetHack on the online server nethack.alt.org), I thought "wait, you can't have a tool-assisted speedrun of a nondeterministic game with hidden information...!" (particularly on an online server where you can't roll back history).

Then I read the article and saw that this project went to absolutely insane lengths to work around the "nondeterministic" and "hidden information" parts.

They had to do quite a lot of source diving to achieve this.

The bumping into a wall to advance the RNG state without changing the game time is a really neat trick that I would otherwise have been completely unaware of, and I have played Nethack for many years and done some source diving myself.

Truly a great feat of engineering here.

This reminds me of something I read on reinforcement learning playing Atari / video games ... often you see the Deep net (I think the game in question was a tank game) just spazzing out on the controller when there’s no enemy, the tank was spinning on the spot while waiting for a door to open for example.

Initially thought just to probably be some numerical instability when the next actions are all equally likely (I.e. there’s nothing for it to do) but what was actually happening is the pseudo RNG was partially fed by controller input, and certain patterns of controller input would make random rewards more likely to spawn.

I always thought it was cool how these exploits get discovered by the deep nets

Do you have a source on this?

I was under the impression that machine learning is only good at learning things that can be approximated by continuous functions.

A RNG is almost the complete opposite of that. It's everywhere discontinuous!

Old games put the P in PRNG. Often, the technical limitations caused them to very roughly approximate randomness, for example a function that used the last n button presses plus the countdown timer as a seed. If your game has to run in under a kilobyte of memory, that n value might be a byte, or less (such as four bits, 2^4)

Some games were worse, far worse. Doom used a list of 256 random numbers that it looped through.

Pokemon is another game where the RNG function is extensively mapped, and even used in combination with bugs to generate Mew events, something that should never ever happen.

You see a lot of TAS of old games, especially popular ones, that abuse the RNG generator where feasible.

If the result from the RNG is not actually perfectly random, and is actually partially determined by e.g. controller input, then even if the function is discontinuous there may be a continuous function that approximates it closely enough to be useful.

Old games have such predictable RNG that humans can manipulate them in non-TAS runs. See the run for Final Fantasy 1 for a good example.

Atari computers actually had a hardware random number generator driven by electrical noise. (I'm not sure what the 2600 system had, most of their latter game consoles were based on their computers). Most other computers in those days just used a pseudo random number generator.

The 2600 didn't have a built-in RNG, but many games took advantage of uninitialized registers on powerup to seed their own RNG.

I remember it as using a pseudorandom noise source. Wikipedia on POKEY[0] says 8-bit values from a 17-bit polynomial counter. Sounds about right.

[0] https://en.wikipedia.org/wiki/POKEY

I remember hearing about this on the podcast roguelike radio a long time ago - truly a brilliant little hack.

Here's the link for anyone interested: http://www.roguelikeradio.com/2016/06/episode-122-nethack-to...

A very niche topic on an already niche podcast, but probably will get some decent overlap on HN.

(Also I'm assuming this is the same team? It's hard to tell.)

That's why my submission https://news.ycombinator.com/item?id=18843584 called it a "Tool Assisted Speedrun on NetHack with RNG Exploitation". :-)

I'm not sure about the exact terminology. Is an ascension by a bot (like https://www.youtube.com/watch?v=unCQHAbGsAA) also as a TAS?

Although you are right that the group that tried to do a TAS for NetHack (not sure what's their status) chose the MS-DOS port of 3.4.3 for ease of manipulating the RNG in memory and so getting rid of the "hidden information" part.

Edit: also in a game like NetHack, there is potential for an automated tool to help the player. InterHack (https://taeb.github.io/interhack/) was an interface layer for 3.4.3 that added lots of useful stuff, e.g. automatic price identification or wand id from engraving. Most of that has since been incorporated in vanilla NetHack or at least forks.

To be fair, most TASes have RNG exploitation, just of a different sort (they do things that cause the RNG to be polled so that they can get rid of "bad results" and force a desired result).

That's exactly what this bot does once the gamestate is known; it starts by repeatedly walking the character into a wall to consume bad RNG values so the good ones can be used for fountain wishes. The additional wrinkles are that (i) there are 2^32 possible initial gamestates given their start-of-game choices, and the server is remote, so they needed to figure out a way to determine the initial gamestate to enable RNG exploitation, and (ii) they had to express the bot logic in a more generic way that could handle (almost?) any initial state, rather than hardcoding for a specific initial state.

Wouldn't something as simple as DCSS autoexplore/go to functionalities classify as "tool assisted" ?

They seem straightforward to implement even for nethack.

UnNetHack and NetHack4 and its forks have autoexploration.

The problem with it is that it's less efficient than exploring on your own.

I usually don't care about that. You learn fast when to autoexplore and when not to, to not miss particular places you value higher than the program. When playing on a tablet, it's tremendously useful and a real time saver.

Hah! This reminded me a bit of when I was working on integration tests for my multiplayer roguelike last year. My problems didn't need cloud computing to solve though, just using an explicitly seeded random number generator that was injected into my modules from the tests.

Games done quick marathon is going on right now[0]; for some of the games they do some pretty extreme RNG or memory manipulation (particularly on older NES and SNES games) that is very interesting to watch. It's worth checking it out.

[0] gamesdonequick.com

This isn't the first time RNG manipulation in NetHack happened. In 2009, Adeon released a set of RNG manipulation tools for NetHack 3.4.3 (nethack_rng_tools-0.2.3.tar.bz2 -- I can't find that filename anymore, so I put up a mirror[1]). This allowed determining the RNG seed from a running game. However, he also made a patch to use a cryptographically secure PRNG[2]. I'm not sure if nethack.alt.org (NAO) ran that patch. If they did, I'm not sure why they kept random() for 3.6.1 that was apparently run by SWAGGINZZZ.

[1] Since it had license headers, this is probably okay. https://xorhash.bitbucket.io/nh/nethack_rng_tools-0.2.3.tar....

[2] https://bilious.alt.org/?349

RNG manipulations are among some of my favorite speedruns just because of the absurd lengths players will go to align absolutely everything perfectly. For example, Dragon Warrior at AGDQ last year was an absolute treat to watch [1]

[1] https://www.youtube.com/watch?v=Bgh30BiWG58

FYI, gameplay/commentary starts at 7:23. Here's a link at the timestamp: https://www.youtube.com/watch?v=Bgh30BiWG58&feature=youtu.be...

Remarkable. So is this player performing all of these movements that change the RNG behaviour from (muscle) memory?

Yeah, pretty much. Speedrunning takes all the obsessive practicing of classical piano concert performance and applies it to video games. It's insane

They look down at their notes at several time, so not just pure memory, but it's still impressive.

Also note that when you move the cursor in a direction that it can't move (e.g. off the top of the menu) the cursor freezes for an exact number of frames. So if you e.g. hit "up" then "right" the cursor will always move right after a specific frame delay. They use that in order to get frame exact timings that would otherwise be impossible (the "Command?" message also has a different delay, so they can combine the two to get to the frame they need).

The memory is impressive, but belies the massive amount of trial and error that was needed to find the correct combinations.

Wow, that's insane!

The best thing that nethack did for me was letting me ingrain the hjkl muscle memory. This in turn helped me thrive in vim.

Thriving in the dungeons though... that's something that's always been elusive.

I hacked the source slightly so I don't take any damage in combat. Is a simple one line change so it's a cheat but a tiny cheat. I still cannot get past level 10-12 or so. (Wow, I suck.)

Had to look up this abbreviation:

c!oGL = cursed potion of gain level

https://nethackwiki.com/wiki/Abbreviations

For non-NetHack players, this is a joke that results in a useful strategy. The potion of gain level normally causes you to get an experience level. But if the potion is cursed, the universe instead misinterprets the magical effect and you gain a dungeon level instead of an experience level—that is, "You rise up, through the ceiling".

This is generally very disappointing because an opportunity for your character to become more powerful was effectively squandered due to the curse. But magically moving upward quickly through the dungeon can be very useful if you need to escape from a dangerous monster quickly—or at the end of the game when you need to escape from the dungeon as a whole. The latter is what this speedrun used in order to avoid having to walk through the dungeon and take the stairs.

Most normal characters wouldn't be close to having enough potions of this kind to get entirely out of the dungeon by this means (also because of a certain complicating factor that prevents characters who can't control the RNG from knowing in advance exactly how many they'll need!). Although it's been done before by different forms of grinding, this is a whole other matter because the potions were obtained almost instantly with a preposterously lucky series of wishes.

Thanks for the write up, that makes parts of the article make more sense.

Blindly jumping to the altar and one-shotting the priest does of course take A LOT of attempts, but modern CPUs are pretty fast and NetHack is a pretty low-end game.

I can't help thinking of Phil in Groundhog Day coming up with new challenges as he spends eternity in Punxsutawney PA.

Maybe I'm reading too far into this, but I think there's a greater lesson to be learned from this.

This game's been around for 30 years, and is still under development. Some would assume that security patches on any 30 year old piece of software would have found nearly every bug or account for unexpected usages.

There's also a big assumption that random states on remote systems can't be determined. Our assumptions around what's "good enough" keep getting broken. 32-bit states, MD5, SHA-1, etc... Now clearly (until quantum computers go mainstream) some problem spaces are just too big to reasonably brute force or find collisions.

Could/will we find critical bugs that allow us to do similar types of attacks for modern computing systems that aren't games?

Huh. Given that the first 6 minutes (out of 7:15 total) were spent with a HUMAN player fumbling around looking for a fountain, presumably writing an AI capable of doing that step would get the ascension time down to just over a minute. I wonder why they didn't do so?

I’ve been trying to reach the amulet for 30 years.

I’ve been playing since 1987 with the IBM PC version called Hack. My friend’s floppy disk got damaged so he couldn’t use a scroll of identify because it crashed the game, but he was still able to finish the game without it. For Hack all you needed to do was find the Amulet of Yendor under a boulder and bring it to the top.

I’ve never ascended on Nethack though despite all my time invested. I’m probably playing it wrong but I don’t care it’s still fun as hell.

That sounds closer to Rogue than Nethack.

No it was called Hack. This is around 1985 or 1986.

I played on and off for over a decade before deciding I was going to ascend. If you spend some time on the wiki and learn all the little tricks hidden in the game, it’s not too hard to win. There are a few common strategies to get through the middle game where most people die. Gehennom is fairly repetitive and you will be powerful enough by that point in the game and familiar enough with your character to not botch it every time.

Keep going, bro. It took me 12 years.

I try to explain my friends how fiendishly hard NetHack is but they always say stuff like 'Well I've won in Dark Souls so I know about hard games'. It's not even in the same league imho.

Here's how I describe it:

It's like dark souls if there were way more monsters and items with interactions that can one shot you if you aren't knowledgeable and careful, but you don't know what they do right away, and when you die you have to start from the beginning with a totally different level layout, starting loadout and pickup RNG, AND you forget what all the items do.

It took me about 20 years of casual play, then another couple months of fairly obsessive play. It's effectively impossible without spoilers.

I know folks who consider NetHack to be a Unix tutorial. It teaches hjkl to acclimatize one to vi. And people who win the game are those who have read the source (or, these days, the wiki) enough to grok the game. And once you grok the source enough to win, you might even find a bug. And since you've alienated your meatbag "friends" and replaced them with the NetHack fandom, you'll be encouraged to report & patch the bugs.

But yeah... I've seen some fake amulets, but I've never gotten the real one...

Well, now you know what to do:

    Find non-magic fountain next to a wall (manually)
    90 wishes. Eyes to phase-jump through walls. 60 c!oGL. ~+100 MB
    Genocide LcPUn (due to lazy bot code ;))
    Tele Vlad, phase-jump tower, get candelabrum.
    h-strats to provoke Rodney (who is not allowed to return by RNG)
    Wait for quest
    Level-tele to jumping distance from quest leader (save realtime over landing next to).
    Go to end
    Land jumping distance from square
    Phase-jump to priest
    c!oGL to top (Mysterious force not allowed. Lovely.)
    Hallu for RNG manip without walls (just press space)
    Force portals relatively close on Earth, Air, Fire.
    Ascend.

You and me both. :(

Just waiting for AlphaNethackZero to beat this record.

> Turns out, every function in NetHack seems to find a way to call random(), causing the RNG state to drift.

I recently stumbled across the concept of splittable RNGs, which works around this very problem.

Once seeded, you can either "hand in" the generator to get a random number, or you can split it into two (or more) new generators that themselves can be handed in or split.

From a single seed generator, you would split off multiple generators for things like map generation and monster behavior, which then split their generators in turn to generate the level or move monsters.

As a consequence, if you change some monster behavior that uses the RNG, that does not cause the level generation to change, because that was split off earlier and is thus on an independent chain of random numbers.

Splitting the PRNG would provide resistance to tampering by walking into walls and the like, but it would also reduce the avalanche effect of code changes, hiding inaccurate probability distributions (e.g. if a polymorph potion turns you into a yeti the next spawned monster is likely to have low hit points) that would cease to change drastically as PRNG calls are added or removed anywhere.

this seems like the plot of "edge of tomorrow," [1] but in nethack form.

so neat -- i love that the RNG space fits into 100GB (all nethack games that ever will be).

[1] https://en.wikipedia.org/wiki/Edge_of_Tomorrow

The original article points out that it's all possible "Tou Hum Fem Neu" (female neutral human tourists). You have lots of other choices when you start a NetHack game. :-)

oh gosh, i didn't realize that. looks like there are around 38 combinations; i wonder what the table space looks like for the other ones!

In theory there should be 2³² possibilities for each although it might be trickier for a player to notice which one he or she is in.

The other thing is that two instances of the same game diverge quickly when the player doesn't take exactly the same actions, because monster generation and dungeon level generation will use the current state of the RNG. So although the RNG will produce the same series of values, the millionth RNG value for one player might be used for the success probability of the player's attempt to hit a kobold, and for another player might be used for some aspect of generating a new dungeon level.

The problem with the other classes is that their starting equipment is less random, so it's more difficult to figure out which seed you are on. You would have to include more of the generated map in the database to figure out which seed you are on.

And of course this would all be shot to hell if Nethack went to a 64 bit seed.

yeah, i wonder how much of the game information you would have to include to make it unique.

that being said, wouldn't map information be sufficient for the remainder of the classes? so using starting equipment is really just an optimization available for this class?

The problem with using the map is that you can't see most of it when you first load the game. So you have to play more (and build up more state) before you get to a completely unique solution. Being able to use the starting equipment makes it much simpler.

haha, nice. https://alt.org/nethack/fastasc.html

An ascension in -2147483648 turns by Khaos is another thing to note in the table. Did he really wait for 2 billion turns before ascending to overflow that counter?!

https://nethackwiki.com/wiki/1-turn_ascension

Check out the information at the very end of this page.

> paste it into NetHack's terminal, and wait approximately 19 days.

Thanks for the laugh

> If NetHack is compiled for a 64-bit platform, the "long" type will not wrap around until it gets to 9,223,372,036,854,775,808. The above trick still works in principle, but will take a few hundred million years to complete.

Another laugh.

I wonder if someone will figure out how to overflow the score counter.

Overflowing is actually not that hard in NetHack. Score gets rather meaningless in NetHack as killing monsters always yields the same number of score points.

So if you grind long enough, every high score is possible and overflowing the score counter with pudding farming was quite easy on 3.4.3 on 32 bit systems (the score counter is a long).

What players have done is a MAX_INT game or ascension. That needs some preparation and the MAX_INT game is easier to do than the ascension, as the ascension gives you additional score points, so you have to anticipate this.

There are even 64 bit MAX_INT ascensions, although those are done of course with exploiting some bugs.

https://nethackwiki.com/wiki/Notable_ascensions

Maud is a beast!

How can you achieve a +100 Magicbane without Wizard-mode? Damn.

I didn't watch the TTYREC but I am seriously puzzled by that. Anyone has insight into this?

Scroll of enchant weapon above +6 has a 2/3 chance of vaporizing the weapon and then a 1/N chance of actually increasing the enchantment by +1, so if you can manipulate RNG you can make sure that you always get the no-vaporize +1 result.

Is this just ai job for the 3000 if logic. Seems there is a feedback loop for the core trial and error logic

Something else that's not obvious to me: why does the fountain have to be next to a wall?

From the post:

> The fountain is required for wishes. The wall is required to be able to offset the random state without advancing the game state – every time the character attempts to walk into a wall, it calls random() without wasting any in-game time. From the fountain, the bot ascends completely on her own.

They describe that in the article. To be able to bump into the wall and advance the RNG one step at a time without passing in-game time. Presumably that's to ensure that the next Wish will be successful.

D'oh. Not sure how I missed/forgot that. Thanks.

NetHack can be very fun, if you invest some time. I recommend to start with a GUI version.

Alternatively, for a roguelike cut from the same mold as Nethack but with a very different philosophical bent, I recommend Dungeon Crawl Stone Soup, which can be played either locally, online in the classic SSH fashion, or via a web browser with a nice graphical UI (e.g. http://crawl.akrasiac.org:8080/#lobby , click on any name there to observe other players in action).

I agree wholeheartedly. Nethack is fun but gameplay-wise it's a bit of a mess, many of the mechanics are extremely obtuse if you don't spoil yourself. And when you start spoiling you never know when to stop.

On the other hand DCSS's game design is pretty stellar in my experience. It's better balanced than Nethack and relies less on arcane knowledge to get through the game. I've always ended up being frustrated while playing Nethack blindly because it feels unfair, meanwhile when I started reading spoilers I felt like I was cheating. DCSS handles that a lot better I think.

I think it's the very best dungeon crawler when it comes to comfort of use and startability for new players.

And I would suggest it not just for gamers but for programmers as well. There is a lot one can learn about user interfaces, shells, coding, architecture, data management (items, races etc are all data) with the additional motivation to learn it while playing.

> for programmers as well

https://twitter.com/crawlcode :)

I played my first NetHack games about 20 years ago and started with the GUI versions, but the game really hooked me when I tried it with the ASCII graphics. They are quite good and if you put a bit of time to it, you should be able to ascend in a couple of months.

Aye, good times...

> you should be able to ascend in a couple of months.

I think it took me a couple years to ascend without cheating, I don't know whether to cry or laugh at my former self :)

Btw, I think modern nethack playing is quite different from the old times, because of the amount of easy to find information (i.e. wiki,guides etc).

Playing without spoilers is more interesting but can become frustrating much faster.

I thought I was good in Nethack, being ascended a couple of time with a valkyrie and once with a samurai. Then I started in uni where people ascended all the characters quite frequently in the guild room computers.

You just need time and imagination.

I started with Hack on DOS and later graphic versions of NetHack also never appealed to me. The biggest drawback was recognizing all the different monsters. With ASCII it's quite clear what letters you must fear the most. I played for years and never ascended though.

I don't, GUI is just not the same. Lice are the same graphic size as dragons, it's hard to ignore that. If it's an "l" vs a "D" my imagination is allowed to make the difference.

I recommend this series https://www.youtube.com/watch?v=eV676QuiEj8&list=PLHzN3MktVP...

It is two guys, the player is starting from almost no knowledge and there is a "leader" who is a veteran leading him through the game (or watching him die). It's very entertaining and also acts as a tutorial.

I recommend trying Pixel Dungeon (similar to Rogue) or Sprouted Pixel Dungeon (similar to Hack) on Android first.

I have yet to find the right gui nethack for me... what are your suggestions?

Also - any good tower defense suggestions?

The best NetHack GUI that I have used is glhack, but I believe it was discontinued long ago.

sudo pacman -S glhack

Looks like the TTYrec is missing. Did NAO remove it?

Looks like the URL is mangled by being repeated, that's odd. It seems to work when I de-dupe it, though. ^^

https://alt.org/nethack/trd/?file=https://alt.org/nethack/us...

That only has 3 frames...that can't be right..?

Try Firefox. Doesn't work in Chrome for me either.

Works for me! Thanks!

Reply on news.ycombinator.com