Raumschach y Complejidad Computacional: Espacio de Estados, Tamaño del Árbol de Juego y un Esbozo de EXPTIME-Dureza
Un artículo técnico consolidado, que sustituye a las Notas Técnicas de la IRF N.º 1–14
1. Introducción
El ajedrez plano es EXPTIME-completo en su forma generalizada (n×n) (Fraenkel & Lichtenstein, 1981), y su espacio de estados se ha estimado desde Shannon (1950) en aproximadamente 1043–1047 posiciones legales, con una complejidad del árbol de juego cercana a 10123. Anteriormente no existía un análisis comparable para el Raumschach, la variante de ajedrez tridimensional del Dr. Ferdinand Maack de 1907, jugada en un tablero de 5×5×5. Este artículo presenta dicho análisis: una comparación combinatoria (Sección 2), un argumento estructural de por qué la prueba de dureza del ajedrez plano probablemente se extiende al Raumschach (Sección 3), y un conjunto de gadgets verificados suficientes, en principio, para llevar a cabo esa extensión de forma explícita (Secciones 4–7).
Este artículo sustituye a las Notas Técnicas de la IRF N.º 1–14, que registraron el proceso de desarrollo en su totalidad, incluidos varios errores encontrados y corregidos en el camino. Los lectores que deseen únicamente el estado actual y correcto de este trabajo deben leer este artículo. Dichas notas se conservan internamente como registro institucional del proceso de desarrollo, incluidos tres errores distintos en el gadget de condición de victoria, una afirmación no válida sobre el bloqueo del Unicornio, y una colisión de posiciones real entre dos gadgets, pero no se publican por separado.
2. Espacio de Estados y Complejidad del Árbol de Juego
El tablero de 125 casillas del Raumschach (cinco niveles de 5×5) sostiene 20 piezas por bando, frente a las 64 casillas y 16 piezas por bando del ajedrez plano. Una comparación de primer orden de la combinatoria de colocación, eligiendo casillas ocupadas sin distinguir el tipo de pieza — la misma simplificación que usó la estimación original de Shannon para el ajedrez —, arroja:
C(64,32) ≈ 1018.3 (ajedrez plano)
C(125,40) ≈ 1032.9 (Raumschach)
El volumen del tablero y el número de piezas por sí solos elevan el techo combinatorio en aproximadamente quince órdenes de magnitud. Una estimación de la complejidad del árbol de juego, siguiendo el método de Shannon de elevar el factor de ramificación a la potencia de la duración típica de la partida, usa el factor de ramificación de apertura del Raumschach de 61 movimientos pseudolegales (frente a los 20–35 del ajedrez) y un exponente de duración de partida comparable:
3580 ≈ 10123.5 (ajedrez plano)
61100 ≈ 10178.5 (Raumschach)
Ambas estimaciones son aproximaciones de orden de magnitud y no conteos exactos, ofrecidas como una primera aproximación a la espera de una corrección multinomial más rigurosa para la distinguibilidad de tipos de pieza. Ninguno de los dos juegos está resuelto en el sentido formal; la frontera de verificación exhaustiva del ajedrez plano se extiende a tablas de finales de siete piezas, y el análogo más cercano en Raumschach es el propio trabajo de veredictos de finales de la IRF (Serie Raumschach, Vol. V).
3. Hacia la EXPTIME-Dureza: El Método de Reducción y el Argumento a Favor de Tres Dimensiones
La prueba de Fraenkel–Lichtenstein reduce desde G3, un juego de fórmulas booleanas ya conocido por ser EXPTIME-completo (Chandra & Stockmeyer, 1976), codificando una instancia arbitraria de G3 como una posición de ajedrez construida a partir de un pequeño catálogo de gadgets: gadgets de arista/corredor, que representan el valor de verdad de una variable como la posición de un testigo dentro de un corredor amurallado; gadgets de vértice/unión, que combinan varios corredores en operaciones lógicas AND/OR; y un gadget de victoria, que entrega jaque mate forzado exactamente cuando la fórmula codificada se satisface. El componente técnicamente más exigente de la construcción bidimensional original es el gadget de cruce, necesario cada vez que dos corredores deben cruzarse en el plano sin interactuar de forma ilegal — consecuencia de forzar un circuito booleano arbitrario (y en general no planar) sobre un tablero bidimensional.
La tercera dimensión del Raumschach elimina este obstáculo en lugar de añadir uno nuevo: dos corredores que necesitarían cruzarse en un solo nivel pueden, en cambio, ocupar niveles distintos, tal como el enrutado de circuitos multicapa evita el problema de cruce que enfrenta el enrutado de una sola capa. Este es un argumento estructural, no una prueba, pero identifica el componente más difícil conocido de la reducción y da una razón concreta y geométrica para esperar que la versión en Raumschach no sea más difícil de construir, y posiblemente más sencilla. Las Secciones 4–7 presentan los gadgets que llevarían a cabo esta construcción, cada uno verificado computacionalmente contra un generador explícito de movimientos legales.
4. Método de Verificación
Cada gadget a continuación se comprobó contra un generador de movimientos legales de Raumschach construido específicamente para este propósito, que implementa las reglas de movimiento de la Torre (6 rayos), el Alfil (12 direcciones), el Unicornio (8 triagonales), la Reina (Torre±Alfil, 18 direcciones), el Rey (26 pasos, excluyendo correctamente las casillas atacadas por el oponente) y el Peón (avance frontal y ascenso hacia arriba) dadas en la Serie Raumschach, Vol. I. Las coordenadas se dan como (L,f,r) en un tablero generalizado de lado n, siguiendo la convención de que la cuestión de complejidad concierne a la familia de tableros escalable, no al juego fijo de n = 5. La verificación procedió mediante consulta directa de la salida de movimientos legales del generador contra el comportamiento afirmado, para cada combinación relevante de entradas del gadget, en lugar de basarse únicamente en el argumento manual; varias afirmaciones que parecían correctas por inspección no sobrevivieron esta comprobación, y aquí solo se presentan las construcciones corregidas que sí la superaron.
5. Los Gadgets de Corredor y de Cruce de Nivel
Un corredor es una cadena de Alfiles que avanzan un paso a la vez a lo largo de un nivel fijo, flanqueada por Peones a ambos lados. Cada Peón flanqueador se vuelve inmóvil por tres condiciones independientes: su avance frontal está bloqueado por un segundo Peón, apoyado, inmediatamente delante; su ascenso hacia arriba — una ruta sin análogo en el ajedrez plano — está bloqueado por una pieza inamovible directamente encima; y ninguna pieza enemiga se coloca nunca al alcance de captura. Las tres condiciones se verificaron directamente: un Peón flanqueador construido de esta manera no arroja ningún movimiento legal según el generador.
Un cruce de nivel transporta una señal entre niveles a lo largo del rayo del eje de nivel de una Torre, con la columna amurallada contra intrusiones. La configuración de muro correcta bloquea las ocho casillas diagonales un nivel por encima y un nivel por debajo de la columna en cada punto a lo largo de ella — no, como se intentó primero, solo las cuatro casillas ortogonalmente adyacentes a la columna en cada nivel, lo cual deja a un Unicornio libre para deslizarse directamente hacia la columna a lo largo de un rayo triagonal puro que no toca ninguno de los muros ortogonales. Tanto el fallo como la configuración corregida se confirmaron directamente: un Unicornio enemigo colocado tres niveles atrás en el rayo triagonal relevante alcanza la columna bajo la configuración original de muro (solo ortogonal), y no alcanza ninguna casilla de la columna bajo la configuración corregida (diagonal).
6. La Puerta AND Combinada y la Condición de Victoria
La condición de victoria y la puerta booleana AND que la alimenta se realizan como una única construcción unificada, a la que se llegó tras tres intentos anteriores, cada uno defectuoso por separado (cada uno documentado en su totalidad en las notas originales). El diseño final y verificado:
Se coloca un Rey en una esquina del tablero, (1,1,1), reduciendo sus casillas de huida de las 26 genéricas a 7. Seis de estas siete casillas de huida se sellan permanentemente: las tres casillas adyacentes por cara, mediante un Peón ocupante defendido por una Torre más alejada en el mismo rayo (un bloqueador indefenso es simplemente capturado por el Rey, el primer error encontrado); las tres casillas diagonales de arista, mediante Alfiles posicionados de forma que su diagonal de cobertura no se extienda a través de la propia casilla del Rey (un Alfil que cubre una casilla de huida desde la misma diagonal en la que se encuentra el Rey también ataca al Rey directa e incondicionalmente, el segundo error encontrado). La séptima casilla de huida, la triagonalmente adyacente al Rey, se deja abierta deliberadamente.
Una única Torre, V, sirve simultáneamente como el marcador que bloquea el acceso triagonal de la casilla de huida abierta y como la propia puerta AND, anclada en el único punto donde su línea de rango se cruza con dicha línea triagonal. Los testigos de entrada booleanos (Torres, para un número arbitrario de variables — el mecanismo se verificó que escala a tres entradas sin cambios) se sitúan más adelante en la línea de rango de V, cada uno bloqueando la retirada de V cuando representa Falso y desviándose de la línea cuando representa Verdadero. La retirada de V es legal si y solo si todos los testigos se han desviado — un AND de aridad n, verificado para n = 2 y n = 3. Una vez que es legal y se realiza, la retirada de V abre la línea triagonal para que un Unicornio de jaque independiente ocupe la misma casilla que V dejó vacante. Desde esa casilla, el rayo del Unicornio atraviesa la casilla de huida antes abierta y da jaque al Rey en el mismo instante, ya que ambas casillas se encuentran en la misma línea triagonal — el jaque y el cierre de la última casilla de huida del Rey llegan juntos, no como eventos con temporización separada.
Ambos extremos de esta construcción se verificaron directamente: con V presente, se confirma que el Rey no está en jaque y conserva su única casilla de huida legal para toda combinación de las entradas booleanas (un estado no terminal, seguro con independencia de la fórmula); con V ya retirada y el Unicornio de jaque en su lugar, se confirma que el Rey está en jaque con cero movimientos legales — jaque mate — alcanzable únicamente mediante la secuencia legal que permite la puerta AND.
7. La Puerta OR
El OR booleano se realiza sin necesidad de un nuevo primitivo de movimiento, usando el propio conjunto de direcciones de rayo independientes de una sola Torre como unión. A un testigo se le asignan dos de sus seis direcciones de torre, cada una amurallada de forma independiente respecto de las otras cuatro del testigo; una dirección está bloqueada por un subtestigo que representa la negación de la primera variable de entrada, la otra por un subtestigo que representa la negación de la segunda. El testigo principal tiene algún movimiento de escape legal si y solo si al menos una de las dos direcciones está abierta — un OR directo sobre las dos entradas, verificado para las cuatro combinaciones de entrada.
Colocar este gadget requiere cuidado: un primer intento de integración colocó sus piezas de muro en el mismo eje de coordenadas que la Torre de la puerta AND / condición de victoria de la Sección 6, bloqueando silenciosamente la retirada de dicha Torre con independencia de cualquier entrada booleana, puramente como consecuencia de la reutilización de coordenadas y no de ningún fallo lógico en ninguno de los dos gadgets. Se verificó que la colocación corregida, sobre un conjunto de coordenadas completamente disjunto, no introduce tal interferencia.
8. Discusión y Trabajo Futuro
Todo gadget necesario para codificar una fórmula booleana arbitraria en el estilo que requiere la reducción de Fraenkel–Lichtenstein — corredor, cruce de nivel, AND, OR, y una condición de victoria dependiente de la fórmula — existe ahora en una forma verificada contra la generación real de movimientos legales de Raumschach, no solo mediante argumento manual. Lo que queda, y no se afirma aquí, es triple. Primero, el ensamblaje completo: tomar una fórmula G3 arbitraria y no trivial y disponer efectivamente sobre un solo tablero el conjunto completo de gadgets que requiere, incluida la maquinaria de sincronización de tiempos (fusible) necesaria cuando corredores de distinta longitud deben mantenerse sincronizados con la estricta alternancia de movimientos de G3. Segundo, una disciplina de asignación de coordenadas o un proceso automatizado de comprobación de colisiones para dicho ensamblaje; la interferencia del gadget OR encontrada en la Sección 7 ilustra que la colocación manual de coordenadas no escala de forma fiable más allá de un puñado de gadgets. Tercero, una prueba completamente formal — verificada a mano o mediante búsqueda computacional independiente, y apta para su presentación a una publicación revisada por pares — de que la construcción ensamblada reduce correctamente desde G3 para toda instancia, no solo para los pequeños casos comprobados hasta la fecha. Cada uno de estos puntos es una pieza de ingeniería sustancial pero acotada, no una nueva cuestión teórica abierta; la teoría, a la fecha de este artículo, está esencialmente completa para el caso de dos puertas, y lo que queda es construir a escala.
Referencias
- 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.
- Federación Internacional de Raumschach. (2026). La Serie Raumschach, Vols. I–VI: Teoría y Veredictos de Finales. theory1.html
- Federación Internacional de Raumschach. (2026). Notas Técnicas de la IRF, N.º 1–14 (registro de desarrollo interno; sustituidas por este artículo y no publicadas por separado).