3.3.3 Применение обратной индукции для анализа шахматных окончаний

В 1969 г. в СССР математики Александр Брудно и Игорь Ландау применили ретроанализ для решения шахматной задачи под названием «Неприкосновенный король». В задаче на доске три фигуры: белый король, белый ферзь и чёрный король. Белый король находится на поле c3 и не имеет права двигаться (поэтому и называется неприкосновенным). Вопрос заключается в том, может ли белый ферзь с помощью своего неприкосновенного короля заматовать одинокого короля чёрных. Эта задача была известна ещё в XIX в., и многие шахматисты, в том числе гроссмейстеры, ошибочно предполагали, что заматовать короля нельзя. Брудно и Ландау выяснили с помощью машины, что мат даётся при любом начальном положении белого ферзя и чёрного короля, причём не позднее двадцать третьего хода. Они также доказали, что белые побеждают только в том случае, если «неприкосновенный король» в задаче стоит на полях c3, c6, f3 или f6. Вполне вероятно, что это был первый случай в истории шахмат (и математики), когда вычислительная машина решила шахматную задачу раньше человека^, .

В 1970 г. математик Томас Штрохлейн защитил диссертацию о компьютерном анализе шахматных окончаний. Когда на шахматной доске остаётся мало фигур, задача нахождения оптимальных ходов становится вычислимой. В 1969 г. Штрохлейн выполнил ряд расчётов на компьютере AEG-Telefunken TR4 в Вычислительном центре им. Лейбница в Мюнхене (Leibniz-Rechenzentrum München, сегодня это учреждение обычно называют Суперкомпьютерным центром им. Лейбница), проанализировав такие окончания, как «король и ферзь против короля» (KQK), «король и ладья против короля» (KRK), «король и пешка против короля» (KPK), «король и ферзь против короля и ладьи» (KQKR), «король и ладья против короля и слона» (KRKB) и «король и ладья против короля и коня» (KRKN). Это традиционно считается первым случаем практического применения ретроспективного анализа для шахматных окончаний.

В 1970-е гг. сотрудники Института проблем управления АН СССР Эдуард Комиссарчик и Арон Футер осуществили машинный анализ эндшпиля «король, пешка, ферзь против короля и ферзя» (с белой пешкой, фиксированной на поле g7), а также эндшпиля «король, пешка, ладья против короля и ладьи» (KRPKR)^, .

Именно работу по анализу последнего эндшпиля я вспоминаю, когда смотрю очередную серию анимационного сериала Netflix «Любовь, смерть и роботы» (Love, Death & Robots), и вот почему. В 2007 г. свет увидела книга Дэвида Леви с похожим названием — «Любовь и секс с роботами» (Love and Sex with Robots). Леви также выступает в качестве организатора скандально известной одноимённой ежегодной конференции (loveandsexwithrobots.org), проведение которой в 2015 г. было сорвано из-за запрета властей Малайзии. Дэвид Леви весьма яркая личность в мире ИИ. Например, он руководил разработкой и финансировал создание чат-ботов, становившихся победителями премии Лёбнера в 1997-м (Converse) и 2008-м (Do-much-more). Леви возглавляет Международную ассоциацию компьютерных игр (International Computer Games Association, ICGA), созданную в 1977 г. как Международная ассоциация компьютерных шахмат (International Computer Chess Association, ICCA). Леви сам является международным мастером спорта по шахматам, победителем чемпионата Шотландии по шахматам (1968-го, в 1975-м разделил первое место со Стивеном Суонсоном), а в 1972 г. играл на первой доске за команду Шотландии на Шахматной олимпиаде в Скопье. Как видите, мы совсем близко, до искомого эндшпиля уже практически рукой подать.

Кроме игры в шахматы и очевидного интереса к теме ИИ, Дэвид Леви также является заядлым спорщиком.

В 1968 г. Леви и Джон Маккарти, один из пионеров шахматного программирования (и автор термина «искусственный интеллект», о чём мы упоминали в начале книги), встретились на вечеринке, устроенной Дональдом Мичи. Маккарти пригласил Леви сыграть в шахматы — и последний одержал победу. Маккарти прокомментировал эту победу словами: «Вы можете победить меня, но через десять лет появится компьютерная программа, которая сможет победить вас». Леви предложил заключить пари, и Маккарти согласился. Спорщики поставили по 500 фунтов, это была более чем внушительная сумма, эквивалентная примерно 14 000 долларов 2023-го. По признанию самого Леви, в то время он зарабатывал 895 фунтов в год. Позже ставка более чем удвоилась, когда к ней присоединились Дональд Мичи, Сеймур Пейперт из Массачусетского технологического института и Эд Коздровицкий из Калифорнийского университета в Дейвисе.

Забегая вперёд, скажем, что Леви одержал победу в этом пари, выиграв в последующие годы несколько матчей против различных программ (Chess 4.5, Каиссы и MacHack), включая решающий матч 1978 г. против программы Chess 4.7 в Торонто^, , а в 1984 г. Леви выиграл вторую, на этот раз пятилетнюю ставку в пари против разработчиков программы Cray Blitz.

Но вернёмся назад, когда исход этого пари ещё был неясен, а Леви не прекращал спорить.

В 1973 г. во время Северо-Американского чемпионата по шахматам среди компьютерных программ (North American Computer Chess Championship, NACCC), организованного Ассоциацией вычислительной техники (Association for Computing Machinery, ACM) в Атланте, Леви поспорил с создателями программы CHAOS, которые выразили сомнение в его заявлении о том, что в течение года они не смогут запрограммировать компьютер для правильной игры в окончании «король и ладья с пешкой против короля и ладьи» так, чтобы машина всегда была способна выиграть, находясь в выигрышной позиции, и никогда не проигрывала в ничейной. Сумма пари составила 100 долларов, и спустя год, в ноябре 1974 г., Леви получил деньги, поскольку программисты признали, что задача оказалась слишком сложной для них.

Однако удача не всегда способствовала Леви, и как минимум одно знаменитое пари он проиграл. Этот спор в истории компьютерных шахмат носит название «Скотч против водки» (Scotch versus Vodka). Как пишет сам Леви, «будучи довольно жадным», он решил повторить успех пари с создателями CHAOS и в декабре 1974 г., находясь в Москве, заключил аналогичное пари с Владимиром Арлазаровым: в случае поражения Леви должен был подарить Арлазарову двенадцать бутылок скотча, а в случае победы Леви должно было достаться двенадцать бутылок водки. Примерно через год спор завершился победой Арлазарова, под началом которого как раз и работали Комиссарчик и Футер, успешно решившие упомянутое окончание при помощи программы, использующей метод ретроспективного анализа^, .

Ещё одна беседа спорщика Леви имела неожиданные последствия. В составе команды разработчиков другой шахматной программы — Belle — в чемпионате 1974 г. участвовал Кен Томпсон, сегодня больше известный как создатель операционной системы Unix (совместно с Деннисом Ритчи), языка программирования Би, ставшего предшественником Си, а также кодировки UTF‑8. Томпсон вспоминает: «…после игр мы разговаривали в баре, и он [Леви] утверждал, что „компьютеры не могут играть эндшпили, даже простые, и они никогда не смогут“. Он сказал: „Я эксперт в окончании «ладья и пешка против ладьи», и компьютер никогда не сможет играть этот эндшпиль“. В тот вечер я пошёл в свою комнату, произвёл расчёты и пришёл к выводу, что задача вычислима, что вы можете получить решение этой игры, решить её с помощью иного механизма, понимаете, не с помощью обычных [алгоритмов] компьютерных шахмат, а совсем другим способом. Вы можете просто получить ответ, посмотреть его и составить таблицу правильных ходов. Вернувшись на следующий день, я сказал ему [Леви] об этом, на что он ответил „не-не, это потребует слишком большого числа полуходов, вы знаете“, на что я сказал „нет, это не зависит от числа полуходов, это другой метод“, но он ответил „о нет“, он просто отмахнулся от меня, и я, знаете, не просто разозлился, это не то слово, я… знаете… знаете… я пошёл домой и около десяти лет посвятил эндшпилям».

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

Альфред Шейнволд, всемирно известный эксперт по бриджу, в одной из своих статей упоминает несколько ценных советов, которые он получил от отца в юности. «Сын! — говорил старший Шейнволд. — Однажды ты встретишь незнакомца, который предложит тебе поспорить на пять долларов, что он сможет заставить пикового вальта выпрыгнуть из колоды и пустить струю пива тебе в ухо. Сын, не спорь с ним, потому что если ты сделаешь это, то получишь полное ухо пива». К глубокому его сожалению, гроссмейстер Уолтер Браун, по всей видимости, игнорировал мудрость предков, поэтому получил струю условного пива в своё условное ухо. Браун позарился на ​​100 долларов, предложенные Томпсоном за победу над машиной в окончании «король и ферзь против короля и ладьи». Несмотря на два с половиной часа, выделенных на обдумывание, и целых пятьдесят ходов, гроссмейстер не смог выполнить задание и был вынужден заплатить. Казалось бы, какая ерунда, любой учебник шахматных окончаний рассказывает, как выиграть с ферзём против ладьи. Это действительно так, при правильной игре сильнейшая сторона гарантированно добивается победы, но оказалось, что это окончание намного сложнее, чем кто-либо мог предположить.

Свои результаты по анализу эндшпиля «ладья и король против ферзя и короля» Томпсон представил в 1977 г. на конференции Международной федерации по обработке информации. Помимо пари с Брауном, Томпсон провёл несколько показательных выступлений. Против программы пытались играть Ханс Берлинер, экс-чемпион мира по переписке, и Лоуренс Дей, чемпион Канады. Ни тот ни другой не смогли выиграть у программы, хотя любая позиция была для них выигрышной. В 1978 г. Брауну удалось наконец взять реванш: забрав ладью ровно на 50-м ходу, он всё-таки смог выиграть в позиции, в которой при идеальной игре победа достигалась за 31 ход.

В 1970–1980-е гг. Томпсоном и другими энтузиастами были посчитаны все четырёхфигурные окончания, а к концу 1980-х — уже и все пятифигурные.

Результаты, полученные Томпсоном, наделали много шума в шахматном мире. «Идеальный игрок», которым стала машина, вскрыл множество человеческих заблуждений относительно шахматной игры. Эффект был столь сильным, что ревизии подверглись даже сами шахматные правила. Мы уже упоминали правило пятидесяти ходов — правило шахматной игры, согласно которому игрок, имеющий очередь хода, имеет право потребовать ничью, если на протяжении последних пятидесяти ходов ни одна фигура не была взята и не было ни одного хода пешкой. Ещё в начале XX в. шахматный композитор Алексей Троицкий доказал, что в некоторых эндшпилях («король и два коня против короля и пешки» и «король, ладья и слон против короля и ладьи») выигрыш достигается более чем за пятьдесят ходов, в связи c чем FIDE в 1928 г. установила в правиле увеличение числа ходов для подобных эндшпилей. Далее это правило ещё несколько изменялось, и к 1982 г. было три вида окончаний, для которых число ходов было увеличено до ста.

Но в 1989 г. из-за данных, полученных Томпсоном, число 50 заменили на 75 (вместо 100) уже для шести видов окончаний. Между тем компьютерный анализ эндшпиля продолжался, было открыто множество новых эндшпилей, нарушающих правило пятидесяти ходов, ввиду чего в 1992 г. было принято соломоново решение: отменить все исключения из правила пятидесяти ходов.

В настоящее время рекордный вариант семифигурного эндшпиля, найденный в 2008 г., представляет собой 517 ходов без взятий при наилучшей игре для окончания «король, ферзь и конь против короля, ладьи, слона и коня».

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

Весной — летом 2012 г. были рассчитаны семифигурные окончания. Авторы таблиц — Владимир Махнычев и Виктор Захаров, сотрудники факультета вычислительной математики и кибернетики (ВМиК) Московского государственного университета им. М. В. Ломоносова. Таблицы названы таблицами Ломоносова, поскольку в расчётах, помимо компьютера IBM Blue Gene/P, был использован суперкомпьютер МГУ «Ломоносов».

В настоящее время существует два альтернативных набора эндшпильных таблиц для всех семифигурных окончаний (Lomonosov и Syzygy), база данных семифигурных эндшпилей в формате Syzygy занимает 17 терабайт дискового пространства.

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

‎

Loading comments...