Raumschach und Berechnungskomplexität: Zustandsraum, Spielbaumgröße und eine Skizze zur EXPTIME-Härte

Ein konsolidiertes Fachpapier, das die IRF Technical Notes Nr. 1–14 ersetzt

International Raumschach Federation · 2026

Errata (nach Veröffentlichung hinzugefügt): Die Konstruktion des UND-Gatters/der Gewinnbedingung in Abschnitt 6 erwies sich für mehr als eine Boolesche Eingabe als fehlerhaft — sie liefert Schachmatt bereits, sobald der V am nächsten liegende Token abzweigt, unabhängig von allen weiteren Eingaben, statt wie behauptet zu verlangen, dass alle Eingaben Wahr sind. Siehe IRF Technical Note Nr. 15 für den Befund, seine Ursache und eine verifizierte Lösung: Vs Gatter ist für genau einen benachbarten Token korrekt, und mehrvariablige Formeln werden korrekt zusammengesetzt, indem die Logik der Teilformel abseits von Vs Feld berechnet und das Ergebnis eingespeist wird — auf Kosten der ursprünglich beschriebenen Einzeltoken-„Dreifachfunktion“. Die Konstruktionen für Korridor, Ebenenübergang und ODER-Gatter (Abschnitte 5 und 7) sind davon nicht betroffen; auch das allgemeine strukturelle Argument aus Abschnitt 3 bleibt unberührt. Eine vollständige, korrigierte Reduktionsskizze mit dieser Korrektur, die zur Begutachtung eingereicht wurde, ist verfügbar unter Toward EXPTIME-Hardness of Raumschach: A Verified Gadget Construction.

Das klassische zweidimensionale Schach nimmt in der Berechnungskomplexitätstheorie einen gesicherten Platz ein: verallgemeinertes (n×n)-Schach ist EXPTIME-vollständig (Fraenkel & Lichtenstein, 1981), und sein Zustandsraum sowie seine Spielbaumkomplexität werden seit Shannon (1950) geschätzt. Für Raumschach, die dreidimensionale Schachvariante auf einem 5×5×5-Brett, existierte bislang keine vergleichbare Analyse. Dieses Papier legt drei Ergebnisse vor. Erstens einen kombinatorischen Vergleich: Raumschachs Obergrenze der Aufstellungskombinatorik übertrifft die des klassischen Schachs um rund fünfzehn Größenordnungen, und seine geschätzte Spielbaumkomplexität (∼10¹⁷⁸) übersteigt die des Schachs (∼10¹²³). Zweitens ein strukturelles Argument, gestützt durch eine ausgearbeitete Skizze auf Gadget-Ebene, dass sich die EXPTIME-Härtereduktion von Fraenkel und Lichtenstein plausibel auf ein verallgemeinertes Raumschach-Brett erweitern lässt und dass die dritte Dimension des Raumschachs die heikelste Komponente des ursprünglichen zweidimensionalen Beweises (die Leitungskreuzung) beseitigt, statt ein neues Hindernis zu schaffen. Drittens eine Reihe von Gadgets — Korridor, Ebenenübergang, kombiniertes UND-Gatter mit Gewinnbedingung sowie ODER-Gatter —, jedes rechnerisch gegen einen eigens hierfür entwickelten Generator für legale Züge verifiziert, die zusammen genügen, um eine beliebige Boolesche Formel im von der Reduktion geforderten Stil zu kodieren. Jedes hier vorgestellte Gadget entspricht seiner endgültigen, korrigierten Form; ein vollständiger Bericht der während der Entwicklung gefundenen und behobenen Zwischenfehler wird intern als Entwicklungsprotokoll (IRF Technical Notes, Nr. 1–14, nicht gesondert veröffentlicht) zu institutionellen Zwecken aufbewahrt. Eine vollständige, brettverifizierte Reduktion für eine beliebige Formel sowie ein vollständiger, für externe Begutachtung geeigneter Komplexitätsklassenbeweis bleiben zukünftige Arbeit und werden in Abschnitt 8 beschrieben.

