Математики уточнили вычислительную сложность Super Mario Bros.

Математики из Массачусетсткого Технологического Института и Университета Оттавы уточнили вычислительную сложность игры Super Mario Bros. — оказалось, что игра является PSPACE-полной. Это означает, что для проверки того, проходима ли теоретически обобщенная игра, требуется полиномиальное количество памяти. Ранее ученые смогли показать, что по сложности игры по меньшей мере сопоставима с самой сложной задачей в классе NP (требующем для проверки решения «да/нет» полиномиального времени), входящем в состав PSPACE. Ключевым в доказательстве стало создание так называемых «дверей» — ситуаций, в которых определенные траектории могут менять «проходимость». О работе ученые доложат на Восьмой Международной конференции Fun with Algorithms (препринт статьи), кратко с результатами можно ознакомиться в пресс-релизе MIT.

В исследовании авторы формализовали игру, определяя ее сложность не для конкретных уровней, а исходя из принципиальных возможностей игры для составления уровней. Задача, сложность решения которой оценивалась учеными, звучала так «может ли Марио спасти принцессу?» — то есть включала в себя прохождение всей последовательности уровней. В своем доказательстве математики сделали важное допущение о том, что весь уровень вмещается на один гипотетический экран — иными словами, игра сохраняет состояния тех частей уровня, которые уже не находятся вблизи Марио.

Ранее ученые уже показали, что игра является по меньшей мере NP-сложной. Однако, принадлежит ли она классу NP — можно ли проверить ее решение с помощью недетерминированной машины Тьюринга — было неизвестно. Одним из способов опровергнуть этот факт была постройка внутри игры «дверей», меняющих свое состояние между «открытым» и «закрытым». Они ведут себя подобно битам информации, поэтому их наличие может потребовать класса PSPACE проблем разрешимости.

Авторы отмечают, что ранее удалось построить такие «двери» в игре Donkey Kong Country, но создание их в Super Mario Bros. казалось в принципе невозможным. В новой работе построение удалось выполнить с помощью особой конфигурации уровня. В роли «двери» выступал спайни — дикобраз, которого нельзя убить прыжком. Он не позволял пройти напрямую, перемещаясь между двумя блоками, однако, обойдя его снизу и ударив кирпич можно добиться того, что спайни переместится в другое место и откроет путь.

Вычислительная сложность — важная характеристика для компьютерных задач и алгоритмов. Она определяется количеством времени и памяти, необходимых для выполнения какого либо действия. К примеру, поиск наибольшего из N чисел потребует время пропорциональное N, вычисление расстояний между N аэропортами потребует количества времени, пропорционального N², и так далее. Когда время пропорционально N в некоторой степени говорят о полиномиальной сложности. Существуют экспоненциальные алгоритмы, например, перебор паролей из N бит — время для поиска требуемой комбинации пропорционально 2^N.

К играм, принадлежащим к классу PSPACE-полных также относятся реверси, пасьянс Маджонг, компьютерные игры Sokoban («кладовщик») и некоторые из The Legend of Zelda. Существуют игры, требующие экспоненциальной памяти (EXPSPACE) для проверки решений — к ним, например, относится го.

Владимир Королёв.