AlphaZero — не совсем сенсация, но точно шаг вперёд

Шахматы были важной частью культуры прошлого столетия (можно вспомнить набоковскую «Защиту Лужина», турнир, устроенный Остапом Бендером в Васюках, и ещё множество шахматных эпизодов из литературы и кино). Поэтому сейчас может показаться, что это игра из прошлого: мы играем в другие «настолочки», а в шахматы «режутся» старики в парках. Однако и сегодня шахматное событие может взбудоражить общественность; правда, нынешние громкие шахматные новости чаще всего связаны со сферой искусственного интеллекта. Так, на днях в СМИ прогремело: алгоритм AlphaZero, основанный на нейронных сетях, обыграл шахматный движок Stockfish, который занял первое место на чемпионате шахматных движков TCEC (Top Chess Engine Championship) в 2016-м году.

Со стороны IT

О том, что значит победа AlphaZero над Stockfish, рассказывает эксперт в области машинного обучения и специалист по шахматным программам Сергей Марков:

История применения глубоких нейронных сетей в шахматных движках (а именно это отличает AlphaZero от большинства других таких движков) началась несколько лет назад, когда Мэтью Лай (Matthew Lai) создал программу Giraffe, в которой использовал подход, называемый обучением с подкреплением (reinforcement learning, это когда система обучается сама, сталкиваясь с окружающей средой).

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

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

В один прекрасный момент Мэтью Лая пригласили работать в DeepMind, и он прекратил работу над Giraffe. В итоге он стал заниматься проектом AlphaZero, то есть, по сути, развитием того подхода, который изначально был предложен в Giraffe. Основное отличие нового подхода (AlphaZero) заключается в том, что, во-первых, Giraffe в качестве переборного алгоритма использовал классические методы — поиск c основным вариантом (Principal variation search, наследник альфа-бета перебора). Нейронная сеть использовалась только для оценки позиций, а в AlphaZero для перебора используется тот же самый алгоритм, который используется в AlphaGo, это метод Монте-Карло поиска по дереву (Monte Carlo tree search). При этом этот перебор тоже управляется нейронной сетью, в отличие от Giraffe. Это радикальное архитектурное отличие AlphaZero.

AlphaZero позиционируется как универсальный фреймворк для разных и до какой-то степени непохожих настольных игр. Благодаря тому, что программная часть, которая описывает правила игры, вынесена в независимый модуль, а сам алгоритм обучения является общим для всех этих игр, алгоритм показывает результаты и на го, и на сёги, и на шахматах. При этом эти игры довольно разные — у них разный размер доски, разные коэффициенты ветвления (branching factor, сколько возможных ходов можно сделать в определённой позиции на игровой доске). Шахматы — это пример игры со сравнительно небольшим коэффициентом ветвления по сравнению с го и с сёги. И доска меньше в шахматах, чем в го. Кроме того, для шахмат и до этого были известны способы сравнительно простой, но надёжной оценки позиций, в отличие от го.

Я уверен, что пресса будет говорить, что AlphaZero — это очередная революция, но есть несколько «но»:

1. Если посмотреть на графики обучения (рис. 1), видно, что разница в силе игры между AlphaZero и Stockfish (даже несмотря на разгромный счёт, см. рис. 2) — не так уж велика. Тем более что Stockfish играл без дебютной библиотеки.

2. Когда кто-то говорит, что AlphaZero за четыре часа научилась обыгрывать Stockfish, упускается из виду тот факт, что в демонстрационном матче две программы играли на совсем разном оборудовании. Stockfish работал на обычном CPU, правда на 64-ядерном, а AlphaZero — на 4-х тензорных процессорах. А при обучении AlphaZero вообще было задействовано 5000 TPU первой версии и 64 TPU версии 2.

Эти процессоры трудно сравнить напрямую — у них разная архитектура. Если сравнить их «в лоб» (такое сравнение всё равно будет не совсем корректным), скажем, взять производительность во flops (количество операций с плавающей запятой в секунду), то оборудование AlphaZero (4 TPU) оказывается на два порядка более мощным, чем 64-ядерный CPU, 180×4 Tflops VS 3 Tflops (https://www.ixbt.com/news/2016/06/21/xeon-phi-knights-landing.html, https://www.eetimes.com/document.asp?doc_id=1331753). Это, получается то же самое, как если бы мы запустили Stockfish играть против самого себя, но на гораздо более мощном оборудовании. Но это просто невозможно: у нас нет таких многоядерных процессоров, чтобы они сравнялись с TPU по мощности. Да и Stockfish не предназначен для другой архитектуры, поэтому сравнить программы на равных вычислительных мощностях — не получится.

3. Сторонники «сенсации» могут привести ещё один аргумент: заявленная скорость перебора была у AlphaZero существенно ниже, чем у Stockfish. AlphaZero просматривал только 80 тысяч позиций в секунду (node per second, nps; формально говоря речь идёт об узлах переборного дерева в секунду, но каждый узел такого дерева это шахматная позиция), а Stockfish — 70 миллионов. В этом сравнении много лукавства, потому что разные шахматные программы по-разному считают просматриваемые позиции. Генератор ходов в шахматной программе генерирует список возможных ходов. При этом не всегда генерируются все возможные ходы, в некоторых узлах дерева может осуществляться сокращённая генерация — например, генерируются только взятия фигур и шахи. Другие ходы отсеиваются уже после генерации — в результате действия различных эвристик. Включать или не включать отсеянные узлы в подсчёт количества узлов? Общей практики не существует. Даже если ход не был отсеян, для получившейся в результате его совершения позиции может быть вызвана оценочная функция, а может быть и не вызвана. Если оценочная функция вызвана, то может происходить сокращённая оценка (lazy evaluation). Шахматные программы обычно используют алгоритм постепенного итеративного углубления (internal iterative deepening). Вначале перебираются все варианты на один полуход (полуход — это когда сделали ход только чёрные или только белые; ход — когда обе стороны сделали ход), потом на два полухода, потом на три, потом на четыре, и так до того момента, пока не кончится время. Однако существует важная тонкость — допустим, программа осуществляет в данный момент перебор всех вариантов на 2 полухода в глубину. Рассмотрим вариант, когда мы сделали ход фигурой, и на следующем полуходе её взял соперник. Можно подумать, что это не очень хорошо, ведь в терминальной позиции дерева ограниченного глубиной в 2 полухода, у противника будет лишняя фигура. Но если посмотреть на один полуход вперёд — возможно, окажется, что это всего лишь размен, и фигура следующим полуходом отыгрывается. Поэтому, чтобы не совершать таких грубых ошибок, шахматные программы в терминальных узлах дерева не останавливаются, а переходят на сокращённый перебор, в котором рассматриваются только некоторые взятия, некоторые проведения пешек, некоторые шахи. Это «похудевшее» дерево перебора называется «форсированный вариант». Если мы говорим, что мы перебираем все варианты на два полухода, то мы перебираем не строго на два полухода в глубину, а иногда несколько глубже.

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

В зависимости от набора и параметров применяемых эвристик, будут отличаться и способы подсчёта количества просматриваемых позиций. Это известная старая проблема. Даже программы, у которых алгоритмы перебора очень похожи, могут в качестве выходных данных выводить сильно отличающиеся по количеству позиций в секунду показатели. Например, программа Rybka, показывает очень маленькие значения nps, на порядок ниже, чем у того же Stockfish, хотя архитектурно эти программы очень похожи. В целом, и среди «классических» шахматных программ распространен подход, когда скорость перебора приносится в жертву более «осмысленной» стратегии перебора, при которой программы компенсируют потерю скорости за счёт отсечения большего количества ненужных для анализа позиций. Но такой обмен целесообразен тогда и только тогда, когда в итоге сила игры растёт при использовании идентичного оборудования.

В общем, сравнивать две программы по этой метрике — плохо, поскольку мы не знаем, что считается за узел в каждой из сравниваемых программ. Учитывая не такую большую разницу в силе игры, а также большую мощность оборудования AlphaZero, сказать однозначно, что AlphaZero сильнее Stockfish, пока сложно. Тем не менее следует признать, что AlphaZero — проект уникальный и прогрессивный. Во-первых, программ, эффективно использующих GPU или подобное оборудование для матричных вычислений до сих пор не существовало, как и сильных программ, использующих нейронные сети. Весьма вероятно, что на сегодняшний день AlphaZero — это сильнейшая в мире шахматная машина (при этом не факт, что AlphaZero является сильнейшей в мире программой). Большой шаг вперёд — это переход от перебора, управляемого множеством эвристик, придуманных людьми, к перебору, который управляется нейронной сетью. Весьма вероятно, что эвристики, придуманные людьми, содержат в себе множество дефектов, являющихся плодами предвзятости экспертов. AlphaZero — это первая ласточка. Полученные результаты не являются мегасенсацией, но это хороший шаг вперёд.

Со стороны шахмат

Одну из партий AlphaZero VS Stockfish 8 комментирует международный мастер спорта по шахматам Николай Власов:

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

Теперь, когда прошли охи-ахи и немного улеглись восторги, попробуем подумать — что это вообще было?! На что это похоже? И что с этим делать-то?
В известном варианте с жертвой пешки белые вроде бы не преуспели, но отказались от возможной ещё ничьей и после пары странно выглядящих ходов пожертвовали ещё и фигуру на 19-м ходу. Жертва на человеческий взгляд выглядит некорректной. И на взгляд Стокфиша, играющего обычно намного сильнее любого человека, тоже некорректной — иначе он её не принял бы.

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

Больше всего это похоже на недоумение пополам с восторгами, которое вызывал в своё время Таль. Он тоже часто жертвовал «не пойми за что», его соперники (люди) тоже не выдерживали напряжения, допуская в итоге необъяснимые по отдельности ошибки (но прекрасно понятные психологически в целом — после того как раз за разом приходится решать сложнейшие задачи — мозг даёт сбой). Уже в компьютерную эру внезапно выяснилось, что многие жертвы Таля были-таки вполне корректными. Просто гений (как и другие до и после него) расширял и улучшал наши представления о реальности и возможном.

Тут примерно та же картинка — только непонятно, как мог устать железный Стокфиш. Перегрелся? Усталость металла? Просто не повезло? (И так двадцать раз). Уже высказана очевидная гипотеза про неудачную конфигурацию, неудачный контроль времени и что там еще мешает плохому танцору. Хорошая гипотеза, рабочая, но как тогда он работал в очистке продержался на том же железе с тем же контролем до 34-го хода?

Как можно, отдав материал, продолжать менять оставшихся — примерно, понятно. Каждый размен уменьшал число защитников черного короля, увеличивая относительный вес оставшейся вне игры ладьи а8. И после последнего размена (ошибки на 34-м, превед Пелевину) весы резко качнулись — у белых в игре остались ферзь с ладьёй против ферзя с королём (ладья а8 и конь в8 опоздали к Ватерлоо). Удивительно, но понятно, сеанс магии с последующим разоблачением.

А вот почему АльфаЗеро раз за разом выбирал риск? Предположим, что человеческий взгляд врёт, жертва корректна и достаточна для ничьей — но почему не сделать ту ничью сразу, когда были возможности? Учитывал ли АЗ вероятность возможной ошибки соперника? Это бы многое объяснило — точно так же отказывается от ничьей в равной и даже худшей позиции человек, играющий с заведомо более слабым соперником.

Чтобы ответить на вопрос «что делать?» нужно сначала осознать где находимся. Довольно очевидно, что наше понимание ситуации и проблем, с ней связанных, крайне далеко от идеального. В такой ситуации мозг привычно подсовывает более-менее правдоподобные гипотезы (вроде бога) и пытается на них остановиться-успокоиться. Или принизить значение проблемы, чтобы пожалеть времени в ней разбираться дальше.

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

Нужно ли оно (постижение истины) современным шахматистам — бог весть, скорее нет. Интересна ли задача постижения шахмат современным учёным? Тоже скорее похоже, что неинтересна. Но пока не возьмёмся — будут рулить конспирологические гипотезы вроде «Стокфиш подставили для рекламы Гугла» или «Таль гипнотизировал своих соперников пришелец из будущего со встроенным чипом».