Головоломка для ИИ

Как я учил агента собирать клетку 2048 в игре 2048

Привет! Меня зовут Ринат Максутов, я работаю в подразделении Intelligent Engineering Services департамента Technology российского офиса компании Accenture, и веду проекты по заказной разработке. За свою многолетнюю карьеру в Аксенчере я попробовал много разных областей: мобильная разработка, фронт-энд, бэк-энд и даже дата саенс с машлерном. Однако мой рассказ будет не про работу, а про хобби. Мне очень нравится учиться и исследовать новые области на собственных pet-проектах. Сегодня я расскажу об одном из них - как я учил Reinforcement learning (RL) агента играть в известную головоломку 2048. В статье намеренно не будет кода, математики, state-of-the-art подходов и новейших открытий в области, поэтому люди, хорошо знакомые с RL, ничего нового для себя не откроют. Эта статья - рассказ для широкой публики о том, как я поставил себе необычную цель и достиг ее.

Наша компания инвестирует значительные средства в постоянное обучение сотрудников. Например, в прошлом году была запущена программа, по которой сотрудники могут бесплатно пройти один из Nanodegree на Udacity (Nanodegree - набор из нескольких курсов с финальным проектом). Я уже проходил Deep Learning Nanodegree на этой платформе, поэтому в этот раз решил выбрать курс по обучению с подкреплением.

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

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

Чтобы закрыть этот пробел, я попытался решить какую-то задачу, которая раньше никем не решалась (по крайней мере, с помощью RL), и на ней изучить различные аспекты построения сред для агентов. В качестве такой задачи была выбрана простая в плане механики игра-головоломка 2048 (поиграть в браузере можно здесь: https://play2048.co/). В этой игре игроку, сдвигая клетки в одном из четырех направлений (вверх, вниз, вправо, влево), нужно объединять клетки с одинаковым значением, и попытаться собрать клетку с максимально возможным значением. Когда вы совершаете сдвиг, на случайной свободной клетке появляется новая двойка (с вероятностью 0.9) или четверка (с вероятностью 0.1). Игра заканчивается, когда на поле не останется пустых клеток, и игрок не может объединить никакие клетки.

Несмотря на название, 2048 не является максимально возможным значением клетки в игре. При должной тренировке, можно собрать клетки и 4096, и 8192, и так далее. Максимальное теоретически возможное - 131 072, то есть 2^17:

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

Почему эта стратегия не гарантирует победу?

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

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

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

Небольшое введение в Reinforcement learning

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

Под капотом агента может находиться некоторая математическая модель, которая и определяет, какое действие будет наилучшим, исходя из текущего состояния среды. Изначально агент, в общем случае, ничего не знает о том, что за среда ему дана, и как на нее влияют его действия. Обратную связь от среды агент получает через так называемую награду. Это некоторое число, по которому агент может судить, насколько правильным было выбранное им действие. Задача агента - выучить политику - стратегию действий, которая максимизирует получаемую агентом награду за весь период существования агента в среде. Эта награда - и есть то самое подкрепление, это означает, что правильные действия подкрепляются положительной наградой, а неправильные - предотвращаются (не смог найти более подходящего русского аналога для discourage) отрицательной. Так через многократные итерации агент (а точнее, модель) начинает более точно предсказывать потенциальную награду от каждого возможного действия и выбирать наиболее ценное действие.

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

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

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

Дело в том, что традиционно машинное обучение используется для автоматизации задач, которые: 1) сложно алгоритмизируются, 2) легко выполняются достаточно обученным человеком, но 3) требуют от человека значительного времени на выполнение задачи. Например, в задачах распознавания образов человек может легко определить, есть на ней искомый объект или нет, но очень сложно написать достаточно надежный и более-менее универсальный алгоритм определения объекта, и при этом для большого количества изображений человек будет делать эту работу очень долго. Или, например, выявление мошенничества: тренированный человек по последовательности транзакций сможет выявить подозрительные операции, но их поиск и анализ будут занимать колоссальное количество времени, и эту задачу также сложно описать универсально заранее заданными наборами правил.

