Ошибки шахматных программ

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

Правила турниров я затрагивать не буду.

Базовая логика шахматных ходов

• Игроки ходят по очереди.

• За 1 ход можно походить одной фигурой.

• У фигур есть свой паттерн движения.

• Фигуры блокируют движения друг друга.

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

Последнее является цитатой из Википедии.

Эти правила являются ядром самой игры, и занимают самый нижний уровень(фундамент), но очевидно они не единственные. Но как вы могли заметить большинство из них нарушается. В самом нарушении этой базовой структуры нет ничего плохого если это закрывает пробелы в балансе, устраняет проблемы или даёт уникальные новые возможности, то есть приносит разнообразие в игру, и в таком случае это стоит рассматривать как уникальную фишку(частность\исключение). Если обобщить, то наличие исключения допустимо если на вопрос «А зачем это надо?» есть ответ в функциональных возможностях(количестве и качестве игровых ситуаций).

О хороших фишках

• Конь

Конь нарушает правило блокировки фигурами и привносит возможность передвигаться свободно по своему паттерну что даёт новые возможности в стратегии. Ощущается это весьма уместно и работает безусловно — абсолютно всегда.

• Превращение пешки

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

• Мувсет пешки

Как и в превращении, правил не нарушает(нарушает, но об этом позже), но имеет ряд особенностей, а именно разделение мувсета атаки и передвижения, возможность совершить в начале особый ход на 2 клетки и + «взятие на проходе»( о котором ниже). Такая способность позволяет немобильной пешке быть полезной блокируя другие пешки и защищать сразу 2 фигуры, а возможность выдвигать пешку на 2 клетки ускоряет начальную стадию вывода фигур из позиций и увеличивает количество дебютных партий. Ощущается это весьма уместно и работает. О пешке ещё поговорим ниже.

• Рокировка

И тут уже нарушается 3.5 правила(почему именно 3.5 объясню ниже). Нарушаются правила паттерна движения который не соответствует королю, перемещаются сразу 2 фигуры, и король не блокирует передвижение ладьи, и не нарушается, а просто не соблюдается правило убийства фигур(об этом ниже). Собственно зачем нужна рокировка и что она даёт если так сильно выделяется? Перемещение короля на дальнюю дистанцию чтобы защитить его, а также вывод ладьи в центр. Полезно ли это? — да. Ощущается уместно? — да. Важна ли рокировка? — да. Но тем не менее условия которые нужно соблюсти при рокировке оставляют множество вопросов к которым я ещё вернусь.

Все эти «фишки» имеют под собой функциональные возможности и увеличивают количество стратегий\ситуаций.

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

6 мин

29K

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

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

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

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

---

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

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

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

Общее количество уникальных партий в шахматы составляет примерно 10¹²⁰, что на 10⁴⁰ превышает количество атомов во Вселенной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if α ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if β ≤ α then
                break (* α cutoff *)
        return value

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

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

Из всего множества вариантов развития событий программа выбирает ряд линий, которые в перспективе ведут к улучшению позиции. Их она анализирует более глубоко – на 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 учитывает стратегическую позицию. 

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

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

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

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

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

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

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

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

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

Создать своего гениального цифрового шахматиста или получить Level Up по навыкам и зарплате можно пройдя онлайн-курсы SkillFactory со скидкой 40% и промокодом HABR, который даст еще +10% скидки на обучение. Узнайте подробности.

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Другие профессии и курсы

Проблемная часть

• «Взятие на проходе»

Начну, по моему мнению, с самого лютого бреда, апофеоза глупой механики, со странного да и просто никому неизвестного правила, со «взятия на проходе». Я о нём узнал буквально недавно, при том что я и в шахматный кружок всю школу проходил, и всю жизнь периодически играл в шахматы с разными людьми которых наберётся пара сотен, и никто не знал о нём(во всяком случае не говорил об этом правиле и ни разу не пользовался им).

Смотря профессиональные(турнирные) игры я ни разу не видел чтобы происходило «взятия на проходе»(не исключаю того что такие игры есть). Наблюдая за играми в живую, ни разу не видел «взятия на проходе». Спросив у людей с которыми я сейчас активно играю о нём, никто не знал о «взятии на проходе». Во время составления этой статьи просмотрел несколько видео по правилам шахмат на ютубе и в 2 из 4 видео о «взятии на проходе» не было сказано.

Вот что Википедия говорит о правиле:

