Ученые вычислили сложность Mario и Donkey Kong

Скриншот Super Mario

Международная группа исследователей из Массачусетского технологического института и Брюссельского свободного университета определила сложность пяти серий классических игр от Nintendo - Mario, Donkey Kong, Zelda, Pokemon и Metroid. Статья ученых пока не принята к публикации в рецензируемом журнале, однако, ее препринт доступен на сайте arXiv.org.

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

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

При этом вопрос для Mario и Donkey Kong оказался NP-полным, то есть всякая задача в классе NP может быть сведена к данной за полиномиальное время обычной машиной Тьюринга. Также оказалось, что некоторые игры из серии Zelda имеют сложность PSPACE, то есть для решения задачи требуется полиномиальное количество памяти. По словам исследователей, полученные ими результаты позволяют оценить снизу сложность поиска оптимального пути между двумя точками в таких играх - очевидно, что поиск подобного пути заведомо не проще вопроса разрешимости того или иного лабиринта.

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

В феврале в arXiv.org появились работы, в которых ученые аналогичным образом вычислили сложность игры Scrabble ("Скрэббл"), известной в русском варианте как "Эрудит", а также нескольких классических игр, например, Pacman.

Обсудить
Наука и техника00:0311 декабря
Проект наземной мобильной версии электромагнитной пушки

И так сойдет

Америка прекратила разработку сдерживающего Россию оружия
Они ушли
Русские покидают Сирию. Там остаются тысячи террористов, а войне не видно конца
«Этим проклятым американцам мы еще покажем!»
Афганцы полюбили русских и возненавидели США
Кровавый конвейер
На Гаити круглый год режут и свежуют скот
Реджеп Тайип ЭрдоганВ спину не больно
Россия забыла обиды и взахлеб дружит с Турцией
Дональд ТрампСвоих не бросаем
План Трампа: спасти богатых и сэкономить на бедных
Домашние заготовки
Почему российской строительной сфере не обойтись без отечественных алюминиевых панелей
Выплюнь бяку
Личинки, тараканы и ДНК человека — на что можно нарваться в батоне колбасы
Тест-драйв лучшей BMW M5
Знакомимся с первой полноприводной «эмкой» на серпантинах Португалии
Самые редкие версии BMW M5
Эксклюзивные M5 для пуристов, арабских шейхов и просто прогулок с ветерком
Невероятные стартапы, которые изменят жизнь водителей
Автомат по продаже машин, встроенный алкотестер и так далее
Самые необычные фары в истории
Головная оптика, от которой можно офонареть
«Меня не убили, просто развели»
Россиянка влюбилась по уши и лишилась жилья
Что-то встало за окном
Строения, вызывающие самые пошлые ассоциации
С собой не увезешь
Как живут российские олигархи за границей
Его ворсейшество
Бессмертные ковры возвращаются на стены российских квартир