Главная » Игры » [Перевод] Почему машина может нечеловечески хорошо играть в Mario, но не в Pokemon?

[Перевод] Почему машина может нечеловечески хорошо играть в Mario, но не в Pokemon?

В преддверии нашего турнира по олдскульным видеоиграм Game Overnight мы решили поговорить о ботах в компьютерных играх.

Такие боты могут быть жёстко запрограммированными, всегда одинаково реагирующими на одни и те же наборы входных данных. Наверное вы слышали о том, что возможности современных ботов для компьютерных игр превышают человеческие. Они по-разному ведут себя в одних и тех же ситуациях в попытках найти оптимальные решения встающих перед ними проблем. Ещё один подход к их разработке заключается в том, что им позволяют учиться и эволюционировать.


Вот несколько известных примеров таких ботов:

  • AlphaZero — шахматный бот, который, после 24-х часового обучения, стал величайшим игроком на Земле.
  • AlphaGo — программа, которая обыграла в Go Ли Седоля и Кэ Цзе.
  • MarI/O — бот для Super Mario, который самостоятельно обучается, стремясь как можно быстрее проходить уровни игры.

Шахматы, го, Super Mario — непростые игры, боты представляют собой разумно подобранные комбинации алгоритмов, на их обучение нужно немало времени.

Этот материал посвящён анализу бота MarI/O и рассказу о том, почему подход, использованный при создании этого бота, не поможет написать программу, которая сможет хорошо играть в Pokemon.

В чём разница между Mario и Pokemon?

Между играми Mario и Pokemon существуют три ключевых отличия, которые и определяют возможный успех ботов:

  1. Количество целей.
  2. Коэффициент ветвления.
  3. Противоречие между глобальной и локальной оптимизацией

Сравним игры с учётом этих факторов.

Количество целей

Машины обучаются, оптимизируя некую целевую функцию. Это может быть максимизация функции вознаграждения или функции приспособленности (при обучении с подкреплением и при использовании генетических алгоритмов), это может быть минимизация функции потерь (при обучении с учителем). В любом случае, если говорить о применении к игре, речь идёт о наборе максимально возможного количества очков.

Проще говоря, чем дальше удалось продвинуться в игре — тем лучше. В игре Mario есть одна цель: дойти до конца уровня. Этот показатель выражает единственная целевая функция, и возможности модели могут быть оценены, просто и понятно, по единственному показателю.

Цель игры Mario

Попробуем их выяснить. А вот в Pokemon много целей. Может это — поимка всех покемонов? Может быть, цель игры заключается в том, чтобы победить элитную четвёрку? Возможно, что цель игры является некоей комбинацией всех предыдущих целей или даже чем-то совершенно другим. А может — нужно натренировать самую сильную команду? Вполне вероятно, что в реальности, если спросить об этом конкретного игрока, его цель будет представлена в виде сложной комбинации множества достижений, доступных в игре.

Цели игры Pokemon

Анализируя игру, нужно не только определить её конечную цель, но и решить, как именно происходит продвижение в игре, как некие действия влияют на целевую функцию, ухудшая её или улучшая в зависимости от огромного множества вариантов действий, доступных игроку в отдельно взятый момент времени.

Собственно говоря, выбор варианта действия в некоей ситуации приводит нас ко второму показателю сравнения игр.

Коэффициент ветвления

Коэффициент ветвления — это, если говорить простыми словами, показатель, указывающий на число вариантов действий, доступных на каждом шаге игрового процесса. В шахматах средний коэффициент ветвления — 35. В го — 250. Если бот пытается «заглянуть в будущее», просчитав методом полного перебора все ходы, которые он может совершить прямо сейчас, а потом — все ходы, которые он может совершить после выполнения текущего хода, и так далее, то каждый такой уровень означает серьёзный рост сложности задачи. А именно, число вариантов при таком подходе растёт экспоненциально, выражаясь формулой вида (коэффициент ветвления)^(число уровней).

Число вариантов действий, которые нужно оценить боту, невелико. В Mario персонаж может двигаться влево или вправо, может прыгать и может просто ничего не делать. Чем меньше коэффициент ветвления — тем дальше в будущее бот может заглянуть, затратив на это приемлемые вычислительные ресурсы.

Варианты действий в Mario

Это означает, что в каждый конкретный момент времени у игрока много вариантов действий. В Pokemon открытый игровой мир. Вместо этого роль играют некие действия, имеющие в игровом мире какой-то смысл. При этом простое перечисление направлений возможного перемещения персонажа в данном случае не подходит для вычисления коэффициента ветвления. При этом число вариантов выбора, по мере продвижения по игре, растёт. Будет ли следующим действием бой, разговор с игровым персонажем, переход в другую область карты?

