Горячие Новости

Облако тегов

Вычислена сложность Mario и Donkey Kong

Вычислена сложность Mario и Donkey Kong

Новости инвестиций, игры. Группа ученых из Массачусетского института и Брюссельского университета взялись за исследование степени сложности пяти классических игр, представленных Nintendo. В пятерку вошли, конечно же, серии Donkey Kong, Mario Zelda, Metroid и Pokemon. Результаты были сформированы в статью, однако, на данном этапе ее пока еще не приняли для публикации в журнале с рецензией. Тем не менее, препринт все же удалось найти.


Ученые использовали в своем эксперименте универсальную машину Тьюринга, при помощи нее они формализовали игры. Каждый уровень, практически, во всех указанных играх представляет собой определенный лабиринт с ограничением на размер, в котором предлагается точное количество ловушек. Исследователи задали лишь один вопрос вычислительному устройству, есть ли способ пройти весь лабиринт от начала до конца, если известно состояние ловушек в нем и местоположение врагов.  


Как оказалось, обычная машина Тьюринга может делать выводы и она подошла к поиску ответа легко. Вопрос определения сложности каждого уровня Donkey Kong Country 1-3, Super Mario Bros., Super Mario World,  всех серий Legend of Zelda (кроме, Zelda II), Metroid и Pokemon решался просто – сложность NP. То есть, это означает, что техника может выполнить поставленные задачи за полиномиальное время.

Автор:
Мнение автора может не совпадать с мнением редакции. Если у Вас иное мнение напишите его в комментариях.
Возник вопрос по теме статьи - Задать вопрос »
comments powered by HyperComments
« Предыдущая новость «  » Архив категории «   » Следующая новость »

Рекомендованный брокер №1

Журнал «Биржевой лидер»

Журнал, интересные статьи

Видео

Энциклопедия

Сергей Собянин
Сергей Собянин
Яндекс.Блоги
Яндекс.Блоги
Google
Google
Пётр Порошенко
Порошенко Пётр Алексеевич
Грузия
Грузия
24 мая
24 мая