Logo de l’IRF

La porte AND qui ne filtre pas : une faille de validité dans la construction de la condition de victoire

Note technique no 15 de l’IRF — un erratum à la Section 6 de Raumschach et complexité computationnelle

Fédération Internationale de Raumschach  ·  Notes techniques de l’IRF, no 15  ·  2026

La Section 6 de l’article consolidé (Raumschach et complexité computationnelle) décrit un mécanisme porte AND/condition de victoire dans lequel une Tour V, se trouvant sur la ligne d’une pièce donnant échec, se retire si et seulement si chacun de plusieurs jetons d’entrée booléens le long de sa ligne de rangée s’est détaché. La poursuite des travaux vers l’assemblage complet d’une formule non triviale a testé ce mécanisme, pour la première fois, contre un véritable générateur de coups légaux avec plus d’un jeton d’entrée en véritable séquence — une configuration qu’aucun test antérieur, y compris la propre vérification de la Section 6, ne semble avoir exercée. Le résultat est une véritable faille de validité : le mécanisme délivre l’échec et mat dès que le seul jeton le plus proche de V se détache, indépendamment de l’état de tout jeton plus loin sur la ligne, ce qui est l’opposé logique de l’AND revendiqué. Cette note documente la découverte, retrace sa cause à une hypothèse sur le rayon de la pièce donnant échec qui ne tient pas sous une retraite partielle, identifie lesquelles des autres constructions de ce projet sont affectées et lesquelles ne le sont pas, et présente une résolution vérifiée : la propre porte de V est valide pour exactement un jeton adjacent, et des formules booléennes arbitraires peuvent être composées correctement en calculant toute la logique des sous-formules entièrement en dehors de la case de V et en câblant le résultat dans la présence ou l’absence de ce jeton unique, au prix du « triple usage » à jeton unique que ce projet poursuivait par composition.

I. Résumé

L’article consolidé (Raumschach et complexité computationnelle, Section 6) décrit le mécanisme porte AND/condition de victoire ainsi : une Tour V se trouve au point où sa propre ligne de rangée croise une ligne triagonale menant au Roi, avec des jetons d’entrée booléens plus loin sur cette même ligne de rangée, chacun bloquant la retraite de V lorsqu’il est Faux et se détachant de la ligne lorsqu’il est Vrai ; la retraite de V est légale « si et seulement si chaque jeton s’est détaché ». Une fois légale, énonce l’article, la retraite de V ouvre la ligne triagonale pour une Licorne d’échec, qui délivre l’échec et ferme la dernière case de fuite du Roi simultanément.

La poursuite des travaux informatiques, œuvrant vers l’assemblage complet d’une formule non triviale, a vérifié ce mécanisme contre un véritable générateur de coups légaux pour la première fois avec plus d’un jeton d’entrée en véritable séquence — un cas que la vérification originale (Note no 9 et les propres tests de la Section 6 de l’article consolidé) ne semble pas avoir exercé, puisque tous les tests antérieurs ne vérifiaient que si V pouvait atteindre une case d’échappement spécifique, entièrement repliée, sous une seule attribution préalablement choisie. Ce contrôle a révélé une véritable faille de validité : le mécanisme, tel que spécifié, n’implémente pas AND pour plus d’un jeton d’entrée. Il délivre l’échec et mat dès que n’importe quel jeton unique le plus proche de V s’est détaché, indépendamment de l’état de tout jeton plus loin sur la ligne. Ceci est l’opposé du comportement revendiqué, et plus proche d’un OR que d’un AND.

II. La cause sous-jacente