«Правило взятия на проходе было введено в шахматы в XV веке практически одновременно с другим правилом, которое разрешало делать первый ход пешкой сразу на два поля вперёд. Обосновывается это правило просто: пешка не может перемещаться без риска быть взятой, когда поле прохода находится под боем противника»

И это объяснение едва ли логично и противоречиво ведь другим фигурам возможность «перемещаться без риска быть взятой, когда поле прохода находится под боем противника» дана всегда, ясно что пешка получает это только 1 раз за игру, но так ли это плохо\сильно\имбово\нечестно? Ведь это даже не уникальная особенность а лишь следствие из правила двойного хода. И что делает это правило ещё более странным так это условия которые нужно обязательно соблюсти чтобы «взятия на проходе» можно было сделать и то как оно выполняется:

1. Пешки должны находиться в одной горизонтали.

2. Пешки должны быть на 4\5 линии(для чёрных и белых по разному).

3. Пешка-жертва должна делать свой первый ход.

4. Этот ход обязательно должен быть на 2 клетки.

5. «Взятия на проходе» можно сделать только в первый ход после четвёртого пункта(что логически не стыкуется с идеей добавления механики).

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

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

Обилие условий, в купе с глупым произведением взятия, общественным незнанием о том что «так вообще возможно?», количеством ситуаций(0.0000001%(это не точно)) в которых механика утилизируется и спорными отзывами о нужности, делает как минимум «взятие на проходе» сомнительной механикой. Но не менее смешным является то как его добавили в шахматы(за истину беру информацию из Википедии).

Следующее предложение является выдумкой(сказкой), но отражает претензию.

Значится, был XV век на дворе, сидели гроссмейстеры и думу думали как бы нам решить проблемы насущные в наших любимых шахматах, а проблемы были таковы: 1 — первые ходы были долгим выставлением пешек освобождая путь для фигур; 2 — малое количество дебютных партий которые заучиваются и итог очень быстро становится очевидным. Обозначили проблемы они, сели за стол обсуждений и начали накидывать варианты их решения. Первый гроссмейстер говорит — «а давайте сделаем так что можно убивать свои фигуры», «круто» — ответили ему хором, и следом второй предлагает — «А давайте вообще уберём пешки, нет пешек, нет проблем», «круто» — ответили ему хором и т.д. Длилось это долго, целых 100 дней и 100 ночей они старались придумывать новые варианты. И вот уставшие, истощённые гроссмейстеры посмотрели на все предложение варианты, выписали все три варианта на таблички и начали голосовать поднимая их и выбрали последний, третий вариант который позволял пешкам ходить на 2 хода. Довольные гроссмейстеры сразу сели играть, играют они 100 партий, 200 партий, 1000 партий и понимают что их решение породило новую проблему в лице того что пешки спокойно преодолевают двойным ходом атаку других пешек. Собрали они снова совет и начали думать как решить и эту проблему. Умнейшие из них хватались за головы, слабейшие пали храброй смертью в первые дни рассуждений и спустя 500 дней худые, костлявые гроссмейстеры решили что хватит мучаться, взяли абсолютно все предложенные варианты смешали их в кучу, так и появилось «взятие на проходе», ну а все кто участвовал в дебатах благополучно умерли в тот день.

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

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

Если мы считаем что если пешка совершая ход на две клетки пролетает битое поле контролируемое другой пешкой без риска проблемой:

1) Ограничить количество двойных ходов для пешек до 1-2 за игру, или же разрешать делать ход на две клетки только в первые 3-4 хода. Чем оно плох и хорош этот «костыль», да тем что банально не исключает возможность возникновения самой проблемы, а лишь делает возникновение и так очень редкой ситуации ещё реже, и в добавок к этому добавляет ещё одно правило, что явно не идёт на пользу.

2) Запретить пешке делать ход на 2 клетки если она встанет по соседству в одну горизонталь с вражеской пешкой. Ведь ситуация с ходом на 1 и 2 клетки почти идентичны. Почему почти, потому что если в первом примере белая пешка не побила бы чёрную, то чёрная была бы на 1 клетку дальше. Чем плох этот «костыль», тем что он исключает выше описанную ситуацию, тем что это всё ещё искусственное решение с похожими условиями как и «взятие на проходе». Чем хорош, тем что условий здесь меньше, реализация менее странная и это проще объяснить, ведь если противник не знает об этом правиле и делает ход на 2 клетки ему всегда можно указать на ошибку, в отличие от «взятия на проходе» в котором ты просто упускаешь возможность.

