Игры роботов: последняя открытая игра пала под натиском искусственного интеллекта

9 марта начался матч между программой AlphaGo и одним из сильнейших игроков планеты, Ли Седолем. Еще месяц назад Седоль был совершенно уверен в своей победе, но проиграл программе в первом же раунде — неожиданно и для себя, и для наблюдавших за матчем других профессиональных игроков. На следующий день он сдал и вторую игру. Чем закончится вся серия игр, станет известно на следующей неделе. Пока же N+1 рассказывает, как устроена система машинного обучения AlphaGo и что об этой истории думают эксперты — профессиональные игроки в го и специалисты по теории игр.
Матч
«Я был уверен, что у нас есть хотя бы 10 лет в запасе. Еще пару месяцев назад мы играли с программами на форе в четыре камня — это примерно как фора в ладью в шахматах. И тут — бац! — сразу Ли Седоль повержен» — так описывает свои впечатления от матча один из самых сильных российских игроков, семикратный чемпион Европы по игре го Александр Динерштейн. «Я прогнозировал счет 5-0 в пользу Ли Седоля. И многие ведущие профессионалы были согласны с этой оценкой. Сейчас все в шоке, никто не знает, что будет».
Впрочем, не для всех такой результат оказался столь неожиданным. Судя по всему, в Google предчувствовали победу: посмотреть на игру приехали не только непосредственные авторы AlphaGo, но и топы компании — один из ключевых инженеров Джеф Дин и сам Эрик Шмидт. Корея, где игра го традиционно популярнее, чем где бы то ни было, встречала создателей алгоритма первыми полосами газет и сюжетами на телевидении.
Все профессиональные комментаторы сходятся в том, что первая игра прошла очень необычно и сильно отличалась о того, что AlphaGo демонстрировала в матче с Фань Хуэем. Среди ценителей го Ли Седоль славится активной, даже агрессивной манерой игры, которой обычно не хватает компьютерам (или так о них принято думать). И в этом матче он в полной мере пытался реализовать это свое преимущество.
Ли Седоль начал с домашней заготовки, призванной выбить AlphaGo из колеи известных партий. «Уже после семи ходов у игры не оказалось аналогов в базе профессиональных партий, — поясняет Динерштейн. —Седоль, очевидно, применил такую стратегию для того, чтобы AlphaGo думал самостоятельно и не мог скопировать ходы других профи. Это одно из преимуществ го, например, перед шахматами, где все на пол-игры расписано в справочниках».
Поначалу AlphaGo отвечала на эту стратегию консервативно, пытаясь постепенно выравнивать стратегического преимущество. «Дальше программа несколько раз сыграла пассивно, многие поверили, что Ли Седоль впереди. Это в один голос утверждали все комментаторы матча, корейские и японские профессионалы го. И тут, когда казалось, что человек легко победит, последовал сильнейший удар, вторжение в огороженную зону Ли Седоля, которую он уже считал своей территорией. Партия длилась 186 ходов, но решилась она именно этим одним единственным ударом», — поясняет Александр Динерштейн.
Речь идет о ходе номер 102 (всю партию можно просмотреть здесь). Александр Динерштейн особо подчеркивает, что никто не ожидал такого удара, ни сам Ли Седоль, ни комментаторы матча: «Получилось что-то сродни тому, как бывает у высших профессионалов в боксе: компьютер не показывал ничего особенного, защищался, играл пассивно. Но стоило человеку чуть-чуть расслабиться, как последовал удар, и партию было уже не спасти. Редко такое бывает. Иногда можно допустить с десяток ошибок и выиграть партию. А тут один красивый ход все решил. Ли Седоль был удивлен: он явно этого не ожидал и дальше просто не смог оправиться от шока».
Важно отметить, что речь не идет о «зевке» — случайной ошибке, допущенной человеком по невнимательности. Все сходятся в том, что партия была выиграна «по делу» и силы в матче равны. Если раньше Ли Седоль безоговорочно верил в свою победу со счетом 5-0 (ну от силы 4-1), то после первой партии он признался, что сейчас его шансы не более чем 50 на 50.
Вторая партия также завершилась поражением корейца. После нее даже «50 на 50» выглядят чересчур оптимистично: «Я видел сотни партий Ли Седоля, но не помню, чтобы он так совсем без шансов проигрывал. В обеих партиях, получив плохую позицию, он не смог ее даже обострить, хотя умение вытаскивать тяжелые позиции — это его конек». Что касается программы, то впечатления чемпиона Европы однозначны:
«Сегодня стало понятно, что у AlphaGo нет слабых мест, это просто монстр какой-то».
О том, что будет к концу матча, наш собеседник предсказать отказывается. «Сейчас игроки всего мира, безусловно, болеют за Ли. Может быть за очень редким исключением. Все-таки быть последней непобежденной игрой — это очень дорогого стоит. Многие приходили в го, как раз зная, что это последняя игра с полной информацией, в которой компьютеры не считались серьезными соперниками. У нас даже правила касательно электроники во время матча довольно расслабленные: всем понятно, что на высоком уровне компьютер играть в го не может, искать у него подсказки глупо. Если Ли проиграет, все это сильно изменится. Но история с DeepBlue в шахматах растянулась на несколько лет, так что у нас, я думаю, еще есть надежда», — неуверенно резюмирует Александр Динерштейн.
Обрезка и прополка
Чтобы объяснить, как команде Демиса Хассабиса, создавшей AlphaGo, удалось добиться такого впечатляющего результата, придется немного погрузится в теорию игр.
Го, как и шахматы, шашки, нарды и многие другие игры относится к играм с открытой информацией. Это значит, что оба игрока знают все о своей позиции и вариантах ходов, которые им доступны. В такой игре можно ввести функцию, которая для любой позиции на доске s возвращает оптимальный ход для игрока при условии оптимальной игры всех сторон. Иметь такую функцию v*(s) значит, собственно, математически «решить» игру (найти глобальный оптимум).
Мнения 22.08.2015 02:01Чувствительные роботы: что может машина, обладающая зрением и слухом
Органы чувств все активнее внедряются в системы искусственного интеллекта...
Сделать ее, казалось бы, несложно: достаточно перебрать все дерево вариантов, которое доступно игрокам. Но проблема, конечно же, в том, что в приличных играх вариантов развития событий слишком много для простого перебора. И го здесь занимает особо почетное место: число допустимых комбинаций камней на гобане (доске для игры в го) превышает число атомов во Вселенной. Так что надеяться получить истинное значение функции v*(s) для го — сейчас или в каком-то отдаленном будущем — бесполезно.
Однако задолго до того, как появились DeepBlue, AlphaGo и другие сильные алгоритмы, математики придумали несколько остроумных методов замены «настоящей» функции v*(s) на ее приблизительный аналог v(s) ≈ v*(s), который можно вычислить уже за какое-то разумное время.
Один из самых очевидных и простых способов решения этой задачи — подрезка «хилых» ветвей у дерева перебора. Он основан на том, что в игре обычно существуют позиции, которые «очевидно плохие» или «очевидно хорошие». Например, какая-то терминальная позиция в шахматах может еще не быть матом, но уже настолько плохой, что ни один игрок не найдет разумным ее доигрывать. Достижение такой позиции уже можно считать проигрышем не в даваясь в детали того, как именно он произойдет, если доводить игру до конца. Такой подход, в котором ветви дерева вариантов подрезаются и заменяются средними значениями их исходов, позволяет сократить глубину перебора.
Другие подходы основаны на сокращении ширины перебора, то есть на уменьшении числа вариантов ходов из всех разрешенных до некоторого набора популярных — на основе баз известных партий. Понятно, что такой подход позволяет существенно сократить число вариантов развития событий и, соответственно, время вычислений. Но он же делает поведение программы стереотипным, консервативным и предсказуемым — то есть как раз придает те качества, которыми известны слабые алгоритмы. В таком подходе программа фактически не пытается выиграть, а пытается угадать, как в похожей ситуации поступал игрок, матч которого она помнит. Для го, где широта возможностей велика как нигде, данная конкретная партия может стать совершенно уникальной уже за несколько ходов, и программе просто не на что будет опереться в выборе. Эту проблему можно решать, если рассматривать не доску целиком, а локальную ситуацию в отдельном фрагмента доски, где вариантов меньше, но проблемы со стереотипностью те же.
Страницы12