День 133. Компьютер обыграл человека в го

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

Я был очень удивлен, когда узнал сегодня, что ЭТО СЛУЧИЛОСЬ. Компьютер обыграл в го самого сильного человека. Что удивительно, многие коллеги на работе уже знали это — вот он уровень) И на мои вопросы ответили — Как ты так живешь… (не зная таких новостей)

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

Матч между компьютерной программой AlphaGo и корейским профессионалом 9 дана Ли Седолем состоялся в марте 2016 г. Победу со счетом 4-1 одержал искусственный интеллект.

Введение

Го — сложная настольная игра, требующая помимо логики применение интуиции, творческого и стратегического мышления. В течение длительного времени обучить компьютерные программы играть в го на уровне сильного любителя было крайне сложно. По сравнению с шахматами, в го перед искусственным интеллектом ставится больше задач, решение которых требует имитацию мыслительного процесса человека. Ещё в 1965 году математик Ирвинг Джон Гуд писал:

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

До 2015 года лучшие программы, играющие в го, могли достичь лишь уровня любителя. До появления AlphaGo некоторые разработчики заявляли, что компьютеры никогда не смогут победить лучших игроков среди людей. Илон Маск в 2016 году заявил, что по мнению экспертов, искусственный интеллект находится в 10 годах от победы над лучшим из профессиональных игроков.

Матч AlphaGo против Ли Седоля можно сравнить с шахматным матчем между программой Deep Blue и Гарри Каспаровым 1997 года, где победа программы, созданной IBM, над действовавшим чемпионом стала символической точкой отсчёта новой эпохи, когда компьютеры превзошли людей в шахматах.

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

Подготовка

 В начале 2016 года были опубликованы материалы о том, что в октябре 2015 года AlphaGo победила трёхкратного чемпиона Европы по го Фань Хуэя (2 профессиональный дан) со счётом 5-0; таким образом, искусственный интеллект впервые одержал победу над профессиональным игроком на доске размером 19x19 без форы. Часть экспертов указывала на сильный разрыв в уровне игры между Фань Хуэем и Ли Седолем, обладателем наивысшего ранга — 9 профессионального дана. Почти все эксперты предсказывали победу Ли Седоля в интересной борьбе, единицы указали за равные шансы соперников. После своего поражения, Фань Хуэй заявил, что благодаря этому матчу он стал играть лучше и стал видеть те вещи в игре, которые не замечал ранее; к марту 2016 года мировой рейтинг Фань Хуэя поднялся примерно на 300 позиций.

Эксперты по го нашли несколько ошибок, сделанных AlphaGo в партиях против Фань Хуэя, в частности, в оценке позиции на всей доске в противовес отдельным тактическим моментам; однако, к началу матча против Ли Седоля, не было известно, насколько с тех пор усилилась программа. AlphaGo просматривала партии сильных игроков-любителей, сыгранные на интернет-серверах, после чего играла сама против себя; в базе данных тренировки AlphaGo не было партий Ли Седоля.В интервью перед матчем Ли Седоль предсказывал, что он легко выиграет, затем 2-3 года Google будут дорабатывать AlphaGo, после чего захотят взять у него реванш. В этом случае играть с обновлённой версией AlphaGo будет действительно интересно, считал Ли.

AlphaGo — компьютерная программа, созданная компанией Google DeepMind. Алгоритм AlphaGo использует комбинацию последних достижений для поиска оптимальной стратегии в дереве игры с новейшими методами машинного обучения в сочетании с интенсивным изучением партий людей, так и тренировкой при игре с самой собой. Изначально AlphaGo тренировали подражанию человеческой игре через изучение множества партий, сыгранных как профессионалами так и сильными любителями. После достижения определённого уровня в стратегии и тактике, программа перешла на игру против самой себя и обучение с подкреплением. Система не использует базу данных ходов. Как пояснил один из создателей программы: Хоть мы и программировали эту машину, мы не знаем, какой ход она сделает. Её ходы представляют собой феномен эмерджентности, что стало результатом тренировки. Мы всего лишь создаём ряды данных и алгоритмы обучения. Но ходы, к которым она прибегает, не в наших руках, и намного лучше, чем мы, как игроки, могли бы выбрать.

Общие комментарии

Комментируя первую партию матча, отметили, что AlphaGo значительно усилилась по сравнению с октябрьским матчем против Фань Хуэя. Уже на стадии дебюта стало ясно, что программа играет на уровне лучших игроков среди людей. Сам Ли Седоль после проигрыша во второй партии заявил: «Вчера я был удивлён, но сегодня у меня нет слов». После третьего поражения Ли Седоля AlphaGo досрочно победила в матче и комментаторы сошлись на том, что остаётся надежда на одну победу человека.

В партиях со стороны программы были замечены ошибки; разработчики программы заявили, что они будут тщательно проанализированы, и что видимо AlphaGo «не знает некоторые классические тэсудзи и совершает тактические ошибки», что стало видно после проигранной ей партии, когда программа после ключевого победного хода Ли Седоля стала делать нелогичные ходы вместо того, чтобы сдаться. 

