Глубокое обучение и игра в Го

Макс Памперла и Кевин Фергюсон
Глубокое обучение и игра в го

Max Pumperla and Kevin Ferguson
Deep Learning  
and the Game of Go

Макс Памперла и Кевин Фергюсон
Глубокое обучение  
и игра в го
Москва, 2020

УДК 004.891
ББК 32.972.13
П15
Памперла М., Фергюсон К.
П15 
Глубокое обучение и игра в го / пер. с анг. М. А. Райтмана. – М.: ДМК Пресс, 
2020. – 372 с.: ил. 
ISBN 978-5-97060-769-5
Древняя стратегическая игра го представляет собой отличный пример для демонстрации возможностей искусственного интеллекта. В 2016 году система, основанная 
на принципах глубокого обучения, потрясла мир го, победив одного из чемпионов.
В данной книге вы познакомитесь с методами глубокого обучения и научитесь 
создавать го-ботов. По мере чтения вы будете применять все более сложные методы 
и стратегии, используя библиотеку глубокого обучения Keras, написанную на языке 
Python. Вы будете с удовольствием наблюдать за тем, как ваш бот осваивает игру го, 
и узнаете о вариантах применения полученных навыков ко множеству других задач!
Издание предназначено широкому кругу читателей, знакомых с языком Python 
и желающих на практике познакомиться с методами глубокого обучения.
В России можно отыскать десятки тысяч ценителей игры го. Во многих городах страны функционируют го-клубы. Под эгидой Российской федерации го 
ежегодно проводятся сотни турниров. Их полный список можно найти на сайте 
https://gofederation.ru/.
УДК  004.891
ББК  32.972.13
Original English language edition published by Manning Publications USA, USA. Copyright © 
2019 by Manning Publications Co. Russian-language edition copyright © 2020 by DMK Press. All 
rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой 
бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав.
ISBN 978-1-617-29532-4 (анг.) 
Copyright © 2019 by Manning Publications Co
ISBN 978-5-97060-769-5 (рус.) 
©  Оформление, издание, перевод, ДМК Пресс, 2020

Содержание
Предисловие ...........................................................................................................11
Введение...................................................................................................................13
Благодарности.........................................................................................................14
Об авторах................................................................................................................15
Об иллюстрации на обложке...............................................................................16
Об этой книге...........................................................................................................17
Часть I. ОСНОВЫ ...................................................................................................22
На пути к глубокому обучению: введение в машинное обучение ...........23
1.1. Что такое машинное обучение?..........................................................................24
1.1.1. Связь машинного обучения и искусственного интеллекта.......................26
1.1.2. Что можно и чего нельзя сделать с помощью машинного обучения........27
1.2. Пример машинного обучения............................................................................27
1.2.1. Использование машинного обучения в приложениях...............................30
1.2.2. Обучение с учителем....................................................................................31
1.2.3. Обучение без учителя...................................................................................33
1.2.4. Обучение с подкреплением.........................................................................33
1.3. Глубокое обучение...............................................................................................35
1.4. Что вы узнаете из этой книги?............................................................................36
1.5. Резюме..................................................................................................................37
Глава 2. Игра го как проблема машинного обучения...................................38
2.1. Почему игры?.......................................................................................................38
2.2. Краткое введение в игру го.................................................................................39
2.2.1. Описание доски............................................................................................39
2.2.2. Размещение и захват камней.......................................................................40
2.2.3. Завершение игры и подсчет очков..............................................................41
2.2.4. Правило ко.....................................................................................................43
2.3. Фора......................................................................................................................44
2.4. Дополнительные ресурсы...................................................................................44
2.5. Чему можно научить машину?...........................................................................44
2.5.1. Выбор ходов в дебюте...................................................................................45
2.5.2. Поиск игровых состояний............................................................................45
2.5.3. Сокращение количества рассматриваемых ходов.....................................45
2.5.4. Оценка игровых состояний..........................................................................46
2.6. Определение силы ИИ для игры в го..................................................................47
2.6.1. Традиционные ранги го...............................................................................47
2.6.2. Сравнительный анализ вашего ИИ для игры в го......................................48
2.7. Резюме..................................................................................................................48

