Hacia la EXPTIME-Dureza del Raumschach: Una Construcción de Gadgets Verificada

Una reducción candidata desde la Geografía Generalizada, con corrección de gadgets comprobada mecánicamente — presentada para revisión por pares

Federación Internacional de Raumschach  ·  2026  ·  sustituye a la Sección 6 de Raumschach y Complejidad Computacional, según la Nota Técnica N.º 15 de la IRF

1. Introducción

El resultado clásico de Fraenkel y Lichtenstein (1981) muestra que decidir el ganador de una posición de ajedrez generalizado n×n requiere un tiempo exponencial en n bajo cualquier algoritmo fijo, mediante una reducción desde un juego de fórmulas alternante difícil para PSPACE, jugado sobre un grafo planar. Un obstáculo técnico persistente en dicha construcción, y en trabajos posteriores que la extienden, es que el grafo de flujo de control de la reducción no es planar en general, lo cual obliga a un gadget explícito de “cruce de cables” para enrutar una señal lógica sobre otra en un tablero bidimensional.

El Raumschach, la variante de ajedrez tridimensional de 5×5×5 ideada por Ferdinand Maack (1907), elimina este obstáculo por una razón estructural: un tablero con una tercera dimensión espacial genuina admite dos corredores que no comparten un plano, de modo que el cruce no es un caso especial que requiera su propio gadget — es simplemente dos caminos disjuntos. Este artículo desarrolla esa observación hasta convertirla en una reducción candidata y reporta, en su totalidad, tanto el estado actual de la reducción como un error encontrado y corregido en el proceso de comprobarla.

Este trabajo sigue un arco de desarrollo registrado internamente en las Notas Técnicas de la IRF 1–15 (las Notas 1–14 se conservan como registro institucional, no publicadas por separado) y el artículo consolidado Raumschach y Complejidad Computacional, al cual este artículo sustituye específicamente en lo referente a la construcción de puerta AND / condición de victoria (Sección 6 de dicho artículo), según la errata de la Nota Técnica 15, que sí está publicada. Los lectores que deseen el análisis de espacio de estados y tamaño del árbol de juego, que no se ve afectado por nada en este artículo, deben consultar directamente dicho artículo.

Qué es este artículo, y qué no es. Este es un informe técnico que describe un esbozo de reducción, un conjunto de gadgets, y un programa de verificación computacional de dichos gadgets en instancias finitas — incluyendo un ejemplo no trivial completamente trabajado con seis variables booleanas, juego alternante real, y jaque mate confirmado. No es una prueba matemática general y terminada de que la reducción sea correcta para un tamaño de fórmula arbitrario, y no afirmamos aquí la EXPTIME-dureza como un teorema establecido. Describimos exactamente dónde se encuentra actualmente la brecha entre “verificado en las instancias que comprobamos” y “demostrado para todas las instancias”, en la Sección 8.

2. Preliminares

2.1 Raumschach

El Raumschach se juega en un tablero de 5×5×5, con coordenadas (L, f, r) ∈ {1,…,5}³ en la notación estándar (nivel, columna, rango). Las piezas incluyen la Torre, el Alfil, la Reina, el Rey y el Peón habituales, más el Unicornio, que se mueve a lo largo de rayos triagonales puros — las tres coordenadas cambiando en ±1 en cada paso. Para la reducción, trabajamos sobre un tablero ampliado n×n×n, con n polinómico en el tamaño de la fórmula, siguiendo la práctica habitual en esta línea de trabajo de usar un tablero sobredimensionado para incrustar una reducción y luego argumentar que la construcción respeta cualquier conjunto de piezas y reglas de movimiento que defina el juego base.

2.2 El Problema de Origen

