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

Международная группа исследователей из Массачусетского технологического института и Брюссельского свободного университета определила сложность пяти серий классических игр от 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:0116 февраля
Луис Глазман «Битва при Ситке»

Обойдемся

Эти индейцы воевали с русскими до 2004 года. Они вынудили Россию продать Аляску
Звери с Чумного озера
Щелковская ОПГ не знала пощады и отправляла жертв на корм рыбам
Земля и доля
Подмосковные крестьяне бьются с Грудининым за свои гектары
Огонь, вода и бандитские трупы
На работе он стреляет в боевиков, а по выходным людей спасает
Темные времена
Лихие 90-е: спецпроект «Ленты.ру»
Восстание зануд
Первый тест самой странной Audi нашего времени – лифтбека A7 нового поколения
Тест: Made in USSR? Точно?
Угадай машину, придуманную в СССР
Самая лучшая Audi наших дней. Или нет?
Видео: первый тест Audi A7
Сегодня ничего не произошло
Длительный тест Hyundai Sonata: итоги, конкуренты, стоимость владения
Abandoned Howey MansionИ тишина
Прекрасные заброшенные уголки мира
В комнате пыток
Сколько стоит самое дешевое и страшное жилье в Москве
Он же памятник
Угадай полководца: хитрый военный тест «Ленты.ру»
Соседи из ада
Интеллигентные жильцы превратили жизнь москвички в кошмар