1. Einführung

Das klassische Schach ist in seiner verallgemeinerten (n×n)-Form EXPTIME-vollständig (Fraenkel & Lichtenstein, 1981), und sein Zustandsraum wird seit Shannon (1950) auf rund 10⁴³–10⁴⁷ legale Stellungen geschätzt, bei einer Spielbaumkomplexität nahe 10¹²³. Für Raumschach, Dr. Ferdinand Maacks 1907 erfundene dreidimensionale Schachvariante auf einem 5×5×5-Brett, existierte bislang keine vergleichbare Analyse. Dieses Papier legt diese Analyse vor: einen kombinatorischen Vergleich (Abschnitt 2), ein strukturelles Argument dafür, warum sich der Härtebeweis des klassischen Schachs plausibel auf Raumschach erweitern lässt (Abschnitt 3), sowie eine Reihe verifizierter Gadgets, die im Prinzip genügen, um diese Erweiterung explizit durchzuführen (Abschnitte 4–7).

Dieses Papier ersetzt die IRF Technical Notes Nr. 1–14, die den Entwicklungsprozess vollständig dokumentierten, einschließlich mehrerer im Verlauf gefundener und behobener Fehler. Leser, die nur den aktuellen, korrekten Stand dieser Arbeit kennenlernen möchten, sollten dieses Papier lesen. Jene Notizen werden intern als institutionelles Protokoll des Entwicklungsprozesses aufbewahrt — einschließlich dreier gesonderter Fehler im Gewinnbedingungs-Gadget, einer fehlerhaften Behauptung zur Einhorn-Blockade und einer echten Platzierungskollision zwischen zwei Gadgets —, werden jedoch nicht gesondert veröffentlicht.

2. Zustandsraum und Spielbaumkomplexität

Raumschachs Brett mit 125 Feldern (fünf 5×5-Ebenen) trägt 20 Figuren pro Partei, gegenüber den 64 Feldern und 16 Figuren pro Partei des klassischen Schachs. Ein kombinatorischer Vergleich erster Ordnung der Aufstellungsmöglichkeiten, bei dem besetzte Felder ohne Rücksicht auf die Unterscheidbarkeit der Figurentypen gewählt werden — dieselbe Vereinfachung, die Shannons ursprüngliche Schachschätzung verwendete —, ergibt:

C(64,32) ≈ 10^18,3 (klassisches Schach)
C(125,40) ≈ 10^32,9 (Raumschach)

Brettvolumen und Figurenzahl allein heben die kombinatorische Obergrenze um rund fünfzehn Größenordnungen an. Eine Schätzung der Spielbaumkomplexität nach Shannons Methode, den Verzweigungsfaktor mit der typischen Spiellänge zu potenzieren, verwendet Raumschachs Eröffnungsverzweigungsfaktor von 61 pseudo-legalen Zügen (gegenüber 20–35 beim Schach) und einen vergleichbaren Spiellängen-Exponenten:

35⁸⁰ ≈ 10^123,5 (klassisches Schach)
61¹⁰⁰ ≈ 10^178,5 (Raumschach)

Beide Schätzungen sind Näherungen der Größenordnung und keine exakten Zählungen; sie dienen als erster Ansatz bis zu einer strengeren multinomialen Korrektur für die Unterscheidbarkeit der Figurentypen. Keines der beiden Spiele ist im formalen Sinne gelöst; die Grenze der erschöpfenden Verifikation reicht beim klassischen Schach bis zu Endspiel-Tablebases mit sieben Figuren, und Raumschachs nächstes Gegenstück ist die eigene Endspielbeurteilungsarbeit der IRF (Raumschach-Reihe, Bd. V).

3. Auf dem Weg zur EXPTIME-Härte: Die Reduktionsmethode und das Argument für drei Dimensionen

