Эта статья входит в число избранных

AlphaGo

Материал из Википедии — свободной энциклопедии
Стабильная версия, проверенная 30 декабря 2024. Изменения шаблонов на этой странице ожидают проверки.
Перейти к навигации Перейти к поиску
AlphaGo
Логотип программы AlphaGo
Тип программа для игры в го[вд] и искусственная интеллектуальная сущность[вд]
Разработчик Google DeepMind
Сайт deepmind.com/alph… (англ.)
deepmind.com/rese… (англ.)
Логотип Викисклада Медиафайлы на Викискладе

AlphaGo — программа для игры в го, разработанная компанией Google DeepMind в 2015 году. AlphaGo стала первой в мире программой, которая выиграла матч без гандикапа у профессионального игрока в го на стандартной доске 19 × 19,➤ и эта победа ознаменовала собой важный прорыв в области искусственного интеллекта, так как большинство специалистов по искусственному интеллекту считало, что подобная программа не будет создана ранее 2020—2025 годов.➤ В марте 2016 года программа выиграла со счётом 4:1 у Ли Седоля, профессионала 9-го дана (высшего ранга), во время исторического матча, широко освещавшегося в прессе[1]➤. После победы в матче Корейская ассоциация падук присвоила AlphaGo «почётный 9-й дан» за «искренние усилия» программы в овладении мастерством игры[2].

Победу AlphaGo над Ли Седолем часто сравнивают с шахматным матчем между программой Deep Blue и Гарри Каспаровым 1997 года, где победа программы, созданной IBM, над действовавшим чемпионом стала символической точкой отсчёта новой эпохи, когда компьютеры превзошли людей в шахматах[3]. В отличие от Deep Blue, AlphaGo — это программа, которая не привязана к конкретному аппаратному обеспечению. Кроме того, AlphaGo основана на общих принципах машинного обучения и практически не использует (в отличие от шахматных программ) ни алгоритмов, ни оценочных функций, специфичных для игры в го. При разработке AlphaGo авторы использовали только самую элементарную теорию игры в го, программа достигла высокого уровня игры, обучаясь сама на партиях профессионалов.➤ Таким образом, её методы машинного обучения могут быть использованы в других областях применения искусственного интеллекта. В частности, команда разработчиков планирует применить опыт, полученный при написании AlphaGo, для создания системы медицинской диагностики.➤

AlphaGo комбинирует технику, которая дала большой прорыв в силе программ для игры в го в 2007—2012 годах (метод Монте-Карло для поиска в дереве[англ.]), и недавние успехи в области машинного обучения, а именно глубинное обучение с помощью многоуровневых нейронных сетей.➤

История

[править | править код]

По словам одного из авторов AlphaGo, Давида Сильвера[англ.], работа над программой началась в 2014 году с исследования того, как новые методы глубинного обучения будут работать в го[4].

Чтобы оценить силу своей программы, авторы устроили турнир между AlphaGo и лучшими свободными и коммерческими программами для игры в го (Crazy Stone[англ.], Zen[англ.], Pachi, Fuego), которые использовали метод Монте-Карло, и GNU Go, которая была лучшей свободной программой до использования метода Монте-Карло. В результате версия AlphaGo, использующая один компьютер, выиграла 494 матча из 495[5].

Матч с Фань Хуэем

[править | править код]
Фань Хуэй

В октябре 2015 года AlphaGo выиграла у трёхкратного чемпиона Европы Фань Хуэя (2 профессиональный дан) матч из пяти партий со счётом 5—0. Это первый в истории случай, когда компьютер выиграл в го у профессионала в равной игре. Об этом было публично объявлено в январе 2016 года после публикации статьи[6] в Nature[7][8]. На каждую партию игрокам давалось по одному часу и 3 бёёми по 30 секунд.

После своего поражения Фань Хуэй заявил, что благодаря этому матчу он стал играть лучше и стал видеть те элементы игры, которые не замечал ранее; к марту 2016 года мировой рейтинг Фань Хуэя поднялся примерно на 300 позиций[9].

Ниже приведён пример партии, в которой AlphaGo играла чёрными. Фань Хуэй сдался после 165 ходов[5].

19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Первые 99 ходов (96 в 10)
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Ходы 100—165.

После матча с Фань Хуэем программа AlphaGo стала играть существенно лучше (её рейтинг Эло, считаемый по играм разных версий программы друг с другом, возрос на 1500 пунктов и превысил 4500). Новая версия могла выигрывать у старой, давая фору 3—4 камня[10].

Матч AlphaGo — Ли Седоль

[править | править код]
Основная статья: Матч AlphaGo — Ли Седоль
Ли Седоль в 2016 году

C 9 по 15 марта 2016 года проходил матч AlphaGo с Ли Седолем (9-й дан)[7] в Сеуле, Южная Корея. Было сыграно 5 партий. На каждую партию игрокам давалось по 2 часа и 3 бёёми по одной минуте. Призовой фонд составил 1 млн долларов. Игры транслировались в прямом эфире на YouTube[11].

На момент матча у Ли Седоля было второе место по количеству выигранных чемпионатов мира[12]. Несмотря на то, что не существует единого официального международного метода ранжирования игроков в го, некоторые источники ставят Ли Седоля четвёртым в мире игроком на время матча[13][14].

AlphaGo выиграла матч со счётом 4—1. Ли Седоль сдался в четырёх из пяти игр. AlphaGo, играя чёрными, проиграла в четвёртой партии после 180 ходов. По словам разработчиков программы, AlphaGo сдаётся, когда оценивает вероятность своего выигрыша меньше 20 %[15].

По мнению экспертов, AlphaGo во время матча с Ли Седолем была существенно сильнее и предлагала более сложную игру, чем во время матча с Фань Хуэем[16]. Ли Седоль во время пресс-конференции сказал, что его поражение — это «поражение Ли Седоля», а не «поражение человечества»[17].

Неофициальные игры в конце 2016 — начале 2017

[править | править код]

29 декабря 2016 на го-сервере Tygem[англ.] новый аккаунт «Master» начал играть партии с профессионалами го, 1 января 2017 он перешёл на го-сервер FoxGo. 4 января 2017 компания DeepMind подтвердила, что за Master и ещё за один более ранний аккаунт Magister играла обновлённая версия AlphaGo[18][19]. AlphaGo выиграла все 60 сыгранных партий (30 на каждом сервере)[20]. По окончании всех игр сооснователь DeepMind Демис Хассабис написал в своём твите: «с нетерпением ждём официальных полных матчей го позже в 2017, в сотрудничестве с организациями и экспертами го»[18][19].

Master играл по 10 игр в день и быстро привлёк внимание многих игроков сервера Tygem своими исключительными навыками. Многие быстро заподозрили, что это ИИ-игрок, так как между играми или не было перерывов, или они длились очень мало. Противниками Master становились чемпионы мира, такие как Кэ Цзе, Пак Чжон Хван, Юта Ияма, То Цзяси, Ми Юйтин, Ши Юэ, Чэнь Яое, Ли Циньчэн, Гу Ли, Чан Хао, Тан Вэйсин, Фань Тинъюй[англ.], Чжоу Жуйян, Цзян Вэйцзе[англ.], Чжоу Цзюньсюнь[англ.], Ким Джисок[англ.], Кан Дон Юн, Пак Ён Хун, Вон Сонджин[англ.]; помимо них национальные чемпионы и серебряные призёры мировых чемпионатов: Лянь Сяо, Тань Сяо[англ.], Мэн Тайлин, Дан Ифэй, Хуан Юньсун, Ян Динсинь[англ.], Син Джинсо, Чо Хансын, Ан Сунджун. Все 60 игр, кроме одной, были быстрыми с тремя 20- или 30-секундными бёёми, лишь в игре с Не Вэйпином Master предложил увеличить бёёми до одной минуты ввиду пожилого возраста последнего. После 59 выигрышных партий Master раскрыл в чате, что им управляет доктор Айа Хуань из DeepMind[21].

Позже программист AlphaGo Давид Сильвер[англ.] пояснил, что в отличие от предыдущих версий AlphaGo, версия, которая играла за «Master», больше полагалась на обучение во время игры самой с собой, чем на обучение на играх профессиональных игроков, кроме того эта версия использовала в десять раз меньше вычислений и обучалась в течение недели, а не месяцев, как версия, которая играла с Ли Седолем[22].

Саммит «Будущее Го»

[править | править код]
Основная статья: Саммит «Будущее Го»

23-27 мая 2017 года в китайском городе Вучжен[англ.] проходил саммит о будущем го, где среди прочих событий AlphaGo провёл несколько показательных партий[23] и победил во всех:

  • Мини-матч из 3 партий: AlphaGo против Кэ Цзе.
  • Продвинутое го: Человек+AlphaGo против Человека+AlphaGo.
  • AlphaGo против объединённой команды лучших китайских профессиональных игроков в го.

Уход из го

[править | править код]

После завершения саммита о будущем го основатель DeepMind Демис Хассабис объявил об уходе AlphaGo из го, в будущем никаких матчей проходить больше не будет. Кроме того, DeepMind не планирует выпускать версию AlphaGo, доступную широкой публике[24].

AlphaGo Zero

[править | править код]

В октябре 2017 DeepMind сообщила о появлении ещё более сильной версии AlphaGo — AlphaGo Zero. Новая нейросеть обучалась играть в го с нуля, «tabula rasa», играя сама с собой (без обучения на партиях, сыгранных людьми, как это было в более ранних версиях AlphaGo). Всего за 21 день самообучения система достигла уровня силы игры AlphaGo Master, а затем и превзошла его. К 40-му дню достигнув превосходства более чем в 300 пунктов эло.

Сравнение версий AlphaGo

[править | править код]
Версии Аппаратное обеспечение[25] Рейтинг Эло1 Матчи
AlphaGo Fan 176 GPU,[26] распределенные вычисления 3144[27] 5:0 Матч AlphaGo — Фань Хуэй
AlphaGo Lee 48 TPU,[26] распределенные вычисления 3739[27] 4:1 Матч AlphaGo — Ли Седоль
AlphaGo Master 4 TPU[26] v2, одна машина 4858[27] 60:0 против профессиональных игроков го;

Саммит «Будущее Го»;
3:0 Матч AlphaGo — Кэ Цзе

AlphaGo Zero (40 блоков) 4 TPU[26] v2, одна машина 5185[27] 100:0 против AlphaGo Lee

89:11 против AlphaGo Master

AlphaZero (20 блоков) 4 TPU v2, одна машина 5018[28] 60:40 против AlphaGo Zero (20 блоков)2
Примечания:

[1] Для сравнения рейтинг эло лучшего человека игрока в го Кэ Цзе по состоянию на октябрь 2017 года составлял 3670 пунктов[29].
[2] Рейтинг AlphaZero (20 блоков) меньше чем у AlphaGo Zero (40 блоков), в тестовом матче AlphaZero победила AlphaGo Zero со счетом 60:40 т.к. там сравнивались версии нейросети с равным числом блоков.

Значение

[править | править код]

До создания AlphaGo го являлось одной из немногих традиционных игр, в которые человек играл лучше компьютера[30].

Го намного сложнее шахмат из-за большего количества возможных позиций. Во-первых, как правило, в го в каждой позиции существует больше разрешённых ходов, чем в шахматах. Во-вторых, партия в го в среднем длится больше ходов. Эти два свойства делают го очень сложной для традиционных методов искусственного интеллекта, таких как альфа-бета-отсечение[8][31].

Другая сложность го по сравнению с шахматами и многими другими логическими играми заключается в создании оценочной функции, сопоставляющей произвольной позиции определённую оценку: для какой из сторон данная позиция выгоднее и насколько (либо позиция равная). В AlphaGo используются 2 нейронные сети, одна из которых специализируется на оценке позиции. Таким образом, её можно условно назвать аналогом оценочной функции в шахматах[32].

