Исследования группы MIT показали, что решить задачу достижения замка в игре Super Mario невозможно — по сложности это сопоставимо с расшифровкой финансовых транзакций. Более того, определение возможности успешного завершения уровня оказывается одной из самых сложных проблем теории вычислений.
Контекст исследования
Проект, которому посвящены исследования, был инициирован в рамках курса по алгоритмическим задачам в классе профессора Эрика Демаина. Более 14 лет команда ученых во главе с Демаином изучала различные аспекты игры. Ранее считалось, что Super Mario находится в классе PSPACE — задач с вычислительной сложностью, но последняя работа студентов изменила статус игры на класс RE-Complete, где рассматриваются неразрешимые задачи.
Эрик Демаин, получивший премию МакАртура за достижения в области вычислительной геометрии, в частности, связанными с фолдингом белков, с удовольствием объединяет свою страсть к играм с научной деятельностью. "Я вырос на играх NES и провел много часов за игровыми консолями," — делится Демаин.
Неожиданные открытия студентов
Четверо студентов, принимавшие участие в этом исследовании, создали уровни в Super Mario, которые настолько сложны, что невозможно предсказать их результат с помощью компьютерной программы. Проблема, продемонстрированная в их проекте, поразила даже самого Демаина: "Это самый сложный класс вычислительной сложности, который мы могли создать для таких игр".
Данные результаты имеют значительные последствия для теории сложности и показывают, что даже популярные видеоигры могут помочь в исследовании вычислительных границ. Например, проблема Гальдера в 1936 году продемонстрировала ограничения компьютеров, а новое открытие в Super Mario обостряет эти аспекты даже в развлекательной среде.
Что это значит для ИТ-отрасли
Для профессионалов в области ИТ новость о том, что сложность некоторых задач может соответствовать уровням безопасности и защиты данных, служит напоминанием о важности теории сложности в разработке эффективных систем. Учитывая аналогичные трудности в области криптографии и других сложных задач, программистам стоит обращать внимание на разработку алгоритмов, учитывающих подобные несоответствия.
Следующие исследования в данной области потенциально могут определить новые пути для обучения ИИ и создания вычислительных моделей, способных преодолевать неразрешимые задачи.