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

Облако тегов

Вычислена сложность 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

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

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

Видео

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

иранский народ
Народ Ирана
Пекельна кухня
Пекельна кухня
Михайлов Станислав Владимирович (Стас Михайлов)
Михайлов Станислав Владимирович (Стас Михайлов)
Liberty Reserve
Liberty Reserve
30 января
30 января
Правительство
Правительство