Математики выяснили, что Super Mario Bros. сложнее NP-полных задач

Линейная (красная), степенная (синяя) и экспоненциальная (зелёная) зависимости. Изображение: wikipedia.org

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

В теории алгоритмов сложность задач определяют по расчетному времени, которое требуется на их решение. К примеру, на поиск наибольшего числа из неупорядоченного списка N чисел требуется время, пропорциональное N. Для более сложных задач это может быть N^2, N^3 и другие степени N — тогда алгоритмы их решения будут называться полиномиальными. Задачи объединяют в классы сложности: к примеру, задачи, решение которых можно проверить за полиномиальное время, называют NP-трудными задачами. Классический пример NP-трудной задачи — задача коммивояжера, в которой требуется найти самый короткий маршрут между несколькими городами, проходящий через каждый из них ровно один раз.

Следующий по сложности — класс PSPACE. На поиск решения задач из этого класса, как и на некоторые NP-задачи, уходит экспоненциальное время, то есть зависимость времени решения от размера задачи N будет иметь вид e^N. Более того, даже при наличии правильного решения на проверку его правильности в PSPACE-классе также уходит экспоненциальное время.
Линейная (красная), степенная (синяя) и экспоненциальная (зеленая) зависимости. Изображение: wikipedia.org

В своей статье математики из США и Канады рассчитали максимальную сложность уровня, который можно составить из базовых элементов игры Super Mario Bros. Об их исследовании сообщается на сайте Массачусетского технологического института, а ознакомиться с деталями можно в их статье.

Для начала ученые создали модель для описания уровня компьютерной игры на алгоритмическом языке. В своей предыдущей работе они использовали концепцию «закрытой двери», которая представляла основную единицу пути. Поскольку дверь может находиться в двух состояниях, открытом и закрытом, ее можно закодировать одним битом информации. Каждый путь на заданном уровне можно представить в виде последовательности дверей: состояние каждой встретившейся игроку двери определяет его дальнейшие передвижения.

Для Super Mario Bros. в роли «закрытой двери» выступали колючие монстры — Спайни (англ. spiny — колючий). В игре они могут непрерывно двигаться туда-сюда между двумя барьерами, не перепрыгивая их. Ударив снизу по кирпичному блоку, Марио может перебросить монстра за барьер, тем самым открыв себе путь.
Иллюстрация из статьи


В противном случае Спайни не даст Марио пройти — «дверь» закрыта. Используя такой подход, ученые доказали, что из элементарных блоков игры Super Mario Bros. можно составить уровень, прохождение которого будет относиться к классу PSPACE-трудных задач.

Поскольку с математической точки зрения компьютерные игры — один из способов представления реального мира, авторы работы отмечают, что в будущем подобный подход к анализу сложности может использоваться в областях, о которых мы пока даже не подозреваем. Кроме того, компьютерные игры — интересный и наглядный способ изучения алгоритмических задач в целом.

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

Читать еще на Чердаке: