Русская Википедия:AlphaGo

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Alphago logo Reversed.svg
Лого AlphaGo

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 годах (Шаблон:Нп5), и недавние успехи в области машинного обучения, а именно глубинное обучение с помощью многоуровневых нейронных сетейШаблон:Переход.

История

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

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

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

Файл:FAN Hui vs BAO Yun.jpg
Фань Хуэй

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

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

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

Шаблон:Goban

Первые 99 ходов (96 в 10)

Шаблон:Goban

Ходы 100—165.

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

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

Шаблон:Main

Файл:Lee Se-Dol.jpg
Ли Седоль в 2016 году

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

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

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

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

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

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

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

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

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

Шаблон:Основная статья

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

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

Уход из го

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

AlphaGo Zero

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

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

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

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

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

89:11 против AlphaGo Master

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

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

Значение

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

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

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

По этим причинам даже спустя почти двадцать лет, после того как компьютер Deep Blue впервые выиграл у чемпиона мира Каспарова в 1997 году, самые сильные программы, играющие в го, достигли только любительского 5 дана, и не могли выиграть у профессионала на полной доске <math>19\times 19</math>[6][30][31]. Лучшими достижениями искусственного интеллекта в го были победы программы Шаблон:Iw, работающей на кластере из четырёх компьютеров, против профессионала 9 дана Масаки Такэмия два раза с форой в пять и четыре камня в 2012 году[32], а также победа программы Шаблон:Iw над Ёсио Исидой (9 профессиональный дан) с форой в четыре камня в 2013 году[33].

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

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

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

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

Устройство AlphaGo

Шаблон:Mainref

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

Существенной особенностью AlphaGo является то, что она использует общие алгоритмы, которые практически не зависят от особенностей игры го[43]. В алгоритм AlphaGo заложены только базовые принципы игры, с которых начинает изучение игры любой начинающий, такие как подсчёт числа свободных пунктов (дамэ) у группы камней, и анализ возможности захватить камни, используя приём «лестница» (ситё). Остальное AlphaGo выучила сама, анализируя базу данных из 160 тысяч партий общими методами, которые могут использоваться и в других областях искусственного интеллектаШаблон:Sfn. Этим AlphaGo отличается от таких систем, как Deep Blue — шахматного суперкомпьютера[4]. При написании алгоритма для Deep Blue использовалась продвинутая шахматная теория. Так, например, для оценки позиции Deep Blue использовал 8000 настраиваемых признаков, в Deep Blue была заложена огромная библиотека дебютов[44]. AlphaGo — программа, которая может работать на любом аппаратном обеспечении (хотя она использовала процессор, разработанный специально для машинного обученияШаблон:Переход), и принципы которой можно использовать в других областях. Она не использует библиотеку дебютов и во время игры не обращается ни к какой базе данных ходов непосредственно (а только использует нейронную сеть, натренированную на большом количестве партий). Сами разработчики программы не знают, как AlphaGo оценивает позицию, её ходы представляют собой феномен эмерджентности[45]. Кроме того, Deep Blue был разработан с одной целью — выиграть матч у Гарри Каспарова в шахматы[4][46]. AlphaGo не была обучена играть специально против Ли Седоля[15][47], более того, в базе данных тренировки AlphaGo не было партий Ли Седоля[48], и во время матча программа AlphaGo не менялась и не подстраивалась под стиль игры Ли Седоля[49].

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

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

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

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

Го является игрой с полной информацией. Теоретически для любой игры с полной информацией существует оптимальная стратегия. Чтобы найти оптимальную стратегию, нужно обойти полное Шаблон:Iw. Например, таким образом в 2007 году программа Chinook полностью Шаблон:Iw английские шашки[52]. Однако для большинства игр этот метод непрактичен, так как размер дерева может быть очень большим. Его можно оценить как <math>b^d</math>, где <math>b</math> — степень ветвления дерева игры (то есть примерное число возможных ходов в каждой позиции), а <math>d</math> — глубина дерева игры (то есть примерная длина партии). Для го <math>b\approx 250, d\approx 150,</math> в то время как для шахмат <math>b\approx 35, d\approx 80.</math> Перебор может быть сокращён с использованием двух техник.

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

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

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

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

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

Файл:Архитектура сверточной нейронной сети.png
Архитектура свёрточной нейронной сети

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

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

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

Алгоритм AlphaGo

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

AlphaGo использует свёрточные нейронные сети для того, чтобы оценить позицию или предсказать следующий ход. Аналогично тому, как при распознавании образов на нейронную сеть подаётся изображение, AlphaGo подаёт на нейронные сети позицию. Каждая позиция представлена как многослойная картинка <math>19\times 19</math>, где каждый слой представляет описания простых свойств каждого пункта доски. Используются следующие простые свойства: цвет камня, количество свободных пунктов (дамэ) у данной группы камней (если их не больше 8), взятие камней, возможность сходить в данный пункт, был ли данный камень поставлен недавно. Единственное нетривиальное свойство, которое используется, — это угрожает ли данной группе захват в лестницу (ситё). Всего используется 48 бинарных свойств (свойства, выраженные целым числом, представляются при помощи унитарного кода). Таким образом каждая позиция представлена в виде таблицы бит <math>19\times 19\times 48</math>Шаблон:Sfn.

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

Для того, чтобы не рассматривать совсем плохие ходы, и тем самым сократить степень ветвления при поиске, AlphaGo использует стратегические сети[55] (Шаблон:Lang-en) — нейронные сети, которые помогают выбирать хороший ход.

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

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

