Raumschach and Computational Complexity: State Space, Game-Tree Size, and an EXPTIME-Hardness Sketch

A consolidated technical paper, superseding IRF Technical Notes Nos. 1–14

International Raumschach Federation · 2026

Erratum (added after publication): Section 6’s AND-gate/win-condition construction was found unsound for more than one Boolean input — it delivers checkmate as soon as the token nearest V branches off, independent of any other input, rather than requiring all inputs True as claimed. See IRF Technical Note No. 15 for the finding, its cause, and a verified resolution: V’s gate is sound for exactly one adjacent token, and multi-variable formulas are composed correctly by computing sub-formula logic off V’s square and wiring in the result, at the cost of the single-token “triple duty” composition originally described. The corridor, level-crossing via, and OR-gate constructions (Sections 5 and 7) are not affected; the general structural argument of Section 3 is also not affected. A full, corrected reduction sketch incorporating the fix, submitted for peer review, is available at Toward EXPTIME-Hardness of Raumschach: A Verified Gadget Construction.

Flat chess has a settled place in computational complexity theory: generalized (n×n) chess is EXPTIME-complete (Fraenkel & Lichtenstein, 1981), and its state space and game-tree complexity have been estimated since Shannon (1950). No comparable analysis previously existed for Raumschach, the 5×5×5 three-dimensional chess variant. This paper presents three results. First, a combinatorial comparison: Raumschach’s placement-combinatorics ceiling exceeds flat chess’s by roughly fifteen orders of magnitude, and its estimated game-tree complexity (∼10¹⁷⁸) exceeds chess’s (∼10¹²³). Second, a structural argument, supported by a worked gadget-level sketch, that the Fraenkel–Lichtenstein EXPTIME-hardness reduction plausibly extends to a generalized Raumschach board, and that Raumschach’s third dimension removes the single most delicate component of the original two-dimensional proof (wire-crossing) rather than adding a new obstacle. Third, a set of gadgets — corridor, level-crossing via, combined AND-gate/win-condition, and OR-gate — each verified computationally against an explicit legal-move generator built for this purpose, together sufficient to encode an arbitrary Boolean formula in the style the reduction requires. Every gadget presented here reflects its final, corrected form; a full account of the intermediate errors found and fixed during development is preserved internally as a development log (IRF Technical Notes, Nos. 1–14, not separately published) for institutional record. A complete, board-verified reduction for an arbitrary formula, and a full complexity-class proof suitable for external peer review, remain future work, described in Section 8.

1. Introduction

Flat chess is EXPTIME-complete in its generalized (n×n) form (Fraenkel & Lichtenstein, 1981), and its state space has been estimated since Shannon (1950) at roughly 10⁴³–10⁴⁷ legal positions, with a game-tree complexity near 10¹²³. No comparable analysis previously existed for Raumschach, Dr. Ferdinand Maack’s 1907 three-dimensional chess variant played on a 5×5×5 board. This paper presents that analysis: a combinatorial comparison (Section 2), a structural argument for why the flat-chess hardness proof plausibly extends to Raumschach (Section 3), and a set of verified gadgets sufficient, in principle, to carry out that extension explicitly (Sections 4–7).

This paper supersedes IRF Technical Notes Nos. 1–14, which recorded the development process in full, including several errors found and corrected along the way. Readers who want only the current, correct state of this work should read this paper. Those notes are retained internally as an institutional record of the development process, including three separate errors in the win-condition gadget, an unsound claim about Unicorn blocking, and a genuine placement collision between two gadgets, but are not separately published.

2. State Space and Game-Tree Complexity

Raumschach’s 125-cell board (five 5×5 levels) carries 20 pieces per side against flat chess’s 64 cells and 16 pieces per side. A first-order placement-combinatorics comparison, choosing occupied cells without regard to piece-type distinguishability — the same simplification Shannon’s original chess estimate used — gives:

C(64,32) ≈ 10^18.3 (flat chess)
C(125,40) ≈ 10^32.9 (Raumschach)

