Mario Is Hard, and That's Mathematically Official
New Scientist (03/14/12) Jacob Aron
Massachusetts Institute of Technology (MIT) researchers recently analyzed the computational complexity of video games and found that many of them belong to a class of mathematical problems called NP-hard. The implication is that for a given game level, it can be very tough to determine whether it is possible for a player to reach the end. The results suggest that some hard problems could be solved by playing a game. The researchers, led by MIT's Erik Demaine, converted each game into a Boolean satisfiability problem, which asks whether the variables in a collection of logical statements can be chosen to make all the statements true, or whether the statements inevitably contradict each other. For each game, the team built sections of a level that force players to choose one of two paths, which are equal to assigning variables in the Boolean satisfiability problem. If they permit the completion of a level, that is equivalent to all of the statements in the Boolean problem being true. However, if they make completion impossible, it is equal to a contradiction. Many of the games proved to be NP-hard, which means that deciding whether a player can complete them is at least as difficult as the hardest problems in NP.
New Scientist (03/14/12) Jacob Aron
Massachusetts Institute of Technology (MIT) researchers recently analyzed the computational complexity of video games and found that many of them belong to a class of mathematical problems called NP-hard. The implication is that for a given game level, it can be very tough to determine whether it is possible for a player to reach the end. The results suggest that some hard problems could be solved by playing a game. The researchers, led by MIT's Erik Demaine, converted each game into a Boolean satisfiability problem, which asks whether the variables in a collection of logical statements can be chosen to make all the statements true, or whether the statements inevitably contradict each other. For each game, the team built sections of a level that force players to choose one of two paths, which are equal to assigning variables in the Boolean satisfiability problem. If they permit the completion of a level, that is equivalent to all of the statements in the Boolean problem being true. However, if they make completion impossible, it is equal to a contradiction. Many of the games proved to be NP-hard, which means that deciding whether a player can complete them is at least as difficult as the hardest problems in NP.
No comments:
Post a Comment