Reducimos desde un juego de fórmulas de dos jugadores y movimiento alternante, al estilo de las formulaciones de Geografía Generalizada / juego-QBF usadas en construcciones de tipo Fraenkel–Lichtenstein: una fórmula booleana φ(x₁,…,x_n) en alguna base fija (aquí, AND y OR bastan, por la ley de De Morgan y la disponibilidad de un NOT real mediante la asignación de jugador — véase la Sección 7), junto con una partición de las variables entre dos jugadores, Jugador A y Jugador B, y un orden fijo en el que se establecen. El Jugador A gana si la asignación resultante satisface φ; el Jugador B gana en caso contrario. Decidir qué jugador tiene una estrategia ganadora para tales juegos es PSPACE-completo en general, y la literatura de reducciones de ajedrez además compone esto con consideraciones de tamaño de tablero para obtener EXPTIME-dureza para el problema de decisión en tableros de tamaño adecuado. No re-derivamos aquí ese fundamento general de teoría de la complejidad; lo tomamos como el objetivo y nos centramos en la reducción a nivel de tablero.

2.3 Qué Debe Hacer una Reducción Correcta

Una reducción de este juego a la determinación del ganador de una posición de Raumschach debe exhibir, para toda fórmula φ y partición/orden de variables, una posición de Raumschach tal que: (a) la posición pueda construirse en tiempo polinómico en |φ|; (b) los movimientos de los dos jugadores en la partida de ajedrez resultante correspondan exactamente a sus elecciones de asignación de variables, en el mismo orden; y (c) las Blancas (sin pérdida de generalidad, el jugador que representa a A) tengan una victoria forzada en la partida de ajedrez si y solo si A tiene una estrategia ganadora en el juego de fórmulas. Cada gadget de la Sección 4 existe para hacer cumplir alguna parte de esta correspondencia; la Sección 5 establece, gadget por gadget, de qué parte es responsable.

3. Panorama General de la Reducción

El tablero se divide en regiones disjuntas: una región por cada variable de la fórmula (un corredor que termina en un punto de ramificación binario, según la Sección 4.1), una región por cada conectivo lógico en el árbol de análisis de la fórmula (una instancia de puerta OR o AND, Secciones 4.3–4.4), relleno de fusible de sincronización de tiempos allí donde dos corredores de longitud natural distinta alimentan el mismo punto en el orden de alternancia (Sección 4.5), y un único gadget de condición de victoria (Sección 4.6) cuya propia legalidad se conecta — no se compone por casilla compartida, véase la Sección 5.4 — al valor de verdad final de la fórmula. La seguridad del Rey se establece una sola vez, con independencia de la fórmula (Sección 4.6.1), usando seis de las siete direcciones de casilla de huida tridimensionales del Rey selladas con material de bloqueo ordinario, y dejando la séptima abierta específicamente para que la cierre el propio mecanismo de jaque descubierto del gadget de condición de victoria.

4. Gadgets

4.1 Corredor de Variable

Cada variable x_i controlada por un jugador dado se representa mediante un Peón confinado a una sola columna, que avanza una casilla por movimiento (los Peones de Raumschach, como su contraparte bidimensional, se mueven exactamente una casilla hacia adelante por movimiento no capturador), con el ascenso (el segundo tipo de movimiento de un solo paso del Peón, que cambia el nivel en uno) bloqueado por una Torre inmóvil en cada casilla a lo largo del corredor excepto la última. En la casilla final, tanto el avance frontal como el ascenso se dejan abiertos: el ascenso representa x_i = Verdadero (el Peón abandona por completo el nivel del corredor), el avance frontal continuado representa x_i = Falso. Esta es una bifurcación binaria real, de elección única, resuelta mediante un movimiento efectivo contra el generador de movimientos legales real, no un valor asumido de antemano.

4.2 Cruce de Nivel (Vía)

Cuando un camino de señal en el árbol de análisis de la fórmula necesitaría, en un tablero bidimensional, cruzar otro camino de ese tipo, se usa directamente la tercera dimensión del Raumschach: el camino que cruza se enruta a través de un nivel adyacente, con un ascenso de Peón que cambia de nivel (o un paso de Alfil/Unicornio, según el tipo de pieza del corredor) sirviendo como la “vía”. No se necesita ningún gadget de cruce dedicado del tipo que requiere la construcción planar de Fraenkel–Lichtenstein; dos corredores en niveles distintos simplemente no se intersecan.

4.3 Puerta OR

