AlphaGo против Ли Седола - AlphaGo versus Lee Sedol

AlphaGo против Ли Седола, также известный как Матч Google DeepMind Challenge, было пять игр Идти матч между 18-кратным чемпионом мира Ли Седол и AlphaGo, а компьютер Go программа разработана Google DeepMind, играл в Сеул, Южная Корея, с 9 по 15 марта 2016 года. AlphaGo выиграла все игры, кроме четвертой;^[1] все игры были выиграны отставкой.^[2] Матч сравнивают с историческим шахматным матчем между Deep Blue и Гарри Каспаров в 1997 г.

Победитель матча должен был выиграть 1 миллион долларов. Поскольку AlphaGo выиграла, Google DeepMind заявил, что приз будет передан благотворительным организациям, в том числе ЮНИСЕФ, и организации Go.^[3] Ли получил 170 000 долларов (150 000 долларов за участие в пяти играх и дополнительные 20 000 долларов за победу в одной игре).^[4]

После матча The Корейская ассоциация бадук присвоил AlphaGo высшее звание гроссмейстера Го - «почетный 9 дан Это было дано в знак признания «искренних усилий» AlphaGo овладеть го.^[5] Этот матч выбрали Наука как один из Прорыв года финалисты 22 декабря 2016 г.^[6]

Фон

Сложная задача в искусственном интеллекте

Внешнее видео
Машина тренирует себя, чтобы побеждать людей в самой сложной игре в мире, Retro Report, 2:51, Ретро отчет[7]

Го - сложная настольная игра, требующая интуиции, творческого и стратегического мышления.^[8][9] Это долгое время считалось сложной задачей в области искусственный интеллект (AI) и значительно сложнее^[10] решить чем шахматы. Многие в области искусственного интеллекта считают, что для Go требуется больше элементов, имитирующих человеческое мышление, чем шахматы.^[11] Математик И. Дж. Хорошо писал в 1965 году:^[12]

Зайти на компьютер? - Чтобы запрограммировать компьютер для разумной игры в го, а не просто в легальную игру, необходимо формализовать принципы хорошей стратегии или разработать обучающую программу. Принципы более качественные и загадочные, чем в шахматах, и больше зависят от суждений. Поэтому я думаю, что запрограммировать компьютер для разумной игры в го будет даже труднее, чем в шахматы.

До 2015 г.^[13] только лучшие программы Go достигли любительский дан уровень.^[14] На маленькой доске 9 × 9 компьютер показал себя лучше, и некоторым программам удавалось выигрывать часть своих игр 9 × 9 у профессиональных игроков. До AlphaGo некоторые исследователи утверждали, что компьютеры никогда не победят лучших людей в Go.^[15] Илон Маск, один из первых инвесторов Deepmind, сказал в 2016 году, что эксперты в этой области считали, что искусственному интеллекту осталось 10 лет до победы над ведущим профессиональным игроком в го.^[16]

Матч AlphaGo против Ли Седола сопоставим с шахматным матчем 1997 года. Deep Blue против Гарри Каспарова. Здесь поражение действующего чемпиона Каспарова компьютером IBM Deep Blue рассматривается как символический момент, когда компьютеры стали лучше людей в шахматах.^[17]

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

Соответствующие результаты исследований применяются в таких областях, как наука о мышлении, распознавание образов и машинное обучение.^[18]

Матч против Фань Хуэй

Фан Хуэй против AlphaGo - Игра 5