La validité de la porte dépend d’une hypothèse qui s’avère ne pas tenir : que V doit se retirer jusqu’au bout vers sa case d’échappement désignée avant que le rayon de la Licorne d’échec ne soit découvert. En réalité, le rayon de la Licorne d’échec passe spécifiquement par la case de départ de V — le seul point où la ligne de rangée de V croise la ligne triagonale du Roi — non par la case d’échappement. À l’instant où V quitte cette seule case de départ, pour quelque raison que ce soit et vers quelque destination que ce soit, le rayon de la Licorne est dégagé et l’échec par découverte est délivré. Ceci a été confirmé directement : déplacer V d’une seule case hors de sa position de départ, avec une Licorne d’échec placée n’importe où plus loin sur la même ligne triagonale avec un chemin dégagé, produit un échec et mat immédiat — avant même que la Licorne elle-même n’ait effectué le moindre coup, et indépendamment de la distance que V a réellement parcourue.

Ceci effondre l’AND multi-jetons voulu. Considérons deux jetons d’entrée, T1 le plus proche de V et T2 le suivant, tous deux immédiatement adjacents sans espace entre eux (le placement le plus fort possible, testé directement plutôt que supposé). Si x1 est Vrai, T1 se détache et libère la case adjacente à V. V dispose désormais d’un coup légal — une case, sur l’ancienne position de T1 — indépendamment du fait que x2 soit Vrai ou Faux, car la légalité pour une Tour d’effectuer un coup dans une direction dépend uniquement de la présence de l’obstacle le plus proche, non de tout obstacle plus loin sur la ligne. Ce coup d’une case suffit : il libère la case de départ de V, et l’échec et mat suit immédiatement, que T2 (représentant x2) se soit détaché ou non.

Ceci a été vérifié directement et précisément : avec x1 = Vrai et x2 = Faux, V dispose d’exactement un coup légal (sur la case libérée par T1) ; jouer ce coup produit une position où le Roi est en échec avec zéro réponse légale — échec et mat — même si la conjonction x1 ∧ x2 est Fausse. Un cas de contrôle (x1 = Faux, x2 = Vrai) confirme que le jeton le plus proche seul suffit à bloquer entièrement V, indépendamment des jetons plus loin : V dispose de zéro coup légal. Entre les deux cas, le motif est sans ambiguïté : le résultat ne suit que l’état du jeton le plus proche de V. Tout autre jeton dans la chaîne est logiquement inerte.

III. Pourquoi la vérification antérieure n’a pas détecté ceci

Chaque test depuis la propre vérification de la Section 6 — à travers les travaux ultérieurs de ce projet sur la composition, la synchronisation des tempos, et l’arbre de jeu — vérifiait la légalité de V en demandant si V pouvait atteindre une case de destination spécifique, entièrement repliée, avec des jetons d’entrée placés (ou omis) directement selon une attribution booléenne préalablement choisie. Ce contrôle donne par hasard une réponse d’apparence correcte chaque fois que la géométrie ne donne jamais à V un coup légal partiel et non terminal à jouer à la place — ce qui était vrai de chaque configuration testée, généralement parce que les jetons étaient espacés avec des intervalles, ou parce qu’un seul jeton était en jeu, ou parce que les tests de composition câblaient directement les valeurs de vérité plutôt que de construire une véritable chaîne multi-jetons avec un placement adjacent. La faille ne surgit que lorsque (a) plus d’un jeton se trouve en véritable séquence sur la ligne de V, (b) le plus proche est capable de se détacher indépendamment des autres, et (c) le contrôle de condition de victoire pose la question que le mécanisme répond réellement — « V dispose-t-elle d’un quelconque coup légal » — plutôt que la question proxy — « V peut-elle atteindre cette case spécifique ». Aucun test antérieur à celui-ci ne posait (c) en présence simultanée de (a) et (b).

IV. Ce qui est affecté et ce qui ne l’est pas

Non affectées : les constructions de couloir, de passage de niveau, et de porte OR (Sections 5 et 7), qui ne dépendent pas de l’astuce case de départ/ligne triagonale de V. La découverte générale selon laquelle la troisième dimension de Raumschach supprime l’obstacle de croisement de fils des échecs plats (Section 3) est un argument structurel, géométrique au plateau, indépendant de ce gadget et n’est pas non plus affectée.

