Как боты учатся играть в компьютерные игры

Механика обучения с подкреплением

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

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

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

Из чего состоит математический аппарат бота

Для построения работающего алгоритма разработчики задают базовые компоненты, которые превращают хаотичные движения персонажа в продуманную тактику.

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

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

Как это работает на примере классического лабиринта и Pac-Man

Для простых двумерных задач отлично подходит метод Q-обучения (Q-learning). В памяти компьютера создается таблица, где по строкам записаны состояния, а по столбцам указаны возможные команды. На пересечении строк и столбцов хранятся так называемые Q-значения. Число показывает суммарную ожидаемую награду, если в данном месте совершить выбранное действие и дальше следовать лучшей стратегии.

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

Дилемма исследования и использования

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

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

Переход от таблиц к глубоким нейросетям

Табличный метод Q-обучения превосходно справляется с крестиками-ноликами или маленькими лабиринтами. Сложности начинаются при росте размерности игрового мира. В шахматах число возможных позиций превышает число атомов в обозримой Вселенной, а в современных трехмерных шутерах состояние описывается непрерывными координатами и огромным потоком визуальных данных. Создать и сохранить такую таблицу на жестком диске физически невозможно.

В 2013 и 2015 годах инженеры компании DeepMind объединили обучение с подкреплением и глубокие сверточные нейросети в архитектуру DQN (Deep Q-Network). Нейросеть стала выполнять роль аппроксиматора функции ценности. Вместо гигантской базы данных программа принимает на вход сырые кадры с экрана, прогоняет их через слои нейронов и на выходе предсказывает полезность каждого действия.

Именно так алгоритм научился играть в классические видеоигры консоли Atari 2600. В игре Breakout бот самостоятельно открыл сложную человеческую стратегию. Он начал целенаправленно пробивать шариком узкий туннель в стене из блоков, чтобы загнать снаряд в верхнее пространство над блоками и быстро выбить максимальное количество очков без риска уронить ракетку.

Проблема взлома функции награды

Настройка наград требует огромной осторожности со стороны инженера. Алгоритмы склонны находить кратчайшие пути к получению очков, полностью игнорируя исходный замысел разработчиков. Это явление называют взломом награды (reward hacking).

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