Scientists have calculated the complexity of Mario and Donkey Kong - Cell phones

Scientists have calculated the complexity of Mario and Donkey Kong - Cell phonesAn international group of researchers from the Massachusetts Institute of technology and the Brussels free University determined the complexity of the five series of classic games from Nindendo - Mario, Donkey Kong, Zelda, Pockemon, and Metroid. Article scientists have not yet accepted for publication in a peer-reviewed journal, however, its Preprint available on the website arXiv.org. Through the work of scientists formalized the game with the help of machines Turing - universal model computing device. Levels in most of these games represent a maze of limited size with a fixed set of traps. The question of algorithmic complexity which was supposed to determine, scientists formulated as follows: for a given status of all traps in the maze and location of enemies is there a way to get from the beginning to the end of the maze. All scientists considered Super Mario Bros. 1, 3, Lost Levels, Super Mario World, Donkey Kong Country 1-3, all games Legend of Zelda (except Zelda II), as well as all games Metroid series and Pockemon. It turned out that the question of the definition of "solvability" of the level is the complexity of the NP. This means that a non-deterministic Turing machine solves this problem in polynomial time. When this question for Mario and Donkey Kong proved to be NP-complete, i.e., any problem in the class NP can be reduced to this in polynomial time an ordinary Turing machine. It also appeared that some games in the Zelda series have the PSPACE complexity, i.e. for solving the problem requires a polynomial amount of memory. According to the researchers, their results allow us to estimate from below the complexity of finding the optimal path between two points in these games - it is obvious that the search for such paths is certainly not more difficult question of solvability of one or another of the maze. However, the researchers note that a natural modification of the maze have helped to simplify the task. The researchers drew attention to the fact that in games like classic Mario all the traps and enemies outside of the fixed region (visible screen) are always fixed in the state of default. When in addition the size of the maze is always limited, scientists have shown that the problem can be solved in polynomial time on an ordinary Turing machine. In February arXiv.org the papers appeared in which scientists similarly calculated the complexity of the game Scrabble ("Scrabble"), known in the Russian version as "Erudite", as well as several classic games such as Pacman..



Похожие статьи

Ваше имя
Ваша почта
Город, область
Рассылка комментариев





Ввести код: