Have there been video games for which perfect speedruns were mathematically proven?

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.

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.