Calling a game “difficult” seems to be a matter of personal judgment. Not so, according to an international team of computer scientists. In recent years, scientists have analyzed Super Mario Bros. like it’s a math problem and beating a certain level is the solution. Now they’ve expanded their analysis to every possible arbitrary level, and they’ve shown it 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. works. For example, every time the game needs a random number, the number generator isn’t really random. from Mario number generator starts with a fixed seed that is updated deterministically every time a scene is calculated. It’s only when a player helps create a particular scene that the scene actually becomes random – something that doesn’t happen when a computer is solving a level.
There are also well-documented cases where, as the authors put it, “the implementation
by Super Mario Bros. goes against the intuitive Mario physics most players are familiar with.” These include the ability to blast Mario through a wall or jump through a brick ceiling, provided there’s a monster on top. And while the game tracks objects that move a little off screen, the game forgets about bad guys who stray too far from the edges.
Still, much of the work is the Mario equivalent of a spherical cow. The levels used in the team’s work have arbitrary dimensions and require customization Super Mario Bros. that remembers what happens to objects that fall off the visible screen. However, just like in the real game, things are loaded from a fixed level file and there are time limits, checkpoints, multiple lives and coins.
The authors believe that within those limits Super Mario Bros. is PSPACE hard. Like NP problems, PSPACE seems to take exponential time on a traditional computer to solve. But PSPACE hard problems also require exponential time to determine whether a proposed solution is correct.
The authors are also looking at a more typical version of the game: one in which off-screen objects are forgotten, the screen is fixed in size, and there are a limited number of sprites on screen at a time. Here the game can be solved in polynomial time and certain iterations fall in NP-hard.
While this kind of work may seem like a waste of time, one of the authors (Erik Demaine at MIT) says it’s valuable from an educational point of view. His students need to understand various forms of math difficulty, and using video games as an example, he argues, makes this intuitive. It has also been used Donkey Kong as a learning tool.
Another author, Giovanni Viglietta of the University of Ottawa, has posted online some of the modified ROMS used in the work. drs. Demaine and Viglietta will be joined by Aaron Williams, a professor of computer science at Bard College, Simon’s Rock, in presenting their new paper at the International Conference on Fun with Algorithms next week.