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

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

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

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://gofede ration.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

 Содержание

Глава 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

 Содержание

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

 Содержание

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