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.
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
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.
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.
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.
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.
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; 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.
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). This allowed determining the RNG seed from a running game. However, he also made a patch to use a cryptographically secure PRNG. 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.
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 
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.
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.
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 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.
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.
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.
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...
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.
> 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.
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.
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.
> 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.
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.
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.
> 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.
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.
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.
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.
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.
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.