Affectée : la construction porte AND/condition de victoire de la Section 6, spécifiquement sa revendication de filtrer correctement un nombre arbitraire d’entrées booléennes. La construction est valide pour exactement un jeton d’entrée (il n’y a rien par rapport à quoi un second jeton pourrait être inerte). Elle n’est pas valide, telle que spécifiée, pour deux ou plus.

Également affectée, en attente de réexamen : la mise à l’échelle à trois entrées revendiquée à la Section 6 (« vérifiée comme s’étendant à trois entrées sans changement ») et la propre validité de la porte OR sous composition, puisque le propre mécanisme d’échappement de la porte OR était, dans les travaux de composition ultérieurs de ce projet, câblé directement dans la même ligne de rangée qu’une entrée de porte AND en utilisant la logique identique de libération de ligne désormais montrée non valide pour le filtrage séquentiel multi-jetons. Toute structure composée bâtie sur les fichiers test_assembly_composite.py, test_double_composite.py, ou test_single_token_composition.py de ce projet hérite de cette faille pour la même raison : chacun câblait une valeur booléenne calculée dans la présence ou l’absence d’un unique jeton proxy sur la ligne de V, ce qui est exactement le cas à un jeton à la fois que cette note montre valide — mais aucun d’eux ne testait deux ou plus jetons indépendamment mobiles sur la même ligne en véritable séquence, ce qui est là où la faille réside réellement.

V. Résolution : une construction valide, avec un coût réel

Mise à jour, ajoutée après des travaux supplémentaires : une résolution valide existe, bien qu’elle soit plus limitée que la revendication originale. Aucune des deux directions nommées ci-dessus (portes en cascade par paires, découplage du rayon d’échec de la case éloignée de V) n’était nécessaire ; la correction est plus simple et se paie au prix de la portée. Elle a été confirmée directement contre le générateur :

Le coût : ceci est une véritable réparation de la validité, non de l’ambition originale. Il n’est plus vrai qu’une seule pièce physique puisse servir un double ou triple rôle — en tant que propre jeton mobile d’une sous-formule, bloqueur de ligne de rangée, et pièce se trouvant sur le rayon d’échec, tout à la fois — de la manière que la Section 6 et les propres fichiers test_single_token_composition.py et test_double_composite.py de ce projet supposaient. La composition requiert désormais une étape de câblage explicite et distincte entre une sous-formule vérifiée et l’unique jeton qui compte réellement pour le mat. Qu’une conception existe qui récupère la composition à jeton unique sans câblage, sans réintroduire le défaut original de cette note, demeure ouvert ; ce qui n’est plus ouvert est de savoir si une quelconque construction valide existe pour des formules arbitraires de cette forme — elle existe, et a été vérifiée.

VI. Conclusion

Le mécanisme porte AND/condition de victoire de la Section 6 de l’article consolidé, tel que spécifié à l’origine, ne filtre pas correctement plus d’une entrée booléenne : le mat est délivré dès que le jeton le plus proche de V se détache, indépendamment de tout autre jeton dans la chaîne, ce qui est plus proche d’un OR que de l’AND revendiqué. Ceci a été vérifié directement contre le générateur de coups légaux avec des jetons placés immédiatement adjacents à V — l’arrangement le plus fort disponible — écartant le placement comme cause. La faille n’était visible dans aucun test antérieur à celui-ci car chaque test précédent, y compris les propres travaux de composition et d’arbre de jeu de ce projet, vérifiait une condition proxy (V peut-elle atteindre une case spécifique) qui coïncide avec la véritable condition de victoire (V dispose-t-elle d’un quelconque coup légal) uniquement dans le cas à entrée unique. Une réparation valide a été trouvée et vérifiée pour des formules arbitraires construites à partir de OR et AND : maintenir la propre porte de V à exactement un jeton adjacent, et calculer toute la logique des sous-formules entièrement en dehors de la case de V, en câblant le résultat. Ceci restaure la correction au prix de la composition à jeton unique et triple usage que ce projet poursuivait ; récupérer cette propriété plus forte, si tant est que ce soit possible, demeure ouvert.

Références