AlphaGo побежден Чемпион Европы Фань Хуэй, 2 дан профессионал, 5–0 в октябре 2015 года, впервые ИИ обыграл профессионального игрока-человека в игре на полноразмерной доске без гандикапа.^[19][20] Некоторые комментаторы подчеркнули пропасть между Фаном и Ли, имеющей 9 дан профессионального уровня.^[21] Компьютерные программы Zen и Безумный камень ранее побеждали игроков-людей с рейтингом 9 дан профессионалов с гандикапом в четыре или пять стоек.^[22][23] Канадский специалист по ИИ Джонатан Шеффер, комментируя победу над Fan, сравнил AlphaGo с «вундеркиндом», которому не хватало опыта, и посчитал, что «настоящее достижение будет, когда программа сыграет игрока в истинном высшем эшелоне». Затем он считал, что Ли выиграет матч в марте 2016 года.^[20] Хаджин Ли, профессиональный игрок в го и Международная федерация го Генеральный секретарь отметила, что она «очень взволнована» перспективой того, что ИИ бросит вызов Ли, и считает, что у двух игроков равные шансы на победу.^[20]

После матча с AlphaGo Фань Хуэй отметил, что игра научила его быть лучшим игроком и видеть то, чего он раньше не видел. К марту 2016 г. Проводной сообщил, что его рейтинг поднялся с 633 в мире до примерно 300.^[24]

Подготовка

Эксперты по го обнаружили ошибки в игре AlphaGo против Fan, в частности, связанные с недостаточной осведомленностью всего игрового поля. Перед игрой против Ли было неизвестно, насколько программа улучшила свою игру после октябрьского матча.^[21][25] Первоначальный набор тренировочных данных AlphaGo начался с игр сильных игроков-любителей с серверов интернет-Go, после чего AlphaGo тренировалась, играя против себя в десятках миллионов игр.^[26][27]

Игроки

AlphaGo

Логотип AlphaGo

AlphaGo - это компьютерная программа, разработанная Google DeepMind играть в настольную игру Идти. Алгоритм AlphaGo использует комбинацию машинное обучение и поиск по дереву техники в сочетании с обширным обучением как в игровой, так и в компьютерной среде. Первоначально нейронные сети системы были созданы на основе человеческого опыта игры. AlphaGo изначально был обучен имитировать человеческую игру, пытаясь сопоставить движения опытных игроков из записанных исторических игр, используя KGS Go Сервер база данных, содержащая около 30 миллионов ходов из 160 000 игр человеческими игроками от 6 до 9 сомов.^[13][28] Когда он достиг определенной степени мастерства, его обучали дальше, настраивая на то, чтобы играть в большое количество игр против других экземпляров самого себя, используя обучение с подкреплением чтобы улучшить свою игру.^[29] Система не использует «базу данных» ходов для игры. Как пояснил один из создателей AlphaGo:^[30]

Хотя мы запрограммировали эту машину на игру, мы не знаем, какие ходы она будет использовать. Его ходы возникающий явление из тренировки. Мы просто создаем наборы данных и алгоритмы обучения. Но ходы, которые он придумывает, находятся вне наших рук - и намного лучше, чем мы, как игроки в го, могли придумать.

В матче против Ли AlphaGo использовала примерно ту же вычислительную мощность, что и в матче против Фань Хуэй.^[31] где использовано 1202 Процессоры и 176 GPU.^[13] Экономист сообщил, что он использовал 1920 процессоров и 280 графических процессоров.^[32] Google также заявил, что его проприетарный блоки тензорной обработки были использованы в матче против Ли Седола.^[33]

Ли Седол

Ли Седол в 2012 году

Ли Седол - профессиональный игрок в го 9 дан ранг^[34] и является одним из сильнейших игроков в история Go. Он начал свою карьеру в 1996 году (повышен до профессионального дана в возрасте 12 лет), с тех пор выиграв 18 чемпионатов мира.^[35] Он - «национальный герой» в своей родной Южной Корее, известный своей нетрадиционной и творческой игрой.^[36] Ли Седол первоначально предсказал, что он победит AlphaGo в "оползне".^[36] За несколько недель до матча он выиграл у корейца. Мюнгин титул, крупный чемпионат.^[37]

Игры

Матч состоял из пяти игр с главным призом в миллион долларов США.^[3] с помощью Китайские правила с 7,5-балльной коми.^[4] Для каждой игры было установлено двухчасовое ограничение по времени для каждого игрока, за которым следовали три 60-секундных Byo-Yomi сверхурочные периоды.^[4] Каждая игра начинается в 13:00. KST (04:00 время по Гринвичу ).^[38]

