Reconstruire à l'identique les plateaux stricts à 460 de la communauté, et découvrir au passage le coup que les solveurs ordinaires ne savent pas jouer : payer deux désaccords sur une même case.
Reproduireavec graine — se reproduit avec la graine donnée·relance la recherche (Voir ci-dessous)·Budget: not logged (exploratory run, not the standardized single-core bench)
Complexité
Temps
DFS with an exact 14-cell tail; 8 threads, 5 s restart cadence, per-witness budget
Espace
bounded by the DFS frontier plus the fixed frame and the witness schedule
Backtracking search is exponential in the worst case; the exact tail and the witness schedule tame it to a targeted replay rather than a blind hunt.
Matériel & exécution
Exécution nativeCPU seul
Cœurs
8
RAM
16 GiB
GPU
0
CPU
Apple M1
Machine
MacBook (Apple M1, 8 cores)
Budget
not logged (exploratory run, not the standardized single-core bench)
REPLAY clôt l'étude sur une
forme d'apprentissage différente. Chaque expérience qui l'a précédée extrayait une
statistique de l'ensemble du corpus ; REPLAY apprend d'un seul plateau, et il
apprend la chose qu'une statistique ne peut pas montrer : le coup exact qu'un record
a joué et que notre recherche ne savait pas faire. Les plateaux publics entièrement
indicés servant d'étalon à ce projet atteignent 460 (le record communautaire est
depuis passé à 464), mais la propre recherche à ruptures autorisées de ce projet
plafonnait à 457 ou 458, quoi qu'il arrive. REPLAY s'est donné pour but de reproduire
ces plateaux 460 à l'identique, pièce par pièce, afin d'apprendre ce qu'ils faisaient
que notre recherche ne savait pas faire. La réponse s'est révélée être un unique coup
resté inaperçu.
Une recherche à ruptures autorisées ne laisse normalement une case porter qu'un seul
désaccord au moment où on la place. REPLAY assouplit cette règle pour en admettre deux
sur certaines cases, et réordonne le classement des placements candidats de sorte que
les coups réellement joués par un bon plateau connu passent devant ceux qui semblent
moins coûteux. Avec ces deux changements, elle peut suivre le chemin même qu'a emprunté
le plateau témoin.
Rejoués ainsi, les plateaux 460 de la communauté se reconstruisent à l'identique,
chaque pièce à sa place, et le score se vérifie. La reproduction est la preuve que
l'ingrédient manquant était bien réel.
▶Interactif : les cases à double ruptureExplorer →
Chargement…
▶Interactif : rejouer l'ordonnancement des rupturesExplorer →
Trouvez les cellules à double défaut sur un vrai plateau
Choisissez un plateau record. On le note en direct, on trouve chaque bord non apparié, et on signale les cellules qui portent deux défauts à la fois. Un solveur qui n'autorise qu'un défaut par cellule — presque tous — ne peut littéralement pas poser ces cellules, et plafonne donc quelques points en dessous. C'est le coup que REPLAY a dû ajouter pour rejouer exactement les plateaux de la communauté.
463 / 480
24 cellules cassées
9 cellules à double défaut
cellule à double défaut (deux défauts)le reste du plateau est parfaitement apparié
Les cellules à double défaut sont calculées ici à partir des bords du plateau (la même règle de bords appariés que le moteur et le classement Bucas) — pas placées à la main. Ouvrez le plateau dans le visualiseur pour inspecter chaque bord. Sur les plateaux strict-460 de la communauté, il y a 4 à 5 telles cellules ; l'ordre prior-over-cost de REPLAY plus un opérateur de défaut de coût 2 les rend atteignables.
Les deux plateaux stricts à 460 de la communauté se rejouent exactement jusqu'à 460.
La découverte : chacun contient quatre ou cinq cases qui paient deux désaccords à la
fois. Une recherche qui n'autorise qu'un seul désaccord par case ne peut littéralement
pas atteindre ces plateaux, et c'est précisément pour cela que les runs antérieurs du
projet saturaient à 457-458. Autoriser la double rupture hisse l'échelle stricte
jusqu'à 460.
C'est une explication nette d'un plateau de longue date, et une mise en garde : une
règle d'apparence raisonnable (une rupture par case) barrait en silence l'accès aux
plateaux mêmes que nous poursuivions.
Le rejeu est une recherche en profondeur d'abord menée dans un mode délibérément
contraint.
Ordonnancement prior-sur-coût. Un DFS ordinaire tolérant aux ruptures classe les
placements candidats par coût de désaccord immédiat, le moins cher d'abord. REPLAY
inverse la priorité en prior-sur-coût : les candidats réellement utilisés par le
plateau témoin passent devant ceux qui semblent moins coûteux, si bien que la
recherche est attirée le long du bon chemin connu au lieu de s'en écarter. C'est le
drapeau --prior-over-cost piloté par l'ordonnancement propre au plateau témoin.
Queue exacte. Les 14 dernières cases sont résolues exactement (--exact-tail 14)
plutôt qu'heuristiquement, si bien que la finale que les runs ordinaires bâclent se
referme de façon déterministe.
Le relâchement qui a compté. Le budget de désaccords par case passe de un à deux.
C'est ce seul changement qui rend les plateaux témoins accessibles.
Menés sur un cadre 460 fixe, 8 threads, une cadence de redémarrage de 5 secondes et un
budget par run, les deux témoins stricts à 460 de la communauté se reconstruisent pièce
par pièce et le score se vérifie : la reproduction est la preuve que l'ingrédient
manquant était la double rupture.
Le constat. Chaque témoin contient quatre ou cinq cases qui paient deux désaccords
à la fois. Une recherche plafonnée à une rupture par case ne peut pas représenter ces
plateaux, et c'est exactement pour cela que les runs antérieurs du projet, tolérants aux
ruptures, saturaient à 457-458. C'est un résultat de complétude de recherche déguisé en
tentative de record : le mur était dans le jeu de coups, non dans le calcul.
Celle-ci est initialisée par graine et plus proche du déterminisme que les
constructeurs stochastiques : le rejeu DFS à partir d'un cadre fixe et d'un
ordonnancement de témoin reconstruit les plateaux 460 de façon fiable. Les cibles qu'il
reconstitue sont les records stricts à 460 propres à la communauté,
si bien que les plateaux eux-mêmes figurent dans la chronologie des records ; ce que
cette expérience ajoute, c'est le rejeu qui les reconstruit. Le rejeu réclame deux
entrées au-delà du puzzle, un cadre de bordure et le plateau témoin de la communauté
qu'il reconstitue ; un répertoire d'appui exécutable livrant les deux est prévu.
Autoriser deux ruptures par case ouvre-t-il une voie vers 461 et au-delà, ou seulement
vers les 460 connus ? Existe-t-il des plateaux nécessitant une triple rupture ? Et
peut-on prédire les cases à double rupture à partir d'un plateau partiel plutôt que de
les découvrir par rejeu ?