10 ms·
NetHack beaten in 7 minutes 15 seconds real time
- schoen 8y agoWhen I saw the previous submission of this as https://news.ycombinator.com/item?id=18853508 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 8y agoThey 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 8y agoThis 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 8y agoDo 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 8y agoOld 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 8y agoIf 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 8y agoOld 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 8y agoAtari 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.
- robocaptain 8y agoI 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-tool-assisted.html 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.)
- riffraff 8y agoWouldn't something as simple as DCSS autoexplore/go to functionalities classify as "tool assisted" ? They seem straightforward to implement even for nethack.
- bhaak 8y agoUnNetHack 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.
- bhaak 8y agoThat's why my submission https://news.ycombinator.com/item?id=18843584 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 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/ 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 8y agoTo 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 8y agoThat'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.
- davedx 8y agoHah! 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 8y agoGames 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
- haolez 8y agoNetHack can be very fun, if you invest some time. I recommend to start with a GUI version.
- samstave 8y agoI have yet to find the right gui nethack for me... what are your suggestions? Also - any good tower defense suggestions?
- kibwen 8y agoAlternatively, 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 http://crawl.akrasiac.org:8080/#lobby , click on any name there to observe other players in action).
- erikb 8y agoI 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.
- floatboth 8y ago> for programmers as well https://twitter.com/crawlcode https://twitter.com/crawlcode :)
- dmix 8y agoHad to look up this abbreviation: c!oGL = cursed potion of gain level https://nethackwiki.com/wiki/Abbreviations https://nethackwiki.com/wiki/Abbreviations
- schoen 8y agoFor 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 8y agoThanks for the write up, that makes parts of the article make more sense.
- MaupitiBlue 8y agoI’ve been trying to reach the amulet for 30 years.
- remote_phone 8y agoI’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 8y agoThat sounds closer to Rogue than Nethack.
- remote_phone 8y agoNo it was called Hack. This is around 1985 or 1986.
- flatline 8y agoI 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.
- greendestiny 8y agoYou and me both. :(
- caymanjim 8y agoIt took me about 20 years of casual play, then another couple months of fairly obsessive play. It's effectively impossible without spoilers.
- njn 8y agohaha, nice. https://alt.org/nethack/fastasc.html https://alt.org/nethack/fastasc.html
- orbital-decay 8y agoAn 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 8y agohttps://nethackwiki.com/wiki/1-turn_ascension https://nethackwiki.com/wiki/1-turn_ascension Check out the information at the very end of this page.
- timClicks 8y agoI wonder if someone will figure out how to overflow the score counter.
- bhaak 8y agoOverflowing 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 https://nethackwiki.com/wiki/Notable_ascensions
- minikomi 8y ago> paste it into NetHack's terminal, and wait approximately 19 days. Thanks for the laugh
- hannofcart 8y agoThe 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 8y agoI 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.)
- beefhash 8y agoThis 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.bz2 https://xorhash.bitbucket.io/nh/nethack_rng_tools-0.2.3.tar.... [2] https://bilious.alt.org/?349 https://bilious.alt.org/?349
- natehouk 8y agoSuper interesting that Google Chrome trusts that https://xorhash.bitbucket.io https://xorhash.bitbucket.io link[0] you posted, but Facebook doesn't trust that SSL cert. Curious if bitbucket.io is serving different SSL certificates based on the web agent? [0] https://xorhash.bitbucket.io/nh/nethack_rng_tools-0.2.3.tar.bz2 https://xorhash.bitbucket.io/nh/nethack_rng_tools-0.2.3.tar....
- xyproto 8y agoJust waiting for AlphaNethackZero to beat this record.
- fzeroracer 8y agoRNG 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 https://www.youtube.com/watch?v=Bgh30BiWG58
- will_pseudonym 8y agoFYI, gameplay/commentary starts at 7:23. Here's a link at the timestamp: https://www.youtube.com/watch?v=Bgh30BiWG58&feature=youtu.be&t=443 https://www.youtube.com/watch?v=Bgh30BiWG58&feature=youtu.be...
- wwwhizz 8y agoWow, that's insane!
- skibz 8y agoRemarkable. So is this player performing all of these movements that change the RNG behaviour from (muscle) memory?
- TremendousJudge 8y agoYeah, pretty much. Speedrunning takes all the obsessive practicing of classical piano concert performance and applies it to video games. It's insane
- aidenn0 8y agoThey 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.
- XCabbage 8y agoHuh. 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?
- XCabbage 8y agoSomething else that's not obvious to me: why does the fountain have to be next to a wall?
- mbel 8y agoFrom 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 8y agoThey 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 8y agoD'oh. Not sure how I missed/forgot that. Thanks.
- Jolter 8y agoLooks like the TTYrec is missing. Did NAO remove it?
- Roujo 8y agoLooks 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/userdata/S/SWAGGINZZZ/ttyrec/2019-01-05.23:56:16.ttyrec# https://alt.org/nethack/trd/?file=https://alt.org/nethack/us...
- fb03 8y agoHow 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 8y agoScroll 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.
- ourmandave 8y agoBlindly 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.
- octernion 8y agothis 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 https://en.wikipedia.org/wiki/Edge_of_Tomorrow
- schoen 8y agoThe 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 8y agooh 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!
- jandrese 8y agoThe 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 8y agoyeah, 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 8y agoThe 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.
- tibbon 8y agoMaybe 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?
- deleted 8y ago[deleted]
- DataWraith 8y 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 8y agoSplitting 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.
- ngcc_hk 8y agoIs this just ai job for the 3000 if logic. Seems there is a feedback loop for the core trial and error logic