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]
Leave a Reply