Шахматные алгоритмы, которые думают лучше человека

отметили
27
человек
в архиве

источник: hsto.org

Когда создавались первые вычислительные машины, их воспринимали только как дополнение к человеческому разуму. И до недавнего времени так и было. Программисты учили компьютеры играть в шахматы с 1960-х годов. И тогда победа у игрока-новичка уже считалась большим прогрессом. О серьёзных матчах даже не задумывались.

В 1980-х программа Belle достигла рейтинга Эло в 2250 пунктов, что примерно соответствует рейтингу мастера спорта. И с того времени развитие компьютерных шахмат вышло на совершенно новый уровень.

Сначала честь человечества не смог защитить Гарри Каспаров в 1996 году, а сегодня уже создана нейросеть с рейтингом около 5000 Эло, что в разы превосходит даже сильнейших игроков.

Сегодня разберёмся, как работают шахматные алгоритмы и почему нейросеть Alpha Zero думает практически так же, как человек, только лучше.

Как работает шахматный движок: от механического перебора вариантов до «умного» выбора

У шахмат довольно простые правила. Две противоборствующие стороны, шесть разновидностей фигур и одна цель – дать мат сопернику.

Но при этом вариативность шахмат просто огромна. Существует 400 уникальных комбинаций первого хода – 20 вариантов первого полухода белых и 20 вариантов ответа чёрных. С каждым последующим ходом количество уникальных позиций увеличивается на степень.

Общее количество уникальных партий в шахматы составляет примерно 10120, что на 1040 превышает количество атомов во Вселенной.

Шахматам не грозит быть посчитанными полностью. Поэтому в бой вступают алгоритмы оценки позиции и дерево возможных ходов.

источник: hsto.org

В шахматной теории у каждой фигуры есть своя ценность, которая измеряется в пешках:

  • Конь – 3 пешки;

  • Слон – 3 пешки;

  • Ладья – 5 пешек;

  • Ферзь – 9 пешек;

  • Пешка – 1 пешка.

Король – бесценен, потому что его потеря означает проигрыш партии.

Анализ современных машин подтверждает истинность такой оценки. Так, в зависимости от позиции на доске компьютер оценивает ферзя в 9–12 пешек, ладью – в 5–6, коня и слона – в 3–5. Короля же машина оценивает в 300 пешек. Это задаёт максимальную границу оценки.

Чтобы было более понятно, преимущество в 0,5 пешки – это уже неплохо для шахматиста. В целую пешку – серьёзный перевес. В 3 пешки – подавляющее преимущество, которое можно практически без проблем довести до победы.

Но счётные возможности машины ограниченны. Иногда она показывает оценку в +51 или что-то вроде. Это означает, что алгоритм видит колоссальное преимущество белых в позиции и материале, но не может найти конкретный путь к мату.

Минимакс, или прямой перебор вариантов, в таком случае не работает. Даже КМС без проблем найдёт на доске мат в 3 хода в миттельшпиле, когда на доске ещё много фигур. А программе для этого нужно будет перебрать свыше 750 млн. полуходов.

Даже если программа перебирает 1 млн вариантов в секунду, чтобы найти мат в 3 хода, ей понадобится до 750 секунд, или 12,5 минут.

И это глубина в 3 хода. В стратегических позициях, где развитие игры идёт с учетом на пять или десять ходов вперёд, такие программы и вовсе будут бесполезными.

Поэтому для анализа позиции используется алгоритм под названием «альфа-бета-отсечение».

источник: hsto.org

Система анализирует начальные варианты ходов и сразу отсекает те из них, которые ведут к мгновенному ухудшению оценки.

Программа отметает те варианты, в которых она сразу проигрывает материал или которые включают комбинации со стороны соперника, в ходе которых она выигрывает материал или партию.

Это позволяет сократить количество рабочих линий на порядки, сосредотачивая вычислительные ресурсы только на тех ветвях дерева, которые в перспективе ведут к улучшению позиции.

Псевдокод для минимакса с ограниченной глубиной с отсечением альфа-бета выглядит следующим образом:

За код особо не ругайте.

Рассмотрим на примере. Движок Stockfish считается сегодня одной из самых сильных компьютерных шахматных программ. Обратите внимание на первые пять линий.

источник: hsto.org

Из всего множества вариантов развития событий программа выбирает ряд линий, которые в перспективе ведут к улучшению позиции. Их она анализирует более глубоко – на 15–20 ходов вперёд, чтобы отсечь возможные проигрышные варианты. В результате она выбирает лучшую из возможных линий и делает ход.

