Raumschach и вычислительная сложность: пространство состояний, размер дерева партии и набросок EXPTIME-трудности

Сводная техническая работа, заменяющая собой Технические заметки IRF №№ 1–14

Международная федерация Raumschach  ·  2026

1. Введение

Плоские шахматы EXPTIME-полны в своей обобщённой (n×n) форме (Fraenkel & Lichtenstein, 1981), а их пространство состояний оценивается начиная с Шеннона (1950) примерно в 10⁴³–10⁴⁷ легальных позиций, со сложностью дерева партии около 10¹²³. Сопоставимого анализа для Raumschach, трёхмерного шахматного варианта д-ра Фердинанда Маака 1907 года, играемого на доске 5×5×5, прежде не существовало. Эта работа представляет такой анализ: комбинаторное сравнение (раздел 2), структурный аргумент в пользу того, почему доказательство трудности плоских шахмат правдоподобно распространяется на Raumschach (раздел 3), и набор проверенных гаджетов, в принципе достаточных для явного осуществления этого распространения (разделы 4–7).

Эта работа заменяет собой Технические заметки IRF №№ 1–14, которые полностью фиксировали процесс разработки, включая несколько найденных и исправленных по пути ошибок. Читателям, которым нужно лишь текущее, корректное состояние этой работы, следует читать настоящую статью. Те заметки сохранены внутренне как институциональная запись процесса разработки, включая три отдельные ошибки в гаджете условия победы, некорректное утверждение о блокировании Единорогом и подлинную коллизию расстановки между двумя гаджетами, но отдельно не публикуются.

2. Пространство состояний и сложность дерева партии

Доска Raumschach из 125 ячеек (пять уровней 5×5) несёт 20 фигур на сторону против 64 ячеек и 16 фигур на сторону у плоских шахмат. Комбинаторное сравнение расстановок первого порядка, выбирающее занятые ячейки без учёта различимости типов фигур — то же упрощение, что использовала исходная шенноновская оценка шахмат, — даёт:

C(64,32) ≈ 10^18.3   (плоские шахматы)
C(125,40) ≈ 10^32.9   (Raumschach)

Один лишь объём доски и число фигур поднимают комбинаторный потолок примерно на пятнадцать порядков величины. Оценка сложности дерева партии, следуя методу Шеннона возведения коэффициента ветвления в степень типичной длины партии, использует дебютный коэффициент ветвления Raumschach в 61 псевдолегальный ход (против 20–35 у шахмат) и сопоставимый показатель степени длины партии:

35⁸⁰ ≈ 10^123.5   (плоские шахматы)
61¹⁰⁰ ≈ 10^178.5   (Raumschach)

Обе оценки представляют собой приближения порядка величины, а не точные подсчёты, предложенные как первое приближение в ожидании более строгой мультиномиальной коррекции на различимость типов фигур. Ни одна из игр не решена в формальном смысле; фронтир исчерпывающей проверки плоских шахмат простирается до эндшпильных таблиц для семи фигур, а ближайший аналог для Raumschach — собственная работа IRF по эндшпильным вердиктам (Серия Raumschach, том V).

3. На пути к EXPTIME-трудности: метод редукции и аргумент в пользу трёх измерений

Доказательство Френкеля–Лихтенштейна редуцирует от G3, булевой формульной игры, уже известной как EXPTIME-полная (Chandra & Stockmeyer, 1976), кодируя произвольный экземпляр G3 в виде шахматной позиции, построенной из небольшого каталога гаджетов: гаджеты рёбра/коридора, представляющие значение истинности переменной как положение токена внутри огороженного стенами коридора; гаджеты вершины/узла, объединяющие несколько коридоров в логические И/ИЛИ; и гаджет победы, обеспечивающий форсированный мат ровно тогда, когда закодированная формула удовлетворена. Самый технически требовательный компонент исходной двумерной конструкции — это гаджет пересечения, необходимый всякий раз, когда два коридора должны пересечься на плоскости без нелегального взаимодействия, — следствие принудительного размещения произвольной (и, как правило, непланарной) булевой схемы на двумерной доске.