Упрощённое представление вариантов действий персонажа в Pokemon

Для того чтобы создать бота, который мог бы выяснить, какую последовательность решений нужно принять в подобной ситуации, нужно чтобы этот бот учитывал бы свои краткосрочные и долгосрочные цели, что ведёт нас к следующему измерению сравнения игр Mario и Pokemon.

Противоречие между глобальной и локальной оптимизацией

Локальную и глобальную оптимизацию можно рассматривать как в пространственном, так и во временном смысле. Краткосрочные цели и окружающее игрового персонажа пространство небольшой площади имеют отношение к локальной оптимизации. Долгосрочные цели и сравнительно большие фрагменты игрового пространства (нечто вроде «города» или всего игрового мира) относятся к глобальной оптимизации.

Локальная оптимизация, позволяющая, скажем, попасть из точки A в точку B, сложностей не вызовет. Если, в Pokemon, разбить каждый ход на составные части — это поможет представить проблему, которую предстоит решить боту, состоящей из очень маленьких фрагментов. Жадные алгоритмы тут нам не помогут, так как локально оптимальные решения необязательно ведут к глобально оптимальным результатам. Гораздо более сложная проблема заключается в выборе точки B, направления движения.

Проблема выбора следующего шага

Карты в Pokemon имеют большие размеры, они сложны и нелинейны. Карты в Mario невелики и отличаются линейностью. А задача организации связи локальных оптимизаций с глобальными целями непроста. Перед игроком, по мере продвижения по игре и по мере того, как он преследует всё более важные цели, постоянно встают новые задачи. По крайней мере, существующие модели пока не готовы её решить.

Итоги

С точки зрения ботов Pokemon — это не одна игра. Боты отличаются узкой специализацией, и бот, который помогает игроку передвигаться по карте, окажется бесполезным, если игрок встретит игрового персонажа, с которым нужно вступить в бой. С точки зрения ботов перемещения по карте и битвы — это совершенно разные задачи.

Боты — это узкоспециализированные системы

Нужно решить, какое действие совершить, какого взять покемона, нужно понять — когда использовать различные предметы. Во время боя на каждом шаге приходится выбирать из десятков вариантов. Вот материал, где исследуется задача по разработке симулятора боя в Pokemon. Всё это, само по себе, представляет сложные задачи оптимизации. Статья это хорошо проработанная, довольно сложная, но и там не рассматривается проблема предметов, важнейшего фактора, влияющего на исход битвы.

Эти игры сложны с математической точки зрения, но их цели определяются легко. В итоге можно сказать, что нам нужно радоваться тому факту, что мы можем создавать ботов, которые лучше нас играют в наши же игры. Делать они это будут, изучая эти проблемы, являющиеся сложными задачами оптимизации. С развитием технологий искусственного интеллекта человечество сможет создать машины, которые смогут решать всё более важные проблемы реального мира. По крайней мере, сейчас дела обстоят именно так. Но пока, могу вас заверить, существуют задачи, которые мы решаем лучше машин, включая игры, в которые многие из нас играли в детстве.

В турнире есть отборочная часть и реальная битва лучших из лучших, которая пройдёт 30 ноября в Музее советских игровых автоматов. Уважаемые читатели! Приглашаем вас принять участие в первом в России турнире по олдскульным видеоиграм Game Overnight. Так что, как говорится, добро пожаловать! Нас ждёт турнир с 20 до 3 часов, пенные напитки Smart Admin, Dj Огурец (Сергей Мезенцев), а помогать ему будет админ RUVDS диджей Unpushible, а ещё мы будем пробовать новые снежные бургеры Sub Zero от наших админов.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Зачем программисту стажировка на кухне — разговор с «Додо пиццей» про гембу, .NET и открытость

Бизнес компании оплетен сетью технологичных сервисов, о своей истории они написали книгу, стек технологий и архитектура системы расписаны прямо на сайте, в паре кликов от главной страницы. Про «Додо пиццу» уже известно много. Даже самые неприятные факапы они спокойно и ...

[Перевод] Профилирование кода с LLVM

Проклятие недетерминизма Моя первая попытка написать проход LLVM — люблю эти сегфолты Под словом «детерминированный» я подразумеваю, что один и тот же код будет выполняться за одно и то же количество единиц времени. Недавно я столкнулся с интересной задачей — ...