Улучшенная стратегическая сеть

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

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

Быстрая стратегическая сеть

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

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

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

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

AlphaGo осуществляет перебор вариантов при помощи Шаблон:Нп5 следующим образом. AlphaGo строит частичное Шаблон:Iw, начиная с текущей позиции, производя многочисленные симуляции игры. Для каждого хода в дереве записывается оценка, которая специальным образом зависит от оценок хода, полученных при помощи стратегическойШаблон:Переход и оценочнойШаблон:Переход сетей, от результата случайных партий в предыдущих симуляциях и от количества предыдущих симуляций, выбравших этот ход (чем чаще выбирался раньше этот ход, тем ниже оценка, чтобы программа рассматривала больше разнообразных ходов).

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

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

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

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

Файл:AlphaGo's TPU.png
Стойка TPU, используемая AlphaGo в матче с Ли Седолем.

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

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

Вычисления Потоков
выполнения		 Число ЦП Число ГП Рейтинг Эло
Параллельные 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 графических процессорахШаблон:Sfn .

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

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

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

Стиль игры

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

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

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

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

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

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

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

Facebook также разрабатывает программу для игры в го, Шаблон:Iw, которая тоже основана на машинном обучении и поиске в дереве[64][72]. На начало 2016 года Darkforest показал сильную игру против других компьютеров, но не смог выиграть у профессионала[73]. По силе Darkforest оценивается на уровне программ Шаблон:Iw и Шаблон:Iw[74].

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

Литература

См. также

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Го Шаблон:Искусственный интеллект

Шаблон:Избранная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Cite web
  4. ↑ 4,0 4,1 4,2 4,3 Шаблон:Cite web
  5. ↑ 5,0 5,1 Шаблон:Cite web
  6. ↑ 6,0 6,1 6,2 Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:YouTube
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite web
  11. ↑ Шаблон:Cite web
  12. ↑ Шаблон:Cite web
  13. ↑ Шаблон:Cite web
  14. ↑ Шаблон:Cite web
  15. ↑ 15,0 15,1 Шаблон:Cite web
  16. ↑ 16,0 16,1 Шаблон:Cite web
  17. ↑ 17,0 17,1 Шаблон:Cite web
  18. ↑ Шаблон:Cite web
  19. ↑ Шаблон:YouTube (23 мая 2017)
  20. ↑ Шаблон:Cite web
  21. ↑ Шаблон:Cite web
  22. ↑ Шаблон:Cite web
  23. ↑ 23,0 23,1 23,2 23,3 Шаблон:Cite web
  24. ↑ 24,0 24,1 24,2 24,3 Шаблон:СтатьяШаблон:Closed access
  25. ↑ Шаблон:Cite web
  26. ↑ Шаблон:Cite web
  27. ↑ Шаблон:Cite web
  28. ↑ Шаблон:Публикация
  29. ↑ Шаблон:YouTube
  30. ↑ Шаблон:Cite web
  31. ↑ Шаблон:Cite web
  32. ↑ Шаблон:Cite web
  33. ↑ Шаблон:Книга
  34. ↑ Шаблон:Cite web
  35. ↑ Шаблон:Cite web
  36. ↑ Шаблон:Cite web
  37. ↑ Шаблон:Cite web
  38. ↑ Шаблон:Cite web
  39. ↑ Шаблон:Статья
  40. ↑ Шаблон:Статья
  41. ↑ Шаблон:Cite web
  42. ↑ Шаблон:Cite web
  43. ↑ Шаблон:Cite web
  44. ↑ Шаблон:Cite web
  45. ↑ 45,0 45,1 Шаблон:Cite web
  46. ↑ Шаблон:Книга
  47. ↑ Шаблон:YouTube
  48. ↑ Шаблон:YouTube
  49. ↑ Шаблон:YouTube
  50. ↑ 50,0 50,1 Шаблон:Cite web
  51. ↑ 51,0 51,1 Шаблон:Cite web
  52. ↑ Шаблон:Публикация
  53. ↑ Шаблон:Cite web
  54. ↑ Шаблон:Cite web
  55. ↑ 55,0 55,1 Шаблон:Cite web
  56. ↑ 56,0 56,1 Шаблон:YouTube
  57. ↑ Шаблон:YouTube
  58. ↑ В статье журнала Nature (Silver et al., 2016 Шаблон:Wayback) утверждалось, что стратегическая сеть AlphaGo предсказывает ход человека с вероятностью 24 %, но позже один из авторов, Айа Хуань, заявил, что эти данные ошибочные. См. Шаблон:YouTube
  59. ↑ Шаблон:Cite web
  60. ↑ Шаблон:Cite web
  61. ↑ Шаблон:Cite web
  62. ↑ Шаблон:Cite web
  63. ↑ Шаблон:YouTube (23 мая 2017)
  64. ↑ 64,0 64,1 Шаблон:Cite web
  65. ↑ Шаблон:Cite web
  66. ↑ Шаблон:Cite web
  67. ↑ Шаблон:Cite web
  68. ↑ 68,0 68,1 Шаблон:Cite web
  69. ↑ Шаблон:Cite web
  70. ↑ Шаблон:YouTube
  71. ↑ Шаблон:Cite web
  72. ↑ Шаблон:Публикация
  73. ↑ Шаблон:Cite web
  74. ↑ Шаблон:Cite web
  75. ↑ Шаблон:Cite web
  76. ↑ Шаблон:Cite web
  77. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:AlphaGo&oldid=8576543