После ответа соперника ситуация снова анализируется по тому же алгоритму. Сначала отсекаются заведомо проигрышные линии (таких порядка 95 %), а затем путём более глубокого анализа перспективных вариантов выбирается лучший из них.

Новая эра в шахматных движках: нейросеть Alpha Zero

В 2017 году компания Deep Mind объявила о создании нейросети Alpha Zero. Тестировать её решили на трёх самых популярных стратегических настольных играх: шахматы, го и сёги.

Обучение и подготовка нейросети отличаются от классических компьютерных движков.

Stockfish и другие движки используют для своей работы существующие дебютные базы и анализ позиций огромного количества сыгранных партий.

Alpha Zero не использует ничего, кроме правил. Ей просто дали стартовую позицию, объяснили, как ходят фигуры, и цель игры – поставить мат сопернику. И всё.

За 24 часа игры с самой собой нейросеть смогла достичь сверхчеловеческого уровня игры и по сути изобрести заново всю шахматную теорию, которую человечество по крупицам разрабатывало веками.

В декабре 2018 года Alpha Zero во второй раз сразилась с самой последней версией движка Stockfish.

Исследователи провели 1000 партий с контролем 3 часа на партию плюс 15 секунд на ход. Alpha Zero одержала уверенную победу, выиграв в 155 партиях, сыграв вничью 839 партий и проиграв только 6.

Более того, Alpha Zero одерживала победу даже в партиях с форой по времени на обдумывание. Имея в 10 раз меньше времени, чем у противника, нейросеть всё равно победила в суммарном итоге. Только 30-кратная фора во времени смогла уравнять шансы и дать Stockfish примерно равную игру – 3 часа у движка и всего лишь 6 минут у нейросети.

Alpha Zero анализирует лишь 60 000 позиций в секунду, а тестируемая версия Stockfish – 60 млн. позиций. Для достижения аналогичных результатов анализа нейросети нужно в 1000 раз меньше ресурсов, чем движку.

Секрет успеха – в качественно другом уровне анализа. Нейросеть использует метод Монте-Карло, который высчитывает математическое ожидание комплекса ходов.

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

И, что гораздо более важно, при оценке ситуации Alpha Zero учитывает стратегическую позицию.

источник: hsto.org

Давайте рассмотрим на примере одной из партий.

После 20-го хода на доске творится невообразимая стратегическая борьба. Но если нейросеть шаг за шагом минимально укрепляет свою позицию, избавляясь даже от призрачных слабостей, то движок с 24-го по 29-й ход просто топчется на месте ладьёй.

Интересно, что Stockfish в упор не видит стратегических решений Alpha Zero, оценивая позицию как абсолютно ничейную. Но в результате минимальных укреплений позиции к 39-му ходу оказывается, что все фигуры белых активны, а чёрный конь и слон занимают пассивную оборонительную позицию. А после размена ферзей и ладей даже Stockfish оценивает преимущество нейросети в +2,2. Ещё несколько ходов – и король черных зажат в углу доски, а конь в одиночку не способен справиться с проходной пешкой. Поэтому программа сдалась.

Позиционная игра – это то, что отличает нейросеть от классического шахматного движка. Ведь она подразумевает длительные игровые планы, которые часто превышают вычислительные возможности машин.

Тем не менее нейросеть умеет играть позиционно не хуже человека и при этом идеально играет тактические позиции, где преимущество достигается в течение 5 или меньше ходов.

Более того, нейросеть уже помогла найти теоретикам шахмат целый ряд неочевидных, но при этом очень сильных разветвлений дебютов, которые никогда не рассматривали ранее.

Многие теоретики считают, что благодаря шахматным компьютерам повысился и средний рейтинг топовых шахматистов. Ведь современные тренировки включают глубокую проработку компьютерных вариантов и разбора партий движками. Средний рейтинг ведущих топ-100 шахматистов в 2000 году составлял 2644 пункта Эло, а в январе 2021 года – 2715. За 20 лет среднее значение увеличилось на 71 пункт.

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

Она умеет мыслить позиционно и при этом не допускает зевков и ошибок. И самое интересное в этом ситуации – шахматы для Alpha Zero являются только тестировочным полигоном, где система оттачивает навыки работы. Реальные же её цели Google не раскрывает. Поэтому здесь может быть всё что угодно: от анализа изменений климатической ситуации до создания системы идеально персонифицированной рекламы. А как вы считаете, для чего создают настолько мощную нейросеть?

