NetHack beaten in 7 minutes 15 seconds real time

(pellsson.github.io)

417 points | by User23 155 days ago

19 comments

  • schoen 155 days ago

    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.

    • merlincorey 155 days ago

      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.

      • malux85 155 days ago

        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

        • zawerf 155 days ago

          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!

          • dklsafhjskljfl 155 days ago

            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.

            • simonh 155 days ago

              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.

              • dharmab 155 days ago

                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.

              • bluGill 155 days ago

                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.

                • sehugg 155 days ago

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

                  • karmakaze 155 days ago

                    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

                • robocaptain 155 days ago

                  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.)

                • bhaak 155 days ago

                  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.

                  • Gaelan 155 days ago

                    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).

                    • chrchang523 155 days ago

                      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.

                  • riffraff 155 days ago

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

                    They seem straightforward to implement even for nethack.

                    • bhaak 155 days ago

                      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.

                    • davedx 155 days ago

                      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.

                      • lagadu 155 days ago

                        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

                      • beefhash 155 days ago

                        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

                      • fzeroracer 155 days ago

                        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

                        • will_pseudonym 155 days ago

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

                          • skibz 155 days ago

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

                            • TremendousJudge 155 days ago

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

                              • aidenn0 155 days ago

                                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.

                              • wwwhizz 155 days ago

                                Wow, that's insane!

                              • hannofcart 155 days ago

                                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.

                                • linuxlizard 155 days ago

                                  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.)

                                • dmix 155 days ago

                                  Had to look up this abbreviation:

                                  c!oGL = cursed potion of gain level

                                  https://nethackwiki.com/wiki/Abbreviations

                                  • schoen 155 days ago

                                    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.

                                    • dmix 155 days ago

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

                                  • ourmandave 155 days ago

                                    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.

                                    • tibbon 155 days ago

                                      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?

                                      • XCabbage 155 days ago

                                        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?

                                        • MaupitiBlue 155 days ago

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

                                          • remote_phone 155 days ago

                                            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.

                                            • jandrese 155 days ago

                                              That sounds closer to Rogue than Nethack.

                                              • remote_phone 153 days ago

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

                                            • flatline 155 days ago

                                              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.

                                              • fb03 155 days ago

                                                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.

                                                • hxegon 155 days ago

                                                  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.

                                                • caymanjim 155 days ago

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

                                                  • klyrs 154 days ago

                                                    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...

                                                    • YeGoblynQueenne 155 days ago

                                                      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.
                                                      • greendestiny 155 days ago

                                                        You and me both. :(

                                                      • xyproto 155 days ago

                                                        Just waiting for AlphaNethackZero to beat this record.

                                                        • DataWraith 155 days ago

                                                          > 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.

                                                          • HelloNurse 154 days ago

                                                            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.

                                                          • octernion 155 days ago

                                                            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

                                                            • schoen 155 days ago

                                                              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. :-)

                                                              • octernion 155 days ago

                                                                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!

                                                                • schoen 155 days ago

                                                                  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.

                                                                  • jandrese 155 days ago

                                                                    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.

                                                                    • octernion 155 days ago

                                                                      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?

                                                                      • jandrese 155 days ago

                                                                        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.

                                                              • njn 155 days ago
                                                                • orbital-decay 155 days ago

                                                                  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?!

                                                                  • IncRnd 155 days ago

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

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

                                                                    • minikomi 155 days ago

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

                                                                      Thanks for the laugh

                                                                      • kazinator 155 days ago

                                                                        > 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.

                                                                      • timClicks 155 days ago

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

                                                                        • bhaak 155 days ago

                                                                          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

                                                                    • tokai 155 days ago

                                                                      Maud is a beast!

                                                                    • fb03 155 days ago

                                                                      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?

                                                                      • aetimmes 155 days ago

                                                                        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.

                                                                      • ngcc_hk 154 days ago

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

                                                                        • XCabbage 155 days ago

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

                                                                          • mbel 155 days ago

                                                                            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.

                                                                            • Jolter 155 days ago

                                                                              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.

                                                                              • XCabbage 155 days ago

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

                                                                            • haolez 155 days ago

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

                                                                              • kibwen 155 days ago

                                                                                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).

                                                                                • simias 155 days ago

                                                                                  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.

                                                                                  • erikb 155 days ago

                                                                                    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.

                                                                                • pimeys 155 days ago

                                                                                  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...

                                                                                  • riffraff 155 days ago

                                                                                    > 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.

                                                                                    • pimeys 155 days ago

                                                                                      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.

                                                                                    • avian 155 days ago

                                                                                      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.

                                                                                    • Scarblac 155 days ago

                                                                                      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.

                                                                                      • wingerlang 155 days ago

                                                                                        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.

                                                                                        • v_lisivka 155 days ago

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

                                                                                          • samstave 155 days ago

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

                                                                                            Also - any good tower defense suggestions?

                                                                                            • haolez 152 days ago

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

                                                                                              • l0b0 155 days ago

                                                                                                sudo pacman -S glhack

                                                                                            • Jolter 155 days ago

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