A un único testigo de Torre se le dan exactamente dos direcciones de torre activas, cada una amurallada de forma independiente por un testigo de negación: presente (bloqueando) si la entrada correspondiente es Falsa, ausente si es Verdadera. Las otras cuatro direcciones están permanentemente amuralladas. El testigo tiene un movimiento legal si y solo si al menos una de sus dos direcciones controladas está abierta, es decir, si y solo si al menos una entrada es Verdadera — realizando OR. Este gadget no ha cambiado respecto de la Sección 7 del artículo consolidado y no se ve afectado por el error descrito en la Sección 6 más adelante, porque su propio testigo no se sitúa en el rayo de ninguna pieza de jaque.

4.4 Puerta AND (Corregida)

Véase la Sección 6 para el error encontrado en la versión originalmente especificada de este gadget, y la Sección 7 para el diseño corregido: una Torre completamente sellada (las cuatro direcciones laterales y la dirección de "sentido equivocado" amuralladas) con exactamente un testigo bloqueador adyacente, presente si y solo si NO(x_a AND x_b). Este diseño se generaliza a más de dos entradas únicamente anidando instancias de sí mismo (un AND de ANDs), no encadenando múltiples testigos a lo largo de la línea propia de una puerta; véase la Sección 7.2.

4.5 Fusible de Sincronización de Tiempos

Cuando dos corredores que alimentan el mismo punto en el orden de alternancia tienen longitudes naturales distintas (número de movimientos de avance forzado antes de su punto de ramificación), el corredor más corto se rellena con casillas adicionales de avance forzado (ascenso bloqueado, como en la Sección 4.1) de modo que ambos corredores alcancen su punto de ramificación tras el mismo número de movimientos. Esto preserva la alternancia estricta de movimientos entre los dos jugadores a través de corredores paralelos de longitud, por lo demás, desigual.

4.6 Gadget de Condición de Victoria

Una Torre V se sitúa en el único punto del tablero donde su propia línea de rango se cruza con un rayo triagonal hacia el Rey — el mismo rayo que ya ocupa un Unicornio de jaque designado, colocado más lejos en ese rayo con un camino despejado. Las cuatro direcciones laterales de V y su dirección de "sentido equivocado" están permanentemente selladas; su única dirección restante contiene exactamente un testigo bloqueador adyacente (Sección 7.1), presente si y solo si la fórmula global es Falsa. Si V tiene un movimiento legal — lo cual, dado el sellado, ocurre si y solo si la fórmula es Verdadera —, realizar ese movimiento desocupa la casilla de origen de V, descubriendo el jaque del Unicornio a lo largo del rayo ahora despejado directamente hacia el Rey.

4.6.1 Seguridad del Rey

Las seis direcciones de casilla de huida tridimensionales restantes del Rey (de su movilidad completa de 26 vecinos, menos la dirección a lo largo del rayo triagonal usado arriba) se sellan con material de bloqueo ordinario (Peones, Torres, Alfiles defendiéndose mutuamente según sea necesario), con independencia de la fórmula, de modo que la única manera en que la posición del Rey cambia de "seguro, una casilla de huida" a "en jaque mate, cero casillas de huida y en jaque" es mediante el mecanismo de 4.6, que está controlado únicamente por el valor de verdad de la fórmula.

5. Corrección, Gadget por Gadget

Enunciamos la propiedad de corrección de la que cada gadget es responsable. Estas se enuncian al nivel de rigor que un revisor por pares debería poder comprobar mediante inspección de la construcción y, donde exista verificación computacional, confirmar además que la afirmación se cumplió en las instancias comprobadas; no se presentan como pruebas formales verificadas por máquina.

5.1 (Corredor de variable). Para cada variable x_i, el Peón del corredor tiene exactamente un movimiento legal en cada casilla antes de la final (forzado, no informativo respecto de x_i), y exactamente dos movimientos legales en la casilla final, cuyos destinos son distinguibles únicamente por si el destino comparte el nivel del corredor con el origen (Falso) o no (Verdadero). Verificado computacionalmente para longitudes de corredor de hasta 3 con relleno de fusible, Sección 9.

5.2 (Puerta OR). El testigo OR tiene un movimiento legal si y solo si al menos un testigo de negación de entrada está ausente. Verificado computacionalmente para todas las combinaciones de entrada de hasta 4 entradas (dos instancias independientes de 2 entradas alimentando una tercera puerta), Sección 9.

