📰 Наука vs. Грибы: MIT доказали, что Super Mario математически неразрешим. Вспоминаем «Супер Марио: Галактическое кино»
Вот задача, которую вы точно не решали в школе. Представьте: вы амбициозный молодой сантехник из Бруклина, а мир вокруг населён агрессивными грибами размером с человека — гумбами. Любовь всей вашей жизни похитили, и вы пускаетесь в приключение, чтобы её спасти. Путь лежит через трубы и территории, кишащие монстрами, — а единственное оружие в арсенале это ваши суперспособности прыгать и топтать врагов. Настолько изнурительное путешествие, что ни один компьютер — ни реальный, ни гипотетический — не способен просчитать, доберётесь ли вы до неё. Исследование, опубликованное 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 — класс неразрешимых задач. «Это самый сложный класс сложности, который мы можем представить для подобных игр», — констатирует Демейн....
🔗 Полный текст статьи читайте у нас на сайте: Читать на TechLoot
📢 ТехноЛут
