К такому выводу пришли исследователи из Массачусетского технологического института, Оттавского университета и Бард-колледжа в Саймонс-Рок. Они показывают, что проблема решения уровня в «Super Mario Brothers» такая же сложная, как и самые сложные задачи в «классе сложности» PSPACE, а это означает, что она даже сложнее, чем задача коммивояжера или проблема разложения больших чисел на множители. , или любая другая сложная задача, принадлежащая к более известному классу сложности NP.
В стандартной игре «Братья Супер Марио» Марио бежит по местности, которая сливается с правой стороны экрана. Сражаясь с монстрами, он должен выполнять различные задания, которые могут включать в себя навигацию по кирпичным строениям, которые могут подниматься с наземной плоскости игры, но также могут зависать в воздухе без поддержки.

Завершение уровня отмечается достижением Марио флагштока.
В новом документе не делается попытки установить, что какой-либо из уровней в коммерческих версиях "Super Mario Brothers" является жестким для PSPACE, только то, что можно построить сложные уровни для PSPACE из исходных материалов мира "Super Mario".
Работа следует за докладом двухлетней давности с двумя теми же соавторами, который показал, что "Super Mario Brothers" по крайней мере так же сложна, как и самые сложные задачи в NP. Но в то время исследователи не могли определить, было ли это труднее. «PSPACE — это ее последний дом», — говорит Эрик Демейн, профессор электротехники и информатики Массачусетского технологического института и соавтор обеих статей.

Демейн и его коллеги — Джованни Вильетта, доктор электротехники и информатики в Оттавском университете и соавтор более ранней статьи; и Аарон Уильямс, профессор информатики в Бард-колледже в Саймонс-Рок, представят свой новый доклад на Международной конференции по развлечениям с алгоритмами на следующей неделе.

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

Алгоритмы, время работы которых пропорционально N в степени, называются полиномиальными."Полиномиальный алгоритм, время выполнения которого пропорционально, скажем, N ^ 3, медленнее, чем алгоритм, время выполнения которого пропорционально N. Но эти различия бледнеют по сравнению с временем работы экспоненциальных алгоритмов, время работы которых пропорционально 2 ^ N.
Если алгоритму, время выполнения которого пропорционально N, требуется секунда для выполнения вычисления с участием 100 элементов, алгоритм, время выполнения которого пропорционально N ^ 3, занимает почти три часа. Но алгоритм, время выполнения которого пропорционально 2 ^ N, занимает 300 квинтиллионов лет.
Класс сложности NP — это набор задач, решения которых можно проверить за полиномиальное время, даже если на поиск этих решений, насколько известно, требуется экспоненциальное время.

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

Как и NP, PSPACE содержит проблемы, для решения которых требуется экспоненциальное время. Но самые сложные проблемы в PSPACE — сложные проблемы PSPACE — также требуют экспоненциального времени для проверки.

В некотором смысле это делает PSPACE естественным местом для размещения видеоигр. Выяснение того, как пройти чертовски сложный уровень «Братьев Супер Марио», может занять много времени, но точно так же можно пройти по этому уровню, даже имея под рукой решение.

Основные компоненты
В своей более ранней статье Демейн, Виглитта и его коллеги описали общую структуру видеоигры, которую они называют запертой дверью. У конструкции должен быть путь через нее, который может быть либо безопасным, либо нет, и у игрока должен быть способ переключить состояние пути.

Поскольку запертая дверь имеет два возможных состояния, она может представлять собой часть памяти компьютера, а поскольку через нее есть проход, который можно открыть или закрыть, она может служить элементом вычислительной схемы. Исследователи смогли показать, что любую вычислительную проблему можно описать с помощью запертых дверей, соединенных вместе в правильной конфигурации. Если проблема экспоненциально сложна, то выяснить, как пройти уровень, тоже экспоненциально сложно.
В более ранней статье Демейн, Виглитта и их коллеги продемонстрировали, как построить запертые двери в нескольких версиях игры «Donkey Kong Country», но они не могли понять, как построить такую ​​в «Super Mario Brothers».«Мы думали, что это невозможно», — говорит Демейн.

Но это не так. В запертой двери, описанной в новой статье, используется монстр из мира «Братьев Марио», называемый «шип», который будет непрерывно перемещаться вперед и назад между двумя препятствиями, но никогда самопроизвольно не перепрыгнет ни один из них. Однако, когда шип приближается к преграде, Марио может удариться о пол под ним и отправить его через.

В новой запертой двери исследователей, если шип находится на одной стороне барьера, путь через структуру непроходим; если на другом, путь открыт. А отдельные дорожки через структуру позволяют Марио перебрасывать шип с одной стороны на другую.
Веселье и игры
Результат может иметь последствия, выходящие за рамки дизайна все более запутанных игр Super Mario Brothers.«Математически видеоигры не сильно отличаются от вычислительных моделей реальных физических систем, и инструменты, используемые для доказательства сложности результатов в одной, могут быть адаптированы к другой.

«Я действительно в восторге от такого рода доказательств твердости, и я много настаивал на них в последние пару лет», — говорит Демейн. "Я даже прочитал о них целый курс. Я неплохо разбираюсь в них, просто благодаря практике, и я хотел каким-то образом превратить это в форму, которую могли бы изучить другие люди.

Итак, класс был первой попыткой сделать это. Но это уже действительно полезный справочник.

Я все время хожу и смотрю на эти конспекты лекций, чтобы понять:?’"
«Я надеюсь, что через этот курс и такие статьи я побуду больше людей делать это, потому что это действительно способствует накоплению большого опыта, который облегчает решение проблем», — продолжает он. "Чем больше практики мы получаем как коллектив, тем лучше мы решаем проблемы такого типа. И важно знать ограничения алгоритмов."