6    Содержание
Глава 3. Реализация первого бота для игры в го...........................................49
3.1. Представление игры го средствами языка Python............................................49
3.1.1. Реализация доски для игры в го..................................................................52
3.1.2. Отслеживание связанных групп камней в игре го.....................................52
3.1.3. Размещение и захват камней на доске для игры в го................................54
3.2. Фиксация игрового состояния и проверка допустимости ходов.....................56
3.2.1. Самозахват....................................................................................................57
3.2.2. Правило ко.....................................................................................................58
3.3. Завершение игры.................................................................................................60
3.4. Создание первого слабого бота для игры в го...................................................63
3.5. Ускорение игрового процесса с помощью Zobrist-хеширования.....................66
3.6. Игра против собственного бота..........................................................................71
3.7. Резюме..................................................................................................................73
Часть II. МАШИННОЕ ОБУЧЕНИЕ И ИГРОВОЙ ИИ.................................74
Глава 4. Игры и поиск по дереву........................................................................75
4.1. Классификация игр..............................................................................................76
4.2. Прогнозирование действий противника с помощью алгоритма   
минимаксного поиска................................................................................................77
4.3. Крестики-нолики: пример использования минимаксного алгоритма...........80
4.4. Сокращение пространства поиска путем редукции.........................................83
4.4.1. Сокращение глубины поиска с помощью оценки позиции...........................85
4.4.2. Сокращение ширины поиска путем альфа-бета-отсечения......................88
4.5. Оценка игрового состояния методом Монте-Карло.........................................92
4.5.1. Реализация алгоритма Монте-Карло средствами языка Python...............96
4.5.2. Выбор ветви для исследования....................................................................99
4.5.3. Применение алгоритма Монте-Карло к игре го.......................................101
4.6. Резюме................................................................................................................103
Глава 5. Знакомство с нейронными сетями...................................................105
5.1. Простой пример использования: классификация рукописных цифр...........106
5.1.1. Набор данных MNIST..................................................................................106
5.1.2. Предварительная обработка данных MNIST.............................................107
5.2. Основы нейронных сетей..................................................................................114
5.2.1. Логистическая регрессия как простая искусственная нейронная сеть......114
5.2.2. Сети с несколькими размерностями выходного сигнала........................114
5.3. Сети прямого распространения........................................................................116
5.4. Оценка предсказаний. Функции потерь и оптимизация................................119
5.4.1. Что такое функция потерь?........................................................................119
5.4.2. Среднеквадратическая ошибка.................................................................119
5.4.3. Поиск минимумов функции потерь..........................................................120
5.4.4. Градиентный спуск для нахождения минимумов....................................121
5.4.5. Стохастический градиентный спуск для функций потерь......................123
5.4.6. Метод обратного распространения ошибки.............................................124
5.5. Обучение нейронной сети средствами языка Python.....................................127
5.5.1. Слои нейронной сети в Python..................................................................127

Содержание    7
5.5.2. Слои активации в нейронных сетях..........................................................129
5.5.3. Плотные слои в Python как компоненты сетей прямого  
распространения..................................................................................................130
5.5.4. Создание последовательных нейронных сетей средствами языка  
Python....................................................................................................................131
5.5.5. Применение сети к задаче классификации рукописных цифр...............134
5.6. Резюме................................................................................................................135
Глава 6. Создание нейронной сети для данных игры го............................137
6.1. Кодирование игрового состояния для подачи на вход нейронной сети.......139
6.2. Генерирование обучающих игровых данных методом поиска по дереву.....142
6.3. Использование библиотеки глубокого обучения Keras...................................144
6.3.1. Принципы проектирования с помощью библиотеки Keras.....................145
6.3.2. Установка библиотеки глубокого обучения Keras.....................................145
6.3.3. Применение библиотеки Keras к рассмотренному ранее примеру........146
6.3.4. Предсказание ходов в игре го с помощью нейронной сети прямого  
распространения и библиотеки Keras.................................................................148
6.4. Анализ пространства с помощью сверточных сетей......................................152
6.4.1. Назначение сверточных слоев...................................................................152
6.4.2. Создание сверточных сетей с помощью библиотеки Keras.....................156
6.4.3. Сокращение пространственной размерности с помощью слоев  
пулинга..................................................................................................................157
6.5. Предсказание вероятностей для ходов в игре го.............................................158
6.5.1. Использование функции активации softmax в последнем слое..............159
6.5.2. Перекрестная энтропия как функция потерь для задач  
классификации.....................................................................................................159
6.6. Создание более глубоких сетей с помощью прореживания  и блоков  
линейной ректификации.........................................................................................162
6.6.1. Исключение нейронов методом регуляризации......................................162
6.6.2. Функция активации ReLU...........................................................................163
6.7. Объединяем все вместе и создаем более мощную сеть  
для предсказания ходов  в игре го...........................................................................164
6.8. Резюме................................................................................................................167
Глава 7. Глубокое обучение бота на основе данных....................................169
7.1. Импорт записей партий в го.............................................................................170
7.1.1. Формат файла SGF.......................................................................................171
7.1.2. Загрузка и воспроизведение партий в го с сервера KGS..........................172
7.2. Подготовка игровых данных для глубокого обучения....................................173
7.2.1. Воспроизведение партии в го на основе ее записи в формате SGF........173
7.2.2. Создание обработчика данных игры го.....................................................175
7.2.3. Создание генератора данных игры го для обеспечения  
их эффективной загрузки....................................................................................182
7.2.4. Параллельная обработка игровых данных и генераторы........................183
7.3. Обучение глубокой сети на основе партий, сыгранных человеком...............184
7.4. Создание более реалистичных кодировщиков данных игры го.....................189