По этим причинам даже спустя почти двадцать лет, после того как компьютер Deep Blue впервые выиграл у чемпиона мира Каспарова в 1997 году, самые сильные программы, играющие в го, достигли только любительского 5 дана, и не могли выиграть у профессионала на полной доске [8][33][34]. Лучшими достижениями искусственного интеллекта в го были победы программы Zen[англ.], работающей на кластере из четырёх компьютеров, против профессионала 9 дана Масаки Такэмия два раза с форой в пять и четыре камня в 2012 году[35], а также победа программы Crazy Stone[англ.] над Ёсио Исидой (9 профессиональный дан) с форой в четыре камня в 2013 году[36].

Создание программы, которая хорошо бы играла в го, являлось камнем преткновения в развитии искусственного интеллекта[1]. До 2015 года большинство специалистов по искусственному интеллекту считали, что программа, способная победить чемпиона мира в го, не будет создана, по крайней мере, в течение следующих пяти лет[37], а многие из них предполагали, что на это потребуется как минимум десять лет[38][39][40][41]. Даже после победы AlphaGo над Фань Хуэем многие эксперты предсказывали, что AlphaGo проиграет Ли Седолю[42].

После матча с Ли Седолем правительство Южной Кореи объявило об инвестиции 1 триллиона вон (863 миллиона долларов) в исследование искусственного интеллекта в течение следующих пяти лет[43].

Практическое применение

[править | править код]

Методы, разработанные для игры в AlphaGo, могут применяться и в других областях искусственного интеллекта, в частности для медицинской диагностики[44]. Как сообщил основатель DeepMind Демис Хассабис, DeepMind заключил соглашение с Национальной службой здравоохранения Великобритании для изучения возможности применения искусственного интеллекта для анализа медицинских данных[45][46]. Для этого было основано подразделение DeepMind Health.

Устройство AlphaGo

[править | править код]
Основной источник: Silver et al., 2016

Основные принципы

[править | править код]

Существенной особенностью AlphaGo является то, что она использует общие алгоритмы, которые практически не зависят от особенностей игры го[47]. В алгоритм AlphaGo заложены только базовые принципы игры, с которых начинает изучение игры любой начинающий, такие как подсчёт числа свободных пунктов (дамэ) у группы камней, и анализ возможности захватить камни, используя приём «лестница» (ситё). Остальное AlphaGo выучила сама, анализируя базу данных из 160 тысяч партий общими методами, которые могут использоваться и в других областях искусственного интеллекта[48]. Этим AlphaGo отличается от таких систем, как Deep Blue — шахматного суперкомпьютера[4]. При написании алгоритма для Deep Blue использовалась продвинутая шахматная теория. Так, например, для оценки позиции Deep Blue использовал 8000 настраиваемых признаков, в Deep Blue была заложена огромная библиотека дебютов[49]. AlphaGo — программа, которая может работать на любом аппаратном обеспечении (хотя она использовала процессор, разработанный специально для машинного обучения➤), и принципы которой можно использовать в других областях. Она не использует библиотеку дебютов и во время игры не обращается ни к какой базе данных ходов непосредственно (а только использует нейронную сеть, натренированную на большом количестве партий). Сами разработчики программы не знают, как AlphaGo оценивает позицию, её ходы представляют собой феномен эмерджентности[50]. Кроме того, Deep Blue был разработан с одной целью — выиграть матч у Гарри Каспарова в шахматы[4][51]. AlphaGo не была обучена играть специально против Ли Седоля[17][52], более того, в базе данных тренировки AlphaGo не было партий Ли Седоля[53], и во время матча программа AlphaGo не менялась и не подстраивалась под стиль игры Ли Седоля[54].

Главное новшество AlphaGo заключается в использовании глубинного обучения — метода, успешно применявшегося для распознавания образов (например, для поиска картинок в Google Images)[55]. А именно, AlphaGo использует нейронные сети, обученные на большом количестве профессиональных партий, способные предсказывать, какой ход сделает профессионал в той или иной позиции. Сыгранные сами с собой партии дополнительно улучшили нейронные сети. Одно лишь это позволило AlphaGo играть на уровне лучших компьютерных программ 2015 года: без перебора вариантов, используя лишь нейронную сеть для выбора хода, программа смогла выиграть у Pachi (программы, играющей на уровне второго любительского дана)[56].

Как и лучшие предшествующие программы для игры в го, AlphaGo использует также метод Монте-Карло для поиска в дереве[англ.] (MCST)[56]. Суть этого метода (названного по аналогии с методом Монте-Карло в вычислительной математике) состоит в том, что для оценки позиции программа много раз играет сама с собой случайным образом, доводя каждый раз игру до конца. Потом выбирает ход, при котором было наибольшее число побед.

Технологии, предшествующие AlphaGo

[править | править код]

Общие подходы к играм с полной информацией

[править | править код]

Го является игрой с полной информацией. Теоретически для любой игры с полной информацией существует оптимальная стратегия. Чтобы найти оптимальную стратегию, нужно обойти полное дерево игры[англ.]. Например, таким образом в 2007 году программа Chinook полностью решила[англ.] английские шашки[57]. Однако для большинства игр этот метод непрактичен, так как размер дерева может быть очень большим. Его можно оценить как , где  — степень ветвления дерева игры (то есть примерное число возможных ходов в каждой позиции), а  — глубина дерева игры (то есть примерная длина партии). Для го в то время как для шахмат Перебор может быть сокращён с использованием двух техник.

Во-первых, глубина поиска может быть сокращена за счёт оценочной функции: вместо того, чтобы рассматривать игру до конца, можно оценить промежуточную позицию, используя эвристику. Такой подход хорошо зарекомендовал себя в таких играх, как шахматы, где компьютер смог играть лучше человека. Однако такой подход оказался недостаточным для го из-за огромной сложности игры.

Другой подход заключается в сокращении степени ветвления просматриваемого дерева за счёт отбрасывания некоторых ходов. Одним из таких методов является метод Монте-Карло, который позволил компьютерам играть лучше людей в такие игры, как нарды.

Метод Монте-Карло для поиска в дереве

[править | править код]
В другом языковом разделе есть более полная статья Monte Carlo tree search (англ.).
См. также: Компьютерное го § Методы Монте-Карло