Der Beweis von Fraenkel und Lichtenstein reduziert von G3, einem bereits als EXPTIME-vollständig bekannten Booleschen Formelspiel (Chandra & Stockmeyer, 1976), indem eine beliebige G3-Instanz als Schachstellung kodiert wird, die aus einem kleinen Katalog von Gadgets aufgebaut ist: Kanten-/Korridor-Gadgets, die den Wahrheitswert einer Variablen als Position eines Tokens innerhalb eines ummauerten Korridors darstellen; Knoten-/Verbindungs-Gadgets, die mehrere Korridore zu logischem UND/ODER verbinden; und ein Gewinn-Gadget, das genau dann ein erzwungenes Schachmatt liefert, wenn die kodierte Formel erfüllt ist. Die technisch anspruchsvollste Komponente der ursprünglichen zweidimensionalen Konstruktion ist das Kreuzungs-Gadget, das immer dann benötigt wird, wenn sich zwei Korridore in der Ebene kreuzen müssen, ohne unzulässig zu interagieren — eine Folge davon, einen beliebigen (und im Allgemeinen nicht-planaren) Booleschen Schaltkreis auf ein zweidimensionales Brett zu zwingen.

Raumschachs dritte Dimension beseitigt dieses Hindernis, statt ein neues zu schaffen: Zwei Korridore, die sich auf einer einzigen Ebene kreuzen müssten, können stattdessen unterschiedliche Ebenen belegen — genau wie mehrschichtige Leiterbahnführung das Kreuzungsproblem vermeidet, dem einschichtige Führung ausgesetzt ist. Dies ist ein strukturelles Argument, kein Beweis, doch es benennt die bekannteste, schwierigste Komponente der Reduktion und liefert einen konkreten, brettgeometrischen Grund zu erwarten, dass Raumschachs Version nicht schwieriger — und vermutlich leichter — zu konstruieren ist. Die Abschnitte 4–7 geben die Gadgets an, die diese Konstruktion ausführen würden, jedes rechnerisch gegen einen expliziten Generator für legale Züge verifiziert.

4. Verifikationsmethode

Jedes der folgenden Gadgets wurde gegen einen eigens für Raumschach entwickelten Generator für legale Züge geprüft, der die in der Raumschach-Reihe, Bd. I, angegebenen Zugregeln für Turm (6 Strahlen), Läufer (12 Richtungen), Einhorn (8 Triagonalen), Dame (Turm±Läufer, 18 Richtungen), König (26 Schritte, wobei Zuglegalität die vom Gegner bedrohten Felder korrekt ausschließt) und Bauer (Vorwärtszug und Aufwärtsaufstieg) umsetzt. Koordinaten werden als (E,L,R) auf einem verallgemeinerten Brett der Seitenlänge n angegeben, gemäß der Konvention, dass sich die Komplexitätsfrage auf die skalierbare Brettfamilie bezieht, nicht auf das feste Spiel mit n = 5. Die Verifikation erfolgte durch direkte Abfrage der vom Generator ausgegebenen legalen Züge gegen das behauptete Verhalten für jede relevante Kombination von Gadget-Eingaben, statt allein durch Handargumentation; mehrere Behauptungen, die bei Betrachtung korrekt erschienen, hielten dieser Prüfung nicht stand, und nur die korrigierten, bestandenen Konstruktionen werden hier angegeben.

5. Die Korridor- und Ebenenübergangs-Gadgets

Ein Korridor ist eine Kette von Läufern, die sich Schritt für Schritt entlang einer festen Ebene vorwärtsbewegen, beiderseits durch flankierende Bauern ummauert. Jeder flankierende Bauer wird durch drei unabhängige Bedingungen bewegungsunfähig gemacht: Sein Vorwärtszug wird durch einen zweiten, gestützten Bauern unmittelbar davor blockiert; sein Aufwärtsaufstieg — ein Weg ohne Entsprechung im klassischen Schach — wird durch eine unbewegliche Figur direkt darüber blockiert; und niemals befindet sich eine gegnerische Figur in Schlagreichweite. Alle drei Bedingungen wurden direkt verifiziert: Ein so konstruierter flankierender Bauer liefert unter dem Generator null legale Züge.

