О шахматах. И не только

    Сегодня не будет тяжких раздумий о настоящем и будущем компьютерной индустрии. Сегодня я хочу рассказать об одном из своих хобби. Я играю в массу разных игр: футбол, хоккей, теннис (большой и маленький), покер, преферанс, биржа и т.п. Но мой “профильный” вид спорта — шахматы. Дальше кандидата в мастера моя карьера на этом поприще не продвинулась, но любовь к древней игре я сохраняю уже 4 десятка лет. Интересно, что она вполне “ужилась” с другим увлечением – программированием, породив интерес к искусственному интеллекту и теории игр. И разумеется, последние прорывы в этой области связанные с феноменальными успехами проекта AlphaZero не могли пройти мимо меня.

    image

    Тогда я просто сидел и восхищался партиями AlphaZero против Stockfish. А сейчас вернулся к теме в связи с задачей оптимизации нейронных сетей, которой иногда приходится заниматься по работе (увы, меньше чем хотелось бы). Как мне кажется, задачи эти могут оказаться тесно связанными, поэтому захотелось как то систематизировать свои идеи.

    Шахматы – игра с полной информацией, основанная на переборе вариантов (так же как шашки, го и т.п.).

    image

    Проблема однако в том, что дерево вариантов в шахматах растет достаточно быстро (хотя и значительное медленнее, чем в го). Например, при полной доске фигур в спокойной позиции у каждой стороны есть примерно по 10 разумных продолжений. Таким образом, всего за 3 хода черных и белых (6 полуходов) мы можем получить миллион позиций из данной. Также, примем во внимание то, что средняя партия между людьми продолжается 40-50 ходов (между компьютерами ― 80-100). Таким образом, мы придем к выводу, что полный просчет дерева вариантов для большинства позиций невозможен – а значит мы должны ориентироваться на частичное обрезание дерева перебора, как по ширине, так и в глубину. А теперь давайте посмотрим, как люди и машины справлялись с этой проблемой. Начну я с небольшого исторического обзора.

    «Белковые шахматы».

    Шахматы известны порядка 1400 лет, но первые большие турниры по ним начали проводиться в середине XIX века. Это было время открытых и романтических сражений. Соперники старались побыстрее ввести в бой фигуры, вскрыть позицию и начать атаку на короля. С материальными и позиционными уступками никто особенно не считался. Но как ни удивительно, первым официальным чемпионом мира стал антагонист романтических шахмат – Вильгельм Стейниц.

    image

    Он заложил основы позиционной игры. Во многом благодаря Стейницу мы стали оперировать такими понятиями, как «пешечная структура», «сильные и слабые поля», «хорошие и плохие фигуры». Именно это и привнесло в шахматы элемент стратегии, основанной на долгосрочных преимуществах. Стейниц развивал позиционный подход и неумолимо наказывал своих противников за материальные жертвы и позиционные огрехи. О первом чемпионе очень хорошо сказал Эммануил Ласкер, сменивший его на шахматном троне: «Одаренность Стейница как практического игрока была ниже, чем одаренность Блэкберна или Цукерторта, которых он все же победил, ибо был великим мыслителем, а они – нет». Стейниц сформулировал базовые принципы оценки позиции и вытекающие из них планы игры на языке высокого уровня (в данном случае немецком).
    Соответственно, он сделал их доступными для изучения другими людьми
    . Это и сформировало то, что мы называем человеческим подходом к шахматной игре. Мы очень серьезно обрезаем дерево вариантов в шахматах, основываясь на позиционных принципах. Какие-то ходы отбрасываются потому, что ведут к плохой позиции на просчитываемом горизонте. Kакие-то ― потому что ведут к долговременным уступкам, другие ― потому что являются бесцельными. В итоге мы просчитываем совсем небольшую часть возможных вариантов.

    Дальнейшее понимание шахмат было по сути развитием идей, заложенных первым чемпионом. Появились такие понятия как блокада, профилактика, доминация. Шахматисты стали изучать принципы разыгрывания типовых позиций, возникающих из различных дебютов(замкнутые цепи, изолированная пешка и т.п.). Так или иначе, изучались позиции близкие к материальному равновесию. Но бывали и исключения – например, молодой Михаил Таль играл в ином стиле. Он создавал острые несбалансированные позиции с нарушением соотношения материала (позднее подобную игру демонстрировал и Гарри Каспаров). Не привыкшие к подобной игре противники пасовали один за другим. Таль стал чемпионом мира в 1960, но год спустя проиграл матч-реванш. Во второй половине ХХ века фокус исследования сместился в сторону начала партии – дебюта. С легкой руки Mихаила Ботвинника (6-го чемпиона мира) и Гарри Каспарова (13-го) львиную долю своего времени шахматисты стали уделять проработке конкретных дебютных вариантов. Все больше используя компьютеры в этом процессе. В результате многие варианты в популярных дебютах разработаны вплоть до позиций, где результат игры предопределен. Это приводит к определённому выхолащиванию шаxмат, а также к необходимости запоминать огромное количество вариантов, чтобы не быть разгромленным уже в дебюте. Неудивительно, что последнее время маятник качнулся в обратную сторону. Нынешний чемпион мира Магнус Карлсен скорее стремится к тому, чтобы получить по итогам дебюта не перевес, а игровую позицию, не “заезженную вдоль и поперек” компьютерными движками. Тяжесть борьбы переносится на более поздние стадии партии (миттельшпиль, эндшпиль).

    «Силиконовые шахматы».

    По меткому выражению Александра Кронрода, шахматы являются «дрозофилой» искусственного интеллекта. Их изучение началось с появлением первых компьютеров и привлекало таких пионеров как Алан Тьюринг и Клод Шеннон. Именно Шеннон выдвинул первую оценку стоимости шахматных фигур «Король =200, Ферзь =9, Ладья = 5, Слон = 3, Koнь =3, Пешка =1». Как ни странно, именно эта простая оценка определила развитие шахматного программирования на следуюшие 70 лет. Также Шеннон предугадал разделение шахматных программ на «быстрые» (brute force) и «умные» (clever). «Быстрые» программы полностью перебирают все возможные варианты на определенную глубину, оценивают позицию с помощью простой оценочной функции (вроде соотношения материала) и выбирают наилучший ход с помощью принципа минимакса. «Умные» программы используют более сложные алгоритмы и варьируют глубину перебора примерно так же, как это делает человек. Созданием подобного алгоритма в последние годы жизни занимался 6-й чемпион мира Михаил Ботвинник. Однако без особого успеха, как и многие другие создатели «умных» программ. Ибо в третьем своем предсказании Шеннон ошибся – «умные» программы постоянно терпели неудачу в борьбе с «быстрыми». Причина в том, что перебор очень хорошо параллелится и оптимизируется. А простая оценка Шеннона оказалась достаточно устойчивой и робастной. Ибо как известно шахматистам, любой позиционный перевес рано или поздно трансформируется в материальный. В то время как принципы оценки позиции поддаются формализации гораздо хуже.

    Они требуют громоздких последовательных вычислений и плохо оптимизируются. В результате с ростом производительности компьютеров «быстрые» программы стали доминировать. Так сформировался mainstream компьютерных шахмат, разительно отличающийся от человеческих – перебор на определенную глубину с использованием aльфа-бета отсечения (и еще кой-каких эвристик) и оценка позиции по Шеннону. Также программы стали активно развивать и использовать дебютные (когда игра еще не ушла далеко от начальной позиции) и эндшпильные (когда количество фигур мало и дерево вариантов может быть просчитано полностью) базы. А производительность компьютеров все время росла, и программисты тоже не сидели без дела, постоянно оптимизируя движки. 11 мая 1997 года произошло эпохальное событие компьютер Deep Blue победил чемпиона мира Гарри Каспарова в матче из 6 партий.

    image

    Сразу после этого IBM прикрыла этот ни разу не дешевый проект. Специально для Deep Blue были созданы чипы, ускоряющие шахматные расчеты! Впрочем, и без них превосходство компьютера над человеком уже было очевидным. Deep Fritz, Deep Junior, Rybka, Komodo, Stockfish стали беспощадно громить ведущих гроссмейстеров, даже давая им материал вперед… Между собой они, впрочем, играли с переменным успехом ― результаты чемпионатов мира среди программ можно найти тут.

    Все изменилось, когда создатели AlphaZero, победив чемпиона мира по игре в го Ли Седоля, взялись наконец за шахматы. Результат оказался феноменален – после 4 часов игры с самим собой AlphaZero разгромил StockFish, выиграв 28 партий и сведя вничью 72. Через год DeepMind провел более чистый эксперимент, разрешив Stockfish пользоваться дебютной и эндшпильной книгами. И все равно результат +155 -6 =839 не оставляет сомнений в том, кто является сильнейшим игроком в мире на данный момент.

    Давайте разбираться, как устроено это новое чудо. (Для желающих поковыряться в python-скриптах есть уже целая книга). Основной алгоритм – поиск по деревьям Монте Карло. Это тоже, конечно, перебор, что роднит AlphaZero c другими шахматными программами. Но слово Монте Карло не должно вводить в заблуждение – поиск управляется нейронной сетью (для го была 80-слойная, здесь не знаю какая) и является узконаправленным. АlphaZero обрезает дерево перебора, исходя из позиционных соображений, так же как это делает человек! По сравнению со Stockfish Alphazero перебирает в почти в 1000 раз меньше вариантов. Она лопатит гораздо меньше «мусора», но наиболее вероятные сильнейшие варианты просчитывает глубже и точнее. Поэтому выигрывает даже имея меньше времени или на более слабом железе. Ну и самое главное – АlphaZero «изучала» шахматы исключительно на «собственном опыте». У нее не было никакой априорной информации. Ее “понимание” не испорчено «Шенноновской оценкой». У неё своё уникальное понимание видение шахмат и стиль игры, зачастую игнорирующий материальное соотношение (как молодой Таль!).

    Какие выводы мы можем сделать из этого замечательного эксперимента?

    1. Он решительно опровергает все соображения о выхолащивании шахмат. Самое появление игрока, который играет в невиданном до сих пор стиле и демонстрирует тотальное превосходство над конкурентами свидетельствует о том, что возможности игры еще далеко не исчерпаны.
    2. Показывает насколько мало все же мы знаем о шахматах. За 4 часа тренировки искусственный интеллект сумел понять об игре много больше чем мы («тупые белковые») за полторы тысячи лет! Пытаясь как то осознать этот феномен я нашел такую аналогию – наше знание о шахматах похоже на разложение функции в степенной ряд (типа Тейлора-Маклорена) вблизи нуля. Где нулевой точкой является материальное равновесие. Применимость такого представления падает по мере удаления от материального равенства. В то время как AlphaZero видит всю картину(функцию) целиком.
    3. Ставит главный вопрос – что же дальше? Конечно можно идти экстенсивным путем – увеличивая время тренировки, используя все более мощное железо, оптимизируя софт и т.п. Но мне кажется, что гораздо важнее другое направление. Для AlphaZero – натренированная нейронная сетка – это все лишь набор чисел –коэффициентов. Как мы можем извлечь из этого набора чисел новое знание об игре? В каком то смысле мы должны решить задачу, сродни той, которую решил Стейниц полтора века назад. Описать знание об игре, используя человеческий язык. И сделать его доступным для изучения другими людьми. Это именно то с чем я столкнулся при оптимизации нейронных сеток и называю обратной задачей искусственного интеллекта. А решать ее нам придется во многих областях. И если мы не сумеем призрак SkyNet станет чуть менее далеким и чуть более зловещим… Ну а пока я был бы благодарен за ссылки, статьи и идеи как подступиться к этой проблеме.

    PS. А партии вы все же посмотрите. Я получил ни с чем не сравнимое удовольствие.
    Huawei
    Huawei – мировой лидер в области ИКТ

    Комментарии 42

      +5
      С момента AlphaZero в компьютерных шахматах появилось много интересных вещей.

      1. Во первых это Leela Chess. Это открытая реализация нейросетевого подхода AlphaZero, активно развивающаяся, с большим количеством вариантов сетей.

      И если смотреть по результатам компьютерного чемпионата TCEC она действительно сумела обыграть StockFish, но в последние два раза StockFish взял убедительный реванш. Так что на данном этапе StockFish пока превосходит нейросетки по типу AlphaZero.

      2. Но совсем недавно появилась новая архитектура нейронной сети, работающая только на CPU. Она называется NNUE. Она позволяет улучшить alpha-beta отсечение с использованием нейросетевой оценки. Она работает только на CPU, так как копировать данные между CPU и GPU слишком накладно. Судя по последним данным, такой гибридный подход радикально усилил силу игры, почти на 100 ELO NNUE evaluation, что для текущих компьютерных шахмат серьезный прорыв.

      Вот такая гибридная арихектура на CPU пока самая сильная на данный момент времени.

      Вот график прироста ELO с использованием NNUE

      image
        +3
        Ага. На NNUE я смотрел — ибо иногда поглядываю на исходники Stockfish. Вообще, конечно, классно, что в любимой игре (и движках :) ) появилось столько новых идей в последнее время. Меня однако волнует вопрос, как мы «белковые» можем извлечь из этого какую то полезную информацию для себя. Как нам самим научиться лучше играть?
          +6
          У меня тут есть несколько соображений.

          1. Я не вижу в нейросетях чего-либо революционного. Это обычный эволюционный процесс накопления знаний и повышения эффективности обработки информации. Появление письменности, книгопечатание, библиотеки книг, библиотечные каталоги, регулярная научная периодика, онлайн каталоги + поиск, нейросети, и т.п. Это просто звенья одной цепи. В нашей временной перспективе это кажется прорывом. Но если так подумать, то гораздо большим прорывом в свое время была концепция публикации научных знаний в журналах, доступных всем.

          2. В очень многих ситуациях человек просто не может постичь всю глубину шахмат. Вот простейшие примеры из 7-фигурной базы. Не считая королей, всего 5 фигур. Но мат достигается только 545 единственными ходами!

          3. А игра уже меняется. Если лет десять назад считалось, что необходимо получить преимущество в дебюте, то сейчас ведущие гроссмейстеры идут на просто игровые позиции. И очень много компьютерных приемов я уже замечаю, например задвижение крайних пешек.
            +6
            Спасибо. Про эти примеры из 7-фигурок я не слышал (господи, какой кошмар!). Для меня в свое время сюрпизом стало даже то, что эндшпиль ферзь против ладьи совсем не так элементарно выигрывается, как это писалось в детских книжках :)
              0

              Ссылка на статью не открывается, это у меня что-то не так?..

                0
                На какую?
                  0

                  На слова про семифигурную базу отвечает "Данная статья не существует или еще не написана".

                    0
                      0

                      То же самое. Это в мобильном браузере, попозже попробую с компа, возможно, это он ссылку портит.

                        0
                        С компа тоже не открывается
                          0

                          Странно. Но возможно этот ужас лучше просто не видеть… :)

                            +1

                            "Статья не существует или не написана"

                              0
                              Странно. У многих не открывается. Посылал двум член-корреспондентам РАН. У них тоже не открылось. Так что вы в этой же когорте :)
                0
                у меня открылась
                tb7.chessok.com/articles/Top8DTM_eng
                0
                Я досмотрел все 545 хода.
                  0
                  И как впечатления? :)
                    +1
                    Просто было интерестно в какой момент произойдёт что-то интерестное.
                    Какая фугура потеряется первой и при каких обстоятельствах.

                    На 511 хочу чёрныне потеряли качество, потом пошло быстрее, на 529 слона, на 544 коня и 545 мат.

                    Вот ссылка на позицию.
                    tb7.chessok.com/probe/3/65
                      0
                      Интересно, как сейчас правило 50 ходов в шахматах действует? Помнится, там вводили какие то исключения, но жизнь показывает, что их куда больше…
                        0
                        Насколько я помню, впервые это правило отменили для мата двумя конями. Вообще считается, что мат двумя конями невозможен. Но (!) если добавить слабейшей стороне пешку, вроде как усиливая ее, мат становится возможен. Но далеко за пределами 50 ходов.

                        На этой позиции у сильнейшей стороны два коня. Результат ничья.

                        Но мы добавляем слабейшей стороне пешку. И получаем мат в 138 (!) ходов. Непостижимо для человека. Всего три фигуры. Но результат мат. При этом белые очень аккуратно обходят эту пешку. А черный король бродит по всей доске.
            +2
            Как мы можем извлечь из этого набора чисел новое знание об игре?

            Тоже подумал, гляди эти партии, об explainable AI (можно этот термин применить к тому, чего вы хотите). Было бы здорово, если бы ИИ умел сформулировать новые эвристики по типу существующих «ладья дружит со слоном, а ферзь с конем» и пр. Причем в паре партий видел, как AlphaZero шел на нарушение эвристик, известных «человечеству», хотя каких-то конкретных оснований для этого не просматривалось (ладно я их не видел — но и Stockfish, видимо, тоже :)).

              0
              Ну да. Хотелось бы чего то такого. В конечном итоге это все равно перебор, но хотелось бы извлечь какое то знание из того, что содержится в нейронной сетке, которая этот перебор направляет. А вы где партии смотрели? Я шарился по разрозненным ссылкам — а вот чтобы все в одном месте не нашел…
              +3
              Хотя ничего особо нового тут не изложено, всё же приятно читать статью, когда автор не журналист, а действительно разбирается в теме.
                0
                Спасибо. Это дейcтвительно некий обзор с целью собрать в кучу свои мысли и как то подступиться к проблеме :)
                  0
                  Тоже рад, что написано шахматистом, но всё же небольшое уточнение:
                  Проблема однако в том, что дерево вариантов в шахматах растет достаточно быстро (хотя и значительное медленнее, чем в го)
                  дерево вариантов в го вообще не растёт. Зато оно огромно с самого начала…
                    0

                    Я тут может не совсем ясно выразился. Под ростом я имел в виду сколько позиций можно получить из данной за 1 (или n) ходов

                  0
                  Я кстати, последнее время даже про покерных ботов больше думаю, чем про шахматные :)
                  +1
                  Как мы можем извлечь из этого набора чисел новое знание об игре?

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

                    +1
                    Да я понимаю, что это непросто. Что меня восхищает, так это то, как AlphaZero «смотрит» на позицию. Мы, люди, смотрим на материальное соотношение и позиционные факторы. Но как то отдельно. А она смотрит на все в целом. Особенно поразили тихие нефорсированные ходы при материальном недовесе вот здесь — www.youtube.com/watch?v=nPexHaFL1uo. Вот и хочется осознать, как она оценивает позицию…
                      0

                      Очень любопытно, что какие то приёмы AlphaZero уже применялись людми, и довольно успешно. Например, движение крайней пешки или классическая жертва пешки/качества за инициативу.

                        0
                        Да. Но как определить «инициативу»? Много раз видел это слово (например в книгах Каспарова). Но как это формализовать и обьяснить «машине»?
                    0
                    Интересен вопрос, а предельное умение игры может существовать? И каково оно?
                      0

                      Известно каково. База со всеми возможными шахматными партиями. Так просчитали шашки. Даже 100 клеточные. Но, надеюсь в шахматах до этого ещё далеко…

                        0

                        И не факт, что реально, по крайней мере для игры "Го" — точно нет из-за огромного количества вариантов.

                      +1
                      Как мы можем извлечь из этого набора чисел новое знание об игре?

                      Мне, как не шахматисту, в принципе интересно, насколько для шахматиста-человека важны именно знания? А насколько важны приобретенные навыки?

                      Знания — это ведь то, что можно сформулировать и запомнить в виде слов, звуков, картинок или какими-то образов, и в таком виде достать из своей памяти. Наверное, знания максимально важны на этапах дебюта и эндшпиля: шахматист должен осознанно отобрать из своей памяти подходящий вариант из известного ему множества.

                      Знания, это то, чем оперирует наша медленная, лобная часть мозга. Но как пользоваться знаниями в середине партии? Возможно, тут важна быстрая «интуитивная» часть нашего белкового процессора? Та, что отвечает за «озарения» и всё такое? Можно ли ее как-то программировать, кроме как наработкой навыков? То есть именно многократным проигрыванием партий, например, за Альфу?
                      То есть если раньше люди учили компьютеры, то теперь нам надо тренировать свои навыки проигрыванием лучших партий Альфы Зеро. Научится думать как машина. Но это не думание словами, а именно навыки на основе корреляций, или как там оно работает, в нашем мозгу. Надо перечитать Канемана «Думай медленно, решай быстро»…

                      PS: Для себя вновь открыл шахматы во время летней самоизоляции: играли с женой и ребенком. Играли как могли, по ходу вспоминая правила и путая названия фигур. Но что мне понравилось, так это прямо физиологическое ощущение того, что мозг работал) Усердно перебирал варианты, и для этого, по всей видимости, организму приходилось активно его кровоснабжать. Мне как ВСД-шнику это было приятно.
                        +1
                        Вы меня тут на одну мысль натолкнули. Про знания и навыки и быстро- медленно. Я собственно задумывался именно над тем как знанме может быть передано. Когда оно формализовано в словах, принципах, уравнениях — оно передается быстро. Мы можем научить других вокруг себя. С навыками все обстоит сложнее. Так вот когда знание формализуется то прогресс всего сообщества игроков идет быстро. А появление гения ( у которого все эти навыки врожденные) -вроде Капабланки или Таля, к такому же быстрому прогрессу не приводит…
                          0
                          Возможно у компьютеров просто другой «механизм передачи знаний', чем у нас. И вопрос обучения одной нейронной сетки от другой куда лучше изучен, чем вопрос передачи знания от машины к человеку…
                          +1
                          В шахматных движках и альфазиро не силен, но хочу оставить свои пять копеек. Интерпретация нейронной сети — это еще не решенная задача, поэтому предлагаю зайти с другой стороны.
                          В начале статьи автор писал, что шахматные движки пришли к тому, что делают ставку не сложную оценочную функцию, а на глубину просчета. Но с альфазиро все наоборот — глубина просчета поменьше, а вот оценочная функция — это сложная глубокая сеть.
                          Как же так получилось? А секрет, я думаю, в огромных мощностях гугла, и сотнях тысяч лет игры самой с собой. То есть, мы можем взять обычный шахматный движок, заложить в его оценочную функцию тысячи или десятки тысяч параметров, а далее по методу монте-карло или генетическим алгоритмам или еще как-то подбирать эти параметры так, чтобы прийти к оптимуму. Но нужны огромные вычислительные мощности, которые кроме как компании-гиганты никто не располагает, а им этим понятное дело заниматься не интересно. Далее по этим параметрам уже было бы сильно проще делать интерпретацию шахматной стратегии.
                            0
                            наше знание о шахматах похоже на разложение функции в степенной ряд (типа Тейлора-Маклорена) вблизи нуля. Где нулевой точкой является материальное равновесие. Применимость такого представления падает по мере удаления от материального равенства.

                            Может и не падать, если функция аналитическая.

                              0
                              В данном случае — падает :)
                              0
                              А партии вы все же посмотрите.


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

                              Ну и в принципе не вижу перспектив у шахмат. Ещё лет 15 назад были дебютные базы на ходов 20 с достаточно точными оценками позиций, а что уж сейчас могут натворить нейросети при наличии терафлопсов и киловатт-часов. И нахождение каких-то чудных позиций, которые разыгрывают в течение 500 ходов, — это лишнее тому подтверждение. Когда какая-то поверхность настолько хорошо изучена, что на ней находятся какие-то микро-желобы многокилометровой длины.
                                0
                                Ещё лет 15 назад были дебютные базы на ходов 20 с достаточно точными оценками позиций, а что уж сейчас могут натворить нейросети при наличии терафлопсов и киловатт-часов.

                                Следующий этап — уместить все это в обычный десктопный компьютер, а потом и в телефон.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое