14 ms·

When 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

by schoen 8y ago

When 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 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 8y 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 8y 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 8y 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 8y 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 8y 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 8y 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 8y 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 8y 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 https://en.wikipedia.org/wiki/POKEY
- robocaptain 8y 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-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 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 8y 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.
bhaak 8y ago
That'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 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 8y 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.
davedx 8y 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 8y 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

by schoen 8y ago

merlincorey 8y 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 8y 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 8y 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 8y 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 8y 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 8y 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 8y 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 8y 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 8y 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 https://en.wikipedia.org/wiki/POKEY
robocaptain 8y 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-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 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 8y 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.

bhaak 8y ago

That'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 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 8y 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.

davedx 8y 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 8y 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