It looks like a team of Scientists just confirms the notion that Classic Nintendo games are indeed hard. Yes,it's on their research paper. Wow.
According to the paper, five Nintendo classics are "NP-Hard." It means that the games are
“...are most difficult to solve by computational means because the time it takes to find a solution tends to increase so quickly with the size of the problem that it just isn’t practical to perform the computation.”
In verbatim, from the paper itself, Super Mario Bros. is a hard game. Why?
Suppose there is a solution and consider any path that Mario takes through the stage. This path needs to visit every enemy at most once. The only other permanent objects in the game are potential Koopa shells, but these can only slide and fall, so they must either fall down a bottomless pit eventually and leave the game, or they enter a cycle where they bounce back and forth between two walls. In either case, the shell can be ignored, because a perfect player gains nothing by jumping on the shell to stop it. Therefore there exists a solution that is polynomial in the size of the input.
More info from the Washington Post here.
No comments:
Post a Comment
Say something! No log-in reguired!