Новый алгоритм научит пользователей играть в Super Mario Bros.

Программисты из Нью-Йорка разработали систему искусственного интеллекта, которая создает обучающие уровни для игры Super Mario Bros. Как сообщается в препринте на arXiv.org, она научит пользователя бегать, прыгать и преодолевать препятствия.

Сегодня системы искусственного интеллекта все чаще начинают использоваться в играх. Алгоритмы умеют играть как в примитивные игры, например в «муравьиный» футбол, так и в более сложные, включая Quake III Arena, Elite Dangerous и даже в Star Craft. Как правило, компьютер выступает в качестве одного из участников игры — например, члена команды или соперника — однако теперь программисты разработали систему, которая будет обучать пользователей.

Генетический алгоритм, взятый за основу группой Майкла Грина (Michael Green) из Нью-Йоркского университета, использует находящийся в открытом доступе генератор уровней для создания сцен, которые требуют определенных игровых навыков для их прохождения. Например, сцену для отработки прыжков невозможно будет пройти, ни разу не прыгнув. Чтобы агент отработал все навыки, программа генерирует уровень из сцен, которые последовательно сменяют друг друга. При этом алгоритм работает в двух направлениях: он улучшает сцены с заведомо непроходимыми препятствиями до того, пока они не станут проходимы, и повышает качество уже готовых уровней.

Для прохождения игры использовались четыре агента: B A* (возможности никак не ограничены), LJ A* (не может прыгать высоко), EB A* (не видит врагов) и NR A* (не может бегать и совершать длинные прыжки). Уровни, сгенерированные системой ИИ, эволюционировали таким образом, чтобы их мог пройти только агент, чьи способности не были ограничены.

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

Генетические алгоритмы являются разновидностью эволюционных вычислений. О том, что это такое и как это работает, можно почитать в материале из цикла Азбука ИИ.

Ранее математики из Массачусетсткого Технологического Института и Университета Оттавы уточнили вычислительную сложность Super Mario Bros. — оказалось, что игра является PSPACE-полной. Это означает, что для проверки того, проходима ли теоретически обобщенная игра, требуется полиномиальное количество памяти.

Кристина Уласович