Hacker News Reader

Comment by hakuseki | Hacker News Reader

I'm not sure which part you're saying is unbounded, but everything looks bounded to me. A game is played in finite time, on hardware with bounded operations per second, and AFAIK the NES is a deterministic computer, so the solution does not need to involve any algorithms -- it is simply a fixed sequence of button presses.

View on HN

> A game is played in finite time, on hardware with bounded operations per second, and AFAIK the NES is a deterministic computer, so the solution does not need to involve any algorithms -- it is simply a fixed sequence of button presses.

Glitches allow you to write arbitrary data into arbitrary memory positions.

So whilst it is bounded, it is bounded to "any program that can run in less than X time", which as far as I know, is beyond what we can predict within bounded time. The solver may never complete.

Most of the time once you get execution, you jump to the end credits, without a lot of other setup. At worst, you have two phases. Phase 1 is before abritrary code execution, where your inputs are limited by the original program, which usually samples the controllers once per frame; phase 2 would start once you get code execution and could count cycles if need be.

Both of these are bounded by existing solutions. We know how many frames, and how many cycles, so you can stop when you get there. Still a very large search space, though.

Reply on news.ycombinator.com