Го: речь поражения

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

Матч

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

Впрочем, не для всех такой результат оказался столь уж неожиданным. Судя по всему, в Google предчувствовали победу: посмотреть на игру приехали не только непосредственные авторы 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 и оценки методом Монте-Карло. Для того чтобы принять решение, алгоритм сложным образом складывает их независимые оценки. 

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

После го

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

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

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

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

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

Александр Ершов