5.3 (Puerta AND, corregida). El testigo AND tiene un movimiento legal si y solo si el bloqueador adyacente está ausente, lo cual está conectado para ocurrir si y solo si ambas entradas son Verdaderas. Esta no es una afirmación sobre una cadena de testigos independientemente móviles (que la Sección 6 demuestra falsa); es una afirmación sobre la presencia o ausencia de un único testigo, una propiedad más simple y, creemos, ahora correctamente enunciada. Verificado computacionalmente para todas las combinaciones de hasta 6 variables compuestas a través de 4 instancias de puerta, Sección 9.

5.4 (Composición). Instancias de puerta distintas ocupan casillas de tablero disjuntas y líneas infinitas disjuntas (ejes de torre, diagonales de alfil, triagonales de unicornio), excepto donde una conexión es intencional (por ejemplo, la salida de una puerta OR conectada al bloqueador de una puerta AND), comprobado mecánicamente mediante un registro de colisión de coordenadas (Sección 9.1) en lugar de por inspección manual. Consideramos que este registro, y no la revisión humana, es el estándar de evidencia apropiado para esta afirmación específica, ya que el propio error de la Nota 15 surgió exactamente del tipo de coincidencia accidental que el registro está construido para detectar.

5.5 (Condición de victoria). V tiene un movimiento legal si y solo si el valor de fórmula conectado es Verdadero, y realizar ese movimiento produce jaque mate real (Rey en jaque, cero respuestas legales), confirmado contra el generador de movimientos legales en lugar de asumido a partir de la descripción geométrica del gadget. Verificado computacionalmente para el ejemplo trabajado de la Sección 9.3.

6. Un Error Encontrado, y Qué Enseña

La construcción de puerta AND originalmente propuesta (Sección 6 del artículo consolidado, antes de la corrección de este artículo) encadenaba múltiples testigos booleanos independientemente móviles directamente a lo largo de la propia línea de rango de V, con el razonamiento de que la retirada de V es legal solo una vez que todos los testigos han desocupado su casilla. La comprobación mecánica, usando el mismo generador de movimientos legales en el que se apoya todo este proyecto, encontró que esto era falso: el rayo del Unicornio de jaque se descubre en el instante en que V abandona su casilla de origen, por cualquier motivo y hacia cualquier destino — no solo al alcanzar una casilla específica y totalmente retirada. En consecuencia, solo importa el testigo más cercano a V: en cuanto este desocupa su casilla, V tiene algún movimiento legal con independencia del estado de cualquier testigo más adelante en la línea, y el mate se sigue de todos modos. La construcción, tal como estaba especificada, calculaba algo más cercano a OR que al AND afirmado. Los detalles completos, incluido el caso que aísla esto de cualquier artefacto de colocación, se registran en la Nota Técnica 15 de la IRF.

Reportamos esto no meramente como una errata, sino porque ilustra un riesgo específico de este estilo de construcción: los gadgets construidos alrededor de una única pieza física que sirve simultáneamente como elemento computacional (aquí, una cadena bloqueadora de línea de rango) y como componente del mecanismo de entrega de mate (situada en el rayo de una pieza de jaque) se validan, mediante una comprobación sustituta incompleta, de una manera que parece sólida hasta que el propio mecanismo de mate se comprueba directamente y en combinación. Toda prueba en este proyecto anterior a la que encontró este error comprobaba la alcanzabilidad de una casilla específica en lugar de la condición de victoria real (si V tiene algún movimiento legal en absoluto); ambas coinciden únicamente en el caso de una sola entrada. Consideramos esto una advertencia para los revisores de este estilo de construcción en general, no solo para este gadget específico.

7. La Construcción Corregida

7.1 Un Solo Testigo, Completamente Sellado

La reparación (Secciones 4.4, 4.6) restringe a V, y a cualquier puerta AND construida sobre el mismo principio, a exactamente un testigo bloqueador adyacente, con todas las demás direcciones — incluida la dirección de "sentido equivocado" a lo largo del eje propio de la puerta — permanentemente selladas. Este caso se reconfirmó directamente como sólido: la presencia del testigo implica cero movimientos legales; su ausencia implica exactamente un movimiento legal, cuya ejecución produce jaque mate confirmado (para V específicamente) o la señal lógica pretendida (para una puerta AND interior).

7.2 Composición por Desacoplamiento, No por Compartición

Las fórmulas multivariable se manejan calculando el valor de cada subfórmula usando puertas construidas enteramente sobre coordenadas disjuntas de V y de cualquier rayo de pieza de jaque, de modo que el movimiento propio del testigo de ninguna subpuerta pueda desencadenar por sí mismo un jaque descubierto, y conectando el valor resultante al único bloqueador adyacente de la siguiente puerta hacia arriba en el árbol (en última instancia, de V). Un AND de más de dos entradas se realiza anidando instancias de puerta AND (un AND de ANDs), no añadiendo testigos a la línea de una sola puerta.

Esta reparación tiene un costo real, expresado con claridad y no minimizado: ya no es cierto que una sola pieza física pueda cumplir triple función como testigo móvil propio de una subfórmula, bloqueador de línea de rango, y pieza en el rayo de jaque, todo simultáneamente, de la manera en que la construcción original preveía y en que una etapa anterior del propio trabajo de verificación de este proyecto (antes de la Nota 15) asumía sin comprobar. La composición ahora requiere un paso de conexión explícito entre una subfórmula verificada y el único testigo que importa para la siguiente puerta hacia arriba. Si existe una construcción que recupere la composición de un solo testigo sin conexión explícita sin reintroducir la falla de la Sección 6, es, hasta donde sabemos, una cuestión abierta.

8. Qué Está Establecido y Qué No

Consideramos importante, para un documento destinado a revisión por pares, ser inequívocos al respecto.

Establecido, en el sentido de comprobado mecánicamente en instancias finitas: la propiedad de corrección enunciada de cada gadget individual (Sección 5), para los tamaños de instancia específicos probados; la ausencia de colisión de coordenadas para las instancias ensambladas específicas probadas; y, para una fórmula trabajada de seis variables con juego alternante real y dos corredores sincronizados en tiempo, que la tubería completa — corredores, puertas, composición, condición de victoria — produce un valor minimax que coincide con el razonamiento independiente de teoría de juegos sobre dicha fórmula, con la posición final de la línea ganadora confirmada como jaque mate real contra el generador.

No establecido: una prueba general y paramétrica en tamaño (por ejemplo, por inducción sobre la estructura de la fórmula) de que la construcción es correcta para n arbitrario, profundidad de anidamiento arbitraria, y partición variable-jugador arbitraria; una contabilidad formal de todas las reglas de Raumschach no ejercitadas por los gadgets tal como están construidos (capturas que interactúan con material de gadgets más allá de lo que anticipan los muros propios de cada gadget, promoción, cualquier interacción con la repetición triple o la regla de los cincuenta movimientos, y sutilezas de piezas defendidas más allá del argumento de seguridad del Rey de 4.6.1); una prueba formal verificada por máquina o a mano en el sentido que un teórico de la complejidad exigiría para un teorema de dureza apto para publicación; y una cota formal que relacione el tamaño de la fórmula con el tamaño de tablero construido n (necesaria para confirmar que la reducción es genuinamente de tiempo polinómico, no solo de apariencia polinómica en las instancias probadas).

Describimos, en consecuencia, la afirmación general de este artículo como: un conjunto de gadgets corregido que sobrevive a toda comprobación que hemos podido ejecutar contra un generador independiente, presentado junto con dichas comprobaciones, en apoyo de un resultado conjeturado de EXPTIME-dureza para el Raumschach que aún no hemos demostrado en general.

9. Metodología de Verificación Computacional

9.1 Registro de Colisión de Coordenadas

Cada instancia de gadget declara las casillas de tablero que ocupa y, para cada pieza móvil, las líneas infinitas (eje de torre, familia de plano diagonal de alfil, familia triagonal de unicornio) por las que en principio podría deslizarse. Un registro comprueba, a medida que cada gadget se añade a un ensamblaje, si comparte una casilla o línea con cualquier gadget añadido previamente con el que no haya declarado explícitamente una conexión intencional. Esta comprobación es estática (geométrica), independiente de la legalidad de movimiento, y está diseñada específicamente para detectar la clase de error — dos gadgets independientemente correctos que coinciden por casualidad de coordenadas — que este proyecto ha encontrado más de una vez en gadgets construidos antes de que existiera el registro.

