Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

NetHack beaten in 7 minutes 15 seconds real time

pellsson.github.io

Post reply on HN
Print view View original

71–80 of 92 posts

Re: NetHack beaten in 7 minutes 15 seconds real time

#71

Post by tibbon »

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?

Re: NetHack beaten in 7 minutes 15 seconds real time

#72

Post by octernion »

schoen wrote: post #70
octernion wrote: post #61

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!

Re: NetHack beaten in 7 minutes 15 seconds real time

#73

Post by jandrese »

octernion wrote: post #72
schoen wrote: post #70

Earlier quoted context omitted.

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!

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.

Re: NetHack beaten in 7 minutes 15 seconds real time

#74

Post by Gaelan »

bhaak wrote: post #34
schoen wrote: post #2

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 pro…

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 e…

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

Re: NetHack beaten in 7 minutes 15 seconds real time

#75

Post by jandrese »

remote_phone wrote: post #10
MaupitiBlue wrote: post #6

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 wro…

That sounds closer to Rogue than Nethack.

Re: NetHack beaten in 7 minutes 15 seconds real time

#76

Post by schoen »

octernion wrote: post #72
schoen wrote: post #70

Earlier quoted context omitted.

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.

Re: NetHack beaten in 7 minutes 15 seconds real time

#77

Post by Liskni_si »

dlgeek wrote: post #64
Roujo wrote: post #55

Earlier quoted context omitted.

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.

Re: NetHack beaten in 7 minutes 15 seconds real time

#78

Post by karmakaze »

bluGill wrote: post #57
malux85 wrote: post #23

Earlier quoted context omitted.

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

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.

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

Re: NetHack beaten in 7 minutes 15 seconds real time

#79

Post by octernion »

jandrese wrote: post #73
octernion wrote: post #72

Earlier quoted context omitted.

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!

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?

Re: NetHack beaten in 7 minutes 15 seconds real time

#80

Post by aidenn0 »

skibz wrote: post #44
fzeroracer wrote: post #25

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

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

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.

Post reply on HN