Ein Ebenenübergang trägt ein Signal entlang eines Turmstrahls auf der Ebenenachse zwischen den Ebenen, wobei die Säule gegen Eindringen ummauert ist. Die korrekte Mauerkonfiguration blockiert die acht diagonalen Felder eine Ebene darüber und eine Ebene darunter an jedem Punkt entlang der Säule — nicht, wie zunächst versucht, nur die vier orthogonal an die Säule angrenzenden Felder auf jeder Ebene, was einem Einhorn erlaubt, entlang eines reinen Triagonalstrahls, der keine der orthogonalen Mauern berührt, direkt in die Säule zu gleiten. Sowohl das Scheitern als auch die korrigierte Konfiguration wurden direkt bestätigt: Ein gegnerisches Einhorn, drei Ebenen zurück auf dem relevanten Triagonalstrahl platziert, erreicht die Säule unter der ursprünglichen (nur orthogonalen) Mauerkonfiguration, erreicht jedoch unter der korrigierten (diagonalen) Konfiguration kein Säulenfeld.

6. Das kombinierte UND-Gatter und die Gewinnbedingung

Die Gewinnbedingung und das sie speisende Boolesche UND-Gatter werden als eine einzige, vereinheitlichte Konstruktion realisiert, zu der man nach drei früheren, jeweils fehlerhaften Versuchen gelangte (jeder davon in den Originalnotizen vollständig dokumentiert). Der endgültige, verifizierte Entwurf:

Ein König wird in eine Brettecke gesetzt, (1,1,1), wodurch sich seine Fluchtfelder von den generischen 26 auf 7 verringern. Sechs dieser sieben Fluchtfelder werden dauerhaft versiegelt: die drei flächenbenachbarten Felder durch einen besetzenden Bauern, der von einem Turm weiter außen auf demselben Strahl gedeckt wird (ein ungedeckter Blocker wird vom König schlicht geschlagen — der erste gefundene Fehler); die drei kantendiagonalen Felder durch Läufer, die so positioniert sind, dass ihre deckende Diagonale nicht durch das Feld des Königs selbst verläuft (ein Läufer, der ein Fluchtfeld von derselben Diagonale aus deckt, auf der der König steht, greift den König zugleich direkt und bedingungslos an — der zweite gefundene Fehler). Das siebte Fluchtfeld, das triagonal an den König angrenzende, bleibt bewusst offen.

Ein einzelner Turm, V, dient zugleich als Platzhalter, der den triagonalen Zugang zum offenen Fluchtfeld blockiert, und als das UND-Gatter selbst, verankert an dem einen Punkt, an dem seine eigene Reihenlinie diese Triagonallinie schneidet. Boolesche Eingabe-Token (Türme, für beliebig viele Variablen — der Mechanismus wurde ohne Änderung auf drei Eingaben skaliert verifiziert) sitzen weiter entlang Vs Reihenlinie, wobei jedes Vs Rückzug blockiert, wenn es Falsch darstellt, und von der Linie abzweigt, wenn es Wahr darstellt. Vs Rückzug ist genau dann legal, wenn jedes Token abgezweigt ist — ein n-stelliges UND, verifiziert für n = 2 und n = 3. Sobald legal und ausgeführt, öffnet Vs Rückzug die Triagonallinie, sodass ein separates schachbietendes Einhorn dasselbe Feld besetzen kann, das V verlassen hat. Von diesem Feld aus verläuft der Strahl des Einhorns durch das zuvor offene Fluchtfeld und setzt den König im selben Augenblick schach, da beide Felder auf derselben Triagonallinie liegen — Schach und das Schließen des letzten Fluchtfelds des Königs treten gemeinsam ein, nicht als zeitlich getrennte Ereignisse.