9.2 Generador de Movimientos Legales

Se usa un generador de movimientos independiente (movimientos deslizantes de Torre, Alfil, Unicornio, Reina; paso y seguridad del Rey; avance de un paso y ascenso del Peón) para comprobar directamente cada afirmación de gadget: conjuntos de movimientos legales en posiciones específicas, estado de jaque/jaque mate del Rey mediante square_attacked_by y enumeración completa de movimientos del Rey, y, para el ejemplo compuesto, una búsqueda completa por inducción hacia atrás sobre cada turno de ramificación real.

9.3 Ejemplo Trabajado

La fórmula φ = (OR(x₁,x₂) AND OR(x₃,x₄)) OR AND(x₅,x₆), seis variables, con el Jugador A controlando x₁,x₄,x₅ y el Jugador B controlando x₂,x₃,x₆, se ensambló con el corredor de x₁ a longitud natural 3 y el de x₂ a longitud natural 1 rellenado con un fusible de 2 movimientos, ambos confirmados para alcanzar su punto de ramificación en sincronía tras exactamente 3 movimientos forzados cada uno, intercalados turno por turno. La inducción hacia atrás completa sobre el árbol de juego resultante de 64 hojas encontró que A tiene una victoria forzada (φ = Verdadero bajo juego óptimo), lo cual coincide con el razonamiento independiente: A controla una variable en cada cláusula OR del primer disyunto de la fórmula y puede forzar ambas cláusulas a Verdadero unilateralmente, con independencia de cualquier elección disponible para B. La posición terminal de la línea ganadora se confirmó como jaque mate genuino — Rey en jaque, cero respuestas legales — contra el generador, no asumido a partir de la geometría de la construcción.

10. Trabajo Relacionado

Fraenkel y Lichtenstein (1981) establecieron el resultado fundacional del cual desciende la afirmación de complejidad que este artículo persigue, incluido el obstáculo de cruce de cables que el uso de una tercera dimensión espacial de este artículo pretende eludir. No tenemos conocimiento de trabajo previo que aplique esta observación específica al Raumschach; el artículo consolidado que este documento sustituye en parte (Sección 6) representa un intento anterior de este mismo proyecto, corregido aquí.

11. Conclusión

Hemos presentado un conjunto de gadgets para reducir un juego de fórmulas booleanas alternante a la determinación del ganador de una posición de Raumschach, corregido un error de solidez genuino encontrado durante la verificación mecánica (documentado por separado en la Nota Técnica 15), y verificado computacionalmente la construcción corregida en instancias de hasta seis variables con juego alternante real y jaque mate confirmado. Consideramos que los gadgets individuales y su composición están bien respaldados por esta comprobación, y consideramos que la prueba general de corrección para n arbitrario, junto con una contabilidad completa de las reglas del Raumschach más allá de lo que ejercitan los gadgets, es trabajo abierto. Presentamos este artículo en ese espíritu: como un esbozo riguroso y de alcance honestamente delimitado para revisión, no como un resultado cerrado.

Referencias

• 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.
• Federación Internacional de Raumschach. (2026). Raumschach y Complejidad Computacional: Espacio de Estados, Tamaño del Árbol de Juego y un Esbozo de EXPTIME-Dureza. complexity-of-raumschach.html (el análisis de espacio de estados y tamaño del árbol de juego no se ve afectado por este artículo; la Sección 6 fue sustituida según la Nota Técnica 15).
• Federación Internacional de Raumschach. (2026). Nota Técnica N.º 15 de la IRF: La Puerta AND No Filtra. technical-notes-15.html (el error corregido en las Secciones 6–7 de este artículo, en su totalidad).
• Federación Internacional de Raumschach. (2026). Notas Técnicas de la IRF, N.º 1–14 (registro de desarrollo interno anterior al artículo consolidado; no publicadas por separado).
• Maack, F. (1907). Raumschach (descripción original de la variante de 5×5×5).