Метод Монте-Карло для поиска в дереве в простейшем виде состоит в следующем. Сначала из текущей позиции выбираются все возможные ходы, а затем для каждого хода разыгрывается большое количество случайных партий. Ход оценивается как соотношение побед к поражениям для случайных игр, начинающихся с этого хода. При этом вероятность выбрать тот или иной ход также зависит от текущей оценки позиции: позиции, в которых чаще происходил выигрыш, выбираются с большей вероятностью. Такая стратегия асимптотически стремится к оптимальной. Используя такой подход, программы-предшественники AlphaGo, смогли достичь в го уровня слабого любителя.

Для улучшения этого алгоритма применялись функции, позволяющие предсказать наиболее вероятный следующий ход. До AlphaGo использовались линейные оценочные функции и функции, полученные поверхностным обучением (shallow policies). Такой подход позволил достичь уровня сильного любителя.

Архитектура свёрточной нейронной сети

Глубинное обучение

[править | править код]

AlphaGo работает, используя нейронные сети, — технику, которая успешно применяется при распознавании образов. Большой прорыв в этой области произошёл благодаря использованию многоуровневых свёрточных нейронных сетей и специальной техники их тренировки — глубинному обучению. Свёрточные нейронные сети состоят из нескольких уровней нейронов. Каждый уровень получает на вход матрицу чисел, комбинирует их с некоторыми весами и, используя нелинейную функцию активации, выдаёт множество чисел на выходе, которые передаются на следующий уровень. При распознавании образов изображение подаётся на первый уровень, а последний уровень выдаёт результат. Нейронные сети обучают на большом количестве изображений, постоянно корректируя веса, используемые для вычисления результата. В результате нейронная сеть приходит в такую конфигурацию, которая способна сама распознавать аналогичные изображения. Этот процесс невозможно предсказать, поэтому сложно сказать, как нейронная сеть «думает», но, грубо говоря, выходы на промежуточных уровнях соответствуют различным возможным классификациям[55][58].

С помощью этой техники удалось добиться больших успехов в распознавании образов, в частности в распознавании лиц. Кроме того, компания DeepMind использовала её для создания искусственного интеллекта, способного самостоятельно обучаться видеоигре на игровой консоли Atari 2600, используя в качестве входа видео, полученное с экрана[59].

Алгоритм AlphaGo

[править | править код]

Представление позиции

[править | править код]

AlphaGo использует свёрточные нейронные сети для того, чтобы оценить позицию или предсказать следующий ход. Аналогично тому, как при распознавании образов на нейронную сеть подаётся изображение, AlphaGo подаёт на нейронные сети позицию. Каждая позиция представлена как многослойная картинка , где каждый слой представляет описания простых свойств каждого пункта доски. Используются следующие простые свойства: цвет камня, количество свободных пунктов (дамэ) у данной группы камней (если их не больше 8), взятие камней, возможность сходить в данный пункт, был ли данный камень поставлен недавно. Единственное нетривиальное свойство, которое используется, — это угрожает ли данной группе захват в лестницу (ситё). Всего используется 48 бинарных свойств (свойства, выраженные целым числом, представляются при помощи унитарного кода). Таким образом каждая позиция представлена в виде таблицы бит [60].

Стратегическая сеть

[править | править код]

Для того, чтобы не рассматривать совсем плохие ходы, и тем самым сократить степень ветвления при поиске, AlphaGo использует стратегические сети[61] (англ. policy networks) — нейронные сети, которые помогают выбирать хороший ход.

Одна из таких сетей (SL policy networks) может предсказывать ход, который в данной позиции сделал бы профессионал. Это 13-уровневая нейронная сеть получена обучением «с учителем» (англ. supervised learning, SL) на 30 миллионах позиций, взятых из 160 тысяч партий, сыгранных на сервере KGS[англ.] игроками от 6 до 9 дана. Обучение происходило в течение четырёх недель на 50 GPU; в качестве обучающего алгоритма использовался стохастический градиентный спуск[англ.] для поиска максимального правдоподобия[62]. Получившаяся нейронная сеть вычисляла распределение вероятностей среди всех возможных ходов в данной позиции (представленной, как описано выше). В результате нейронная сеть смогла правильно предсказывать ход, который выбрал человек, в 57 % тестовых ситуациях[англ.] (не использованных при обучении). Для сравнения лучший результат до AlphaGo был 44 %. Даже небольшое увеличение точности предсказаний существенно увеличивает силу игры.

Стратегическая сеть способна сама играть в го, выбирая каждый раз случайный ход с вычисленной вероятностью.

Улучшенная стратегическая сеть
[править | править код]

Стратегическая сеть была улучшена при помощи обучения с подкреплением (англ. reinforcement learning, RL): а именно сеть постоянно улучшалась, играя с одной из сетей, полученных ранее. При этом каждый раз выбиралась случайная сеть из полученных ранее, чтобы избежать переобучения (ситуации, когда программа выбирает лучший ход, в предположении, что оппонент использует ту же стратегию, но может плохо играть против другого оппонента). В результате получилась стратегическая сеть (RL policy network), которая выигрывала у первоначальной сети 80 % игр.

Оказалось, что полученная стратегическая сеть, не используя ни оценочную функцию, ни перебор вариантов, смогла выиграть 85 % игр у самой сильной на то время открытой программы Pachi. Для сравнения, до этого лучшая программа, которая играла, не используя перебор вариантов, а только свёрточную нейронную сеть, выигрывала у Pachi 11 % игр. Таким образом AlphaGo без перебора вариантов смогла достичь примерно уровня третьего любительского дана по оценке авторов программы[63].

Быстрая стратегическая сеть
[править | править код]

Для симуляции игры, требуемой в методе Монте-Карло (см. ниже), AlphaGo использует более быстрый, но менее точный вариант стратегической сети (rollout policy), который получает ответ всего за 2 мкс. Эта быстрая сеть предсказывает ход человека с вероятностью 30 %[64], в то время как улучшенная стратегическая сеть выдаёт ответ на том же оборудовании за 3 мс с вероятностью 57 %.

Оценочная сеть

[править | править код]

