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

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

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

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

В один прекрасный момент Мэтью Лаи пригласили работать в DeepMind, и он прекратил работу над Giraffe. В итоге он стал заниматься проектом AlphaZero, то есть, по сути, развитием того подхода, который изначально был предложен в Giraffe. Основное отличие нового подхода (AlphaZero) заключается в том, что, во-первых, Giraffe в качестве переборного алгоритма использовал классические методы — поиск основных вариаций (principle variation search, наследник альфа-бета перебора). Нейронная сеть использовалась только для оценки позиций, а в AlphaZero для перебора используется тот же самый алгоритм, который используется в AlphaGo, это метод Монте-Карло (Monte-Carlo Tree Search https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9C%D0%BE%D0%BD%D1%82%D0%B5-%D0%9A%D0%B0%D1%80%D0%BB%D0%BE). При этом этот перебор тоже управляется нейронной сетью, в отличие от Giraffe. Это радикальное архитектурное отличие AlphaZero.

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

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

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

<Рисунок 1> — график сравнения

<Рисунок 2> — статистика по играм

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

Tensor Processing Unit, TPU, — это специализированные процессоры для нейронных сетей, разработкой которых занимается Google. Сейчас получить к ним доступ можно только в облаке, то есть, это такое очень специальное оборудование.

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

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

Чтобы сэкономить время, шахматные программы в таких узлах не останавливаются, а переходят на сокращённый перебор, в котором рассматриваются только некоторые взятия, некоторые проведения пешек, некоторые шахи. Это «похудевшее» дерево перебора называется «форсированный вариант». Если мы говорим, что мы перебираем все варианты на два полухода, то мы перебираем не на два, а дальше, так как мы что-то пропускаем, а в нижних узлах дерева перебираем ещё сколько-то вариантов. То есть, даже глубина в два полухода тоже не фиксированная. А есть определённые алгоритмы, которые в каждом узле могут принять решение о том, чтобы глубину перебора для данного конкретного узла увеличить или уменьшить на один полуход, например, если произошёл шах.

Дальше появляется куча эвристик (следующих из шахматного опыта советов или правил, основанных на эмпирике игры), которые влияют на реальную глубину перебора в каждом узле. Параметры эвристики как-то подстраиваются, они управляют глубиной перебора в каждом конкретном узле. При этом разные программы будут использовать разные эвристики, будут по-разному считать эти узлы. Это известная старая проблема. Даже программы, у которых алгоритмы перебора очень похожи, могут в качестве выходных данных выводить сильно отличающиеся по количеству узлов (nps) в секунду показатели. Например, есть программа Rybka, которая показывает очень низкий nps, потому что в ней считаются в качестве узлов только некоторые узлы.

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

Стиль игры AlphaZero больше похож на «человеческий» — правда или нет?

«Человеческий» стиль — представление субъективное, так как у каждого есть своё понимание того, «как играли бы люди». Так, если дать сравнить шахматисту две партии и сказать, что одну из них играла машина, а другую — шахматные мастера, то человек, скорее всего, будет ошибаться в 50% случаев. У кого-то есть предубеждение, что машины играют плохо и некрасиво, а кто-то считает, что, наоборот, компьютеры играют лучше и красивее. Или, например, считается, что шахматный движок не будет жертвовать фигуры ради «сомнительных инициатив». Но то, что с точки зрения человека — «сомнительная инициатива», с точки зрения компьютера может быть просчитанной стратегией. Николай Власов, международный мастер по шахматам, в комментарии к одной из игр AlphaZero VSStockfish 8 говорит:

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

То есть, и машина может играть по-людски, и человек — в манере компьютера. Всё, как всегда, зависит от перспективы.

Подготовка материала

Александра «Renoire» Алексеева