Board volume and piece count alone raise the combinatorial ceiling by roughly fifteen orders of magnitude. A game-tree complexity estimate, following Shannon’s method of raising branching factor to the power of typical game length, uses Raumschach’s opening branching factor of 61 pseudo-legal moves (against chess’s 20–35) and a comparable game-length exponent:

35⁸⁰ ≈ 10^123.5 (flat chess)
61¹⁰⁰ ≈ 10^178.5 (Raumschach)

Both estimates are order-of-magnitude approximations rather than exact counts, offered as a first pass pending a more rigorous multinomial correction for piece-type distinguishability. Neither game is solved in the formal sense; flat chess’s frontier of exhaustive verification extends to seven-piece endgame tablebases, and Raumschach’s nearest analogue is the IRF’s own endgame-verdict work (Raumschach Series, Vol. V).

3. Toward EXPTIME-Hardness: The Reduction Method and the Case for Three Dimensions

The Fraenkel–Lichtenstein proof reduces from G3, a Boolean formula game already known to be EXPTIME-complete (Chandra & Stockmeyer, 1976), by encoding an arbitrary G3 instance as a chess position built from a small catalogue of gadgets: edge/corridor gadgets representing a variable’s truth value as a token’s position within a walled corridor; vertex/junction gadgets combining several corridors into logical AND/OR; and a win gadget delivering forced checkmate exactly when the encoded formula is satisfied. The single most technically demanding component of the original two-dimensional construction is the crossover gadget, needed whenever two corridors must cross in the plane without illegally interacting — a consequence of forcing an arbitrary (and generally non-planar) Boolean circuit onto a two-dimensional board.

Raumschach’s third dimension removes this obstacle rather than adding a new one: two corridors that would need to cross on a single level can instead occupy different levels, exactly as multi-layer circuit routing avoids the crossing problem single-layer routing faces. This is a structural argument, not a proof, but it identifies the reduction’s hardest known component and gives a specific, board-geometric reason to expect Raumschach’s version to be no harder to construct, and plausibly easier. Sections 4–7 give the gadgets that would carry out this construction, each computationally verified against an explicit legal-move generator.

4. Verification Method

Every gadget below was checked against a purpose-built Raumschach legal-move generator implementing the Rook (6 rays), Bishop (12 directions), Unicorn (8 triagonals), Queen (Rook±Bishop, 18 directions), King (26 steps, with move legality correctly excluding squares attacked by the opponent), and Pawn (forward advance and upward ascent) movement rules given in the Raumschach Series, Vol. I. Coordinates are given as (L,f,r) on a generalized board of side n, following the convention that the complexity question concerns the scalable board family, not the fixed n = 5 game. Verification proceeded by direct query of the generator’s legal-move output against the claimed behavior for every relevant combination of gadget inputs, rather than by hand-argument alone; several claims that appeared correct on inspection did not survive this check, and only the corrected, surviving constructions are given here.

5. The Corridor and Level-Crossing Gadgets

A corridor is a chain of Bishops advancing one step at a time along a fixed level, walled by flanking Pawns on both sides. Each flanking Pawn is rendered immobile by three independent conditions: its forward advance is blocked by a second, supported Pawn immediately ahead; its upward ascent — a route with no flat-chess analogue — is blocked by an immovable piece directly above; and no enemy piece is ever placed within capturing range. All three conditions were verified directly: a flanking Pawn constructed this way returns zero legal moves under the generator.

A level-crossing via carries a signal between levels along a Rook’s level-axis ray, with the column walled against intrusion. The correct wall configuration blocks the eight diagonal squares one level above and one level below the column at each point along it — not, as first attempted, only the four squares orthogonally adjacent to the column at each level, which leaves a Unicorn free to slide directly into the column along a pure triagonal ray that touches none of the orthogonal walls. Both the failure and the corrected configuration were confirmed directly: an enemy Unicorn placed three levels back on the relevant triagonal ray reaches the column under the original (orthogonal-only) wall configuration, and reaches no column cell under the corrected (diagonal) configuration.

6. The Combined AND-Gate and Win Condition

