К настоящему времени вы, наверное, слышали о ботах, играющих в видеоигры на сверхчеловеческих уровнях. Эти боты могут быть запрограммированы явно, реагируя на заданные входы заданными выходами или учиться и развиваться, по-разному реагируя на одни и те же входные данные в надежде найти оптимальные ответы.
Вот несколько известных примеров:
- AlphaZero, шахматный бот, ставший величайшим игроком на Земле за 24 часа тренировок.
- AlphaGo, бот Го, который обыграл игроков мирового класса Ли Седол и Кэ Джи
- MarI / O, бот Super Mario, который может самостоятельно научиться ускорять бег на любом уровне Mario.
Эти игры сложны, и для обучения этих машин требуются умные комбинации сложных алгоритмов, повторяющихся симуляций и времени. Я хочу сосредоточиться на MarI / O и на том, почему мы не можем использовать аналогичный подход для победы над игрой в покемонов (посмотрите видео по ссылке выше, если вы не знакомы с тем, как это работает).
Есть 3 ключевых различия между Марио и Покемоном, ответственными за это:
- Количество целей
- Фактор ветвления
- Глобальная и локальная оптимизация
Давайте сравним игры, используя каждый из этих факторов.
Количество целей
Машина учится путем оптимизации какой-то целевой функции. Будь то максимизация функции вознаграждения или приспособленности (в обучении с подкреплением и генетических алгоритмов) или минимизация функции затрат (в обучении с учителем), цель аналогична: достичь максимально возможного результата.
У Марио одна цель: дойти до конца уровня . Проще говоря, чем больше прав вы получите перед смертью, тем лучше вы справитесь. Это ваша единственная целевая функция, и возможности ваших моделей можно измерить непосредственно с помощью этого числа.
У покемонов… много. Попробуем обозначить нашу цель. Чтобы победить Elite 4? Чтобы поймать всех покемонов? Тренировать сильнейшую команду? Это все вышеперечисленное или что-то совсем другое? Странно просто задавать этот вопрос, поскольку ответ, вероятно, представляет собой некоторую лично субъективную комбинацию всех из них.
Мы должны не только определить конечную цель, но и то, как выглядит прогресс, поэтому каждая единица действия соответствует награде или проигрышу на основе множества, многих возможных вариантов выбора в любой момент.
Это подводит нас к следующей теме.
Фактор ветвления
Проще говоря, фактор ветвления - это количество вариантов, которые вы можете сделать на любом этапе. В шахматах средний коэффициент ветвления равен 35; в Go это 250. Для каждого дополнительного шага в будущее у вас есть (фактор ветвления) ^ (шагов) количество вариантов, которые нужно оценить.
В Марио вы либо идете влево, вправо, прыгаете, либо ничего не делаете. Число вариантов, которые машина должна оценить, невелико. И чем меньше коэффициент ветвления, тем дальше в будущее бот может позволить себе взглянуть с точки зрения вычислений.
Pokemon - это игра с открытым миром, а это значит, что у вас есть много вариантов выбора в любой момент времени. Простое перемещение вверх, вниз, влево или вправо - бесполезная мера для расчета коэффициента ветвления. Вместо этого мы смотрим на следующее значимое действие. Следующим действием будет битва, разговор с NPC или переход в следующую локацию слева, справа, вверх или вниз? По мере прохождения игры количество возможных вариантов варьируется от большого до очень большого.
Построение машины, которая может выбрать лучший набор вариантов, требует, чтобы она рассмотрела свои краткосрочные и долгосрочные цели, что подводит нас к последней теме.
Локальная и глобальная оптимизация
Локальную и глобальную оптимизацию можно рассматривать как пространственно, так и хронологически. Краткосрочные цели и ближайшая географическая область считаются локальными, тогда как долгосрочные цели и относительно большие области, такие как города или даже вся карта, считаются глобальными.
Разбивка каждого запуска на составные части может быть способом разложить проблему покемонов на куски размером с укус. Оптимизировать локально, чтобы добраться из точки A в точку B в одной области, легко, но решить, какой пункт назначения является лучшей точкой B, гораздо сложнее. Жадные алгоритмы здесь терпят неудачу, поскольку шаги локально оптимального решения не обязательно приводят к глобальному оптимуму.
Карты Марио маленькие и линейные. Карты покемонов большие, сложные и нелинейные. Ваш главный приоритет меняется с течением времени в погоне за целями более высокого порядка, и преобразование глобальных целей в приоритетные локальные проблемы оптимизации - непростая задача. Наши нынешние модели просто не способны справиться с этим.
Последняя вещь
С точки зрения ботов, Pokemon - это не просто одна игра. Боты - специалисты, и бот, который помогает вам перемещаться по карте, бессилен помочь, когда вы сталкиваетесь с NPC, который хочет сражаться. С их точки зрения, это две совершенно разные задачи.
В бою каждый ход предлагает десятки вариантов. Выбор того, какой ход использовать, какого покемона заменить и когда использовать разные предметы, - это сложная задача оптимизации сама по себе. Осмотревшись, я нашел эту статью, где кто-то объясняет свой процесс создания симулятора боя. Он хорошо продуман и невероятно сложен, и при этом даже не учитывает использование предметов, что является ключевым фактором для определения исхода битвы.
Пока что мы должны радоваться тому факту, что мы можем создавать ботов, которые лучше справляются с нашими собственными играми, чем мы. Пока что эти игры сложны математически, но объективно просты. По мере развития искусственного интеллекта мы будем создавать машины, способные решать все более серьезные проблемы реального мира, используя их собственное обучение комплексным задачам оптимизации. Будьте уверены, что есть еще вещи, в которых мы преуспеваем, в том числе наши детские игры - по крайней мере, на данный момент. Спасибо за прочтение!
