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