Для сокращения глубины поиска AlphaGo использовала оценочную сеть[61] (англ. value network). Эта нейронная сеть оценивает вероятность выигрыша в данной позиции. Эта сеть является результатом обучения на 30 миллионах позиций, полученных при игре улучшенной стратегической сети с собой. При этом из каждой игры выбиралось не более чем по одной позиции (чтобы избежать переобучения из-за похожести позиций в одной игре). Для каждой из этих позиций оценивалась вероятность выигрыша методом Монте-Карло: устраивался турнир из многих партий, в которых улучшенная стратегическая сеть, построенная на прошлом этапе➤, играла сама с собой, начиная с этой позиции. После этого оценочная сеть была обучена на этих данных. Обучение заняло одну неделю на 50 GPU. В результате получилась сеть, которая могла предсказывать для каждой позиции вероятность выигрыша, при этом используя в 15 000 раз меньше вычислений, чем метод Монте-Карло.

Поиск в дереве

[править | править код]

AlphaGo осуществляет перебор вариантов при помощи метода Монте-Карло для поиска в дереве[англ.] следующим образом. AlphaGo строит частичное дерево игры[англ.], начиная с текущей позиции, производя многочисленные симуляции игры. Для каждого хода в дереве записывается оценка, которая специальным образом зависит от оценок хода, полученных при помощи стратегической➤ и оценочной➤ сетей, от результата случайных партий в предыдущих симуляциях и от количества предыдущих симуляций, выбравших этот ход (чем чаще выбирался раньше этот ход, тем ниже оценка, чтобы программа рассматривала больше разнообразных ходов).

Вначале каждой симуляции AlphaGo выбирает ход в уже построенном дереве, с максимальной оценкой. Когда симуляция доходит до позиции, которой нет в дереве, эта позиция добавляется в дерево, вместе со всеми ходами, разрешёнными в этой позиции, которые оцениваются при помощи стратегической сети➤. Далее, как в методе Монте-Карло, игра симулируется до конца без ветвления. В этой симуляции каждый ход выбирается случайно с вероятностью, полученной при помощи быстрой стратегической сети➤.

В конце симуляции, в зависимости от результата, обновляются оценки ходов в построенном дереве. Таким образом каждая симуляция начинается с текущей игровой позиции, доходит до конца, и в результате одной симуляции в текущем дереве раскрывается одна позиция.

Авторы программы обнаружили, что на этом этапе выгоднее использовать не улучшенную стратегическую сеть➤, а первоначальную (SL policy network)➤. Как считают авторы, это связано с тем, что профессиональные игроки выбирают более разнообразные ходы, чем улучшенная сеть, что позволяет программе рассматривать больше вариантов. Таким образом улучшенная стратегическая сеть не используется во время игры, но её использование существенно для построения оценочной сети➤, когда программа обучается, играя сама с собой.

Аппаратное обеспечение

[править | править код]
Стойка TPU, используемая AlphaGo в матче с Ли Седолем.

Обучение AlphaGo происходило в течение нескольких недель на 50 графических процессорах, используя платформу Google Cloud[англ.]*, сервера которой расположены в США[62][65].

AlphaGo тестировалась в компьютерных системах с различным количеством процессоров и графических процессоров, работающих параллельно или распределённо. В каждом случае давалось 2 секунды на ход. Достигнутые при этом рейтинги, рассчитанные на основе результатов игр друг с другом по системе Эло, представлены в таблице:[66]

Вычисления Потоков
выполнения		 Число ЦП Число ГП Рейтинг Эло
Параллельные 40 48 1 2181
Параллельные 40 48 2 2738
Параллельные 40 48 4 2850
Параллельные 40 48 8 2890
Распределённые 12 428 64 2937
Распределённые 24 764 112 3079
Распределённые 40 1202 176 3140
Распределённые 64 1920 280 3168

Версия, которая выиграла у Фань Хуэя в октябре 2015 года, работала на 1202 процессорах и 176 графических процессорах[67] .

В игре с Ли Седолем в марте 2016 года AlphaGo использовала 1920 процессоров и 280 графических процессоров, работающих в распределённой сети[68].

В мае 2016 года представители компании Google объявили, что AlphaGo использовала TPU, процессор, разработанный Google, специально для машинного обучения[69][70].

В матче против Кэ Цзе в мае 2017 года новая версия AlphaGo использовала только один компьютер на Google Cloud c TPU процессором, то есть примерно в 10 раз меньшую вычислительную мощность, чем была использована в матче с Ли Седолем[71].

Стиль игры

[править | править код]

Тоби Маннинг, судья в матче AlphaGo с Фань Хуэем, охарактеризовал стиль игры AlphaGo скорее как консервативный, чем агрессивный[72]. По словам генерального директора DeepMind Демиса Хассабиса, AlphaGo пытается увеличить вероятность выигрыша, а не разрыв в количестве очков[4].

Профессиональные игроки отмечали, что некоторые ходы AlphaGo, первоначально кажущиеся ошибочными, при более глубоком изучении оказывались стратегически важными[73].

Не Вэйпин (9 профессиональный дан, Китай) после первой игры с Ли Седолем предположил, что AlphaGo играет на уровне 6 или 7 профессионального дана в фусэки и 13—15 дана в тюбане[74].

В третьей партии выяснилось, что AlphaGo способна управлять ситуацией при ведении ко-борьбы, что ранее считалось значительной слабостью большей части программ, играющих в го[75].

Некоторые обозреватели охарактеризовали ошибки AlphaGo, приведшие к поражению в четвёртой партии, как типичные ошибки для программы, работающей на основе метода Монте-Карло[76]. Демис Хассабис заявил, что эти ошибки будут тщательно проанализированы, и что, видимо, AlphaGo не знает некоторые классические тэсудзи и совершает тактические ошибки[77]. Впоследствии Айа Хуань (один из разработчиков AlphaGo, который ставил камни за AlphaGo) сказал, что у команды авторов два предположения о причинах этих ошибок: либо AlphaGo просто не хватило глубины просмотра, чтобы проанализировать ситуацию; либо 78-й ход Ли Седоля был настолько необычным (комментаторы его называли «божественным»[76]), что программа при самообучении не встречала подобных ситуаций, в результате её оценочная функция (см. выше) в этой ситуации оказалась слаба. В любом случае, по словам Айа Хуаня, новая версия AlphaGo в этой ситуации уже играет правильно. При этом команда не делала ничего специального, AlphaGo сама в результате обучения перестала делать такие ошибки[78].