Теперь рассмотрим под этим углом обучение с подкреплением. Задача данной области - научить агента (по сути, ту же модель машинного обучения) действовать в некоторой среде, то есть принимать решения в зависимости от текущей ситуации. Под такую идею подходит не так много задач - в основном в области управления чем-то, например, роботизированным манипулятором на сборочном конвейере, автомобилем на дороге, толпой зергов в StarCraft и так далее. Но в области управления, обычно, людям уже известны правила или стратегии, по которым достигается нужный результат. Мы не хотели бы, чтобы манипулятор на сборочном конвейере сначала обучался ставить деталь на нужное место в течение десятков тысяч циклов и испортил десятки тысяч экземпляров продукции, прежде чем начал делать то, что нужно. Гораздо надежнее написать программу, точно позиционирующую манипулятор на каждом шаге сборочного процесса. Мы не хотели бы, чтобы автомобиль отъездил миллионы километров и выучивал, что значит каждый из дорожных знаков по пришедшим ему через неделю штрафам - гораздо быстрее и надежнее заложить это знание изначально. Именно поэтому обучение с подкреплением пока еще очень экспериментальная область, и практических применений для нее мало. Замечательная статья на эту тему трехлетней давности до сих пор актуальна и очень хорошо описывает проблему, советую почитать. На этом вводная заканчивается, возвращаемся к нашей задаче.

Грабли и велосипеды

Достижение клетки 2048 (хотя по меркам более-менее опытного игрока, 2048 - совсем не достижение) - это долгий путь проб, ошибок, разочарований, глупейших багов, воодушевления и радости.

Поначалу все казалось довольно просто: берем готовый код, реализующий Deep Q-network из моих домашних заданий на Udacity, немного адаптируем под собственную среду, и все получится. Наивно.

Чтобы вы понимали, на что были потрачены 3 месяца экспериментов (если ничего не понятно, можно просто удивиться количеству буллитов и проскроллить дальше):

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

Первое, с чем пришлось столкнуться - отсутствие прогресса в обучении агента ВООБЩЕ. И связано это было с тем, что именно агенту выдавала среда.

Среда для агента

Написать логику доски для игры оказалось довольно просто, и заняло пару часов. Несколько простых трюков с матрицами - и движок готов. Он производит схлопывание и сдвиг клеток в зависимости от выбранного действия, заполнение новой клетки и подсчет очков. Текущее состояние среды, таким образом, описывалось простой матрицей 4х4, где в каждой ячейке было значение соответствующей клетки. Поскольку я использовал обычную нейросеть из fully-connected слоев, то прежде чем отправить состояние среды в нейросеть, ее нужно было трансформировать в вектор 1х16:

И здесь меня поджидала первая проблема. Качество обучения переставало расти, когда агент добирался до клетки 512. Больше нее он не мог собрать, сколько бы я его ни обучал. Проблема здесь оказалась в значениях клеток, которые имеют колоссальный разброс: от 0 до сотни тысяч. Пусть меня простят специалисты, но далее будет очень вольное объяснение причины такого поведения: я намеренно упрощаю, чтобы была понятна общая идея.

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

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

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

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

И для агента значение имело бы только то, что a+a = b, b+b=c и т.д., а не то, какие значения скрываются за a, b и с. (+ в данном случае - не сложение, а то самое схлопывание). К чему это все? К тому, что значения клеток можно рассматривать не как числовые значения, а как категориальные. И поскольку мы знаем максимально возможное значение клетки, можно каждую клетку представить в виде one-hot encoded вектора. То есть для каждой клетки использовалось не ее значение, а вектор размерности 18, у которого все значения были нули, и только одно значение, позиция которого соответствует одному из наших возможных значений, равнялось единице. И таких векторов - по количеству клеток. Мне до сих пор не ясно, почему, но именно такое, а не числовое представление, помогло агенту гораздо быстрее достигать более высоких значений.

Награда

Первоначально награда считалась просто как сумма значений всех клеток на поле. Казалось, что этот счет и будет тем самым двигателем прогресса для агента, ведь по постепенному увеличению счета можно судить, правильные действия выбираются или нет, и именно это можно использовать в качестве награды. Оказалось, что нет. И причина здесь - в механике игры.

Возьмем очень простую игру, например, Space Invaders. На ней несколько лет назад Google тренировал своих агентов.

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

В 2048 такой подход не сработает. И вот почему. Допустим, у вас есть 2 клетки с одинаковыми значениями, стоящие рядом. Вы их схлопываете, и счет на доске не изменился. Потому что их значения по отдельности равняется значению новой клетки. То есть совершив правильное действие, агент не получит позитивного подкрепления и не узнает, что делать нужно именно так. Более того, после каждого действия заполняется новая случайная клетка, как я писал выше, значением 2 или 4. То есть какое бы действие ни совершил агент, он всегда будет получать в ответ значение, которое равняется [счет до шага + 2 или 4]. Очевидно, этой информации недостаточно, чтобы понимать, насколько хорошее действие агент выбрал. И именно из-за этого обучение практически не прогрессировало.

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

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

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

Штрафы

Этот подход используется в RL довольно часто для того, чтобы агент не просто научился выполнять задачу, но и делал это наиболее экономно. А чтобы показать ему, какой из ходов - экономный, а какой - расточительный, нужно заложить эту информацию в награду. В моем случае я решил каждый ход штрафовать агента за все клетки, которые сдвинулись (то есть изменили свое положение) после выбранного действия. И чем больше клеток было сдвинуто, тем выше был штраф. То есть если он накапливает крупные значения в правом нижнем углу, и продолжает делать ходы вправо или вниз, то штрафом для него на каждом шагу будут только значения новых клеток. Если же он вдруг решит сделать ход вверх или влево, то сдвинется не только новая клетка, но также сместятся и все те, которые концентрировались в правом нижнем углу, и штраф будет огромным. Со временем агент понял, что наибольшая награда получается не только когда он схлопывает более крупные клетки, но и когда он двигает наименьшее количество клеток - и это заставляет его придерживаться выбранной стратегии, и только в исключительных случаях делать шаги в неприоритетных направлениях - когда ожидаемая награда с учетом штрафов оказывается действительно выше.

На картинке видим, как постепенно менялась стратегия в правильную сторону: в первых играх направления сдвигов выбирались равномерно, но затем появились приоритетные - вправо и вниз.

Был еще один забавный момент в поведении агента, который сильно замедлял обучение. Как я писал выше, агенту не давались знания о правилах игры. Соответственно, он не знал, что нельзя делать ход, например, вправо, если у тебя все клетки уже прижаты к правой части доски. То есть даже если ты сделаешь такой ход, ничего на доске не изменится. В какой-то момент нейросеть почему-то решала, что самый выгодный ход - тот, при котором ни одна клетка не двигается, потому что если ничего не сдвинулось, то и штрафа не будет. Возможно, из-за своего размера штрафы за сдвиг для него были страшнее, чем неполучение награды за схолпнувшиеся клетки. А поскольку после такого хода доска не поменялась, то, и вводные для следующего шага оставались такими же. Ну и, понятно, выбиралось такое же действие. И так в течение тысяч итераций, пока не срабатывал рандомный ход (на каждой итерации с очень малой вероятностью - в десятые или сотые доли процента - делался случайный ход вместо вычисленного, чтобы, среди прочего, выводить из таких зацикливаний). Эта проблема могла быть решена более тонкой настройкой штрафов и наград, но вместо этого я просто решил очень сильно штрафовать агента за невозможные ходы, и он довольно быстро отучился это делать.

Результат

Зеленый график показывает максимальное значение клетки в каждой игре. Выброс - в одной из игр максимально полученное значение клетки - 2048.

Для того, чтобы собрать клетку 2048 агенту пришлось отыграть чуть больше 60 тысяч партий. Однако важная деталь в том, что однократное достижение еще не означает, что агент научился делать это стабильно. Посмотрите на начало зеленого графика, где видно, как агент учился доходить до клетки 1024. Сначала был такой же выброс, затем 1024 появлялось все чаще и чаще, и затем где-то после 30 тысяч игр агент уже довольно уверенно доходил до 1024. То есть если говорить о том, чтобы агент действительно научился собирать 2048, то, экстраполировав закономерность, можно прикинуть, что агенту потребуется более миллиона игр, чтобы закрепить этот навык, и устремиться к следующей цели - 4096.

Вы наверное уже устали читать, поэтому больше не буду грузить другими выкрутасами, которые я пробовал. Вместо этого вот вам 20-минутный видосик, где собирается клетка 2048 (начиная с отметки 16:40).

Обучение я вел на своем рабочем ноуте (да простит меня руководство!), поэтому получение этого результата заняло около двух дней. Но как я написал выше, 2048 - далеко не предел в этой игре. Поэтому если у вас есть свободные мощности и время, вполне возможно дойти и до гораздо больших клеток - берите мой код на GitHub и попробуйте обучить своего агента! Если удастся побить мое достижение, присылайте гифки и ссылки на свои результаты в комменты. Всем спасибо!

PS: Пользуясь случаем, нам в команду сейчас очень нужны back-end разработчики на Python и Java, и front-end на React. В Москве, Твери или Ростове-на-Дону. Также с удовольствием приглашу пообщаться людей, которые любят исследовать технологии, делать proof-of-concept и искать им применения в бизнесе. Откликайтесь на наши вакансии или, если не нашли подходящей, пишите в личку!