Матч был сыгран в Отель Four Seasons в Сеул, Южная Корея в марте 2016 г. и транслировалась в прямом эфире с комментариями Майкл Редмонд (9 дан профессионал) и Крис Гарлок.^[39][40][41] Аджа Хуанг, член команды DeepMind и любитель 6 дан Го, положил камни на Перейти на борт для AlphaGo, который прошел через Облачная платформа Google со своим сервером в США.^[42]

Резюме

Игра 1

AlphaGo (белый) выиграл первую игру. Ли, казалось, контролировал игру большую часть матча, но AlphaGo получил преимущество в последние 20 минут, и Ли подал в отставку.^[45] Ли позже заявил, что допустил критическую ошибку в начале матча; он сказал, что стратегия компьютера в начале игры была «превосходной» и что ИИ сделал один необычный ход, который не сделал бы ни один игрок-человек.^[45] Дэвид Ормерод, комментируя игру в Go Game Guru, охарактеризовал седьмой камень Ли как «странный ход для проверки силы AlphaGo в дебюте», охарактеризовав этот ход как ошибку, а ответ AlphaGo как «точный и эффективный». Он описал позицию AlphaGo как благоприятную в первой части игры, учитывая, что Ли начал возвращаться на 81-м ходу, прежде чем сделать «сомнительные» ходы на 119 и 123, после чего последовал «проигрышный» ход на 129.^[46] Профессиональный игрок в го Cho Hanseung прокомментировал, что игра AlphaGo значительно улучшилась по сравнению с Фань Хуэй в октябре 2015 года.^[46] Майкл Редмонд описал компьютерную игру как более агрессивную, чем против Fan.^[47]

По словам гроссмейстера 9 дан Го Ким Сон Рёна, Ли казался ошеломленным сильной игрой AlphaGo на 102-м камне.^[48] Наблюдая за тем, как AlphaGo делает 102-й ход, Ли более 10 минут обдумывал свои варианты.^[48]

Первые 99 ходов

Ходы 100–186

Игра 2

AlphaGo (черный) выиграла вторую игру. Ли позже заявил, что «AlphaGo сыграла почти идеальную игру»,^[49] «с самого начала игры я не чувствовал, что есть точка, которую я веду».^[50] Один из создателей AlphaGo, Демис Хассабис, сказал, что система была уверена в победе с середины игры, хотя профессиональные комментаторы не могли сказать, какой игрок впереди.^[50]

Майкл Редмонд (9p ) отметил, что 19-й камень AlphaGo (ход 37) был «творческим» и «уникальным».^[30] Ли потребовалось необычно много времени, чтобы отреагировать на это движение.^[30] Янггил (8p) назвал 37-й ход AlphaGo «редким и интригующим ударом плеча», но сказал, что контратака Ли «изящна». Он заявил, что контроль переходил между игроками несколько раз перед эндшпилем, и особенно похвалил шаги AlphaGo 151, 157 и 159, назвав их «блестящими».^[51]

AlphaGo показала аномалии и ходы с более широкой точки зрения, которые профессиональные игроки в го описали как ошибки на первый взгляд, но как преднамеренную стратегию в ретроспективе.^[52] Как объяснил один из создателей системы, AlphaGo не пытается максимизировать свои очки или свой запас победы, но пытается максимизировать свою вероятность победы.^[30][53] Если AlphaGo придется выбирать между сценарием, в котором она выиграет с разницей в 20 очков с вероятностью 80 процентов, и другим сценарием, в котором она выиграет с разницей в полтора очка с вероятностью 99 процентов, она выберет последний, даже если ей придется отказаться от очков для достижения Это.^[30] В частности, ход 167 AlphaGo, казалось, дал Ли шанс на борьбу и был объявлен комментаторами очевидной ошибкой. Ан Янгил заявил: «Значит, когда AlphaGo делает слабый ход, мы можем рассматривать это как ошибку, но, может быть, это более точно следует рассматривать как объявление победы?»^[54]