После матча Ли Седоль заявил, что был побеждён психологически, но вовсе не технически[79]. Программа показала способность к креативным решениям, что удивило многих игроков (например, ход № 37 во второй партии); некоторые ходы противоречили классической теории го, но в матче доказали свою эффективность, некоторые профессионалы стали использовать эти находки в своих партиях[50].

Аналогичные системы

[править | править код]

Facebook также разрабатывает программу для игры в го, Darkforest[англ.], которая тоже основана на машинном обучении и поиске в дереве[72][80]. На начало 2016 года Darkforest показал сильную игру против других компьютеров, но не смог выиграть у профессионала[81]. По силе Darkforest оценивается на уровне программ Crazy Stone[англ.] и Zen[англ.][82].

1 марта 2016 года разработчики программы Zen (Ёдзи Одзима и Хидэки Като), компания DWANGO и исследовательская группа глубинного обучения Токийского университета (которая создала программу Ponanza[яп.] для игры в сёги, победившую человека) объявили о совместном проекте «Deep Zen Go Project», с целью победить AlphaGo в течение 6—12 месяцев. Японская ассоциация го обещала поддержать проект[83]. В ноябре 2016 года Deep Zen Go проиграла со счётом 2-1 самому титулованному игроку Японии Тё Тикуну[84][85].

Литература

[править | править код]

См. также

[править | править код]

Примечания

