Ever since I saw someone beat Super Mario World by reprogramming the game from <i>within the game itself</i> (<a href="https://youtu.be/14wqBA5Q1yc" rel="nofollow">https://youtu.be/14wqBA5Q1yc</a>), I realized that speedrunning retro games is truly next-level these days.
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).<p>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.<p>[0] <a href="https://compcert.org/" rel="nofollow">https://compcert.org/</a>