Maybe you’ve seen these videos online of video game “speed-runs,” where the goal is to complete, let’s say, a game of “Super Mario Bros.” as fast as possible. They generally fall into one of two categories: actual humans playing the game in real-time, punching actual buttons and all that, or the “tool-assisted” variant, where players use an emulator to basically play the game slowed down, being able to use button combinations that wouldn’t be physically possible on a real controller, and, the big one: being able to “rewind” the game and doing moves over and over until they get them perfect.
I’ve played around with an NES and SNES emulator a bit and it’s basically like a combination of Neo’s powers at the end of “The Matrix” and the ability to travel back in time to fix mistakes that those aliens in “Edge of Tomorrow” have. After I’ve played that way for a few hours I got so used to this strange power that I had to remind myself the real world doesn’t quite work that way. Which is a good thing to keep in mind when you’re riding your bike down a busy street…
There are huge communities around both tool-assisted and non-assisted speed-runners, and one thing that kinda blows my mind is that even for games that have been around for two decades they are still setting new records on a regular basis. These guys and girls don’t rest on their laurels; they’re constantly looking for ways to improve the current runs, even if the end result’s just one frame faster than the old record. It’s fascinating.
The human element, even with tool-assisted speed-runs, is a huge, important part of the experience, and I immensely enjoy both the skill and the creativity on display there. But I was wondering if a computer program, on its own, would be able to find the fastest way through a video game. If we take something relatively simple like the the first Super Mario Bros. on the NES, and just let a computer play through all possible ways to play the first level, how long would it take to master it?
The options aren’t unlimited. The NES controller only has a few inputs: four directions (up, down, left, right), an “A”-button that makes Mario jump, and a “B”-button that, when held down, makes Mario run. Without physical restrictions (it’s impossible [I think?] to press both “up” and “down” simultaneously on the controller), our computer would have, on each frame of the game, the option to either press no button at all, one of the six buttons, a combination of two of the six, and so on. That’s, like, 64 unique button combinations per frame?
The longest the level can be played is until the timer runs out, which I gather is around 200 seconds. (I’ve just spent more time than I’d like to admit trying to come up with exact numbers on this. It gets pretty messy with frame rates and other stuff that I don’t really understand. Feel free to write in with the correct numbers.) Let’s say the game has 60 frames per second (again, not an exact number, just something to work with), that would mean a maximum of 12,000 frames per run-through, with 768,000 unique button combinations. Less than that, actually, if you stop the run each time Mario either dies or reaches the goal before the timer is up.
The world record for Level 1-1 of Super Mario Bros., as far as I can tell, is somewhere around 32 seconds (including the little victory animation at the end), so we can just tell our computer to stop trying if it hasn’t reached the goal after that time. So already we’re down to about 120 million button combinations that contain the fastest possible way (or ways) through the level.
If we have our computer play through each combination for 32 seconds in real time it should be done within 45 days.
And why stop there? The record for all of Super Mario Bros. is under 5 minutes, which should take our computer no longer than 10 years to beat (or confirm).
Let’s get on that.