Если мы считаем что ситуация в которой, пешка совершая ход на две клетки пролетает битое поле контролируемое другой пешкой без риска, не является проблемой:
3) То во «взятии на проходе» нет никакой необходимости и мы со спокойной душой можем его удалить из правил.

• Рокировка

Почему рокировка находится в «проблемной части» хотя я описывал её как хорошее решение, как говорится «дьявол кроется в деталях».
Для начала обозначу условия необходимые для возможности совершить рокировку:

1. Рокировка должна быть первым ходом для обеих фигур.

2. Король не должен находиться под шахом.

3. Король не должен становиться под шах после рокировки(что является следствием из обычных правил передвижения короля).

4. Между королём и ладьёй не должно быть ни союзных, ни вражеских фигур.

5. Король не должен проходить через битое поле.

И вот тут уже возникают вопросы зачем столько, и почему именно эти условия.
Удаление 2, 5 и изменение 1 и 4 правила не сделают игру хуже, а лишь сделает её проще для восприятия ведь некоторые правила нелогичны, очевидно что это уберёт одни ситуации из игры и добавит другие. Разберём каждое решение.

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

Второе условие, один вопрос, почему нельзя? Лично здесь я даже не могу предложить что это даёт и зачем это надо.

Пятое условие, как и второе, почему нельзя? Король же на этом месте не заканчивает ход на этом месте и не получает шах, так почему нельзя?

Четвёртое условие, очевидно что если на месте куда передвинуться фигуры после рокировки будут стоять союзные фигуры то рокировка недоступна, ибо клетки заняты, но если во время длинной рокировки эти места свободны, а возле ладьи стоит конь(любая союзная или вражеская фигура) то почему в таком случае рокировку делать нельзя? Ведь ладье при рокировке разрешено как коню перепрыгивать фигуры.
Почему во время шаха рокировка недоступна, ведь это считается обычным ходом, а король может двигаться во время шаха?
Внимание на картинку, почему в ситуации когда на месте куда встанет король после рокировки стоит вражеская фигура рокировку делать нельзя? Логичней было бы разрешить делать рокировку, а стоящая фигура будет взятой как и происходит во всех других ситуациях в игре когда ты занимаешь клетку занятую вражеской фигуры.

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

• «Тронул — ходи»

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

• Мат

Почему игра заканчивается матом, а не убийством короля? Ведь если короля надо было бы убить то игры могли бы моментально заканчиваться по невнимательности из за того что не заметил шах, если смущает что игра проигрывается из за недосмотренности\глупости, а не из за неправильных решений, то смею огорчить по невнимательности игры и так проигрываются, но только дольше, ведь ситуации где ты недосмотрел\поспешил и потерял ферзя или любую другую важную для победы фигуру не исключены. Изменения мата на взятие короля никаких ситуаций бы не убрало из игры, а лишь сделало бы лучше, чем же? Да тем что убрало бы пат из игры и решило бы следующую конфликтную ситуацию.

Посмотрите на картинку, сколько вы видите способов защитить короля?

Если скажите 6 то окажитесь правы, вот все ходы f1-e1, f1-g2, e2-f3, g1-f3, e4-f2, e4-f6. Но есть ещё 1 ход который правилами запрещён e2-h5.

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

Спасибо за внимания, о решении ещё некоторых проблем можете ознакомиться в этой статье.

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

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

Вы знали про правило “Взятие на проходе” до прочтения статьи?

Проголосовали 1029 пользователей.

Воздержались 67 пользователей.

Действительно ли компьютер-шахматист сильнее человека?

9 мин

77K

На написание этого обзора натолкнул пост «Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?», опубликованный 25 мая. В самом посте, и, тем более, в комментариях, было много сказано по поводу компьютерных шахмат вообще и матча Deep Blue — Каспаров (1997) в частности. Понятно, что сейчас, спустя уже без малого двадцать лет, мало кому интересны все подробности того матча: компьютеры развиваются с колоссальной скоростью, современные смартфоны легко дадут фору компьютерам того времени, да и возможно, сами шахматы несколько утратили популярность последнее время — по каким причинам — это уже тема отдельного разговора.

