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

https://towardsdatascience.com/why-can-a-machine-beat-mario-but-not-pokemon-ff61313187e1
  • Перевод
В преддверии нашего турнира по олдскульным видеоиграм 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.

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


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

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


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

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

Итоги


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


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

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

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

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

RUVDS.com

858,00

RUVDS – хостинг VDS/VPS серверов

Поделиться публикацией
Комментарии 21
    +1

    Может быть для разных игр нужны боты с разной спецификой?

      0

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

      0
      Но пока, могу вас заверить, существуют задачи, которые мы решаем лучше машин, включая игры, в которые многие из нас играли в детстве.
      А также Quake. :-)

      Кроме того, на пути прогресса ИИ стоят не только чисто алгоритмические проблемы. Вот недавно мы все следили за противостоянием «кремниевых» и «белковых» в Dota 2. Там интересно не только то, что люди довольно быстро нашли подход к OpenAI и стали уверенно обыгрывать ботов, пользуясь их слабой игрой в лейте, но и колоссальная разница в энергозатратах:
      Для обучения OpenAI в режиме 5х5 постоянно используется 128 тысяч процессорных ядер Google Cloud. Но и это еще не вся мякотка. Так как в обучении бота OpenAI используется машинное зрение (о котором мы поговорим чуть позже), в этой чудовищной конфигурации фигурирует еще 256 GPU P100 NVIDIA
      … против мозга человека, потребляющего 25 Вт. Недавно была тут хорошая статья о проблемах существующих аппаратных архитектур для решения задач МО и ИИ, которая, к сожалению, почему-то не снискала должной популярности и внимания читателей.
        +3
        О, вот тут вы не правы. Давайте сравнивать полные затраты на обучение тогда. Сколько поколений людей сменилось, чтобы текущий игрок смог обыграть кластер? Сколько ресурсов он потратил на своё обучение/развитие?
          0
          Мысль интересная, но с поколениями вы, пожалуй, слегка загнули. Если и проводить такую параллель и пытаться оценить полное время обучения человека, то это 15-20 лет, за которые из младенца вырастает будущий чемпион доты. ;-) Генетическая программа у него уже есть, этого вполне достаточно; даже нет особой необходимости в предварительном изучении накопленных другими игроками знаний об игре — человек вполне успешно осиливает игры методом тыка. В некотором смысле RL-алгоритмы ботов занимаются этим же, но результаты пока намного скромнее.
            +1
            Если и проводить такую параллель и пытаться оценить полное время обучения человека, то это 15-20 лет, за которые из младенца вырастает будущий чемпион доты

            Сейчас есть тема, как быстро получать приемлимый результат в задачах машинного обучения:
            1. взять готовую сеть, которую обучали на имаджнете при помощи оборудования, сопоставимого по мощности с тем, что использовали OpenAI
            2. зафиксировать все слои кроме нескольких выходных
            3. обучить эти несколько слоев на своем датасете на скромном железе.
            То есть, если уже потрачено X процессорной мощности на общую задачу, то чтобы дообучить на свою специализированную, достаточно условного 0.00001X. С мозгом тот же прикол. Сотни тысяч лет эволюции — это Х, решающий ряд общих задач, и заложенный в каждом исправном мозге. 0.00001X — это опыт конкретного игрока. А машине надо проглотить 1.00001Х за один присест)
              0
              Можно провести такой мысленный эксперемент — перемешать выходную картинку случайной, но фиксированой функцией — никакой человек, даже за 15-20 лет, не научится адекватно играть — он не будет ничего видеть. А для AI разницы, вообще, не будет.
                0

                Зависит от того, какой уровень шума даст случайна картинка. Если невысокий — то и человек научится, если высокий — то и сама сеть не сможет вытащить данные.

                  +1
                  Я имею в ввиду не случайный шум, а перевод картинки без потери информации в новую форму. Научить человека читать QR коды проблематично, а для сетки приципиальной разницы нет. Потому что, сетка обучается с нуля, а мы нет.
            +1
            danfe:
            против мозга человека, потребляющего 25 Вт

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

            Вся статья напоминает старые заголовки «Почему машина может нечеловечески хорошо играть в шахматы, но не в Go?», которые уже неактуальны.
            Уверен, что уже на текущей технической базе можно обучить машину, которая сможет «нечеловечески хорошо играть в Pokemon», просто это никому не нужно.
            DeepMind уже перестала устраивать состязания между своим детищем AlphaGo и людьми, чтобы это не напоминало «избиение младенцев».
            OpenAI напротив не мелочится, а хочет захватить последний оплот человечества с помошью превосходства в Dota 2. После того как им это удастся, останется очень мало людей, верящих в то что человек всегда сможет справиться с какой-нибудь задачей лучше компьютера.

            При победе в Pokemon не будет такой зрелищности как при победе в Dota 2.

            PS: справедливости ради нужно добавить, что конечно сам по себе AI не скоро достигнет такого уровня, что сможет в любой задаче превосходить человека. За этим превосходством ещё долго будут стоять люди, которые будут обучать компьютер решать задачи лучше людей.
              0
              Новые подходы в машинном обучении могут ускорить процесс в десятки-сотни и даже тысячи раз
              Конечно, алгоритмы, в т.ч. численные (вычисления пониженной точности и т.п.) будут совершенствоваться, но качественный прорыв имхо потребует такого же качественного прорыва в аппаратной реализации, потому как уже сейчас энергозатраты на то, чтобы просто более-менее играть в доту, выглядят довольно дикими. Впрочем, новые подходы нужны в любом случае; я вообще довольно скептически отношусь к нейросетям — мне кажется, это лишь некий промежуточный этап (например, их довольно просто ввести в заблуждение, а еще они не понимают, что такое оптические иллюзии, и не умеют создавать новые).
              OpenAI напротив не мелочится, а хочет захватить последний оплот человечества с помощью превосходства в Dota 2. После того как им это удастся, останется очень мало людей, верящих в то, что человек всегда сможет справиться с какой-нибудь задачей лучше компьютера.
              Эх, мне вот интереснее посмотреть, когда и как ИИ научится обыгрывать топ-игроков в Quake. :-)
                0
                А почему именно Quake?
                Он же больше заточен на реакцию и четкость движения, чем на планирование и взаимодействия, чем Дота. Т.е., как я вижу ситуацию, у ИИ тут наоборот изначальное преимущество. (Вообще тут вспоминаются ранние боты в CS, которые моментально стреляли в голову когда ты попадал им в область видимости)
                  –1
                  Не сочтите за грубость, просто чтобы не цитировать себя же, — почитайте мои комментарии (можно тупо по Ctrl-F/G, они все, по сути, один большой комментарий) к этому и этому топикам; там я постарался объяснить, почему мне кажется, что сложная Дота — более «удобный», что ли, орешек для ИИ, чем Quake, хотя последний (и тут вы правы) намного проще.
                    0

                    Так мы же вроде там уже обсуждали — в квейке боты давно человека рвут, приходится их подкручивать и давать кожаным мешкам существенный гандикап, чтобы они могли иметь шансы на победу.

                      –1
                      Ну да, обсуждали: нифига не рвут (только перестреливают), и гандикап нужно давать небольшой. Все существующие квачные боты — тупые и предсказуемые, даже относительно продвинутые, типа спитеров или 3zb2. Да это и не ИИ на самом деле: все их абилки (тайминг итемов, умение доджиться, делать некоторые триксы и специфические прыжки) заложены в них изначально, в т.ч. знание карты (AAS/вейпоинты), они ничему не учатся сами.
                        0
                        Ну да, обсуждали: нифига не рвут (только перестреливают)

                        Ну так можно на все заявить — не рвут, а перечто-то там.

                          –1
                          Перестреливают = лучше стреляют, а не выигрывают. У лучших игроков accuracy не превышает 50% (в реальности ниже из-за спама, 25% RL/RG, 35% LG — обычное дело). Даже если бот будет попадать вообще всё (т.е. все хитсканы, от ракет и банок можно увернуться), ему можно просто не давать брать рельсу.

                          Окей, в QW идеально попадающий бот, пожалуй, действительно будет непобедим, но мы же про Q2/Q3. В любом случае, существующие боты это не ИИ. Лучшее достижении ИИ в кваке на сегодня — умение кое-как играть в недо-CTF на плоских сгенерированных «картах» а-ля Wolf3D.
                          Впрочем, я начинаю повторяться, всё уже перетёрто в прошлых топиках.
                0
                К тому же нейронку вроде обучали только сутки на этих мощностях, а люди тратят на это годы и неизвестно, что дороже — аренда этих мощностей на сутки или годы выращивания балбесов, которые не умеют ничего, кроме как играть :)

                Два года его обучали, а не сутки :)
                плюс к этому кожаные мешки выполняли роль тренера, так что нельзя говорить что сам ИИ не использовал преимущества миллионов лет эволюции

                  0
                  Давайте тогда посмотрим на то, что мозгу нужно не просто двигать персонажей, но вести огромную работу по перемещению конечностей, вести расчет задержек между входным и выходным сигналом, координировать дыхание и т.д.
                  В целом, там одного только движения рук достаточно, поскольку используются сложнейшие алгоритмы для позиционирования, согласно входных сигналов.
                  О пределах работы мозга тоже весьма сомнительное заявление. Потому, что там задействовуются далеко не все отделы для решения этой, не сложной для мозга, задачи.
                  И самая не тривиальная задача — это процесс коммуникации этих пяти мозгов. И процесс принятия решений в условиях этой коммуникации.
                    0
                    Я бы еще добавил в «актив» людей миллионы лет эволюции и развития этого самого мозга.
                    0
                    Про проблемы ИИ на базе кремния говорят столько, сколько я помню самое словосочетание ИИ, а я его услышал еще в школе(лет 20 назад). Видимо у людей короткая память, или подросло новое поколение, которое не знает про проблемы, не знает основ, но радуется тому как ИИ играет в игры.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое