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

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

Как мы помним, игровое поле 19х19 описывается некоторыми фичами. Опять же перечислять их все не буду, но несколько примеров приведу. Основными были: цвет камня, количество свободных мест рядом с этой позицией, сколько камней оппонента захватишь, если сделаешь этот ход, сколько собственных камней потеряешь, если походишь в эту позицию и т.п. Сами авторы говорили, что AlphaGo использует меньше фичей, чем любая другая более-менее серьезная программа в Го. Что-ж, поверим им :)

Теперь, собственно говоря, рассказ пойдет про нейронные сети, которые учились на всех этих фичах.

1. Supervised Learning (SL) Policy Network. Первая нейросеть была глубокой и сверточной. Она содержала 13 слоев сверток + нелинейностей в виде ReLU. Ее целью было угадать следующий ход из возможных на данном поле, то бишь выдавала она вероятностное распределение по допустимым ходам. Лосс-функцией, как вы могли догадаться, была кросс-энтропия. Откуда взялись данные, спросите вы? Есть сайт KGS, где онлайн играют профессионалы с 6 по 9 даны. Оттуда было взято порядка 160 000 игр, в каждой примерно 200 ходов, то бишь порядка 30 000 000 ходов для обучения. Тренировалась она при помощи ASGD. В итоге она научилась с точностью 57% предсказывать следующий ход профессионала, что очень и очень неплохо! Натренировали эту сеточку и пока что забыли.

2. SL Policy Rollout Network. Это нейронная сеть ничем не отличается (ни в обучении, ни в лосс-функции) от предыдущей кроме того, что там всего один полносвязный слой (вместо 13 сверточных). Предсказывает ходы профессионалов она с куда меньшей точностью, всего 23-25%, зато очень быстрая. Сразу раскрывая небольшой секрет, она будет использоваться для так-называемых rollout'ов - доигровок партии из какой-то конкретной позиции, путем выбора наиболее вероятных ходов за каждую из сторон.

3. Reinforcement Learning (RL) Policy Network. Проблема первой нейронной сети заключается в том, что она нацелена хорошо предсказывать следующий ход, но прекрасный следующий ход еще не обязательно ведет к победе в парти (бывают же, например, гамбиты). Поэтому перед этой (RL) нейронной сетью стояла задача предсказать не такой ход, который бы сделал профессиональный игрок, а такой ход, который с наибольшей вероятностью приведет к победе. Архитектура у этой сети была та же, что и у первой. Как утверждают авторы, если из каждой партии профессионалов взять все ходы и изменять веса нейросети в зависимости от победы/поражения со знаком +/-, то она переобучается и начнет запоминать партии. Поэтому было сделано вот что: брались две SL policy networks (не rollout) и играли друг с другом до победы. Так продолжалось несколько раз и накапливались данные для градиента. После этого мы делали шаг в градиентом спуске по каждой из сыгранных позиций. Эта модель обзывалась новой, а та с которой она играла отправлялась в пул старых моделей. Далее из пула старых нейросетей случайно выбиралась сеть и играла с новой. Веса, как я уже говорил, изменялись в зависимости от исхода партии: выиграла - идем против градиента (хотим прийти в локальный минимум), проиграла - по градиенту. Таким образом вытренировалась нейронная сеть, заточенная делать шаги, которые вероятнее приведут к конечной победе, чем к локальному выигрышу.

4. RL Value Network. Эта нейронная отличается от предыдущей тем, что в конце поставлен еще полносвязный слой с единственным выходом, задача которого - предсказать по конкретному ходу исход партии. Генерация данных для этой сети происходит в 3 этапа: мы случайно выбираем число U от 1 до 450 и делаем при помощью SL Policy Network U - 1 ход. Затем мы делаем абсолютно случайный допустимый ход (под номером U). После чего мы доигрываем партию с помощью RL Policy Network. В конечном счете, в зависимости от исхода партии мы изменяем веса нейросети согласно, внимание, лишь одному ходу - под номером U + 1 (для сравнения, в RL Policy Network мы считали градиент по всем (!) ходам).

Отлично, составляющие блоки у нас готовы, теперь, так сказать, вишенка на торте, как все это соединяется воедино - Monte-Carlo Tree Search (MCTS). Мы будем строить дерево, в корне которого находится позиция s, из которой в данной момент мы будем делать ход. Изначально у нас одна вершина в дереве - корень, наша позиция. Первым делом мы прогоняем SL Policy Network и считаем вероятности для всех ребер (actions, обозначаемые a), выходящих из этой вершины. Далее мы идем по ребру с наибольшей суммой Q(s, a) + U(s, a). В самом начале Q(s, a) = 0, а U(s, a) пропорционально вероятности, выданной SL Policy Network и обратно пропорционально числу ходов по этому ребру (чтобы постоянно не выбиралось самое вероятное ребро). Мы выбрали по каком ребру нам идти - создаем новый лист в дереве и считаем для него два значения. Во-первых, результат нашей RL Value Network, во-вторых, мы делаем из этой вершины rollout (доигрываем партию до конца SL Policy Rollout Network, которая быстрая) и смотрим, проиграла наша сеть или выиграла. Их взвешенную сумму обзовем буквой V. Так вот Q(s, a) - это среднее значение V по поддереву, растущему из s', в которую мы прийдем после хода a. Так поочередно мы делаем множество симуляций и накапливаем веса. В конечно счете выбирается ребро в дереве (ход), через которое прошло больше всего симуляций.

Еще разочек, идем по дереву, в каждый момент выбираем ход, который максимизирует вероятность SL Policy network, деленное на количество раз, которое мы ходили по этому ребру, + добавка, зависящая от того, насколько хорошими согласно RL Value Network и симуляции rollout'ов все вершины исходящего поддерева. После множества симуляций выбирается самый частой ход.

Кстати, внимательный читатель мог заметить, что никак не использовалась RL Policy Network. Да, при игре она никак не используется, но используется при тренировке RL Value Network.

Вот так вот на самом деле работает AlphaGo, если все же осмелиться заглянуть внутрь черных коробок ;)

Комментарии: