Решение шахмат состоит из поиска оптимальной стратегии игры в шахматы ; то есть тот, с помощью которого один из игроков ( Белый или Черный ) всегда может добиться победы или любой из них может добиться ничьей (см. Решенную игру ). Это также связано с более общим решением шахматных игр (т.е. комбинаторных игр с совершенной информацией ), таких как шахматы Капабланки и бесконечные шахматы . В более слабом смысле решение шахмат может относиться к доказательству того, какой из трех возможных результатов (выигрыш белых; победа черных; ничья) является результатом двух идеальных игроков, без обязательного раскрытия самой оптимальной стратегии (см. Косвенное доказательство ). [1]
Полного решения шахматной задачи ни в одном из двух смыслов не известно , и не ожидается, что шахматы будут решены в ближайшем будущем (если вообще когда-либо). Существуют разногласия относительно того, будет ли нынешний экспоненциальный рост вычислительной мощности продолжаться достаточно долго, чтобы когда-нибудь можно было решить проблему « грубой силой », то есть путем проверки всех возможностей. Прогресс на сегодняшний день крайне ограничен; существуют таблицы идеального эндшпиля с небольшим количеством фигур (до семи), а некоторые шахматные варианты решены хотя бы слабо. Существуют расчетные оценки сложности дерева игры и сложности пространства состояний шахмат, которые дают общее представление о вычислительных усилиях, которые могут потребоваться для решения игры.
Базы таблиц эндшпиля представляют собой компьютеризированные базы данных, содержащие заранее рассчитанный исчерпывающий анализ позиций с небольшим количеством фигур, оставшихся на доске. Табличные базы в ограниченной степени решают шахматы, определяя идеальную игру в ряде эндшпилей , включая все нетривиальные эндшпили с не более чем семью фигурами или пешками (включая двух королей). [2]
Одним из последствий разработки таблицы эндшпиля из семи фигур стало то, что было найдено множество интересных теоретических шахматных окончаний. Самый длинный пример игры из семи фигур — позиция мат-в-549, обнаруженная в таблице Ломоносова Гаем Хауортом, игнорирующим правило 50 ходов . [3] [4] Такую позицию не способен решить ни один человек, и ни один шахматный движок не разыграет ее правильно, без доступа к базе таблиц, для которой изначально (в 2014 году) требовалось 140 ТБ дискового пространства и использование суперкомпьютера, но позже был уменьшен до 18,4 ТБ с помощью табличной базы Syzygy. По состоянию на январь 2023 года самая длинная известная последовательность принудительных матов для основы стола из восьми частей (также игнорируя правило 50 ходов) составляла 584 хода. Это обнаружил в середине 2022 года Марк Бурзучки. [5] Однако столовая основа из восьми частей в настоящее время неполная, поэтому не гарантируется, что это абсолютный предел для таблицы из восьми частей.
Вариант, впервые описанный Шенноном, представляет собой аргумент в пользу теоретико-игровой ценности шахмат: он предлагает разрешить ход «пас». В этом варианте с помощью аргумента кражи стратегии доказывается, что у первого игрока есть как минимум ничья, таким образом: если у первого игрока есть выигрышный ход в начальной позиции, позвольте ему сделать его, иначе пасуйте. Второй игрок теперь сталкивается с той же ситуацией из-за зеркальной симметрии исходной позиции: если у первого игрока в первом случае не было выигрышного хода, то у второго игрока его нет и сейчас. Следовательно, второй игрок в лучшем случае может сделать ничью, а первый игрок может, по крайней мере, сделать ничью, поэтому идеальная игра приводит к победе или ничьей первого игрока. [6]
Решены некоторые варианты шахмат , более простые, чем шахматы. Выигрышную стратегию черных в партии «Махараджа и сипаи» легко запомнить. Вариант мини-шахматы Гарднера 5 × 5 был слабо решен вничью. [7] Хотя проигрышные шахматы играют на доске 8×8, правило принудительного захвата значительно ограничивает их сложность, и вычислительный анализ позволил слабо решить этот вариант как победу белых. [8]
Перспектива решения отдельных, конкретных шахматных игр становится более трудной по мере увеличения размера доски, например, в больших вариантах шахмат и бесконечных шахматах . [9]
Теоретик информации Клод Шеннон в 1950 году изложил теоретическую процедуру идеальной игры (то есть решения шахмат):
«В шахматах в принципе возможно вести идеальную игру или построить для этого машину следующим образом: в данной позиции рассматриваются все возможные ходы, затем все ходы противника и т. д. до конца игры. (в каждом варианте). Окончание должно наступить по правилам игры после конечного числа ходов (с учетом правила розыгрыша 50 ходов ). Каждый из этих вариантов заканчивается победой, поражением или ничьей. Действуя в обратном направлении от В конце можно определить, есть ли вынужденный выигрыш, позиция ничья или проигрыш».
Затем Шеннон подсчитал, что решение шахмат в соответствии с этой процедурой потребует сравнения примерно 10 120 возможных вариантов игры или наличия «словаря», обозначающего оптимальный ход для каждой из примерно 10 43 возможных позиций на доске (в настоящее время известно, что это примерно 5x10 44 ). [6] [10] Однако количество математических операций, необходимых для решения шахмат, может значительно отличаться от количества операций, необходимых для создания всего дерева игры в шахматы. В частности, если у белых есть форсированный выигрыш, только подмножество дерева игры потребует оценки для подтверждения существования форсированного выигрыша (т. е. без опровержений со стороны черных). Более того, расчеты Шеннона сложности шахмат предполагают, что средняя продолжительность игры составляет 40 ходов, но нет никаких математических оснований утверждать, что вынужденная победа любой из сторон будет иметь какое-либо отношение к этой продолжительности игры. Действительно, некоторые умело сыгранные партии (игра на уровне гроссмейстера) длились всего 16 ходов. По этим причинам математики и теоретики игр неохотно заявляют, что решение шахматной задачи является неразрешимой проблемой. [6] [11]
В 1950 году Шеннон рассчитал, основываясь на сложности дерева игры 10 120 и компьютере, работающем на частоте 1 мегагерц (большая натяжка в то время: UNIVAC 1, представленный в 1951 году, мог выполнять ~ 2000 операций в секунду или 2 килогерца), которые могли оценить терминальному узлу за 1 микросекунду потребуется 10 90 лет, чтобы сделать свой первый ход. Поэтому даже с учетом технического прогресса решение шахматных задач в практических временных рамках кажется выходом за рамки любой мыслимой технологии.
Ханс-Иоахим Бремерманн , профессор математики и биофизики Калифорнийского университета в Беркли , далее утверждал в статье 1965 года, что «скорость, память и вычислительная мощность любого возможного компьютерного оборудования будущего ограничены конкретными физическими барьерами: светом барьер , квантовый барьер и термодинамический барьер . Эти ограничения подразумевают, например, что ни один компьютер, какой бы конструкции он ни был, никогда не сможет изучить все дерево возможных последовательностей ходов в игре в шахматы». Тем не менее Бремерманн не исключал возможности того, что когда-нибудь компьютер сможет решать шахматные задачи. Он писал: «Для того, чтобы компьютер играл в идеальную или почти идеальную игру, необходимо будет либо полностью проанализировать игру… либо проанализировать игру приблизительным образом и совместить это с ограниченным количеством поиска по дереву». ...Однако теоретического понимания такого эвристического программирования все еще очень мало». [12]
Последние научные достижения существенно не изменили эти оценки. Игра в шашки была (слабо) решена в 2007 году [13] , но ее значение примерно равно квадратному корню из количества позиций в шахматах. Джонатан Шеффер , учёный, возглавлявший эту работу, сказал, что прежде чем можно будет попытаться решить шахматные задачи, потребуется такой прорыв, как квантовые вычисления , но он не исключает такой возможности, говоря, что единственное, чему он научился за свои 16-летние усилия: Решение шашек «значит никогда не недооценивать достижения технологий». [14]
В таблице ниже серым цветом отмечены ходы, которые еще не решены.