Новий алгоритм навчить користувачів грати в 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-повною. Це означає, що для перевірки того, чи проходить теоретично узагальнена гра, потрібна поліноміальна кількість пам'яті.