Этот текст был написан в марте 2016 года, когда началась серия матчей по игре го между программой AlphaGo и одним из сильнейших игроков планеты, Ли Седолем. До матча Седоль был совершенно уверен в своей победе, однако в результате проиграл со счетом 4:1. N + 1 рассказывает о том, как устроена система машинного обучения 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, которая устроена принципиально иначе.
Продолжение читайте во второй части
Александр Ершов