Третье измерение Raumschach устраняет это препятствие, а не добавляет новое: два коридора, которым потребовалось бы пересечься на одном уровне, вместо этого могут занимать разные уровни, в точности как многослойная трассировка схем избегает проблемы пересечения, с которой сталкивается однослойная трассировка. Это структурный аргумент, а не доказательство, но он выявляет самый трудный из известных компонентов редукции и даёт конкретную, обусловленную геометрией доски причину ожидать, что версия Raumschach будет не труднее в построении, а правдоподобно даже проще. Разделы 4–7 представляют гаджеты, которые осуществили бы эту конструкцию, каждый вычислительно проверен на явном генераторе легальных ходов.

4. Метод проверки

Каждый гаджет ниже был проверен на специально построенном для Raumschach генераторе легальных ходов, реализующем правила движения Ладьи (6 лучей), Слона (12 направлений), Единорога (8 триагоналей), Ферзя (Ладья±Слон, 18 направлений), Короля (26 шагов, с легальностью хода, корректно исключающей поля, атакованные соперником) и Пешки (продвижение вперёд и восхождение вверх), заданные в Серии Raumschach, том I. Координаты задаются как (У,к,р) на обобщённой доске со стороной n, следуя соглашению, что вопрос сложности касается масштабируемого семейства досок, а не фиксированной игры при n = 5. Проверка проводилась путём прямого запроса вывода легальных ходов генератора против заявленного поведения для каждой релевантной комбинации входов гаджета, а не одним лишь рассуждением на бумаге; несколько утверждений, казавшихся корректными при осмотре, не пережили эту проверку, и здесь приведены только исправленные, выжившие конструкции.

5. Гаджеты коридора и межуровневого перехода

Коридор — это цепочка Слонов, продвигающихся на один шаг за раз вдоль фиксированного уровня, огороженная фланкирующими Пешками с обеих сторон. Каждая фланкирующая Пешка обездвижена тремя независимыми условиями: её продвижение вперёд заблокировано второй, поддерживаемой Пешкой непосредственно впереди; её восхождение вверх — путь, не имеющий аналога в плоских шахматах, — заблокировано неподвижной фигурой прямо над ней; и ни одна вражеская фигура никогда не размещается в пределах досягаемости взятия. Все три условия были проверены напрямую: фланкирующая Пешка, построенная таким образом, возвращает ноль легальных ходов на генераторе.

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

6. Комбинированный вентиль И и условие победы

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

Король размещается в углу доски, (1,1,1), сокращая свои поля бегства с общих 26 до 7. Шесть из этих семи полей бегства запечатаны навсегда: три смежных по граням поля — занимающей их Пешкой, защищённой Ладьёй дальше по той же линии (незащищённый блокиратор попросту берётся Королём, первая найденная ошибка); три рёберно-диагональных поля — Слонами, расположенными так, что их накрывающая диагональ не проходит через само поле Короля (Слон, накрывающий поле бегства с той же диагонали, на которой стоит Король, также безусловно и напрямую атакует Короля, вторая найденная ошибка). Седьмое поле бегства, триагонально смежное с Королём, намеренно оставлено открытым.

Единственная Ладья, V, служит одновременно фигурой-заполнителем, блокирующей триагональный подступ к открытому полю бегства, и самим вентилем И, закреплённым в той единственной точке, где её собственная рядовая линия пересекается с этой триагональной линией. Булевы входные токены (Ладьи, для произвольного числа переменных — механизм был проверен на масштабирование до трёх входов без изменений) стоят дальше по рядовой линии V, каждый блокирует отступление V, представляя Ложь, и ответвляется от линии, представляя Истину. Отступление V легально тогда и только тогда, когда каждый токен ответвился — n-арное И, проверенное для n = 2 и n = 3. Как только оно становится легальным и совершается, отступление V открывает триагональную линию для отдельного атакующего Единорога, занимающего то же поле, которое покинула V. С этого поля луч Единорога проходит через прежде открытое поле бегства и объявляет Королю шах в тот же момент, поскольку оба поля лежат на одной и той же триагональной линии — шах и закрытие последнего поля бегства Короля наступают вместе, а не как раздельные по времени события.