The win condition and the Boolean AND-gate that feeds it are realized as a single unified construction, arrived at after three earlier, separately-flawed attempts (each fully documented in the original notes). The final, verified design:

A King is placed at a corner of the board, (1,1,1), reducing its flight squares from the generic 26 to 7. Six of these seven flight squares are permanently sealed: the three face-adjacent squares by an occupying Pawn defended by a Rook further out on the same ray (an undefended blocker is simply captured by the King, the first error found); the three edge-diagonal squares by Bishops positioned so their covering diagonal does not extend through the King’s own square (a Bishop covering a flight square from the same diagonal the King sits on also attacks the King directly and unconditionally, the second error found). The seventh flight square, the one triagonally adjacent to the King, is deliberately left open.

A single Rook, V, serves simultaneously as the placeholder blocking the open flight square’s triagonal approach and as the AND-gate itself, anchored at the one point where its own rank line intersects that triagonal line. Boolean input tokens (Rooks, for arbitrarily many variables — the mechanism was verified to scale to three inputs with no change) sit further along V’s rank line, each blocking V’s retreat when representing False and branching off the line when representing True. V’s retreat is legal if and only if every token has branched off — an n-ary AND, verified for n = 2 and n = 3. Once legal and made, V’s retreat opens the triagonal line for a separate checking Unicorn to occupy the same square V vacated. From that square, the Unicorn’s ray passes through the previously-open flight square and delivers check to the King in the same instant, since both squares lie on the identical triagonal line — check and the closure of the King’s last flight square arrive together, not as separately-timed events.

Both endpoints of this construction were verified directly: with V present, the King is confirmed not in check and retains its one legal flight square for every combination of the Boolean inputs (a non-terminal, formula-independent-safe state); with V departed and the checking Unicorn in its place, the King is confirmed in check with zero legal moves — checkmate — reachable only via the legal sequence the AND-gate permits.

7. The OR-Gate

Boolean OR is realized without a new movement primitive, by using a single Rook’s own set of independent ray directions as a union. A token is given two of its six rook directions, each independently walled off from the token’s other four; one direction is blocked by a sub-token representing the negation of the first input variable, the other by a sub-token representing the negation of the second. The main token has some legal escape move if and only if at least one of the two directions is open — a direct OR over the two inputs, verified for all four input combinations.

Placing this gadget requires care: an early integration attempt placed its walling pieces on the same coordinate axis as the AND-gate/win-condition Rook from Section 6, silently blocking that Rook’s retreat regardless of any Boolean input, purely as a consequence of coordinate reuse rather than any logical flaw in either gadget. The corrected placement, on a fully disjoint set of coordinates, was verified to introduce no such interference.

8. Discussion and Future Work

Every gadget necessary to encode an arbitrary Boolean formula in the style the Fraenkel–Lichtenstein reduction requires — corridor, level-crossing via, AND, OR, and a formula-dependent win condition — now exists in a form verified against actual Raumschach legal-move generation, not only hand-argument. What remains, and is not claimed here, is threefold. First, full assembly: taking an arbitrary, nontrivial G3 formula and actually laying out the complete set of gadgets it requires on one board, including the tempo-matching (fuse) machinery needed when corridors of different lengths must stay synchronized with G3’s strict move alternation. Second, a coordinate-allocation discipline or automated collision-checking process for that assembly; the OR-gadget interference found in Section 7 illustrates that manual coordinate placement does not scale reliably past a handful of gadgets. Third, a fully formal proof — verified by hand or by independent computer search, and suitable for submission to a peer-reviewed venue — that the assembled construction correctly reduces from G3 for every instance, not only the small cases checked to date. Each of these is a substantial but bounded piece of engineering, not a further open theoretical question; the theory, as of this paper, is essentially complete for the two-gate case, and what remains is building at scale.

References

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.
International Raumschach Federation. (2026). The Raumschach Series, Vols. I–VI: Theory and Endgame Verdicts. theory1.html
International Raumschach Federation. (2026). IRF Technical Notes, Nos. 1–14 (internal development log; superseded by this paper and not separately published).