Hacker News Reader

Comment by dane-pgp | Hacker News Reader

I wonder if it will ever be possible for games like Super Mario Bros. to be "solved" in the sense that there is a formal proof of the shortest possible completion time (for a given category / ruleset of speedrun).

Presumably that would first require a disassembly of the game, with a proven compilation process back to the original ROM (something like what CompCert does[0]) and then, after enumerating all the possible glitches, building some sort of state machine that defines how the character can progress through each level.

[0] https://compcert.org/

View on HN

With enough dedication and CPU-cores and reasonably intelligent pruning of the search tree, you may be able to do something like that: http://tasvideos.org/6347S.html for _Breakout_.

I think formally proving it will be difficult, but Mario has been disassembled and I bet that people have tried hitting every possible key combination at every possible location already. With a decade without any theoretical improvement, it's probably solved.

its a pretty large search space. imagine 60fps, 10min of play, 8 possible buttons every frame.

The world record Speedrun is under 5m, which cuts down the search space a lot. Still, well outside of complete search time, but you can cut out a huge amount that never progress or die.

You would have to have a _very_ limited set of rules for the speedrun.

There's a lot of games where certain glitches allow you to actually rewrite the game as you're playing it. Which means that a formal proof would possibly toss you into Turing Complete territory.

It's a decidable problem because the duration is bounded (by the best current time).

The solution may be easily bounded, but the solver may not be.

For example, a simple shift cipher has one solution that simply and easily produces the expected output. However, a one-time-pad is still incredibly difficult to break to demonstrate that output, even when you may know some key parts of the expected output.

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.

> 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