Beide Endpunkte dieser Konstruktion wurden direkt verifiziert: Ist V vorhanden, steht der König nachweislich nicht im Schach und behält für jede Kombination der Booleschen Eingaben sein einziges legales Fluchtfeld (ein nichtterminaler, formelunabhängig sicherer Zustand); ist V abgezogen und das schachbietende Einhorn an seiner Stelle, steht der König nachweislich im Schach mit null legalen Zügen — Schachmatt —, erreichbar nur über die vom UND-Gatter erlaubte legale Zugfolge.

7. Das ODER-Gatter

Boolesches ODER wird ohne neue Bewegungsprimitive realisiert, indem die eigenen unabhängigen Strahlrichtungen eines einzelnen Turms als Vereinigung genutzt werden. Ein Token erhält zwei seiner sechs Turmrichtungen, jede unabhängig von den übrigen vier des Tokens ummauert; eine Richtung wird durch ein Untertoken blockiert, das die Negation der ersten Eingabevariable darstellt, die andere durch ein Untertoken, das die Negation der zweiten darstellt. Das Haupttoken besitzt genau dann einen legalen Fluchtzug, wenn mindestens eine der beiden Richtungen offen ist — ein direktes ODER über die beiden Eingaben, verifiziert für alle vier Eingabekombinationen.

Die Platzierung dieses Gadgets erfordert Sorgfalt: Ein früher Integrationsversuch platzierte seine ummauernden Figuren auf derselben Koordinatenachse wie der Turm des UND-Gatters/der Gewinnbedingung aus Abschnitt 6 und blockierte dadurch stillschweigend dessen Rückzug, unabhängig von jeder Booleschen Eingabe — rein als Folge der Koordinatenwiederverwendung, nicht eines logischen Fehlers in einem der beiden Gadgets. Die korrigierte Platzierung, auf einem vollständig disjunkten Koordinatensatz, wurde verifiziert, keine solche Interferenz einzuführen.

8. Diskussion und zukünftige Arbeit

Jedes Gadget, das nötig ist, um eine beliebige Boolesche Formel im von der Fraenkel–Lichtenstein-Reduktion geforderten Stil zu kodieren — Korridor, Ebenenübergang, UND, ODER und eine formelabhängige Gewinnbedingung —, existiert nun in einer Form, die gegen die tatsächliche Raumschach-Generierung legaler Züge verifiziert wurde, nicht nur durch Handargumentation. Was verbleibt und hier nicht behauptet wird, ist dreierlei. Erstens die vollständige Zusammensetzung: eine beliebige, nichttriviale G3-Formel zu nehmen und den vollständigen Satz der von ihr benötigten Gadgets tatsächlich auf einem Brett anzuordnen, einschließlich der Taktabgleich-(Zünder-)Mechanik, die nötig ist, wenn Korridore unterschiedlicher Länge mit G3s strikter Zugalternation synchron bleiben müssen. Zweitens eine Disziplin der Koordinatenvergabe oder ein automatisierter Kollisionsprüfungsprozess für diese Zusammensetzung; die in Abschnitt 7 gefundene Interferenz des ODER-Gadgets veranschaulicht, dass manuelle Koordinatenplatzierung über eine Handvoll Gadgets hinaus nicht zuverlässig skaliert. Drittens ein vollständig formaler Beweis — von Hand oder durch unabhängige Computersuche verifiziert und zur Einreichung bei einem begutachteten Fachorgan geeignet —, dass die zusammengesetzte Konstruktion für jede Instanz korrekt von G3 reduziert, nicht nur für die bisher geprüften kleinen Fälle. Jeder dieser Punkte ist ein erheblicher, aber begrenzter technischer Aufwand, keine weitere offene theoretische Frage; die Theorie ist zum Stand dieses Papiers für den Zweigatter-Fall im Wesentlichen vollständig, und was verbleibt, ist der Aufbau im großen Maßstab.

Literaturverzeichnis

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, Bd. I–VI: Theorie und Endspielbeurteilungen. theory1.html
International Raumschach Federation. (2026). IRF Technical Notes, Nr. 1–14 (internes Entwicklungsprotokoll; durch dieses Papier ersetzt und nicht gesondert veröffentlicht).