8    Содержание
7.5. Эффективное обучение с помощью адаптивных градиентов........................191
7.5.1. Затухание и импульс в СГС.........................................................................191
7.5.2. Оптимизация нейронных сетей с помощью метода Adagrad..................192
7.5.3. Уточнение адаптивных градиентов с помощью Adadelta........................194
7.6. Проведение экспериментов и оценка эффективности...................................194
7.6.1. Руководство по тестированию архитектур и гиперпараметров..............195
7.6.2. Оценка показателей производительности для обучающих  
и тестовых данных...............................................................................................197
7.7. Резюме.................................................................................................................198
Глава 8. Развертывание ботов...........................................................................199
8.1. Создание агента для предсказания ходов на основе глубокой  
нейронной сети........................................................................................................200
8.2. Создание веб-интерфейса для бота..................................................................202
8.2.1. Пример бота для игры в го.........................................................................205
8.3. Обучение и развертывание бота для игры в го в облаке................................206
8.4. Взаимодействие с другими ботами по протоколу Go Text Protocol...............207
8.5. Локальные игры против других ботов.............................................................209
8.5.1. Пропуск хода и выход из игры...................................................................210
8.5.2. Запуск игры бота против других ботов.....................................................211
8.6. Развертывание бота для игры в го на онлайн-сервере...................................216
8.6.1. Регистрация бота на онлайн-сервере для игры в го.................................219
8.7. Резюме................................................................................................................219
Глава 9. Обучение на практике: обучение с подкреплением...................221
9.1. Цикл обучения с подкреплением.....................................................................222
9.2. Данные опыта....................................................................................................223
9.3. Создание обучающегося агента........................................................................226
9.3.1. Сэмплирование из распределения вероятностей....................................227
9.3.2. Обрезка распределения вероятностей......................................................229
9.3.3. Инициализация агента...............................................................................229
9.3.4. Загрузка агента с диска и его сохранение на диск...................................230
9.3.5. Реализация функции выбора хода.............................................................231
9.4. Игра бота с самим собой: практика компьютерной программы...................233
9.4.1. Представление данных опыта...................................................................233
9.4.2. Симуляция игр............................................................................................235
9.5. Резюме................................................................................................................237
Глава 10. Обучение с подкреплением и градиенты политики.................239
10.1. Выявление хороших решений с помощью случайных игр...........................240
10.2. Изменение политик нейронной сети методом градиентного спуска.........244
10.3. Советы по обучению бота на основе его игры с самим собой......................248
10.3.1. Оценка прогресса......................................................................................248
10.3.2. Измерение небольших различий в силе.................................................249
10.3.3. Настройка алгоритма стохастического градиентного спуска (СГС).....250
10.4. Резюме..............................................................................................................254

Содержание    9
Глава 11. Обучение с подкреплением и методы на основе  
ценности действий...............................................................................................255
11.1. Игры и алгоритм Q-обучения.........................................................................256
11.2. Реализация алгоритма Q-обучения в Keras...................................................260
11.2.1. Создание сетей с двумя входами с помощью Keras................................260
11.2.2. Реализация ε-жадной политики с помощью Keras.................................264
11.2.3. Обучение сети, реализующей функцию ценности действия.................267
11.3. Резюме..............................................................................................................268
Глава 12. Обучение с подкреплением и методы типа  
«актор–критик».....................................................................................................269
12.1. Преимущество позволяет выявить важные решения...................................270
12.1.1. Что такое преимущество?........................................................................270
12.1.2. Вычисление преимущества в процессе игры бота с самим собой........272
12.2. Создание нейронной сети для обучения методом «актор–критик»............274
12.3. Игра с агентом типа «актор–критик».............................................................277
12.4. Обучение агента типа «актор–критик» на данных опыта............................278
12.5. Резюме..............................................................................................................283
Часть III. БОЛЬШЕ, ЧЕМ СУММА ВСЕХ ЧАСТЕЙ.....................................284
Глава 13. AlphaGo: собираем все вместе........................................................285
13.1. Обучение глубоких нейронных сетей для создания бота AlphaGo..............288
13.1.1. Сетевые архитектуры, используемые в программе AlphaGo.................288
13.1.2. Кодировщик доски AlphaGo.....................................................................290
13.1.3. Обучение сетей политики в стиле AlphaGo.............................................293
13.2. Бутстрэппинг игр бота с самим собой из сетей политики............................295
13.3. Создание сети ценности на основе данных, полученных в ходе игры  
бота с самим собой...................................................................................................296
13.4. Повышение эффективности поиска с помощью сетей политики  
и ценности................................................................................................................297
13.4.1. Нейронные сети и развертывания ММК.................................................298
13.4.2. Поиск по дереву с помощью комбинированной функции ценности...299
13.4.3. Реализация алгоритма поиска AlphaGo..................................................302
13.5. Практические советы, касающиеся обучения бота AlphaGo........................307
13.6. Резюме..............................................................................................................308
Глава 14. AlphaGo Zero: интеграция поиска по дереву и обучения  
с подкреплением..................................................................................................310
14.1. Создание нейронной сети для поиска по дереву..........................................311
14.2. Управление процессом поиска по дереву с помощью нейронной сети......313
14.2.1. Спуск по дереву.........................................................................................316
14.2.2. Расширение дерева...................................................................................319
14.2.3. Выбор хода.................................................................................................321
14.3. Обучение..........................................................................................................322
14.4. Повышение эффективности разведки с помощью шума Дирихле..............326

10    Содержание
14.5. Современные методы создания более глубоких нейронных сетей.............327
14.5.1. Пакетная нормализация...........................................................................328
14.5.2. Остаточные сети.......................................................................................328
14.6. Дополнительные ресурсы................................................................................329
14.7. Заключение.......................................................................................................330
14.8. Резюме..............................................................................................................331
Приложение А. Математические основы.......................................................332
Векторы, матрицы, и не только: основные конструкции линейной алгебры......332
Векторы: одномерные данные............................................................................333
Матрицы: двумерные данные.............................................................................334
Тензоры 3-го ранга...................................................................................................335
Тензоры 4-го ранга...............................................................................................337
Математический анализ за пять минут: производные и нахождение  
максимума................................................................................................................337
Приложение Б. Алгоритм обратного распространения ошибки..............340
Пара слов о нотации.................................................................................................340
Алгоритм обратного распространения ошибки для сетей прямого  
распространения......................................................................................................341
Обратное распространение ошибки для последовательных нейронных  
сетей..........................................................................................................................342
Обратное распространение ошибки для всех нейронных сетей в целом............343
Вычислительные сложности, связанные с обратным распространением  
ошибки......................................................................................................................343
Приложение В. Программы и серверы для игры в го.................................345
Программы для игры в го........................................................................................345
GNU Go..................................................................................................................345
Pachi......................................................................................................................346
Серверы для игры в го..............................................................................................346
OGS........................................................................................................................346
IGS..........................................................................................................................347
Tygem....................................................................................................................347
Приложение Г. Обучение и развертывание ботов с помощью  
Amazon Web Services...........................................................................................348
Обучение моделей на сервисе AWS.........................................................................355
Размещение бота на сервисе AWS с помощью протокола HTTP...........................356
Приложение Д. Отправка бота на онлайн-сервер для игры в го.............358
Регистрация и активация бота на сервере OGS......................................................358
Локальное тестирование OGS-бота.........................................................................360
Развертывание OGS-бота на сервисе AWS..............................................................362
Предметный указатель........................................................................................365