Го: речь поражения
Последняя открытая игра пала под натиском искусственного интеллекта
The New York Public Library

Вчера утром начался матч между программой AlphaGo и одним из сильнейших игроков планеты, Ли Седолем. Еще месяц назад Седоль был совершенно уверен в своей победе, но проиграл программе в первом же раунде — неожиданно и для себя, и для наблюдавших за матчем других профессиональных игроков. Сегодня он сдал и вторую игру. Чем закончится вся серия игр, станет известно на следующей неделе. Пока же мы решили рассказать о том, как устроена система машинного обучения AlphaGo и что об этой истории думают эксперты: как профессиональные игроки в го, так и специалисты по теории игр.

Матч

«Я был уверен, что у нас есть хотя бы 10 лет в запасе. Еще пару месяцев назад мы играли с программами на форе в четыре камня — это примерно как фора в ладью в шахматах. И тут — бац! — и сразу Ли Седоль повержен» — так описывает свои впечатления от матча один из самых сильных российских игроков, 7-кратный чемпион Европы по игре го Александр Динерштейн. «Я прогнозировал счет 5-0 в пользу Ли Седоля. И многие ведущие профессионалы были согласны с этой оценкой. Сейчас все в шоке, никто не знает, что будет».

Впрочем, не для всех такой результат оказался столь уж неожиданным. Судя по всему, в Google предчувствовали победу: посмотреть на игру приехали не только непосредственные авторы AlphaGo, но и топы компании — один из ключевых инженеров Джеф Дин и сам Эрик Шмидт. Корея, где игра Го традиционно популярнее, чем где бы то ни было, встречала создателей алгоритма первыми полосами газет и сюжетами на телевидении.

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

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

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

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

Важно отметить, что речь не идет о «зевке» — случайной ошибке, допущенной человеком по невнимательности. Все сходятся в том, что партия была выиграна «по делу» и силы в матче равны. Если раньше Ли Седоль безоговорочно верил в свою победу со счетом 5-0 (ну от силы 4-1), то после первой партии он признался, что сейчас его шансы не более чем 50 на 50.

Вторая, сегодняшняя партия, также завершилась поражением корейца. После нее даже «50 на 50» выглядят чересчур оптимистично: «Я видел сотни партий Ли Седоля, но не помню, чтобы он так совсем без шансов проигрывал. В обеих партиях, получив плохую позицию, он не смог ее даже обострить, хотя умение вытаскивать тяжелые позиции — это его конек». Что касается программы, то впечатления чемпиона Европы однозначны: «Сегодня стало понятно, что у AlphaGo нет слабых мест, это просто монстр какой-то».

О том, что будет к концу матча, наш собеседник представить отказывается. «Сейчас игроки всего мира, безусловно, болеют за Ли. Может быть за очень редким исключением. Все-таки быть последней непобежденной игрой — это очень дорогого стоит. Многие приходили в го как раз зная, что это последняя игра с полной информацией, в которой компьютеры не считались серьезными соперниками. У нас даже правила касательно электроники во время матча довольно расслабленные: всем понятно, что на высоком уровне компьютер играть в го не может, искать у него подсказки глупо. Если Ли проиграет, все это сильно изменится. Но история с DeepBlue в шахматах растянулась на несколько лет, так что у нас, я думаю, еще есть надежда» — неуверенно резюмирует Александр Динерштейн.

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

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

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

Однако задолгодо того, как появились DeepBlue, AlphaGo и другие сильные алгоритмы, математики придумали несколько остроумных методов замены «настоящей» функции v*(s) на ее приблизительный аналог v(s) ? v*(s), который можно вычислить уже за какое-то разумное время.

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

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

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

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

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

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

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

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

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

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

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

Среднеквадратичная ошибка разных методов оценки успешности партии. У всех их она ожидаемо падает с ходом партии. Видно, что оценочная сесть гораздо точнее, чем случайный вариант метода Монте-Карло.

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

Фактически, оценочная сеть была призвана заменить поиск веса позиции методом Монте-Карло, который применяется в других программах Го. И, если бы эта нейросеть была совершенной, то есть выдаваемое ей значение v(s) приближалось к истинному v*(s), то одной ее было бы достаточно для победы над любым противником. Но это оказалось не так.

Из графиков, которые приводит команда Deepmind видно, что «чистая нейросеть», хотя и обыгрывает «чистый Монте-Карло», все же играет на уровне хорошего любителя. Профессионального уровня удается достичь только тогда, когда одновременно используется и оценочная сеть, и «предсказательная» сеть RL и оценки методом Монте-Карло. Для того, чтобы принять решение, алгоритм сложным образом складывает их независимые оценки. В скобках отметим, что успешность того или иного подхода сильно зависит от времени, которое согласно текущим правилам имеется в распоряжении играющих: понятно, что чем больше времени на вычисления, тем точнее методы Монте-Карло и ниже необходимость в «быстрых-и-грязных» методах вроде тактической сети.

The New York Public Library
После го

В играх с совершенной информацией го всегда считалась самой сложной игрой. И выход программ на «нечеловеческий» уровень, безусловно, маркирует какой-то качественный переход во всей области исследований искусственного интеллекта. Ушла эпоха — не иначе.

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

Уровень игры различных алгоритмов и игроков го. На правой части диаграммы видно, что сама по себе оценочная сеть играет существенно хуже, чем в сочетании с RL-сетью и методом Монте-Карло.

Это открывает простор для соревнования между алгоритмами, которые со временем могут становится все совершеннее, но при этом, в отличие от случая шашек, не смогут в обозримом будущем достичь абсолютного совершенства: «DeepBlue умеет определять, что такое неудачный ход, ориентируясь на много ходов вперед, в отличие от человека. Значит, любая ошибка человека, которую можно зафиксировать на расстоянии просчета компьютера, будет мгновенно им использована. Однако если, например, DeepBlue считает на 20 ходов, то нельзя исключать, что бывают ошибки, которые можно обнаружить только просчитав все на 25 ходов. Когда появится программа, умеющая это делать, она сможет обыгрывать DeepBlue» – объясняет Дмитрий Дагаев. Впрочем, все это будет интересно уже не для живых игроков, а для архитекторов и создателей программ новых поколений.

Для тех же, кто не желает участвовать в этой гонке и вообще отказывается играть на поле, где компьютеры сильнее, есть и хорошие новости. Это существование игр с несовершенной информацией, где проявить себя компьютеру будет гораздо труднее: «Любую конечную игру с совершенной информацией понятно как решать — запускаем алгоритм обратной индукции и все. На каждой подыгре находим наилучший ход и при дальнейших рассчетах ориентируемся только на него (рациональному игроку незачем делать неоптимальные ходы). В играх с несовершенной информацией так не получится: когда мы дойдем до ситуации, в которой игрок не будет однозначно понимать текущую позицию, мы не сможем однозначно определить его наилучший ход. Значит, дальше нам тоже придется учитывать несколько вариантов развития ситуации. Рост неопределенности приведет к резкому росту вычислительной сложности» — обнадеживает Дмитрий.

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

The New York Public Library
Александр Ершов