Первые 99 ходов

100–199 ходов

Ходы 200–211

Игра 3

AlphaGo (белые) выиграли третью игру.^[55]

После второй игры игроки все еще сомневались, действительно ли AlphaGo является сильным игроком в том смысле, в каком может быть человек. Третья игра была описана как устранение этого сомнения; аналитики отмечают, что:

AlphaGo победила настолько убедительно, что убрала все сомнения в ее силе из голов опытных игроков. Фактически, он играл так хорошо, что это было почти страшно ... Вынуждая AlphaGo противостоять очень серьезной односторонней атаке, Ли показал свою до сих пор незамеченную силу ... Ли не получал достаточной прибыли от своей атаки ... Один из величайших виртуозов средней игры только что был отодвинут на задний план в черно-белой прозрачности.^[54]

По словам Ан Янгила (8p) и Дэвида Ормерода, игра показала, что «AlphaGo просто сильнее любого известного игрока в го».^[54] Было замечено, что AlphaGo умело преодолевает сложные ситуации, известные как ко этого не было в двух предыдущих матчах.^[56] Ан и Ормерод считают ход 148 особенно примечательным: в центре комплекса ко боя, AlphaGo проявила достаточную «уверенность» в том, что выиграла битву, чтобы сделать большой ход в другом месте.^[54]

Ли, играя черным, открыл Высшее китайское образование и сгенерировал большую зону влияния черных, в которую AlphaGo вторглась на 12-м ходу. Это потребовало от программы защиты слабой группы, что она и сделала.^[54] Ан Янгил описал ход Ли 31 как возможно «проигрышный ход».^[54] и Энди Джексон из Американская ассоциация го посчитал, что исход уже решен к 35-му ходу.^[53] AlphaGo получила контроль над игрой к 48-му ходу и вынудила Ли перейти в оборону. Ли контратаковал на ходах 77/79, но ответ AlphaGo оказался эффективным, и его ход 90 позволил упростить позицию. Затем он получил большую зону контроля в нижней части доски, укрепив свои позиции с помощью ходов от 102 до 112, которые Ан назвал «сложными».^[54] Ли снова атаковал на 115 и 125 ходах, но ответ AlphaGo снова оказался эффективным. Ли в конце концов попытался сложить ко с 131-го хода, не вызвав ошибки в программе, и он сдался на 176-м ходу.^[54]

Первые 99 ходов

Ходы 100–176 (122 на 113, 154 в , 163 на 145, 164 на 151, 166 и 171 на 160, 169 на 145, 175 на )

Игра 4

Ли (белые) выиграл четвертую игру. Ли избрал экстремальную стратегию, известную как амаши, в ответ на очевидное предпочтение AlphaGo Souba Go (пытаясь выиграть за счет множества мелких выигрышей, когда появляется возможность), захват территории по периметру, а не в центре.^[57] Поступая таким образом, его очевидная цель состояла в том, чтобы навязать стиль ситуации «все или ничего» - возможная слабость для оппонента, сильного в переговорных типах игры, и такая, которая могла бы сделать способность AlphaGo определять незначительные преимущества в значительной степени несущественной.^[57]

Первые 11 ходов были идентичны второй партии, где Ли также играл белыми. В начале игры Ли сосредоточился на захвате территории по краям и углам доски, что позволило AlphaGo получить влияние наверху и в центре. Затем Ли вторгся в область влияния AlphaGo наверху с 40-го по 48-й ходы, после амаши стратегия. AlphaGo ответил ударом плечом на 47-м ходу, впоследствии пожертвовав четырьмя камнями в другом месте и получив инициативу на ходах с 47 по 53 и 69. Ли протестировал AlphaGo на ходах с 72 по 76, не вызвав ошибки, и к этому моменту комментаторы партии уже начал чувствовать, что игра Ли проиграна. Однако неожиданная игра белыми 78, описанная как «блестящая Tesuji", перевернула игру.^[57] Этот ход образовал белый клин в центре и усложнил игру.^[58] Гу Ли (9p) описал это как "божественный ход "и заявил, что переезд был им совершенно непредвиден.^[57]