Программа показала способность к креативным решениям, что удивило многих игроков; некоторые ходы противоречили классической теории го, но в матче доказали свою эффективность, некоторые профессионалы стали использовать эти находки в своих партиях. Ли Седоль после матча решил изменить некоторые аспекты своей игры. Комментаторы во время матча сошлись на том, что AlphaGo совершала ошибки, и были уверены, что в конечном итоге ей не хватит территории для победы, но в итоге ходы, изначально казавшиеся слабыми, привели к выигрышу.

Создатели программы пояснили, что AlphaGo пытается максимизировать не количество очков или величину выигрыша, а вероятность своей победы: Если AlphaGo должна выбирать между победой в 20 очков с 80 % вероятностью или победой в 1 очко с 99 % вероятностью, она выберет последнее, даже если ради этого придётся потерять очки.

Четвертая партия 

Четвёртая партия завершилась победой Ли Седоля. По словам Демиса Хассабиса, программа сделала ошибку на 79 ходу, когда, по её собственным оценкам, вероятность её победы составляла 70 %; на 87 ходу эта величина резко упала. Дэвид Омерод охарактеризовал ходы программы с 87 по 101 как типичные ошибки для программы, работающей на основе метода Монте-Карло — поисковой механизм пытается отсечь некоторые последовательности, не относящиеся к конкретной ситуации; в некоторых случаях это может привести к тому, что программа отсекает правильные ходы и уже не может рассматривать их в дальнейшем.

В этой партии Ли Седоль выбрал стратегию амаси (территориально-ориентированный стиль, позволяющий противнику занимать ключевые пункты влияния, но при этом сам игрок получает гарантированную территорию, после чего может попытаться развалить влияние противника), решив получать территорию по сторонам, а не по центру, в противовес стратегии AlphaGo, рассчитанной на победу благодаря множеству небольших приобретений. Сделав выбор в пользу такой стратегии, Ли Седоль надеялся загнать противника в ситуацию ва-банк, что могло быть вероятным слабым местом программы, чьей силой является оценка размена; при такой ситуации способность AlphaGo к выявлению мельчайших преимуществ не оказывала бы сильного влияние на вероятность победы.

Немного анализа

Ли Седоль начинал с домашних заготовок, призванных выбить AlphaGo из колеи известных партий. Уже после семи ходов у игры не оказывалось аналогов в базе профессиональных партий. Седоль, очевидно, применил такую стратегию для того, чтобы компьютер думал самостоятельно и не мог бы скопировать ходы других профи. Это одно из преимуществ Го перед, например, шахматами, где всё на пол-игры расписано в справочниках.

Поначалу AlphaGo отвечала на эту стратегию консервативно, пытаясь постепенно выравнивать стратегического преимущество. Дальше программа несколько раз сыграла пассивно, многие поверили, что Ли Седоль впереди. Это в один голос утверждали все комментаторы матча, корейские и японские профессионалы го. И тут, когда казалось, что человек легко победит, последовал сильнейший удар, вторжение в огороженную зону Ли Седоля, которую он уже считал своей территорией. Партия длилась 186 ходов, но решилась она именно этим одним единственным ударом.

Никто не ожидал такого удара, ни сам Ли Седоль, ни комментаторы матча. Получилось что-то сродни тому, как бывает у высших профессионалов в боксе: компьютер не показывал ничего особенного, защищался, играл пассивно. Но стоило человеку чуть-чуть расслабиться, как последовал удар и партию было уже не спасти. Редко такое бывает. Иногда можно допустить с десяток ошибок и выиграть партию. А тут один красивый ход все решил. Ли Седоль был удивлен — он явно этого не ожидал и дальше просто не смог оправиться от шока.

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

Го, как и шахматы, шашки, нарды, и многие другие игры относится к играм с открытой информацией. Это значит, что оба игрока знают все о своей позиции и вариантах ходов, которые им доступны. В такой игре можно ввести функцию, которая для любой позиции на доске s возвращает оптимальный ход для игрока при условии оптимальной игры всех сторон. Иметь такую функцию v*(s) значит, собственно, математически решить игру (найти глобальный оптимум).

Создать ее, казалось бы, несложно: достаточно перебрать все дерево вариантов, которое доступно игрокам. Но проблема, естественно, в том, что в приличных играх вариантов развития событий слишком много для простого перебора. И го здесь занимает особо почетное место: число допустимых комбинаций камней на гобане (доске для игры в го) значительно превышает шахматный аналог. Так что надеяться получить истинное значение функции v*(s) для го — сейчас или в каком-то отдаленном прекрасном будущем — бесполезно.

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

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

Как реально решают все эти проблемы создатели современных алгоритмов? До сих пор главным подходом к созданию игровых алгоритмов в играх, где открыта информация но невозможен исчерпывающий перебор, были так называемые методы иерархического поиска Монте-Карло. Работают они следующим образом. Представьте, что вы переехали в новый город и хотите выбрать для себя хороший книжный. Вы заходите в один случайно выбранный магазин, подходите к случайной полке, берете случайную книгу, открываете на случайном месте и читаете, что вам попалось на глаза. Если это хороший текст, магазин в ваших глазах получает плюс к карме, если нет — минус. Таким образом вы проводите несколько забегов. Постепено становится понятно, какой из книжных вам больше подходит.

