Raumschach et complexité computationnelle : espace d’états, taille de l’arbre de jeu, et esquisse d’EXPTIME-difficulté
Un article technique consolidé, remplaçant les Notes techniques de l’IRF nos 1–14
1. Introduction
Les échecs plats sont EXPTIME-complets sous leur forme généralisée (n×n) (Fraenkel & Lichtenstein, 1981), et leur espace d’états est estimé depuis Shannon (1950) à environ 1043–1047 positions légales, avec une complexité d’arbre de jeu proche de 10123. Aucune analyse comparable n’existait auparavant pour Raumschach, la variante d’échecs tridimensionnelle du Dr Ferdinand Maack, inventée en 1907 et jouée sur un plateau 5×5×5. Cet article présente cette analyse : une comparaison combinatoire (Section 2), un argument structurel expliquant pourquoi la preuve de difficulté des échecs plats s’étend plausiblement à Raumschach (Section 3), et un ensemble de gadgets vérifiés suffisants, en principe, pour mener à bien cette extension de manière explicite (Sections 4–7).
Cet article remplace les Notes techniques de l’IRF nos 1–14, qui consignaient l’intégralité du processus de développement, y compris plusieurs erreurs trouvées et corrigées en cours de route. Les lecteurs qui ne souhaitent connaître que l’état actuel et correct de ces travaux devraient lire cet article. Ces notes sont conservées en interne comme archive institutionnelle du processus de développement, incluant trois erreurs distinctes dans le gadget de condition de victoire, une affirmation non valide concernant le blocage de la Licorne, et une véritable collision de placement entre deux gadgets, mais ne sont pas publiées séparément.
2. Espace d’états et complexité de l’arbre de jeu
Le plateau de 125 cases de Raumschach (cinq niveaux de 5×5) porte 20 pièces par camp, contre 64 cases et 16 pièces par camp pour les échecs plats. Une comparaison combinatoire de placement de premier ordre, choisissant les cases occupées sans égard à la distinguabilité du type de pièce — la même simplification qu’utilisait l’estimation originale de Shannon pour les échecs — donne :
C(64,32) ≈ 1018,3 (échecs plats)
C(125,40) ≈ 1032,9 (Raumschach)
Le volume du plateau et le nombre de pièces à eux seuls élèvent le plafond combinatoire d’environ quinze ordres de grandeur. Une estimation de la complexité de l’arbre de jeu, suivant la méthode de Shannon consistant à élever le facteur de branchement à la puissance d’une durée de partie typique, utilise le facteur de branchement d’ouverture de Raumschach de 61 coups pseudo-légaux (contre 20–35 aux échecs) et un exposant de longueur de partie comparable :
3580 ≈ 10123,5 (échecs plats)
61100 ≈ 10178,5 (Raumschach)
Les deux estimations sont des approximations d’ordre de grandeur plutôt que des comptages exacts, offertes comme une première approche en attendant une correction multinomiale plus rigoureuse pour la distinguabilité du type de pièce. Aucun des deux jeux n’est résolu au sens formel ; la frontière de vérification exhaustive des échecs plats s’étend aux tables de fin de partie à sept pièces, et l’analogue le plus proche pour Raumschach est le propre travail de verdicts de fin de partie de l’IRF (Série Raumschach, Vol. V).
3. Vers l’EXPTIME-difficulté : la méthode de réduction et l’argument en faveur des trois dimensions
La preuve de Fraenkel–Lichtenstein réduit à partir de G3, un jeu de formules booléennes déjà connu pour être EXPTIME-complet (Chandra & Stockmeyer, 1976), en encodant une instance arbitraire de G3 comme une position d’échecs construite à partir d’un petit catalogue de gadgets : des gadgets d’arête/couloir représentant la valeur de vérité d’une variable comme la position d’un jeton à l’intérieur d’un couloir muré ; des gadgets de sommet/jonction combinant plusieurs couloirs en ET/OU logiques ; et un gadget de victoire produisant un échec et mat forcé exactement lorsque la formule encodée est satisfaite. La composante la plus techniquement exigeante de la construction bidimensionnelle originale est le gadget de croisement, nécessaire chaque fois que deux couloirs doivent se croiser dans le plan sans interagir de manière illégale — une conséquence du fait de forcer un circuit booléen arbitraire (et généralement non planaire) sur un plateau bidimensionnel.
La troisième dimension de Raumschach supprime cet obstacle plutôt que d’en ajouter un nouveau : deux couloirs qui devraient se croiser sur un seul niveau peuvent à la place occuper des niveaux différents, exactement comme le routage de circuits multicouches évite le problème de croisement auquel se heurte le routage monocouche. Il s’agit d’un argument structurel, non d’une preuve, mais il identifie la composante la plus difficile connue de la réduction et donne une raison spécifique, de nature géométrique et propre au plateau, de s’attendre à ce que la version de Raumschach ne soit pas plus difficile à construire, et plausiblement plus facile. Les Sections 4–7 présentent les gadgets qui mèneraient à bien cette construction, chacun vérifié informatiquement contre un générateur explicite de coups légaux.
4. Méthode de vérification
Chaque gadget ci-dessous a été vérifié contre un générateur de coups légaux de Raumschach construit à cet effet, mettant en œuvre les règles de déplacement de la Tour (6 rayons), du Fou (12 directions), de la Licorne (8 triagonales), de la Dame (Tour±Fou, 18 directions), du Roi (26 pas, la légalité des coups excluant correctement les cases attaquées par l’adversaire), et du Pion (avancée frontale et ascension vers le haut) données dans la Série Raumschach, Vol. I. Les coordonnées sont données sous la forme (L,f,r) sur un plateau généralisé de côté n, suivant la convention selon laquelle la question de complexité concerne la famille de plateaux redimensionnable, non le jeu à n = 5 fixe. La vérification a procédé par interrogation directe de la sortie de coups légaux du générateur contre le comportement revendiqué, pour chaque combinaison pertinente d’entrées de gadget, plutôt que par simple argumentation manuelle ; plusieurs affirmations qui paraissaient correctes à l’inspection n’ont pas survécu à cette vérification, et seules les constructions corrigées et survivantes sont données ici.
5. Les gadgets de couloir et de passage de niveau
Un couloir est une chaîne de Fous avançant d’un pas à la fois le long d’un niveau fixe, muré par des Pions flanquants des deux côtés. Chaque Pion flanquant est rendu immobile par trois conditions indépendantes : son avancée frontale est bloquée par un second Pion soutenu immédiatement devant lui ; son ascension vers le haut — une voie sans analogue aux échecs plats — est bloquée par une pièce inamovible directement au-dessus ; et aucune pièce ennemie n’est jamais placée à portée de capture. Les trois conditions ont été vérifiées directement : un Pion flanquant construit de cette manière ne renvoie aucun coup légal sous le générateur.
Un passage de niveau transporte un signal entre les niveaux le long d’un rayon de Tour sur l’axe des niveaux, la colonne étant murée contre toute intrusion. La configuration murale correcte bloque les huit cases diagonales situées un niveau au-dessus et un niveau au-dessous de la colonne, à chaque point le long de celle-ci — non pas, comme tenté initialement, uniquement les quatre cases orthogonalement adjacentes à la colonne à chaque niveau, ce qui laisse une Licorne libre de glisser directement dans la colonne le long d’un rayon purement triagonal qui ne touche aucun des murs orthogonaux. L’échec comme la configuration corrigée ont été confirmés directement : une Licorne ennemie placée trois niveaux en arrière sur le rayon triagonal pertinent atteint la colonne sous la configuration murale originale (orthogonale uniquement), et n’atteint aucune case de la colonne sous la configuration corrigée (diagonale).
6. La porte AND combinée et la condition de victoire
La condition de victoire et la porte booléenne AND qui l’alimente sont réalisées comme une construction unifiée unique, à laquelle on est parvenu après trois tentatives antérieures, chacune séparément défectueuse (chacune entièrement documentée dans les notes originales). La conception finale, vérifiée :
Un Roi est placé à un coin du plateau, (1,1,1), réduisant ses cases de fuite du nombre générique de 26 à 7. Six de ces sept cases de fuite sont scellées de manière permanente : les trois cases adjacentes par une face, par un Pion occupant défendu par une Tour plus éloignée sur le même rayon (un bloqueur non défendu est simplement capturé par le Roi, la première erreur trouvée) ; les trois cases diagonales d’arête, par des Fous positionnés de sorte que leur diagonale de couverture ne s’étende pas à travers la propre case du Roi (un Fou couvrant une case de fuite depuis la même diagonale sur laquelle se trouve le Roi attaque également le Roi directement et sans condition, la seconde erreur trouvée). La septième case de fuite, celle adjacente au Roi par un coin, est délibérément laissée ouverte.
Une seule Tour, V, sert simultanément de jeton substitut bloquant l’approche triagonale de la case de fuite ouverte et de porte AND elle-même, ancrée au point unique où sa propre ligne de rangée croise cette ligne triagonale. Les jetons d’entrée booléens (des Tours, pour un nombre arbitraire de variables — le mécanisme a été vérifié comme s’étendant à trois entrées sans changement) se trouvent plus loin sur la ligne de rangée de V, chacun bloquant la retraite de V lorsqu’il représente Faux et se détachant de la ligne lorsqu’il représente Vrai. La retraite de V est légale si et seulement si chaque jeton s’est détaché — un AND à n arguments, vérifié pour n = 2 et n = 3. Une fois légale et effectuée, la retraite de V ouvre la ligne triagonale pour qu’une Licorne d’échec distincte occupe la même case que V a libérée. Depuis cette case, le rayon de la Licorne traverse la case de fuite précédemment ouverte et délivre échec au Roi au même instant, puisque les deux cases se trouvent sur la ligne triagonale identique — l’échec et la fermeture de la dernière case de fuite du Roi surviennent ensemble, non comme des événements séparés dans le temps.
Les deux extrémités de cette construction ont été vérifiées directement : avec V présente, le Roi est confirmé hors échec et conserve sa seule case de fuite légale pour chaque combinaison des entrées booléennes (un état non terminal, sûr indépendamment de la formule) ; avec V partie et la Licorne d’échec à sa place, le Roi est confirmé en échec avec zéro coup légal — échec et mat — accessible uniquement via la séquence légale que permet la porte AND.
7. La porte OR
Le OR booléen est réalisé sans nouvelle primitive de déplacement, en utilisant le propre ensemble de directions de rayon indépendantes d’une seule Tour comme une union. Un jeton se voit attribuer deux de ses six directions de tour, chacune murée indépendamment des quatre autres du jeton ; une direction est bloquée par un sous-jeton représentant la négation de la première variable d’entrée, l’autre par un sous-jeton représentant la négation de la seconde. Le jeton principal dispose d’un coup d’échappement légal si et seulement si au moins l’une des deux directions est ouverte — un OR direct sur les deux entrées, vérifié pour les quatre combinaisons d’entrée.
Le placement de ce gadget exige de la précaution : une première tentative d’intégration a placé ses pièces murantes sur le même axe de coordonnées que la Tour de la porte AND/condition de victoire de la Section 6, bloquant silencieusement la retraite de cette Tour indépendamment de toute entrée booléenne, purement en conséquence de la réutilisation de coordonnées plutôt que de tout défaut logique dans l’un ou l’autre gadget. Le placement corrigé, sur un ensemble de coordonnées entièrement disjoint, a été vérifié comme n’introduisant aucune interférence de ce type.
8. Discussion et travaux futurs
Chaque gadget nécessaire pour encoder une formule booléenne arbitraire dans le style qu’exige la réduction de Fraenkel–Lichtenstein — couloir, passage de niveau, AND, OR, et une condition de victoire dépendante de la formule — existe désormais sous une forme vérifiée contre une génération réelle de coups légaux de Raumschach, et non plus seulement par argumentation manuelle. Ce qui demeure, et n’est pas revendiqué ici, est triple. Premièrement, l’assemblage complet : prendre une formule G3 arbitraire et non triviale et disposer effectivement sur un seul plateau l’ensemble complet des gadgets qu’elle requiert, y compris la machinerie de synchronisation des tempos (fusible) nécessaire lorsque des couloirs de longueurs différentes doivent rester synchronisés avec la stricte alternance des coups de G3. Deuxièmement, une discipline d’allocation de coordonnées ou un processus automatisé de détection de collisions pour cet assemblage ; l’interférence de gadget OR trouvée à la Section 7 illustre que le placement manuel des coordonnées ne s’étend pas de manière fiable au-delà d’une poignée de gadgets. Troisièmement, une preuve entièrement formelle — vérifiée à la main ou par recherche informatique indépendante, et adaptée à une soumission dans un cadre évalué par les pairs — que la construction assemblée réduit correctement à partir de G3 pour chaque instance, non seulement les petits cas vérifiés à ce jour. Chacun de ces points constitue une pièce d’ingénierie substantielle mais bornée, non une nouvelle question théorique ouverte ; la théorie, à la date de cet article, est essentiellement complète pour le cas à deux portes, et ce qui reste est de construire à grande échelle.
Références
- 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.
- Fédération Internationale de Raumschach. (2026). La Série Raumschach, Vol. I–VI : Théorie et verdicts de fin de partie. theory1.html
- Fédération Internationale de Raumschach. (2026). Notes techniques de l’IRF, nos 1–14 (journal de développement interne ; remplacé par cet article et non publié séparément).