(credit: Aurich Lawson)
Calling a game "hard" would seem to be a matter of personal judgement. Not so, according to an international team of computer scientists. For the past several years, the scientists have been analyzing Super Mario Bros. as if it were a math problem and beating a particular level is the solution. Now, they've extended their analysis to cover any possible arbitrary level, and they've shown that Super Mario Bros. belongs to a class of problems called PSPACE-complete.
The team's work benefits from how much we already know about how Super Mario Bros. operates. For example, every time the game needs a random number, its number generator isn't actually random. Mario's number generator starts with a fixed seed that's updated deterministically each time a scene is calculated. It's only when a player helps create a particular scene that the scene becomes effectively random—something that's not at issue when a computer is solving a level.
There are also well-described cases in which, as the authors put it, "the implementation
of Super Mario Bros. is counter to the intuitive Mario physics with which most players are familiar." These include the ability to pop Mario through a wall or to jump through a brick ceiling, provided there's a monster on top. And, while the game tracks objects that move slightly offscreen, the game forgets about bad guys who wander too far off the edges.
Read 5 remaining paragraphs | Comments
No comments:
Post a Comment