Впрочем, некоторые подробности, судя по всему, действительно неизвестны, а подробности эти таковы, что заголовки о “падении последнего интеллектуального бастиона” — не более, чем газетный прием, ибо случившийся по итогам матча, по сути, скандал, в силу своей шахматной специфичности вряд ли был бы интересен широкой публике. Нет, я, несмотря на то, что всегда являлся поклонником Гарри Кимовича Каспарова (исключительно в шахматном плане), не собираюсь его оправдывать за то поражение и пытаться доказать, что все было совсем не так, как сейчас общеизвестно. И уж тем более целью не является опровержение некоторых комментариев на шахматную тему к посту хабраюзера alizar. Единственная цель — рассказать некоторые подробности того, что именно произошло в Нью-Йорке в начале мая 1997 года, и почему результат этого противостояния, по мнению автора, на самом деле никому ничего не доказал.

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

Недостаточно быть хорошим игроком; вы также должны хорошо играть
(З.Тарраш)

История шахматного программирования началась, по сути, сразу же с обычным программированием. Искусственный интеллект, возможность его создания, волновали людей издавна, и программируемая вычислительная техника оказалась более подходящим средством для поиска такой возможности, чем человек, который обыгрывал Наполеона, сидя в тумбочке. Первые шахматные программы были, впрочем, соперниками лишь друг другу: в силу огромного количества вариантов шахматных партий, речи о полном переборе не было, и нет, кстати, и по сей день. (И не предвидится (с) Швондер.) Это не мешало шахматным программам периодически удивлять профессиональных шахматистов как неожиданно лучшими ходами (что объясняется в первую очередь тем, что форсированные варианты компьютер считает все же быстрее и точнее), так и внезапными просмотрами мата в пару-тройку ходов ради спасения ферзя. Однако, если в тактике даже сравнительно слабые компьютеры были вполне себе сильны, то вот в позиционной игре все было очень печально — если еще как-то можно было научить программу, что ферзь дороже пешки (что в некоторых случаях приводило к вышеупомянутым просмотрам мата), то научить оценке позиции, на которой, собственно, вся партия и держится, возможным не представлялось. Это и неудивительно — правильная оценка позиции — это задача непростая даже для шахматистов-разрядников, единого рецепта нет, даже две практически одинаковые позиции, отличающиеся лишь положением одной пешки, могут иметь противоположные оценки.

С течением времени, впрочем, прогресс стал брать свое. Дебютные библиотеки позволили программам не “плавать” в начальной стадии партии — такие “плавания” нередко приводили к окончанию партии еще в дебюте — все же, несколько столетий опыта и рост дебютной теории с начала ХХ века давали человеку немалую фору. Дебютные библиотеки эту фору не просто устранили — в отличие от человека, компьютер теперь мог разыграть абсолютно любой дебют, уйти от любой дебютной ловушки, да и сам, соответственно, мог в любую ловушку поймать! Шахматистов, знающих все дебюты, не бывает — есть понятие “дебютный репертуар” — это некоторое количество начал, использующихся шахматистом. Человек может этот репертуар расширять, пополнять, готовить, например, новые дебюты к новому турниру, но с появлением у компьютеров в памяти дебютной энциклопедии человек стал проигрывать в этом компоненте. Кстати, фора тут вышла двойная: в отличие от компьютера, который по сути, играет по дебютной библиотеке, человек в ходе партии подсмотреть в дебютную энциклопедию не может. Единственный вариант уравнять тут шансы — неправильные начала, не внесенные в энциклопедии, причем, максимум шансы получится именно уравнять — человек ведь также не имеет возможности применить багаж своих дебютных знаний.

Надо сказать, что проблема дебютных знаний и их чрезмерной распространенности и доступности волновала и самих шахматистов. Так, совершенно нормальными в профессиональных шахматах стали ситуации, когда игроки сделали по 30-40 ходов, и ничего нового в них не было — все эти ходы уже были в другой партии. (Тут, конечно, дело касается не только дебюта, но, как правило, такие ситуации были связаны в первую очередь с дебютными спорами, и некий вариант мог отстаиваться и в глубоком миттельшпиле, и даже в эндшпиле!) Либо ситуации из партий гросс- и супергросс- мейстеров — партия до 20 ходов, обычно — 16-18, все “из книжки” и соглашение на ничью — потому что позиция теоретически ничейна. Спасением виделись Шахматы Фишера, они же Шахматы-960, где фигуры в начальной позиции могут располагаться произвольным образом. Увы (или к счастью?), обычные шахматы этот вариант вытеснить не смог. Почему — сказать сложно, но рискну предположить, что профессиональным шахматистам он не был вполне интересен, им и в стоковых дебютах хватало, чем заняться, а остальным — не давал никаких преимуществ — см. комментарий Каспарова. В самом деле, дебютные принципы не поменялись — “развивай фигуры как можно быстрее и безопаснее и мешай делать то же самое сопернику”, и тот, кто эти принципы понимал в стандартных шахматах — не перестал их понимать и в фишеровских, а кто двигал фигуры исключительно по памяти из справочника и при любом отклонении впадал в панику — стал в эту самую панику впадать гораздо быстрее, на 2-3 ходу.

