3 ms·

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 completi

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/ https://compcert.org/

shakna 5y ago
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.
- hakuseki 5y ago
  It's a decidable problem because the duration is bounded (by the best current time).
  - shakna 5y ago
    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.
    - hakuseki 5y ago
      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.
      - shakna 5y ago
        > 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.
        toast0 5y ago
        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.
boomboomsubban 5y ago
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.
- ant6n 5y ago
  its a pretty large search space. imagine 60fps, 10min of play, 8 possible buttons every frame.
  - GauntletWizard 5y ago
    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.
- deleted 5y ago
  [deleted]
gwern 5y ago
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 http://tasvideos.org/6347S.html for _Breakout_.

shakna 5y ago

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.

hakuseki 5y ago
It's a decidable problem because the duration is bounded (by the best current time).
- shakna 5y ago
  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.
  - hakuseki 5y ago
    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.
    - shakna 5y ago
      > 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.
      - toast0 5y ago
        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.

boomboomsubban 5y ago

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.

ant6n 5y ago
its a pretty large search space. imagine 60fps, 10min of play, 8 possible buttons every frame.
- GauntletWizard 5y ago
  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.
deleted 5y ago
[deleted]

gwern 5y ago

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 http://tasvideos.org/6347S.html for _Breakout_.