# Science Proves Old Video Games Were Super Hard

Sitting down with a bunch of old games in the Super Mario Bros., Donkey Kong, Legend of Zelda, Pokemon and Metroid franchises, Belgian scientists have proven beyond all doubt that those games are way hard. To showcase their work, they've written a scientific paper outlining their findings.

Greg Aloupis, Erik D. Demaine and Alan Guo, from the Free University of Brussels, ultimately found that most of the games can be classified as "NP-hard", a scientific term meaning they're about as tough as a problem can get.

While you'd think this is all a joke, and it mostly is, reading the paper shows a lot of thought has gone into it. Serious thought. Here's Pokemon, for example:

The no-reverse gadget serves a similar function as the one-way gadget, except after traversing

from a to b, the player cannot traverse it from b to a. This is implemented by the gadget in

Figure 21. Clearly, the player cannot enter via b, because that lures the weak Trainer to block the

passage. Suppose the player enters through a. They can safely walk to b, because the weak Trainer

is blocking the bottom strong Trainer's line of sight. However, to reach b, the player must lure the

weak Trainer out of the line of sight of the strong Trainer, hence the player may never return in

the reverse direction.

And here's the sliding block puzzles from Zelda:

Generalized Legend of Zelda is NP-hard by reduction from a puzzle similar to

Push-1, because Legend of Zelda contains blocks which may be pushed according to the same rules

as in Push-1 [2], except that in Zelda, each block may be pushed at most once. Fortunately, all

of the gadgets in the reduction for Push-1 found in [2] still function as intended when each block

can be pushed at most once, with the possible exception of the Lock gadget. However, a simple

modication to the Lock gadget (illustrated in Figure 11) suces. (Here we assume that Link has

no items, in particular, no raft.)

You can take a look at the whole paper at the link below.

Classic Nintendo Games are (NP-)Hard [Cornell, via MIT]

“NP-hard”, a scientific term meaning they’re about as tough as a problem can get.

No, it means they're at least as hard to solve as the class of problems in NP, where NP is the class of problems which can be solved in polynomial time on a non-deterministic machine. Not all NP-hard problems are in NP (the ones that are are referred to as being NP-complete).

It's a whole lot of CompSci hand-waving to say that these are problems where there is no solution which can be calculated in reasonable time (and also a perfect solution for one NP-hard problem actually is the solution for all NP-hard problems). We can only ever get an approximate solution for these problems.

This whole thing is going to be absolutely meaningless to people without a computer science background (it doesn't mean what the article thinks it means) and really shouldn't be reported on a general gaming blog.

Thanks for the clarification -0

Must admit, until I read your comment, I was a bit confused by the examples they used.

I get the feeling Mr Plunkett didn't fully understand what he was writing about. Thanks for clearing things up a bit, would be interesting to see what the US comments thought about it.
While a new perspective on puzzles in old video games, there is something a little confused about the way the article presents it.

Yeah, it's fairly esoteric computer science stuff. 'Big O' notation and things. Hell, even saying 'at least as hard as the hardest NP problems' is hand-waving because of the non-deterministic bit. Non-determinism means you can execute every possible solution at once and gets into the same sort of territory as quantum mechanics, Schrodinger's Cat, infinite monkeys banging on typewriters etc.

Humans are very good at coming up with approximate solutions to these sorts of problems. Our brains are wired for it. Effectively a lot of our day-to-day life involves solving NP-Hard problems with approximate solutions. You could think of the perfect solution to Mario for example as a speedrun where you never die, collect every star, kill every monster and do it with the minimum number of button presses in the shortest space of time. If you had a program that could do that exactly every time, finding that solution in our deterministic universe would take a perverse amount of time. Running every possible version of the solution at once (non-determinism) would reduce the time, but it would still be a very difficult problem.

You can make an AI which could iteratively improve itself toward that optimal solution instead. Which is what people who do speed runs effectively are doing with themselves. But this will always be an approximate solution, and not a perfect one. Approximates are 'good enough' for us most of the time.

See? It's hand-waving that's not relevant to anyone but Computer Scientists.

K, here's your comment from the land of sarcasm (and fat people): "I'm bored. Guess I'll check Kotaku or something... Oh, what? Old video games are harder? Oh, well I REALLY never knew that." *60 seconds later* "Thank you, Luke Plunkett, so much, for wasting one minute of my life I will never, EVER get back." Note: I'm on the Australian site because the US site sucks, imho.

I think the number 5 is a pretty close approximation of infinity. IMO

Awe, this was a let down. I was hoping for something presenting an actual argument! All I get from this is that the researchers thought it would be a waste of time to push blocks in Zelda.

Someone please pay negative zero for his article

Someone please pay negative zero for his article.

lol, journalists thinking they know stuffs about science.

I'm not disagreeing with the topic though. I don't think I finished one game on the Sega Master System 2 and have tried many times. Games like Alex The Kid, Michael Jackson Moonwalker, Smash TV, Wonder Boy 3, Double Dragon, Transbot etc etc. Where I can play games today on hard/extreme with ease. Now you may think, you're older, more experience. I STILL CAN'T FINISH THOSE GAMES NOW ON THE SEGA!!!! Lol!