AlphaGo плохо отреагировала на 79-м ходу, и тогда, по ее оценкам, у нее были 70% -ные шансы на победу. Ли сделал сильный ход белыми 82.^[57] Первоначальная реакция AlphaGo на 83-85 ходах была правильной, но на 87-м ходу ее оценка шансов на победу резко упала.^[59][60] спровоцировав их на серию очень плохих ходов с 87 на 101 черными. Дэвид Ормерод охарактеризовал ходы с 87 на 101 как типичные программные ошибки Монте-Карло.^[57] Ли повел ход белых 92, и Ан Янгил назвал 105 ход черных последним проигрышным ходом. Несмотря на хорошую тактику во время ходов с 131 по 141, AlphaGo не смогла восстановиться в эндшпиле и сдалась.^[57] Отставка AlphaGo была вызвана тем, что она оценила свои шансы на победу менее 20%; это сделано для того, чтобы соответствовать решению профессионалов, которые уходят в отставку, а не играют до конца, когда их позиция кажется безвозвратной.^[58]

Юнггил из Go Game Guru пришел к выводу, что эта игра была «шедевром для Ли Седола и почти наверняка станет известной игрой в истории го».^[57] Ли прокомментировал после матча, что, по его мнению, AlphaGo была сильнейшей в игре белыми (вторая).^[61] По этой причине он попросил его сыграть черными в пятой партии, которая считается более рискованной.

Дэвид Ормерод из Go Game Guru заявил, что, хотя анализ игры AlphaGo в период 79–87 годов еще не был доступен, он полагал, что это результат известной слабости игровых алгоритмов, которые используют Поиск в дереве Монте-Карло. По сути, поиск пытается отсечь менее релевантные последовательности. В некоторых случаях игра может привести к очень специфической линии игры, которая имеет значение, но которую упускают из виду, когда дерево обрезается, и поэтому этот результат «вне поля зрения поиска».^[62]

Первые 99 ходов

Ходит 100–180 (177 на , 178 в )

Игра 5

AlphaGo (белые) выиграли пятую игру.^[63] Игра была описана как близкая. Хассабис заявил, что результат пришел после того, как программа сделала «серьезную ошибку» в начале игры.^[63]

Ли, играя черными, начал игру так же, как и в первой игре, а затем начал разбивать территорию в правом и верхнем левом углах - стратегия, аналогичная той, которую он успешно применил в игре 4, - в то время как AlphaGo получил влияние в центре игры. доска. Игра продолжалась до тех пор, пока белые не пошли с 48 на 58, которые AlphaGo сыграл в правом нижнем углу. Эти движения излишне теряли ко-угрозы и адзи, что позволяло Ли взять на себя инициативу.^[64] Майкл Редмонд (9p) предположил, что, возможно, AlphaGo пропустила «сжатие надгробной плиты» Блэка. Tesuji. Людей учат распознавать конкретный паттерн, но это длинная последовательность движений, если ее нужно вычислять с нуля.

Затем AlphaGo начал развивать верхнюю часть доски, а также центр, и успешно защитился от атаки Ли на ходах с 69 по 81, которые Дэвид Ормерод охарактеризовал как чрезмерно осторожный. К ходу хода белых 90 AlphaGo вернул себе равенство, а затем сыграл серию ходов, которые Ормерод назвал «необычными ... но слегка впечатляющими», что дало небольшое преимущество. Ли попробовал выполнить пас «Радуйся, Мария» с ходами 167 и 169, но защита AlphaGo оказалась успешной. Янгил отметил, что ходы белых 154, 186 и 194 особенно сильны, и программа сыграла безупречный эндшпиль, сохраняя лидерство до тех пор, пока Ли не сдался.^[64]

Первые 99 ходов