Обе конечные точки этой конструкции были проверены напрямую: при наличии V подтверждено, что Король не под шахом и сохраняет своё единственное легальное поле бегства для каждой комбинации булевых входов (нетерминальное, безопасное независимо от формулы состояние); при уходе V и занятии её места атакующим Единорогом подтверждено, что Король под шахом с нулём легальных ходов — мат, — достижимый лишь через легальную последовательность, которую допускает вентиль И.

7. Вентиль ИЛИ

Булево ИЛИ реализуется без нового примитива движения, используя собственный набор независимых направлений лучей одной Ладьи как объединение. Токену выделяются два из его шести ладейных направлений, каждое независимо огорожено от четырёх остальных направлений токена; одно направление блокируется суб-токеном, представляющим отрицание первой входной переменной, другое — суб-токеном, представляющим отрицание второй. У главного токена есть некоторый легальный ход бегства тогда и только тогда, когда открыто хотя бы одно из двух направлений — прямое ИЛИ над двумя входами, проверенное для всех четырёх комбинаций входов.

Размещение этого гаджета требует осторожности: ранняя попытка интеграции разместила его огораживающие фигуры на той же координатной оси, что и Ладья вентиля И / условия победы из раздела 6, незаметно блокируя отступление этой Ладьи независимо от любого булева входа, исключительно вследствие повторного использования координат, а не какого-либо логического изъяна в любом из гаджетов. Исправленное размещение, на полностью не пересекающемся наборе координат, было проверено как не вносящее подобной интерференции.

8. Обсуждение и будущая работа

Каждый гаджет, необходимый для кодирования произвольной булевой формулы в том стиле, которого требует редукция Френкеля–Лихтенштейна — коридор, межуровневый переход, И, ИЛИ и зависящее от формулы условие победы, — теперь существует в форме, проверенной на фактической генерации легальных ходов Raumschach, а не только рассуждением на бумаге. То, что остаётся и не заявляется здесь, троично. Во-первых, полная сборка: взять произвольную, нетривиальную формулу G3 и фактически разместить полный набор требуемых ею гаджетов на одной доске, включая механизм выравнивания темпа (предохранитель), необходимый, когда коридоры разной длины должны оставаться синхронизированными со строгим чередованием ходов G3. Во-вторых, дисциплина распределения координат или процесс автоматизированной проверки коллизий для этой сборки; интерференция гаджета ИЛИ, обнаруженная в разделе 7, иллюстрирует, что ручное размещение координат не масштабируется надёжно за пределы горстки гаджетов. В-третьих, полностью формальное доказательство — проверенное вручную или независимым компьютерным поиском и пригодное для подачи в рецензируемое издание — того, что собранная конструкция корректно редуцирует от G3 для каждого экземпляра, а не только для проверенных на сегодня небольших случаев. Каждая из этих задач — существенный, но ограниченный объём инженерной работы, а не дальнейший открытый теоретический вопрос; теория, по состоянию на эту работу, по существу завершена для случая двух вентилей, и то, что остаётся, — это построение в масштабе.

Источники

• Chandra, A. K., & Stockmeyer, L. J. (1976). Alternation. 17th Annual Symposium on Foundations of Computer Science, 98–108.
• Fraenkel, A. S., & Lichtenstein, D. (1981). Computing a perfect strategy for n×n chess requires time exponential in n. Journal of Combinatorial Theory, Series A, 31(2), 199–214.
• Robson, J. M. (1984). N by N checkers is Exptime complete. SIAM Journal on Computing, 13(2), 252–267.
• Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275.
• Brunner, J., Chung, L., et al. (2020). Complexity of retrograde and helpmate chess problems: even cooperative chess is hard. ISAAC 2020.
• Международная федерация Raumschach. (2026). The Raumschach Series, тома I–VI: Theory and Endgame Verdicts. theory1.html
• Международная федерация Raumschach. (2026). IRF Technical Notes, Nos. 1–14 (внутренний журнал разработки; заменён этой работой и отдельно не публиковался).