[править | править код]
  1. ↑ 1 2 Metz C. Why the Final Game Between AlphaGo and Lee Sedol Is Such a Big Deal for Humanity (англ.). // Wired News (14 марта 2016). Дата обращения: 10 ноября 2016. Архивировано 22 декабря 2016 года.
  2. ↑ Google's AlphaGo gets 'divine' Go ranking (англ.). // The Straits Times (15 марта 2016). Дата обращения: 10 ноября 2016. Архивировано 7 октября 2016 года.
  3. ↑ Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol. // BBC News (12 марта 2016). Дата обращения: 12 июля 2016. Архивировано 26 августа 2016 года.
  4. ↑ 1 2 3 4 Ribeiro J. AlphaGo’s unusual moves prove its AI prowess, experts say. // PC World (14 марта 2016). Дата обращения: 12 июля 2016. Архивировано 17 июля 2016 года.
  5. ↑ 1 2 Silver et al., 2016, p. 488.
  6. ↑ Silver et al., 2016.
  7. ↑ 1 2 Искусственный интеллект впервые победил профессионального игрока в го. // Meduza. Дата обращения: 27 января 2016. Архивировано 4 февраля 2016 года.
  8. ↑ 1 2 3 Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning. // Google Research Blog (27 января 2016). Дата обращения: 28 января 2016. Архивировано 1 февраля 2016 года.
  9. ↑ Metz C. The Sadness and Beauty of Watching Google’s AI Play Go. // Wired News (11 марта 2016). Архивировано 7 ноября 2017 года.
  10. ↑ Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference на YouTube, начиная с 35:56
  11. ↑ Demis Hassabis on Twitter. // Twitter. Дата обращения: 14 февраля 2016. Архивировано 27 июля 2019 года.
  12. ↑ Borowiec S. Google's AI machine v world champion of 'Go': everything you need to know. // The Guardian (9 марта 2016). Дата обращения: 15 марта 2016. Архивировано 15 марта 2016 года.
  13. ↑ Coulom R.[англ.]. Rating List of 2016-01-01. Архивировано 18 марта 2016 года.
  14. ↑ Ji-yoon L. Korean Go master proves human intuition still powerful in Go. // The Korean Herald/ANN (14 марта 2016). Дата обращения: 15 марта 2016. Архивировано из оригинала 12 апреля 2016 года.
  15. ↑ Metz C. Go Grandmaster Lee Sedol Grabs Consolation Win Against Google’s AI. // Wired News (13 марта 2016). Дата обращения: 29 марта 2016. Архивировано 17 ноября 2017 года.
  16. ↑ Ribeiro J. Google’s AlphaGo AI program strong but not perfect, says defeated South Korean Go player. // PC World (12 марта 2016). Дата обращения: 13 марта 2016. Архивировано 13 марта 2016 года.
  17. ↑ 1 2 Sung-won Y. Lee Se-dol shows AlphaGo beatable. // The Korea Times (13 ноября 2016). Дата обращения: 15 марта 2016. Архивировано 14 марта 2016 года.
  18. ↑ 1 2 Хассабис Д. Demis Hassabis on Twitter: "Excited to share an update on #AlphaGo!". // Demis Hassabis' Twitter account (4 января 2017). Дата обращения: 4 января 2017. Архивировано 15 февраля 2019 года.
  19. ↑ 1 2 Gibney E. Google reveals secret test of AI bot to beat top Go players. // Nature (4 января 2017). Дата обращения: 4 января 2017. Архивировано 5 января 2017 года.
  20. ↑ Ещё одна партия закончилась ничьей, так как игрок-человек отсоединился от сервера из-за проблем с сетью. Но результат не был засчитан на сервере FoxGo, поскольку отсоединение произошло в самом начале партии.
  21. ↑ 横扫中日韩棋手斩获59胜的Master发话：我是阿尔法狗. // 澎湃新闻 (4 января 2017). Дата обращения: 5 января 2017. Архивировано 30 сентября 2020 года.
  22. ↑ The Future of Go Summit, Match One: Ke Jie & AlphaGo на YouTube, начиная с 5:58:50 (23 мая 2017)
  23. ↑ Exploring the mysteries of Go with AlphaGo and China's top players (10 апреля 2017). Дата обращения: 10 апреля 2017. Архивировано 11 апреля 2017 года.
  24. ↑ AlphaGo retires from competitive Go after defeating world number one 3-0 — The Verge. Дата обращения: 4 июня 2017. Архивировано 7 июня 2017 года.
  25. ↑ 【柯洁战败解密】AlphaGo Master最新架构和算法，谷歌云与TPU拆解 (кит.). Sohu (24 мая 2017). Дата обращения: 1 июня 2017. Архивировано 17 сентября 2017 года.
  26. ↑ 1 2 3 4 AlphaGo Zero: Learning from scratch. DeepMind official website (18 октября 2017). Дата обращения: 19 октября 2017. Архивировано 19 октября 2017 года.
  27. ↑ 1 2 3 4 Silver, David[англ.]; Schrittwieser, Julian; Simonyan, Karen; Antonoglou, Ioannis; Huang, Aja[англ.]; Guez, Arthur; Hubert, Thomas; Baker, Lucas; Lai, Matthew; Bolton, Adrian; Chen, Yutian; Lillicrap, Timothy; Fan, Hui; Sifre, Laurent; Driessche, George van den; Graepel, Thore; Hassabis, Demis. Mastering the game of Go without human knowledge (англ.) // Nature : journal. — 2017. — 19 October (vol. 550, no. 7676). — P. 354—359. — ISSN 0028-0836. — doi:10.1038/nature24270. Архивировано 19 октября 2017 года.публикация с закрытым доступом — за платной стеной
  28. ↑ A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play | Science. Дата обращения: 16 февраля 2021. Архивировано 8 марта 2021 года.
  29. ↑ Rating of Go players. Дата обращения: 12 июля 2016. Архивировано 1 апреля 2017 года.
  30. ↑ Levinovitz A. The Mystery of Go, the Ancient Game That Computers Still Can’t Win (англ.). // Wired News. Дата обращения: 30 января 2016. Архивировано 31 января 2016 года.
  31. ↑ Schraudolph N. N., Dayan P., Sejnowski T. J. Temporal difference learning of position evaluation in the game of Go. // Advances in Neural Information Processing Systems. — 1994. — С. 817.
  32. ↑ Demis Hassabis Как работает искусственный интеллект (ИИ) DeepMind (озвучивание Hello Robots) на YouTube, начиная с 6:50
  33. ↑ Google achieves AI 'breakthrough' by beating Go champion. // BBC News (27 января 2016). Дата обращения: 12 июля 2016. Архивировано 30 января 2016 года.
  34. ↑ Mullen J. Computer scores big win against humans in ancient game of Go. // CNN (28 января 2016). Архивировано 5 февраля 2016 года.
  35. ↑ Ormerod D. Zen computer Go program beats Takemiya Masaki with just 4 stones! // Go Game Guru. Дата обращения: 28 января 2016. Архивировано из оригинала 1 февраля 2016 года.
  36. ↑ Cambier A. Le Corps sans limites (фр.). — Presses Univ. Septentrion, 2016. — P. 100. — 146 p. — ISBN 9782757414859.
  37. ↑ Gershgorn D. Google's AlphaGo Beats World Champion in Third Match to Win Entire Series. // Popular Science (12 марта 2016). Дата обращения: 13 ноября 2016. Архивировано 16 декабря 2016 года.
  38. ↑ Hoffman W. Elon Musk Says Google Deepmind's Go Victory Is a 10-Year Jump For A.I. // Inverse (9 марта 2016). Дата обращения: 12 марта 2016. Архивировано 12 марта 2016 года.
  39. ↑ Silver et al., 2016, p. 484.
  40. ↑ Google DeepMind computer AlphaGo sweeps human champ in Go matches. // CBC News (12 марта 2016). Дата обращения: 13 марта 2016. Архивировано 13 марта 2016 года.
  41. ↑ Yan S. A Google computer victorious over the world's 'Go' champion. // CNN Money (12 марта 2016). Дата обращения: 13 марта 2016. Архивировано 13 марта 2016 года.
  42. ↑ Borowiec S., Lien T. AlphaGo beats human Go champ in milestone for artificial intelligence. // Los Angeles Times (12 марта 2016). Дата обращения: 13 марта 2016. Архивировано 12 марта 2016 года.
  43. ↑ Zastrow M. South Korea trumpets $860-million AI fund after AlphaGo 'shock' (англ.) // Nature News. — 2016. — 18 March. — doi:10.1038/nature.2016.19595. Архивировано 19 марта 2016 года.
  44. ↑ Zhang Z. When doctors meet with AlphaGo: potential application of machine learning to clinical medicine // Annals of Translational Medicine. — 2016-03-01. — Т. 4, вып. 6. — ISSN 2305-5839. — doi:10.21037/atm.2016.03.25.
  45. ↑ Byford S. DeepMind founder Demis Hassabis on how AI will shape the future. // The Verge (10 марта 2016). Дата обращения: 12 июля 2016. Архивировано 11 июля 2016 года.
  46. ↑ AlphaGo Can Shape The Future Of Healthcare. // The Medical Futurist (5 апреля 2016). Дата обращения: 12 июля 2016. Архивировано из оригинала 14 июля 2016 года.
  47. ↑ Man vs. machine: Google's AI to take on grand master of ancient Chinese board game (англ.). // ABC News (8 марта 2016). Дата обращения: 12 июля 2016. Архивировано 15 июня 2016 года.
  48. ↑ Silver et al., 2016, Methods, p. 489.
  49. ↑ Арлазаров В. Л. Алгоритмы шахматных программ. // acm.mipt.ru. Дата обращения: 12 июля 2016. Архивировано 9 октября 2016 года.
  50. ↑ 1 2 Metz C. Google's AI Wins Pivotal Second Game in Match With Go Grandmaster. // Wired News (10 марта 2016). Дата обращения: 12 марта 2016. Архивировано 11 марта 2016 года.
  51. ↑ Silver N. The Signal and the Noise: Why So Many Predictions Fail-but Some Don't. — Penguin, 2012-09-27. — 449 с. — P. 195. — ISBN 9781101595954.
  52. ↑ Match 3 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo на YouTube, начиная с 22:30
  53. ↑ Match 4 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo на YouTube, начиная с 6:09:35
  54. ↑ Google AlphaGo and machine learning (Alphago Korean Press Briefing 2 of 2) на YouTube
  55. ↑ 1 2 Maas D. How AlphaGo Works (англ.). // Maas Digital (28 января 2016). Дата обращения: 29 сентября 2016. Архивировано 5 октября 2016 года.
  56. ↑ 1 2 Burger C. Google DeepMind's AlphaGo: How it works. // On Personalization and Data (16 марта 2016). Дата обращения: 1 ноября 2016. Архивировано 1 ноября 2016 года.
  57. ↑ Schaeffer J., Burch N., Björnsson Y., Kishimoto A., Müller M., Lake R., Lu P., Sutphen S. Checkers is Solved // Science. — 2007. — Т. 317, № 5844. — P. 1518–22. — doi:10.1126/science.1144079. — PMID 17641166.
  58. ↑ Convolutional Neural Networks (LeNet) - DeepLearning 0.1 documentation. // DeepLearning 0.1 (LISA Lab). Дата обращения: 31 августа 2013. Архивировано из оригинала 28 декабря 2017 года.
  59. ↑ Clark L. DeepMind's AI is an Atari gaming pro now. // Wired UK. Дата обращения: 1 ноября 2016. Архивировано 21 мая 2016 года.
  60. ↑ Silver et al., 2016, Methods.
  61. ↑ 1 2 Черников А. Хроники Го-4. После матча. // Компьютерное Обозрение (18 марта 2016). Дата обращения: 6 июня 2016. Архивировано 2 августа 2016 года.
  62. ↑ 1 2 Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference на YouTube, начиная с 27:00
  63. ↑ Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference на YouTube, начиная с 27:45
  64. ↑ В статье журнала Nature (Silver et al., 2016 Архивная копия от 24 сентября 2019 на Wayback Machine) утверждалось, что стратегическая сеть AlphaGo предсказывает ход человека с вероятностью 24 %, но позже один из авторов, Айа Хуань, заявил, что эти данные ошибочные. См. Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference на YouTube, начиная с 34:45
  65. ↑ 李世乭：即使Alpha Go得到升级也一样能赢 (кит.). // JoongAng Ilbo (23 февраля 2016). Дата обращения: 7 июня 2016. Архивировано 4 марта 2016 года.
  66. ↑ Silver et al., 2016, Table 8.
  67. ↑ Silver et al., 2016, Table 6.
  68. ↑ Showdown: Win or lose, a computer program’s contest against a professional Go player is another milestone in AI (англ.). // The Economist (12 марта 2016). Дата обращения: 28 сентября 2017. Архивировано 14 августа 2017 года.
  69. ↑ McMillan R. Google Isn’t Playing Games With New Chip. // Wall Street Journal (18 мая 2016). Дата обращения: 26 июня 2016. Архивировано 29 июня 2016 года.
  70. ↑ Jouppi N. Google supercharges machine learning tasks with TPU custom chip (англ.). // Google Cloud Platform Blog (18 мая 2016). Дата обращения: 26 июня 2016. Архивировано 18 мая 2016 года.
  71. ↑ The Future of Go Summit, Match One: Ke Jie & AlphaGo на YouTube, начиная с 6:03:10 (23 мая 2017)
  72. ↑ 1 2 Gibney E. Google AI algorithm masters ancient game of Go. // Nature News & Comment (27 января 2016). Дата обращения: 3 февраля 2016. Архивировано 2 мая 2019 года.
  73. ↑ Lee Sedol expects «not easy» game with AlphaGo in 3rd Go match. // Shanghai Daily (10 марта 2016). Дата обращения: 10 марта 2016. Архивировано 11 марта 2016 года.
  74. ↑ Nie Weiping 9d: «AlphaGo is a 6-7 dan pro in the beginning; 13d mid-game; 15d end-game». // Reddit (15 марта 2016). Дата обращения: 13 сентября 2016. Архивировано 1 июля 2016 года.
  75. ↑ Byford S. AlphaGo beats Lee Se-dol again to take Google DeepMind Challenge series. // The Verge (Vox Media) (12 марта 2016). Дата обращения: 12 марта 2016. Архивировано 13 марта 2016 года.
  76. ↑ 1 2 Ormerod D. Lee Sedol defeats AlphaGo in masterful comeback - Game 4 (англ.). // Go Game Guru (13 марта 2016). Дата обращения: 4 ноября 2016. Архивировано из оригинала 16 ноября 2016 года.
  77. ↑ Tanguy C. The Go Files: AI computer wraps up 4-1 victory against human champion (англ.). // Nature (15 марта 2016). Дата обращения: 13 сентября 2016. Архивировано 17 сентября 2016 года.
  78. ↑ Huang A. Alpha Go: Combining Deep Neural Networks with Tree Search // Keynote Lecture CG2016 Conference на YouTube, начиная с 37:28
  79. ↑ Audureau, W. Jeu de go: pour Lee Sedol, la victoire de la machine est moins tactique que psychologique (фр.). // Le Monde (15 марта 2016). Дата обращения: 13 июня 2016. Архивировано 16 марта 2016 года.
  80. ↑ Tian Y., Zhu Y. Better Computer Go Player with Neural Network and Long-term Prediction : [арх. 14 ноября 2016] // ICLR 2016. — 2016. — 29 февраля. — arXiv:1511.06410v3.
  81. ↑ HAL 90210 No Go: Facebook fails to spoil Google's big AI day (англ.) (28 января 2016). Дата обращения: 1 февраля 2016. Архивировано 15 марта 2016 года.
  82. ↑ Hassabis D. Strachey Lecture. // The New Livestream. Дата обращения: 17 марта 2016. Архивировано 16 марта 2016 года.
  83. ↑ 「DEEP ZEN GO プロジェクト」発表。AlphaGo対抗の囲碁ソフト開発をドワンゴが支援、山本一成さんら参加 (яп.) (1 марта 2016). Дата обращения: 13 июля 2016. Архивировано 6 июля 2016 года.
  84. ↑ Jiji. Go master Cho wins best-of-three series against Japan-made AI. // The Japan Times Online (24 ноября 2016). Дата обращения: 27 ноября 2016. Архивировано 14 августа 2017 года.
  85. ↑ Bolton A. Humans strike back: Korean Go master bests AI in board game bout. // CNET (23 ноября 2016). Дата обращения: 27 ноября 2016. Архивировано 25 ноября 2016 года.

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=AlphaGo&oldid=142394302