Les expériences de Raphaël Anjou

Les moteurs partagés qui sous-tendent les expériences de Raphaël Anjou. Les expériences nommées sont des études qui s'appuient dessus ; voici l'appareillage qu'elles ont en commun. Les préréglages CSP et la réimplémentation de Verhaard sont documentés intégralement, aux côtés du moteur de référence, du backtracker JIT, d'un guide de la vitesse et du harnais de l'échelle de tailles ; les moteurs constructifs ne sont pas encore publiés.

Le backtracker Rust-vers-WebAssembly qui anime chaque démo en direct et vérifie chaque chiffre de ce wiki. Non pas une machine à records mais un moteur de référence, porté quatre fois et validé octet par octet, conçu pour que les affirmations d'ici soient rejouables.

Sept expériences de recherche nommées qui visent le score, chacune un pipeline plutôt qu'un algorithme unique : elle construit un plateau avec un moteur, puis le relève ou l'achève avec un autre. À leurs côtés, deux constats décortiquent la machinerie sur laquelle les pipelines s'appuient. Chaque page consigne son idée, son plateau et les questions qu'elle laisse ouvertes.

Une seule question, posée avec soin : parmi les backtrackers en profondeur d'abord pour Eternity II, qu'apporte réellement chaque ordre de remplissage, chaque heuristique et le mécanisme de rupture ? Une famille de backtrackers écrits de zéro, séparés chacun par un seul changement, exécutés sur les mêmes dix variantes à coins fixés, sur un seul cœur, pendant soixante secondes.

Donner à un backtracker cinq pièces correctes gratuitement, dans la géométrie même des indices du puzzle. Il s'avère que cela n'aide pas, et selon l'ordre de remplissage cela peut nuire gravement, car une pièce épinglée est une contrainte dure qu'un ordre de remplissage fixe doit satisfaire à son arrivée. Une famille d'ordres de remplissage, exécutée sur les mêmes plateaux indicés, un seul cœur, mesurée contre l'absence totale d'indices.

La jumelle de l'étude DFS, pour l'autre manière d'attaquer Eternity II : détruire une partie d'un plateau, la reconstruire, garder le changement s'il aide. Une question, posée avec soin. Que rapporte chaque décision de cette boucle : quelle région détruire, comment la reconstruire, quand garder un mouvement, quand redémarrer, et de quel plateau partir ?

Une étude en cinq expériences d'une seule idée : plutôt que de chercher Eternity II à partir de zéro, exploiter la structure du corpus de grilles fortes déjà trouvées et la réinjecter dans une recherche. Un a priori de position, un vote de coup appris, une boussole de demande rare, un mineur d'anti-motifs et un décodage de record, du signal le plus simple au plus subtil, et le mur unique que les cinq atteignent.

Des expériences exactes de fin de partie qui se rejoignent au milieu : énumérer une région depuis deux extrémités et raccorder sur la couture, pour trouver la vraie meilleure complétion avec une preuve plutôt que la meilleure conjecture d'une heuristique. Elles mesurent exactement une petite région au lieu de courir après le score du plateau entier.

Certains moteurs Eternity II mettent tout leur effort à parcourir l'arbre de recherche le plus vite possible ; d'autres le mettent dans le jugement sur où chercher. Voici le plaidoyer pour les premiers - ce qu'achète le débit brut, les trois choses différentes qu'on appelle « rapide », et pourquoi le moteur le plus rapide jamais construit ne sait toujours pas résoudre le puzzle.

Un backtracker Rust en profondeur d'abord, sûr et portable, spécialisé à l'exécution en émettant puis compilant du Rust propre à chaque puzzle, porté de 43 à 123 millions de nœuds de recherche par seconde sur un cœur. Mesuré équitablement face au C de Peter McGavin sur la même machine : à égalité sur les plateaux difficiles et profonds comme le vrai Eternity II, et à environ 44 % de sa vitesse sur les faciles. Chaque échelon parcourt l'arbre identique ; tout le gain vient du code, pas de l'algorithme.

Suivre, couleur par couleur, l'offre de demi-arêtes face à la demande du front dans un DFS à budget de ruptures, et élaguer dès que le déficit ou sa parité dépasse les ruptures restantes. Correct par construction ; le gain se compose avec la profondeur.

Une énergie libre issue de la propagation de croyances, calculée sur les pièces restantes de la dernière rangée, prédit le rang de la meilleure fin possible. Le signal n'est pas un proxy du score brut, survit à un changement de producteur et meurt au-delà d'une rangée.

Un banc qui fait tourner n'importe quel solveur, tel quel, sur des plateaux plantés entièrement résolubles à N = 8, 10, 12, 14, chacun avec un plafond prouvé de 2N(N-1) : la taille d'effondrement d'une méthode se mesure avant de passer des semaines sur le vrai 16×16.