Итак, пока наши новые повелители отдыхают, попробую рассказать вам, как работает AlphaGo. Пост предполагает некоторое знакомство читателя с предметом — нужно знать, чем Фань Хуэй отличается от Ли Седоля, и иметь поверхностное представление о том, как работают нейросети.
Отказ от ответственности: сообщение было написано на основе сильно отредактированных журналов чата.
closecircles.com , отсюда и стиль изложения и наличие уточняющих вопросов Как всем известно, компьютеры плохо играли в го, потому что возможных ходов так много, а пространство поиска настолько велико, что прямой поиск мало что помогает. Лучшие программы используют то, что называется Поиск по дереву Монте-Карло — поиск по дереву с оценкой узлов посредством так называемых роллаутов, то есть быстрого моделирования игры в результате позиции в узле.
AlphaGo дополняет этот поиск по дереву функциями оценки на основе глубокого обучения для оптимизации пространства поиска.
Статья изначально появилась в журнале Nature (и находится за платным доступом), но ее можно найти в Интернете.
Например здесь - https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf Сначала поговорим о составных частях, а затем о том, как они комбинируются.
Шаг 1: обучите нейронную сеть, которая научится предсказывать движения людей — сеть SL-policy
Мы берём 160 тысяч игр игроков довольно высокого уровня, доступных онлайн, и обучаем нейронную сеть, которая предсказывает следующий ход человека на основе позиции.Архитектура сети представляет собой просто 12 уровней сверточных слоев с нелинейностью и softmax для каждой ячейки в конце.
Такая глубина в целом сравнима с сетями обработки изображений предыдущего поколения (Google Inception-v1, VGG, все эти штуки)
Важным моментом является то, что нейронной сети подаются следующие входные данные: 
Для каждой ячейки на вход даны 48 признаков, все они есть в таблице (каждое измерение является двоичным признаком)
Интересный набор.
На первый взгляд кажется, что сети нужно лишь сообщить, есть ли в клетке камень и если да, то какой.
Но фиг там! Есть еще тривиально рассчитываемые характеристики типа «количество степеней свободы камня» или «количество камней, которое будет взято при этом ходе».
Есть и формально неважные характеристики типа «как давно был сделан ход» И даже особенность распространённого явления «захват лестницы/побег по лестнице» — потенциально длинная последовательность вынужденных ходов.
а что такое «всегда 1» и «всегда 0»? Они просто пытаются увеличить количество функций кратно 4, мне кажется.
И при всем этом сетка учится предсказывать движения человека.
Он предсказывает с точностью 57% и к этому нужно относиться с осторожностью — цель предсказания, шаг человека, до сих пор неоднозначна.
Однако авторы показывают, что даже небольшие улучшения точности оказывают большое влияние на мощность в игре (сравнивая сетки разной мощности).
Отдельно от SL-политики тренируют fastrollout policy — очень быструю стратегию, которая представляет собой просто линейный классификатор.
Они дают ей в качестве входных данных еще более подготовленные функции.
То есть ей придаются особенности в виде заранее подготовленных лекал.
Это намного хуже, чем модель глубокой сети, но она сверхбыстрая.
Как это использовать, будет ясно позже.
Шаг 2: тренируйте политику еще лучше, играя с самим собой (обучение с подкреплением) - сеть RL-policy
Выбираем соперника из пула предыдущих версий сети случайным образом (чтобы не переобучиться), играем с ним игру до конца, просто выбирая наиболее вероятный ход из предсказания сети, опять же без всякого перебора.Единственной наградой является реальный результат игры, независимо от того, выиграете вы или проиграете.
После того, как награда известна, вычисляем, как сдвинуть веса — играем в игру заново и на каждом ходу перемещаем веса, влияющие на выбор выбранной позиции, по градиенту + или — в зависимости от результата.
Другими словами, мы применяем эту награду как направление градиента для каждого хода.
(для любопытных, это немного более тонко, и градиент умножается на разницу между результатом и оценкой позиции через сеть значений) И так мы повторяем и повторяем этот процесс – после этого RL-политика гораздо сильнее SL-политики с первого шага.
Предсказание этой обученной RL-политики уже ломает большинство прошлых программ, играющих в Го, без каких-либо деревьев и поисков.
Включая Темный лес Фейсбук? С ней не сравнивали, непонятно.
Интересная деталь! В оригинальной статье сказано, что этот процесс длился всего 1 день (остальное обучение заняло недели).
Шаг 3: давайте обучим сеть, которая «с одного взгляда» на схему скажет нам, каковы наши шансы на победу! — Сеть создания ценности
Те.прогнозирует только одно значение от -1 до 1. Она имеет точно такую же архитектуру, что и сеть политик (кажется, есть еще один дополнительный уровень свертки) +, естественно, полносвязный уровень в конце.
Значит, у него те же функции? Сети ценностей предоставляют еще одну особенность — играет ли игрок черными или нет (сети политики передают камень «свой-чужой», а не цвет).
Я так понимаю, это для того, чтобы она могла учесть коми - дополнительные очки белым за второе место.
Оказывается, ее нельзя обучить на всех позициях из игр людей — поскольку многие позиции принадлежат игре с одинаковым результатом, такая сеть начинает переобучаться — т.е.
запоминать, какая это игра, вместо того, чтобы судить о позиции.
Поэтому он обучается на синтетических данных — делают N ходов по сети SL, затем делают случайный легальный ход, затем заканчивают игру через RL-сеть, чтобы узнать результат, и обучают его на ходе N+2 (! ) - только по одной позиции за сгенерированную игру.
Итак, вот эти обученные кирпичики.
Как мы с ними играем? ТЛ;ДР: Сеть политики прогнозирует вероятные ходы по уменьшению ширины поиска (меньшее количество возможных ходов в узле), сеть ценности предсказывает, насколько выигрышная позиция позволит уменьшить требуемую глубину поиска.
Внимание, картинка! 
Итак, у нас есть дерево позиций, в корне — текущая.
Для каждой позиции существует определенное значение Q, которое означает, насколько она приводит к победе.
Мы запускаем большое количество симуляций параллельно на этом дереве.
Каждая симуляция идет по дереву туда, где Q + m(P) больше.
m(P) — специальная добавка, стимулирующая геологоразведку.
Он больше, если политическая сеть считает, что этот шаг имеет высокую вероятность, и меньше, если этот путь уже был пройден много раз.
(это вариация стандартной техники многорукого бандита) Когда симуляция дошла до листа вдоль дерева и хочет пойти дальше, где еще ничего нет. Затем вновь созданный узел дерева оценивается двумя способами.
- во-первых, через сеть создания стоимости, описанную выше
- во-вторых, играется до конца с использованием сверхбыстрой модели из шага 1 (это называется роллаут)
(там немного сложнее, но можно не обращать внимания) Те.
каждая симуляция пробегает по дереву до наиболее перспективной области (включая разведку), находит новую позицию, оценивает ее, записывает результат во все ходы, которые к ней привели.
А затем Q в каждом узле рассчитывается как среднее значение по всем симуляциям, которые через него выполнялись.
Собственно, это все.
Лучшим ходом объявляется тот узел, через который они проходили чаще всего (оказывается, это немного более стабильно, чем этот Q-показатель).
AlphaGo сдается, если все ходы имеют Q-оценку.
< -0.8, i.e. the probability of winning is less than 10%.
Интересная деталь! В работе для начальных вероятностей ходов P использовалась не RL-политика, а более слабая SL-политика.
Опытным путем выяснилось, что так было немного лучше (возможно, в матче с Ли Седолем это было уже не так, но с Фань Хуэй они играли так), т.е.
требовалось обучение с подкреплением только для обучения сети создания ценности Наконец, что можно сказать о том, чем версия AlphaGo, игравшая с Фань Хуэй (и описанная в статье), отличалась от версии, играющей с Ли Седолем:
- Кластер может стать больше.
Максимальная версия кластера в статье — 280 графических процессоров, но Фань Хуэй поигрался с версией со 176 графическими процессорами.
- Похоже я стал тратить больше времени на ход (в статье все оценки даны по 2 секунды на ход) + добавлено немного ОД на тему тайм-менеджмента
- Перед матчем было больше времени на подготовку ворот. Лично я подозреваю, что главное — чтобы было больше времени на обучение с подкреплением.
1 день в оригинальной статье - это как-то даже не смешно.
Ждем 5:0! Бонус : Попытка реализации с открытым исходным кодом.
Там, конечно, еще пилят и пилят. Теги: #AlphaGo #AlphaGo #DeepMind #глубокое обучение #обучение с подкреплением #Машинное обучение
-
Выход На Глобальный Уровень
19 Oct, 24 -
Пк Одноклассник — История Одного Ноутбука
19 Oct, 24 -
Безопасен Ли Sql-Сервер?
19 Oct, 24 -
Годвилль — Игра Без Игрока
19 Oct, 24