Добавил suare suare 28 Февраля 2021
проблема (3)
Комментарии участников:
badbag
+5
badbag, 28 Февраля 2021 , url

алгоритмы — не думают, думают люди их составившие. Человеку глупо соревноваться с машиной в чисто механических действиях

obamahan
+2
obamahan, 28 Февраля 2021 , url

Здесь скорее «думают» в переносном смысле. Скорее из терминологии игры «обдумывания хода». Правильно было бы сказать «определение следующего хода».

suare
+2
suare, 28 Февраля 2021 , url
suare
+1
suare, 28 Февраля 2021 , url
Rillnews
-4
Rillnews, 1 Марта 2021 , url

News2.ru «выдаёт на ура» статьи о супер-современных нейро-алгоритмах, а сама не способна справиться с примитивным секс-спамом. Позорище.

magmaster
+4
magmaster, 1 Марта 2021 , url

News2.ru это кто? Сайт, владельцы или сообщество? К кому конкретно претензии?

Вот такой же уровень претензий к какойто обобщенной власти. Или кремлю. Или Путину. На каких то своих непонятных виртуальных представлениях.

Покажи как справится. Непозорище.

Тут обычные люди. любители следить за новостями. 

Это форум программистов? Кто конкретно и каким образом должен справится?

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

Нет инструмента? Подскажи тому у кого он есть. Администрация ресурса доступна, можно написать сообщение с конкретным предложением о помощи.

Но легче же ныть. Шеф всё пропало! Власть ничего не делает. Один спам кругом. Как жить!?

 

Посмотри лучше как человек новость оформил. Красота.

suare
+2
suare, 1 Марта 2021 , url

Посмотри лучше как человек новость оформил. Красота.

Спасибо :) Я очень старался для всех и ЗА просто так ;)))

источник: dslov.ru

suare
0
suare, 1 Марта 2021 , url

Ты кого обвиняешь? Меня? За то, что я разместил здесь эту статью и дважды призвал модераторов забанить рекламных ботов?

Ты что, сам не можешь обратиться к администрации? 

Ручонки боишься замарать?

Удались. Не доводи до греха.

Я разместил эту статью не для тебя персонально.

Проходи мимо, не задерживай желающих.

И похвалить и поблагодарить меня персонально не забудь, умник.

Без году неделя на ресурсе, а уже свои правила устанавливает.

Ты здесь три месяца тусуешься, а гонор — как у директора овощебазы в советские времена.

magmaster
+2
magmaster, 1 Марта 2021 , url

Возможно вы как новый участник не понимаете, что администрация сайта и участники которые размещают тут интересные им новости, это разные категории. Никак не связанные. Кроме нахождения на одном ресурсе.  Вы тоже можете размещать новости и принимать участие в их обсуждении.

Если вопрос чисто к администрации, которая могла бы поставить фильтр в сообщения. Тут согласен.  Для этого нужно в каментарии вызвать admin admin может быть примут к сведению.

А пример меж тем очень жизненный. Многие не сильно разбираясь в деталях, во всём любят винить Путина.  Смешивая все на свете и думая что он как минимум царь, а то и волшебник.

Нужно чётко определять категорию и причину происходящего косяка. Тогда и эффективность решения будет выше. Иначе получается вы в куче обругали и Хантера разместившего новость. А он тут явно никаким боком к этом спаму. От слова совсем.

suare
0
suare, 1 Марта 2021 , url

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

При этом нахватал БАНов от участников ТОПа.

Чем он вообще здесь занимается? Троллингом?

Да это банальный клон для разборок одного из свидетелей и активных участников секты Навального.

Забанить его бессрочно — и все дела за флуд, флейм, срач, холивары и троллинг не по темам новостей.

Коллаборант-поджигатель и все дела.

Школота на содержании перед выборами в сентябре.

Дустом его и его подельников на этом ресурсе! Выжечь гнилое семя, как класс!

suare
0
suare, 1 Марта 2021 , url

magmaster
+1
magmaster, 2 Марта 2021 , url

)

У меня тоже такое двоякое впечатление. То ли Юля очередную маску применяет и троллит, то ли школьник завёлся. Любое чудо, научившиеся писать, может спорить наровне с заслуженными участниками. Толку от этих банков. Один хрен Демократия. Слово академика равно слову студента, а то и вовсе наркомана. 



Войдите или станьте участником, чтобы комментировать