В мае 2016 года австралийский математик Марк Уоткинс опубликовал результат, к которому шахматное сообщество вариантов шло пятнадцать лет: поддавки из стандартной начальной позиции являются форсированным выигрышем за белых ходом 1.e3. Доказательство — вычислительное. Оно потребовало дерева позиций такого размера, что в сжатом виде заняло несколько терабайт хранилища, и распределённой по сообществу Lichess работы по верификации, длившейся несколько лет. Это крупнейшая игра, полностью решённая на сегодняшний день какой-либо группой.

Поддавки — также называемые giveaway chess или losing chess — это вариант, в котором цель перевёрнута: вы выигрываете, потеряв все свои фигуры или оказавшись в пате, причём взятия обязательны всегда, когда они доступны. Правило обязательного взятия резко уменьшает фактор ветвления; во многих позициях есть всего один-два легальных хода; в терминах пространства состояний игра гораздо меньше стандартных шахмат. И всё же доказательство, что 1.e3 выигрывает, заняло пятнадцать лет накопленной работы и было воспринято теоретиками компьютерных игр как эталонное достижение. Подробнее правила и доказательство — в статье о поддавках в Caissly.

Естественный следующий вопрос — можно ли решить стандартные шахматы? — и есть тема этого материала. Короткий ответ: нет, ни в каком сроке, релевантном для людей. Длинный ответ интереснее, потому что он показывает, что значит решить игру и где сегодня лежат границы выполнимого.

Что значит «решена»

В комбинаторной теории игр игра сильно решена, когда для каждой достижимой позиции известны её теоретико-игровое значение (выигрыш, ничья, проигрыш) и оптимальный ход. Слабо решена — известно значение из стандартной начальной позиции и есть алгоритм оптимальной игры из неё. Ультраслабо решена — известно значение, но не оптимальные ходы.

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

Стандартные шахматы не относятся ни к одной из этих категорий. Мы не знаем значение начальной позиции. Консенсус, основанный на анализе движков на глубинах далеко за пределами человеческих, — что начальная позиция ничейна при лучшей игре. Доказательства у нас нет. Мы не решили ни одного из первых десяти ходов до терминального значения. Решены все позиции с семью фигурами и меньше (Ломоносовская семифигурная таблица окончаний), но семь фигур всё ещё далеки от тридцати двух.

Почему шахматы сложнее

Комбинаторный разрыв между поддавками и стандартными шахматами — не вопрос степени. У поддавков около 1040 различных позиций. У стандартных шахмат — около 1044–1047 легальных позиций и 10120 различных партий (число Шеннона, стандартная оценка порядка). Правило обязательного взятия в поддавках схлопывает деревья ходов, которые в стандартных шахматах ветвились бы широко и оставались бы разветвлёнными в течение сотни полуходов. Типичная партия в поддавки длится двадцать–тридцать ходов; типичная партия в стандартные шахматы — сорок–шестьдесят.

В этом центральная асимметрия. Решение игры перебором требует касаться каждой позиции, которую алгоритм не может исключить по симметрии или транспозиции. Для шахмат нижняя граница числа релевантных позиций — около 1040 после агрессивного отсечения, а верхняя — намного выше. Никакая доступная или проектируемая вычислительная среда не обладает ни объёмом хранилища, ни числом операций в секунду, чтобы перебрать это пространство в любом релевантном для людей сроке.

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

Эндшпильные таблицы как частичное решение

Что мы действительно решили — это эндшпиль. Семифигурные таблицы Syzygy и Lomonosov покрывают каждую позицию с семью или менее фигурами в сумме (включая королей). Шестифигурный Syzygy помещается примерно в 150 ГБ; семифигурный — в около 17 ТБ. Каждая позиция в этих регионах имеет вычисленное теоретико-игровое значение и идентифицированный оптимальный ход.

Это действительно полезно. Этюдная и эндшпильная работа на высшем уровне теперь рутинно сверяется с таблицами. Знаменитые позиции — Лусена и Филидор, Ванчура, оппозиция в К+П против К — все подтверждены анализом таблиц уже более десяти лет. Таблицы также дали новые результаты: некоторые семифигурные эндшпили, которые гроссмейстеры столетие считали ничейными, на самом деле выигрываются глубокой игрой с последовательностями в пятьдесят и более ходов, которые человек разумно не находит.

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

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

Что нам оставляет нерешённая игра

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

Шахматы движутся к странному промежуточному состоянию: игра движков настолько сильна, что её принимают как прокси оптимальной, но формально она не доказана оптимальной. Лучшие движки расходятся в отдельных позициях. Новые прогоны обучения Leela Chess Zero дают сдвиги оценок в линиях, считавшихся стабильными. Границу игры исследуют нейросети, а не исчерпывающий перебор.

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

Более широкий вопрос

Иногда утверждают, что любая игра, в которую люди играют достаточно серьёзно, в конце концов будет решена. Поддавки решены компьютерным перебором. Шашки решены. «Четыре в ряд» решены в 1988 году. Реверси слабо решён на 8×8. Закономерность: игры с малым пространством состояний поддаются вычислению, с большим — нет, и шахматы оказываются на «неправильной» стороне этой границы в обозримом сроке.

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

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

Источники

Внутренние ссылки на Caissly: Поддавки — про решённый вариант; Atomic и Шахматы 960 — другие современные варианты. Эндшпильные техники: Позиция Лусены, Позиция Филидора, Позиция Ванчуры.

Выпуск № 004 · Журнал · Редакция Caissly