Гораздо лучше в теории дела обстояли с эндшпилем. Особенно с малофигурными окончаниями — чем меньше фигур — тем лучше. Такие ситуации, в отличие от дебютов, просчитывались куда как проще: фигур-то гораздо меньше! Да и ограничения по количеству ходов способствовали (см. Правило 50 ходов). Так или иначе, компьютеры получили возможность пользоваться Эндшпильными таблицами Налимова и это, пожалуй было еще большей победой, нежели дебютные библиотеки. Впрочем, человек тут имел свои козыри — например то, что множество вариантов шахматных окончаний можно было играть, практически не считая варианты, а пользуясь известными алгоритмами, самый знаменитый пример (первый этюд, вероятность возникновения подобных мотивов в реальной партии достаточно высока).

А вот в миттельшпиле человек оставался хозяином положения. Да, совершенствовались алгоритмы для оценки позиции, да, компьютеры считали все дальше и глубже, но оставалось одно, то, из-за чего компьютеры так пока что и не стали ни писателями, ни композиторами: план. Если в дебюте компьютер мог двигать фигуры исключительно “по книжке”, а в эндшпиле — придерживаться неких алгоритмов, то с планом были трудности. Да, очевидно, если при оценке позиции машина находила у соперника слабые места — то могла делать ходы, направленные на их использование. Если слабые места были у машины — то она могла предпринимать действия для защиты. Однако, живой шахматист не будет руководствоваться только своим планом — он попытается определить планы соперника. Замечательная задача для ИИ. Вот только выполнимая ли?

В 1996 году представители компании IBM предложили Гарри Каспарову сыграть матч против их шахматной программы «Дип Блю» с призовым фондом в $500 тыс. «Дип Блю» — суперкомпьютер на базе системы RS6000, состоящий из 32 узлов, каждый из которых состоял из 512 процессоров, аппаратно оптимизированных для шахматной программы. Производительность «Дип Блю» соответствовала 11,38 GFLOPS, и компьютер мог оценивать до 200 млн позиций в секунду (Википедия).

Тринадцатый чемпион мира Гарри Каспаров всегда считал свое занятие прежде всего творчеством. То есть, тем, что машине недоступно и не будет доступно никогда. Каспаров говорил:

“Если компьютер сможет превзойти в шахматах лучшего из лучших, это будет означать, что ЭВМ в состоянии сочинять самую лучшую музыку, писать самые лучшие книги. Не могу в это поверить. Если будет создан компьютер с рейтингом 2800, то есть равным моему, я сам сочту своим долгом вызвать его на матч, чтобы защитить человеческую расу.”

По иронии судьбы, именно Каспаров стал первым чемпионом мира, проигравшим компьютеру. Первая же партия матча Deep Blue — Каспаров (Филадельфия, февраль 1996 г.) принесла сенсацию — Чемпион Мира повержен машиной. Увы для поклонников ИИ — уже во второй партии чемпион мира реваншировался, а после еще двух партий, завершившихся вничью, выиграл дважды, доказав таким образом, что чемпион мира — это чемпион мира. Все же, было уже понятно, что компьютерные шахматы — это реальная сила, и что во втором матче, который IBM предложила спустя чуть более года, чемпиону-человеку придется постараться, чтобы защитить человеческую расу.

Второй матч Каспарова с “Темно-синим” начался, наверное, даже с огорчительного для любителей интриги результата — Каспаров выиграл белыми легко, избрав неправильное начало (точнее, этот дебют вполне можно классифицировать, как Дебют Рети). Казалось, все ясно, идея Каспарова проста — лишить соперника первого козыря, дебютной библиотеки, и играть просто в шахматы, что машине не дано. Конечно, отойти от теории при игре черными гораздо сложнее, тон ведь задают белые, и тут Каспаров, вероятно, надеялся на Испанскую партию, ту самую, которую в количестве восемнадцати штук играл сам Остап Бендер — старинный дебют, где отыграть по книжке сам дебют мало, надо уметь играть миттельшпиль. И тут-то и началось.

