9

Recently, there was posted a video from the YouTube channel Summoning Salt, talking about speedrunning Super Mario Bros and how close humans are to perfectly speedrunning each level. In this video, it is claimed that the perfect speedrun (with the rule of not pressing right and left at same time) of this game is 4:54.26, as this is the best done as a Tool-Assisted Speedrun. This leads to the following questions:

  1. Is there proof that this time is indeed perfect?
  2. Are there any other (non-trivial) video games where it was rigorously proved that a speedrun for it is optimal?
Improve this question
4
  • 4
    The Super Mario Bros ROM is about 30kb, which isn't a lot for a video game, but it is a lot for input to a proof about optimal state space traversal. Creating and optimizing the TAS is already a lot of work; proving optimality would be at least an order of magnitude harder, so given the low interest in such a thing from the community, I'd be surprised if anyone has ever made serious progress in creating such a proof, for this or any other non-trivial game.
    – murgatroid99
    Jun 12, 2021 at 16:28
  • 3
    @murgatroid99 Perhaps a proof could be created for Super Mario World. The game is non-trivial and larger than SMB but the fastest TAS runs are around 40 seconds due to a glitch that gives the player full control over memory early on. See youtube.com/watch?v=FkQdwUns7H8 for example. Perhaps a mathematician could brute force all possible inputs and prove that there is no way to compromise the system quicker.
    – cyberixae
    Jun 12, 2021 at 18:26
  • 3
    With a D-pad (4 directions) and 6 buttons (A, B, X, Y, L, R), that's about 2^8 possible input states on any given frame. The game runs at 60 FPS, so 40 seconds is 2400 frames. That means that you would need to check up to (2^8)^2400 = 2^19200 possible 40 second-long input sequences. That's over 10^6000, which is several thousand orders of magnitude greater than the number of particles in the universe multiplied by the number of planck times since the big bang. You couldn't brute force even a tiny fraction of that in all of time with all of the computers that could ever possibly exist.
    – murgatroid99
    Jun 12, 2021 at 18:48
  • 2
    @murgatroid99 Pure brute force is indeed out of the question for almost any game. It might be possible however to greatly reduce the space of sequences you need to search if you can prove for example that inputs at certain times have no effect on the game, or that there's no glitch that allows you to proceed faster if you don't do certain actions / if you can prove certain kind of movement is optimal, etc.
    – Carla is my name
    Jun 13, 2021 at 8:54

2 Answers 2

Reset to default
6

SMB best time was not proven - even small, simple, and scrutinized as it is, while a new discovery is unlikely, it's not impossible - the code is complex enough that unexpected emergent behaviors could appear.

But there are games that have been proven to have 'perfect' speedruns. One could split these into specific categories:

  • Zero time. Usually in categories using some sort of in-game timer that pauses on certain events, or the time is quantized in intervals that are sufficiently large they can't be decreased any further - say, turn-based strategies finished on turn 1. There's no way to improve that category. Examples would be Pokemon RED with UberLarge Skip Glitches or Europa Universalis 4 Pyramid of Skulls IGT.

  • Trivial frame-perfect solution. A run that consists of only a couple inputs separated by unskippable animation (so that the inputs are processed on the first frame they can be), trivially leading to the perfect time. Example: Clue, and a number of simple point-and-click puzzlers.

  • Sufficiently short that all possible inputs can be analyzed - in other words, if the best known speedrun is a couple thousand frames long, a tool can be written that will permute through all possible inputs on that initial number of frames of the game, checking if any will produce a better result. Drag Racer for Atari 2600 was such a game, where this sort of proof was performed to prove the "world record holder" cheated. This sort of proof is also easy in many side-scroller games in glitchless categories, which don't allow boosting the player over what the game mechanics provides. In this case multiplying the player's maximum speed by distance to the end of the game gives the simple 'best possible' result.

But if you consider these 'trivial', then the answer is "no". Mathematical proofs of pretty much anything about software get exponentially more expensive with size of the software in question, and cost of proving correctness of a program half a kilobyte long goes into many millions of dollars and involves supercomputers. That's something done with jet engine controllers, weapon systems, medical equipment firmware - not with video games. And a game like SMB is way too long and complex for that sort of analysis anyway. The best we can know is that a lot of people scrutinized the code and nobody found any new timesaves - but that is an assumption that failed many times in the past.

Improve this answer
4

SMB is a very 'solved' game. Its an old game, short, that is run by a lot of runners.

So there is no new strats that are found often.

Also, SMB is a 'simple' game. There is no perfect routing for collectibles that could be optimised or a sidequest that could be skipped. Its get to the end of the levels, and the only complexity is the level skip zones, that are known and it would be a surprise if suddenly a new one was found after almost 40 years. In other games there is always the possibility that a different route might suddenly be found and be better. But as I said, SMB being just 'get to the flag and thats it, there is no 'different route' that might work.

So you can assume that looking at a TAS, that makes no errors that humans are doing, and that that TAS is limited to not do inhumane things, the TAS is then what would be the perfect, human achievable time.

But yeah when we say 'Perfect' its 'perfect as of now'. But for SMB, since its a game that lots and lots of speedrunners have ran, and its been analysed backwards and forwards, it can be tought that we will never find a new exploit that REALLY changes the game. Probably a few frames here and there, but not something that would save even seconds. That being said: we can never say with certainty that nothing will be found again. So as I said: Perfect as of now.

Improve this answer
10
  • 3
    There could be some unknown glitch or strat that saves time so that the TAS is not really perfect. Anything less than a rigorous mathematical proof is not enough to convince me. I also don't mind if the TAS does inhumane things: to me a speedrun of a game is a sequence of inputs for every frame that ends in completing the game, and perfect means there is no other sequence with lower time that completes it.
    – Carla is my name
    Jun 12, 2021 at 14:20
  • Yeah when we say 'Perfect' its 'perfect as of now'. But for SMB, since its a game that lots and lots of speedrunners have ran, and its been analysed backwards and forwards, it can be tought that we will never find a new exploit that REALLY changes the game. Probably a few frames here and there, but not something that would save even seconds. That being said: we can never say with certainty that nothing will be found again. So as I said: Perfect as of now.
    – Fredy31 ♦
    Jun 14, 2021 at 13:53
  • 2
    If even 1 frame can be saved, then it's not perfect by the definition i gave. And surprises do happen sometimes.
    – Carla is my name
    Jun 14, 2021 at 13:57
  • 1
    It is not mathematically impossible. At worst you could iterate every possible input sequence in length order until you get one that works. Ofc that is way beyond current technology. Perhaps there could be easier ways for some games.
    – Carla is my name
    Jun 14, 2021 at 14:09
  • 1
    I am aware of that, that's why i said it's "way beyond current technology". Just wanted to point out that it's not correct to say that is "mathematically impossible". And while the space of possibilities is far too big, there's the possibility that we can exclude a very big portion of those possibilities. Something like this was used to prove the "god number" of a 3x3 rubiks cube.
    – Carla is my name
    Jun 14, 2021 at 14:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .