Шахматы (и варианты) Эндшпиль Сложность

Насколько я понимаю, игра Го с японскими правилами Ко, как и большинство таких игр, является EXPTIME-Complete , но ладдеры являются PSPACE-Complete и что эндшпили в Go были независимо проанализированы как PSPACE-Hard .

Проводились ли подобные исследования шахматных эндшпилей?

Голосование за закрытие - это принадлежит cstheory.stackexchange.com
Это, вероятно, было бы закрыто на cstheory, поскольку здесь не так много проблем на уровне исследований (см. Мой ответ). Я думаю, что в целом достаточно интересно, чтобы спросить здесь.

Ответы (1)

Существует очень большое, но лишь конечное число возможных шахматных партий. Это следствие правила 50 ходов, которое ограничивает максимальное теоретическое количество ходов примерно 5000 (хотя в реальной жизни шахматные партии более 100 ходов крайне редки). Чтобы убедиться в этом, мы знаем, что 50 ходов без хода пешки — это ничья. Пешек 16, и каждая пешка может ходить 6 раз.

Итак, у нас есть 50 * (16 * 6 + 1) + 1 = 4851 ход.

Это означает, что сложность шахмат на самом деле O (1), потому что теоретически с достаточно большой таблицей поиска вы могли бы немедленно найти ответ на любую шахматную позицию. Это порождает забавную идею, впервые описанную Шенноном , об игре между двумя совершенными игроками:

Игра между двумя такими ментальными гигантами, мистером А и мистером Б, будет происходить следующим образом. Они садятся за шахматную доску, рисуют цвета, а затем некоторое время рассматривают фигуры. Тогда либо: -

(1) г. А говорит: «Я ухожу в отставку» или

(2) г. B говорит: «Я ухожу в отставку» или

(3) г. А говорит: «Я предлагаю ничью», а мистер Б отвечает: «Я принимаю».

Конечно, размер этой таблицы поиска совершенно непрактичен (больше, чем число атомов в наблюдаемой Вселенной), но ваш вопрос касается вычислительной сложности, а не практичности!

Отсюда следует, что все шахматные эндшпили также равны O(1). Шахматные позиции до 6 фигур были идеально решены , и таким образом были построены справочные таблицы. Однако размер быстро растет; реализованная база данных из 6 частей составляет около 7 ГБ, а база данных из 7 частей оценивается в 1,2 ТБ.

Если игнорировать ограничения на троекратное повторение , то шахматы становятся PSPACE-жесткими . Если вы также готовы отказаться от правила 50 ходов, тогда шахматы становятся трудными для EXPTIME .

Обратите внимание, что подход с «справочной таблицей» работает только для доски фиксированного размера, тогда как вычислительная сложность — и, в частности, результаты по сложности шахмат — связаны с поведением для досок произвольного размера (где подход с использованием справочной таблицы не имеющий отношения).
Имеет ли значение произвольный размер шахматной партии?
Шахматы (и варианты) Эндшпиль Сложность
СпросиСетьПолитика конфиденциальности1y, 0v