Тот не шахматист, кто, проиграв партию, не заявляет, что у него было выигрышное положение
(И.Ильф)

Итак, сначала — только игровые факты. Партии игрались с контролем 2 часа на 40 ходов (классический контроль времени). Играя черными, Каспаров попытался оживить позицию с помощью жертв, машина эти жертвы отклонила, и в итоге, чемпион мира, оказавшийся в сложнейшей позиции, сдался. Все просто и ясно. Далее часть описания и цитат заимствована отсюда (там же можно посмотреть всю партию №2), часть — описана автором.

По мнению чемпиона, первый звоночек прозвенел на 35 ходу — суперкомпьютер, до этого тративший не более трех минут на ход, задумался на четверть часа. Еще шесть минут — над следующим ходом. Результат был еще более неожиданным — компьютер отклоняет жертву пешек черными.

По условиям, после каждой партии IBM предоставляла распечатки анализов, которые компьютер производил во время каждой партии. По словам Каспарова, вариант, избранный машиной, ей же был оценен, как неясный, в отличие от принятия жертвы, которое машина оценивала как выгодное для себя. “Очень мило. Мы имеем дело с уникальным событием, Машина отказывается от выигрыша трех пешек, потому что ей якобы “неясно” — Г.Каспаров.

Партия продолжалась, и двигалась к логическому финалу, который в конце концов и наступил — Каспаров сдался. Однако чудеса на этом не закончились. Как выяснилось практически сразу — чемпион мира сдался в ничейной позиции. Казалось бы, обвинять тут некого, кроме самого потерпевшего. Но все не так просто. Каспаров сдался, просто поверив, что машина непогрешима. И ошибся. Своим последним ходом в партии машина допустила грубейшую тактическую ошибку, после чего черные могли закончить партию вничью. Удивление Каспарова после партии вполне понятно: машина, нашедшая сильнейший позиционный ход, который оказался не под силу даже многим белковым шахматистам, то есть, обошедшая людей на их же территории — в позиционной игре, тут же проиграла на своей территории, где она не может ошибаться — допустив элементарный тактический зевок?

Эти вопросы до сих пор остаются вопросами, а матч, тем не менее, продолжался. Три партии завершились вничью. Была ли шестая партия для Каспарова своеобразным финалом? Финалом в матче за честь и ум человеческой расы.

В шахматах выигрывает тот, кто ошибается предпоследним
(С.Тартаковер)

Пожалуй, с точки зрения компьютерных шахмат, в шестой партии не произошло ничего интересного. Вопросы в этой партии в основном к чемпиону мира — каким образом он мог сделать ход 7.… h6? Компьютер тут же пожертвовал коня и позиция черных покатилась под откос. После 19-го хода белых Каспаров сдался. Единственное его достижение в данной партии — это то, что официально она не стала самым быстрым поражением в его карьере — шахматные статистики не учитывают партии человека с компьютером. Хотя формально, как вы поняли, это именно такая партия.

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

утиль

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

И все же, что доказали эти матчи? Что человек повержен? Если брать оба матча Каспарова с DB — то счет остался в пользу Каспарова — 6,5-5,5. Если даже брать только второй — то во-первых, наверное, статистически результат 2-1 в пользу одной стороны (без учета ничьих) ничего не доказывает. Во-вторых, поражение Каспарова в шестой партии — из-за явного зевка — вряд ли на основании такой грубейшей ошибки (я молчу про сдачу Каспаровым второй партии в ничейной позиции) можно доказывать силу шахматной программы.

После переезда Deep Blue в музей, люди, разумеется, не перестали играть в шахматы с компьютером. Однако, о подобных матчах вообще не слышно, гроссмейстеры теперь предпочитают более экзотические виды использования компьютера. Может, ведущие гроссмейстеры просто боятся поражений от машины? Почему тогда владельцы суперкомпьютеров, авторы мощных шахматных программ, не заявляют, мол, вот мы предложили матч, а чемпион мира отказался? Скорее всего дело действительно в падении интереса к шахматам, интереснее сейчас ставить другие задачи перед ИИ, а поражение от машины в шахматы, пусть даже и чемпиона мира — кому оно интересно, ведь “уже давно машина выиграла у чемпиона мира”.

Ссылки:
Отчет IBM о матче 1997 года
Шестая партия матча 1997 года в википедии