АННОТАЦИЯ 2
ВВЕДЕНИЕ 6
1 ОСНОВНЫЕ МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЯ В ПОЗИЦИОННЫХ ИГРАХ 7
1.1 Алгоритм минимаксного поиска 7
1.2 Алгоритм альфа-бета-отсечения 8
1.3 Алгоритм поиска Монте-Карло 9
1.4 Модификация PUCT (Polynomial Upper Confidence Trees) алгоритма UCT. 10
Выводы по разделу 1 11
2 СВЕРТОЧНАЯ НЕЙРОННАЯ СЕТЬ ДЛЯ ПРЕДСКАЗАНИЯ СЛЕДУЮЩЕГО
ХОДА 12
2.1 Правила игры Го 12
2.2 Сверточная нейронная сеть 13
2.3 Задача классификации 15
2.4 Описание игрового поля для создания обучающей выборки 15
Выводы по разделу 2 18
3 РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 19
3.1 Среда разработки 19
3.1.1 BLAS (Basic Linear Algebra Subprograms) 19
3.1.2 NumPy 20
3.1.3 Theano 20
3.1.4 Keras 20
3.2 Параметры сверточной сети, используемые в данной работе 20
3.3 Параметры метода MCTS с использованием модификации PUCT 22
3.4 Совместное использование сверточной нейронной сети и метода MCTS.... 22
3.5. Обучающая выборка для сверточной нейронной сети 23
3.6 Результаты обучения нейронной сети 23
3.7 Результаты использования MCTS со сверточной нейронной сетью 24
ЗАКЛЮЧЕНИЕ 26
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 27
ПРИЛОЖЕНИЯ
ПРИЛОЖЕНИЕ 1 29
Файл Game.py 29
ПРИЛОЖЕНИЕ 2 37
Файл sgf2hdf5.py 37
ПРИЛОЖЕНИЕ 3 39
Файл cnn.py 39
Файл train.py 41
Файл net_test.py 43
ПРИЛОЖЕНИЕ 4 44
Файл mcts.py 44
Файл mcts_test.py 46
Го это древняя настольная игра, которой насчитывается уже более 3000 лет. Несмотря на то, что правила игры просты, стратегии в Го очень сложные. Уже долгие годы игра Го считается одной из сложнейших задач, поставленных искусственному интеллекту. Даже простой процесс оценки силы позиции включает в себя сложные модели взаимодействия, которые могут охватывать всю доску. Только трудность оценки позиции уже загоняет в угол попытки создать искусственный интеллект, играющий хотя бы на уровне игрока-любителя.
Основные факторы, мешающие реализации искусственного интеллекта:
• пространство состояний игрового поля огромно;
• коэффициент ветвления дерева огромен;
• трудно построить эвристическую функцию для оценки состояния игрового поля.
• правильная стратегия Го требует далеко планировать игру.
Игровое поле стандартного размера состоит из 361 клетки. Каждая из этих клеток может принимать одно из трех значений (черный / белый / пусто). Исходя из этого, пространство состояний составляет 3361, что почти равно 10172. Такое огромное количество возможных позиций делает чрезвычайно трудными попытки обобщить информацию об оценке позиции на поле.
Почти в любой ситуации в игре, пустые клетки это разрешенные ходы. В начале игры существует более 350 возможных ходов. Не смотря на то, что количество свободных клеток в ходе игры уменьшается, среднее число потенциальных, «легальных», ходов в той или иной ситуации составляет порядка 200. Это средний коэффициент ветвления игрового дерева.
Цель работы - создание адаптивной системы искусственного интеллекта для игры Го. Под системой искусственного интеллекта подразумевается совокупность сверточной нейронной, предсказывающей следующий ход, и метода поиска Монте-Карло по дереву.
Для достижения цели были решены следующие задачи:
1. Получение оптимальной обучающей выборки.
2. Обучение сверточной нейронной сети.
3. Оптимизация метода поиска Монте-Карло по дереву.
В работе предложен метод оптимизации метода поиска Монте-Карло по дереву с помощью алгоритма PUCT и сверточной нейронной сети.
В данной работе было показано, что сверточная нейронная сеть может с достаточно высокой точностью предсказывать следующий ход профессионала в игре Го. Было проведено несколько тестов с разными параметрами сети, в результате которых была достигнута точность в 44,3%, что соответствует рангу 4 кю. С другой стороны были отмечены недостатки нейронной сети: неполное понимание глобальной картины игрового поля, неполное понимание статуса жизни или смерти большой группы. Так же недостатком сети является то, что нет понимания такого хода как «пасс», игра всегда будет продолжаться до тех пор, пока не закончится место на доске.
При исследовании комбинации метода поиска Монте-Карло по дереву со сверточной нейронной сетью было замечено, что перечисленные недостатки практически исчезли. Исходя из этого, было принято решение использовать метод поиска Монте-Карло по дереву (с модификацией PUCT) и сверточную нейронную сеть совместно. В результате тестов данного метода был сделан вывод, что использование сверточной сети в методе MCTS значительно увеличивает навык игры «искусственного интеллекта». Было проведено несколько тестов с различным количеством симуляций. Максимальный ранг, полученный данным методом - 2 дан - мастерский ранг.
Все оценки работы были получены в результате большого количества игр «искусственного интеллекта» против эталонной программы Igo Win.
