Вот задача, которую вы точно не решали в школе. Представьте: вы амбициозный молодой сантехник из Бруклина, а мир вокруг населён агрессивными грибами размером с человека — гумбами. Любовь всей вашей жизни похитили, и вы пускаетесь в приключение, чтобы её спасти. Путь лежит через трубы и территории, кишащие монстрами, — а единственное оружие в арсенале это ваши суперспособности прыгать и топтать врагов. Настолько изнурительное путешествие, что ни один компьютер — ни реальный, ни гипотетический — не способен просчитать, доберётесь ли вы до неё. Исследование, опубликованное MIT Hardness Group, доказывает: определить, возможно ли вообще ваше приключение, — задача не менее сложная, чем взлом шифрования финансовых транзакций. Но если бы эта проблема умела говорить, первое, что она сказала бы: «Привет, это я, Марио!» И это не просто отсылка к культовому мультфильму «Супер Марио: Галактическое кино» — это чистая наука.
Ради любви к игре
У MIT Hardness Group есть YouTube-канал, но на самом деле это не официальная исследовательская группа. Скорее, псевдоним для проектов по теоретической информатике, в том числе связанных с Super Mario, которые рождаются на курсе Эрика Демейна «Алгоритмические нижние границы: веселье с доказательствами твёрдости». Демейн — профессор компьютерных наук, получивший стипендию Макартура (она же «грант для гениев») за работы по вычислительной геометрии в области свёртывания белков и оригами. Но он ещё и специалист по теории сложности — области, которая классифицирует задачи по тому, сколько времени и памяти требуется компьютерам для их решения.
И, что немаловажно, Демейн — заядлый фанат Super Mario. «Я вырос на играх для NES, — говорит он. — В детстве проводил за ними часы напролёт, так что спустя годы вернуться к ним и связать с собственными исследованиями — это здорово».
Super Mario разворачивается на бесконечно прокручивающейся по горизонтали вселенной из платформ, труб и прочих препятствий. Цель — спасти принцессу Пич, правительницу Грибного королевства, пробиваясь через уровни, уворачиваясь от гумб и смертоносных дикобразов спайни. В каждой локации — флагшток, который отправляет Марио дальше.
За последние 14 лет Демейн с коллегами доказали о Super Mario многое: например, что игра сложнее пресловутой задачи коммивояжёра (поиск самого эффективного маршрута между множеством точек) или разложения больших чисел на множители. Но результат, который удивил самого Демейна, преподнесли четверо его студентов: Хаяси Ани, Холден Холл, Рикардо Руис и Навин Венкат. В рамках финального проекта на курсе 2023 года команда использовала фанатские редакторы уровней Super Mario и платформу Super Mario Maker для создания уровней настолько сложных, что они оказались неразрешимыми. Иными словами, невозможно написать программу, которая всегда корректно предсказывала бы, сможет ли Марио на этих уровнях добраться до замка.
Ранее Демейн полагал, что Super Mario относится к классу сложности PSPACE — задачи, которые решаемы, но становятся непрактично сложными при росте данных. Он даже называл PSPACE «постоянным домом» Марио. Но новые данные забросили игру в класс RE-Complete — класс неразрешимых задач. «Это самый сложный класс сложности, который мы можем представить для подобных игр», — констатирует Демейн.
Что компьютеры не могут решить
В 1936 году Алан Тьюринг, отец современной информатики, создал головоломку, известную как проблема остановки, чтобы доказать: невозможно сконструировать компьютер, способный решить всё. В основе проблемы — парадокс. Представьте: у вас есть навороченный компьютер — Оракул, который смотрит на любую программу и безошибочно определяет, остановится ли она. Если программа «Возьми 1 и прибавь 3», Оракул скажет — остановится. Если «Возьми 1 и прибавляй 1, пока не станет 0» — будет работать вечно.
Теперь возьмите другой компьютер — Противника — и вставьте в него Оракула. Когда Противнику дают программу, он передаёт её Оракулу, а затем делает противоположное предсказанию. Если Оракул считает, что программа остановится, Противник работает вечно. Если Оракул думает, что программа вечна — Противник останавливается. В любом случае Оракул ошибается, так что задача классификации неразрешима.
Доказательства неразрешимости Super Mario опираются на более сложную версию этой идеи. Студенты разобрали видеоигру с помощью техники редукции: математики превращают решаемую задачу в уже известную. «Классический пример с урока: как вскипятить кастрюлю воды? — вспоминает Демейн. — Наливаю воду из крана, ставлю на плиту, она закипает. А теперь даю кастрюлю, уже наполненную. Как вскипятить? Выливаю воду и свожу к предыдущей задаче».
В мире платформ и дикобразов команда разбила свой уровень на локальные части пути Марио — «гаджеты», с помощью которых доказали неразрешимость. «Гаджет — это любой элемент окружения, определяющий, можешь ли ты пройти через один паттерн», — объясняет Джейсон Линч, научный сотрудник CSAIL и глава алгоритмов в MIT FutureTech. Например, в одном гаджете Марио должен прыгнуть на платформу, уворачиваясь от монстра. Линч, будучи аспирантом под руководством Демейна, формализовал теорию гаджетов и участвовал в ранних работах по Super Mario, но не занимался неразрешимостью.
Один из любимых гаджетов Линча — дверной. Он работает как настоящая дверь: Марио может открыть, пройти и закрыть. Дверь либо открыта (когда Спайни справа), либо закрыта (Спайни слева). Если дикобраз ходит слева, Марио нужно пройти под ним, вовремя подпрыгнуть и ударить кирпичный блок — это сдвинет Спайни направо, дверь откроется. Затем надо пройти и снова отправить зверя налево, чтобы закрыть дверь за собой. Поскольку дверь всегда открыта или закрыта, её состояние можно использовать для симуляции истины или лжи. Ранние работы связывали несколько дверных гаджетов, чтобы смоделировать задачу «истина/ложь», которая уже считалась сложной. Но для доказательства неразрешимости команда применила счётный гаджет — он подсчитывает монстров и препятствия.
Если собрать машину даже из нескольких таких счётчиков, говорит Демейн, можно симулировать произвольный компьютер — способный сделать всё то же, что и любой не-квантовый компьютер, при условии достаточного времени и памяти. А если нет ограничений на количество монстров, такая машина имеет бесконечно расширяемую память, хотя размер уровня не меняется — «довольно дико», по словам Демейна. Иными словами, внутри уровня Super Mario можно построить любой теоретический компьютер. «Его можно использовать для решения любых задач: заполнять налоговые декларации, компилировать код, запускать LLM, оптимизировать расписание», — перечисляет Демейн. Можно даже создавать уровни, которые превзойдут всех в судоку, выстроят оптимальные шахматные стратегии или докажут любую доказуемую математическую теорему.
Математик Марвин Мински из MIT изобрёл счётные машины в 1961 году, чтобы выяснить, насколько простым может быть компьютер, оставаясь «универсальным». Эти теоретические машины хранят два числа, меняя их прибавлением 1, вычитанием 1 или особым действием при достижении заданного значения. В счётных гаджетах, которые разработали студенты для Super Mario, числа отражают количество гумб на уровне. Число растёт, когда труба выплёвывает гумбу, и уменьшается, когда Марио топает по ней. Если Марио столкнётся с гумбой без прыжка — он погибнет, так что продолжать путь можно только когда счётчик на нуле. Мински уже доказал, что счётные машины неразрешимы — они могут выполнять неразрешимые задачи. А раз исследователи доказали, что счётные гаджеты симулируют счётные машины, то любой уровень Super Mario со счётным гаджетом тоже неразрешим. «В будущем, если кто-то захочет показать, что игра неразрешима, ему достаточно сделать один такой гаджет», — отмечает студент Холден Холл.
Существование неразрешимых задач (как проблема остановки) означает, что можно построить неразрешимый уровень Super Mario. Как единая неразрешимая программа для проблемы остановки делает невозможным выяснить, остановится ли компьютер, так и неразрешимый уровень не позволяет определить, пройдёт ли его вообще кто-то.
Добавляя «Super» в Super Mario
Спустя более двух лет после курса Демейна некоторые студенты продолжают еженедельно встречаться и обсуждать свои исследования Mario. «С точки зрения теории сложности изучение видеоигр интересно в основном в дидактических целях, — объяснял Фабрицио Грандони из Университета прикладных наук Швейцарии. — Это простой и естественный способ привлечь студентов к этой теме». Холл, который до курса Демейна почти не сталкивался с теорией сложности — живой пример: «Я записался, потому что много знакомых пошли. Но мне так понравилось, что потом я взял ещё много курсов по этой теме».
Результаты работы MIT Hardness Group выходят далеко за пределы топтания грибов и сбора монеток. Например, исследователи из Техасского университета в Рио-Гранде-Вэлли (включая Тимоти Гомеса, ныне аспиранта MIT) применяют теорию гаджетов, разработанную для анализа игр вроде Super Mario, для изучения сложности планирования движений роботов и моделирования сетей химических реакций