Методы иерархического поиска Монте-Карло работают по такому же принципу: из данной позиции s проводится симуляция игры до самого победного (или проигрышного — это уж как повезет) конца, причем каждый ход на каждом шаге игры выбирается случайным образом. Таким образом, проведя множество случайных симуляций можно грубо оценить выгодность позиции без исчерпывающего перебора. Оценочная функция v(s), полученная таким перебором, асимптотически приближается к истинной v*(s) полного перебора. И лучшие на сегодняшний день программы го основаны именно на таком подходе. Играют они довольно хорошо для любителя, но на профессиональный уровень ни одна из них до сих пор не вышла. Удалось это только AlphaGo, которая устроена принципиально иначе.

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

Интересно, что гибридность AlphaGo разные комментаторы интерпретируют очень по-разному. Либо как очередную убедительную победу нейросетей и глубокого обучения над традиционным формальным подходом к искусственному интеллекту. Либо, наоборот, как признак ограниченности «чистых» нейросетей (последняя точка зрения интересно изложена здесь).

Действительно, последняя громкая победа глубокого обучения в играх, к которой, к слову, также приложил руку Демис Хассабис, была связана с использованием «чистых» нейростей. Речь идет о создании системы ИИ, которая смогла научиться играть в игры ATARI без использования каких-либо инструкций или сложной ручной настройки. Тогда в качестве данных для обучения программа получала только изображение игрового монитора и результат игры: победа или проигрыш. Имея эти данные, программа могла управлять игрой, например, нажимать на рычаги в пинболе. Оказалось, что длительное обучение с подкреплением без какого-либо вмешательства человека может вывести ИИ в подобной игре на уровень человека или даже выше.

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

Как была получена эта архитектура? Инженеры Deepmind начали с создания нейросети для предсказания наиболее вероятного хода на основе базы сыгранных партий человек-против-человека. Это сверточная нейросеть из 13 слоев, очень похожая на те, которые используются для анализа изображения и распознавания символов. Вводные данные для нее, это, фактически, просто картинка положения камней на доске — 19 на 19 пикселей. «Сверточная» в применении к нейросети означает, что в ней используется математическая операция свертки при переходе от слоя к слою, то есть на каждом уровне по полному изображению пробегает маленькое окно, видимое в котором передается на следующий «нейрон» нейросети.

Главное преимущество нейросетей заключается в том, что они позволяют достигать очень высоких уровней абстракции, вычленяя из изображений их, как бы сказать… чисто абстрактные черты. Например, если нейросеть обучена распознаванию котиков, то в ее первый слой просто загружается изображение, а последующие слои обрабатывают его примерно так: второй распознает контрастность пикселей, третий наличие линий, четвертый их ориентацию, пятый мохнатость, шестой «ушастость», а седьмой и последний — «кóтовость». Важно понимать, что это очень условное представление о нейросетях — никто их заранее не программирует и не знает, что и как распознает данный слой. Как раз наоборот: все это происходит само собой по мере обучения. Суть аналогии в том, что уровень абстрактности очень сильно растет по мере движения от нижних к верхним слоям.

Так вот, на первом этапе в Deepmind создали нейросеть, которая просто предсказывает наиболее вероятный ход, который сделал бы человек из данной позиции s. Результат ее работы это, фактически, поле для го с расставленными вероятностными коэффициентами. Эта нейросеть затем была использована для того, чтобы играть против себя самой, совершенствуясь по мере обучения. Здесь был использован классический метод обучения с подкреплением: шаги, которые вели к победе, поощрялись и сеть уже не предсказывала поведение игрока-человека, а предсказывала то, какой ход чаще ведет к победе.    

На последнем этапе в Deepmind собрали так называемую оценочную сеть, задачей которой было численно оценить выгодность той или иной позиции на доске — то есть ответить на вопрос, насколько вероятно, что игрок выиграет, если сделает ход, приводящий к такой позиции. Результат ее работы представлял собой уже не поле с весами выгодных ходов, а единственный параметр — вероятность выигрыша.

Но думать, что теперь, с созданием AlphaGo, эволюция программ остановится, а «вопрос го» будет закрыт — неправильно. Отступление от полного перебора означает, что мы отказываемся от покорения игры. Программа может научиться играть хорошо, но она не будет знать точное решение в любой возможной позиции, а значит, теоретически, ее можно будет обыграть.    

Это открывает простор для соревнования между алгоритмами, которые со временем могут становиться все совершеннее, но при этом, в отличие от случая шашек, не смогут достичь абсолютного совершенства. 

 

Обсудить у себя 0
Комментарии (0)
Чтобы комментировать надо зарегистрироваться или если вы уже регистрировались войти в свой аккаунт.

Войти через социальные сети:

Сахаров Денис
Сахаров Денис
сейчас на сайте
Читателей: 21 Опыт: 786.781 Карма: 6.74063
все 22 Мои друзья