Алгоритм
Го давно считается игрой, обучить в которую искусственный интеллект затруднительно из-за огромного пространства поиска и сложности выбора ходов. Го принадлежит к классу игр с совершенной информацией, то есть игроки знают обо всех ходах, которые ранее совершили другие игроки. Решение задачи поиска исхода игры связано с вычислениями функции оптимального значения в дереве поиска, содержащем приблизительно bd возможных ходов. Здесь b — это количество корректных ходов в каждой из позиций, а d — длина игры. Для шахмат эти значения составляют b ≈ 35 и d ≈ 80, и полный поиск не представляется возможным. Поэтому позиции фигур оцениваются, а потом оценка учитывается при поиске. В 1996 году компьютер впервые выиграл в шахматы у чемпиона, а с 2005 года ни один чемпион уже не в состоянии выиграть у компьютера.
Для го b ≈ 250, d ≈ 150. Возможных позиций камней на стандартной доске более, чем в гугол (10^100) раз больше, чем в шахматах. Число возможных позиций больше, чем атомов во Вселенной. Осложняет ситуацию то, что предсказать ценность состояний трудно из-за сложности игры. Два игрока размещают камни двух цветов на доске определённого размера, стандартное поле — это 19×19 линий. Правила варьируются деталями, но основная цель игры проста: нужно отгородить на доске камнями своего цвета территорию большего, чем соперник, размера.
Существующие программы умеют играть в го на уровне любителей. Они используют поиск в дереве Монте-Карло для оценки ценности каждого состояния в дереве поиска. Также в программы заложены политики, которые предсказывают ходы сильных игроков.
В последнее время глубинные свёрточные нейронные сети смогли добиться хороших результатов в распознавании лиц и классификации изображений. В Google ИИ даже самостоятельно научился играть в 49 старых игр Atari. В AlphaGo похожие нейросети истолковывают положение камней на доске, чем помогают оценить и выбрать ходы. В Google исследователи применили следующий подход: они использовали сети ценности (value networks) и сети политики (policy networks). Затем эти глубинные нейросети обучаются как на множестве партий людей, так и на игре против своих копий. Новым является также поиск, объединяющий метод Монте-Карло с сетями политики и ценности.
Нейросети натренировывали в нескольких стадиях машинного обучения. Сначала проводилось контролируемое обучение сети политики прямо с помощью ходов игроков-людей. Другая сеть политики подвергалась обучению с подкреплением. Вторая играла с первой и оптимизировала её, чтобы политика сдвигалась к выигрышу, а не просто предсказаниям ходов. Наконец, проводилось обучение с подкреплением сети ценности, которая предсказывает победителя игр, в которые играют сети политики. Конечный результат — это AlphaGo, комбинация метода Монте-Карло и сетей политики и ценности. Был достигнут результат корректного предсказания следующего хода в 57 % случаев. До AlphaGo лучший результат составлял 44 %.
В качестве входных данных для обучения использовались 160 тыс. игр с 29,4 млн позиций с сервера KGS. Брались партии игроков с шестого по девятый дан. Миллион позиций был выделен для тестов, а собственно обучение велось на 28,4 млн позиций.
Для работы алгоритмов нужны на несколько порядков большие вычислительные мощности, чем при традиционном поиске. AlphaGo представляет из себя асинхронную многопоточную программу, которая выполняет симуляцию на ядрах центрального процессора и запускает сети политики и ценности на видеочипах. Финальная версия выглядела как 40-поточное приложение, запускаемое на 48 процессорах (вероятно, имелись в виду отдельные ядра или даже гиперпоточность) и 8 графических ускорителях. Также была создана распределённая версия AlphaGo, которая использует несколько машин, 40 потоков поиска, 1202 ядер и 176 видеоускорителей.
Полностью с отчётом DeepMind можно ознакомиться в документе.