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 ?
Il existe deux façons concrètes d'attaquer Eternity II. La première consiste à
construire un plateau case par case et à revenir en arrière lorsqu'il échoue ;
l'étude DFS la décortique.
La seconde consiste à tenir un plateau entier et à le réparer : arracher une
région, la reconstruire, garder le changement s'il a aidé, et recommencer. La
réparation est l'ultime étape des chaînes construire-puis-affiner derrière les
plateaux quasi-record de ce projet, et c'est la méthode vers laquelle la
littérature se tourne dès qu'un plateau est trop bon pour qu'un déplacement d'une
seule pièce l'améliore. Cette étude décortique la boucle de réparation comme sa
jumelle a décortiqué le retour arrière : une décision à la fois, sur les mêmes
dix variantes à coins épinglés, un cœur, soixante secondes par exécution. Le
score maximal est de 480 arêtes appariées.
La boucle elle-même est courte. Une itération, parcourue ci-dessous.
Chargement…
Le but n'est pas de gagner. La plupart des variantes terminent entre 360 et 379,
et celle qui fait le mieux (446) y parvient en partant d'un plateau solide obtenu
par retour arrière plutôt que d'un plateau construit, ce qui constitue en soi la
leçon centrale de l'étude. Réparer un simple plateau glouton sur un cœur pendant
une minute est peu de chose à côté des chaînes qu'emploient les records ; ce que
l'étude mesure, c'est ce que vaut chaque décision de la boucle, en changeant
une chose à la fois et en mesurant le résultat avec le même scoreur canonique
qu'utilisent l'étude DFS et le reste du site.
Cinq familles, disposées de sorte que les voisines ne diffèrent que par une seule
décision, toutes issues d'une même boucle d'ancrage épurée (départ glouton,
destruction des cases dépareillées, recomplétion gloutonne, conservation du
résultat sauf s'il perd du score, jamais de redémarrage). Le plateau de départ
change le point où la boucle commence. L'opérateur de destruction change quelles
cases chaque itération soulève. La réparation change la manière dont le trou
est reconstruit. L'acceptation change le moment où un mouvement non améliorant
est conservé. Le redémarrage change ce qui se passe une fois que la boucle
s'enlise.
Le classement — score final moyen par variante
Score moyen (arêtes appariées) du plateau final de chaque variante, sur dix variantes à coins fixés du puzzle officiel, un cœur, 60 s par run. La couleur marque la famille, nommée sur chaque barre : la couleur n'est jamais le seul signal.
Tracé…
plateau de départopérateur de destructionréparationacceptationredémarrage
Ce que la boucle a ajouté à son plateau de départ
Les mêmes runs, mais montrant seulement le gain : l'amélioration moyenne apportée par chaque variante par rapport au plateau dont elle part. Cela isole la contribution propre de la boucle de réparation de la construction initiale — une variante qui part haut peut ajouter peu et finir haut malgré tout.
Tracé…
gain moyen (arêtes appariées)
Où l'amélioration s'arrête
Pour quatre variantes représentatives, le meilleur score atteint en fonction du nombre d'itérations (échantillonné toutes les 200 itérations, médianes sur les dix instances). Le cœur de l'étude en une image : sur un bon plateau de départ, la boucle guidée par les conflits se stabilise en quelques milliers d'itérations et les centaines de milliers suivantes ne bougent rien, tandis que la destruction aléatoire aveugle continue à trouver des gains bien plus longtemps.
Chaque variante est la même boucle destruction-réparation déclarée comme un seul changement par rapport à son parent. Ce tableau est généré depuis le registre du moteur : il correspond toujours au code exécuté. « dernier gain » est l'itération moyenne où le meilleur score a progressé pour la dernière fois ; comparez-la à « itér. » pour lire quand chaque run a stagné.
variante
famille
le changement qu'elle ajoute à son parent
moy.
gain
dernier gain
itér.
accept.
START-RANDOM
plateau de départ
start from a random board instead of a greedy construction
325.6
+307.6
2K
17.3M
0.147
START-RARE
plateau de départ
start from a rarest-color-first greedy construction (Selby/Riordan rarity)
373.3
+15.6
1K
19.4M
0.136
START-DFS
plateau de départ
start from a 20 s break-DFS board, then repair it (construct-then-refine)
446
+6.6
3K
12.7M
0.309
GREEDY-MISMATCH
opérateur de destruction
the plain loop: greedy start, destroy mismatched cells, greedy refill, keep if not worse
365.5
+17.3
2K
21.0M
0.199
RANDOM-DESTROY
opérateur de destruction
destroy random cells instead of mismatched ones (geometry-blind control)
402
+53.8
6.1M
16.7M
0.741
BAND-DESTROY
opérateur de destruction
destroy the worst band of two rows instead of scattered mismatched cells
348.6
+0.4
0
5.4M
0
COMPONENT-DESTROY
opérateur de destruction
destroy one connected mismatch component plus a one-cell halo
351.8
+3.6
66
4.8M
0.017
REPAIR-JITTER
réparation
break greedy-refill score ties with a seeded coin (controlled exploration)
364.9
+16.7
455
18.7M
0.252
REPAIR-SMALL
réparation
destroy at most six mismatched cells instead of twelve (small-hole baseline)
362.9
+14.7
3K
33.4M
0.651
REPAIR-EXACT
réparation
rebuild the small hole exactly by bounded assignment instead of greedily
359.6
+11.4
620
5.0M
0.997
ACCEPT-STRICT
acceptation
keep only strict improvements (no sideways moves)
360.6
+12.4
13K
18.2M
0
ACCEPT-ANNEAL
acceptation
accept worsening moves under a cooling simulated-annealing temperature
376.6
+28.4
15K
22.7M
0.69
ACCEPT-LATE
acceptation
accept against the score 40 iterations ago (late-acceptance hill climbing)
369.4
+21.2
2K
20.8M
0.303
RESTART-KICK
redémarrage
after 400 stalled iterations, randomly kick 24 cells to escape the basin
364.9
+16.7
524
15.3M
0.186
RESTART-REVERT
redémarrage
on a stall, revert to the best board so far instead of kicking (softer perturbation)
Partir d'un plateau solide obtenu par retour arrière remporte l'étude
entière. La variante qui consacre ses vingt premières secondes à exécuter le
break-DFS de l'étude DFS, puis répare le plateau à un peu plus de 440 qui en
résulte, termine la plus haute de toutes, avec une moyenne de 446 (meilleur
résultat 449). La réparation n'ajoute qu'une poignée d'arêtes par-dessus ce
plateau, mais le plateau dont elle part vaut cent points de plus qu'une
construction gloutonne, et cela se répercute jusqu'au bout. C'est la division du
travail construire-puis-affiner qu'emploient les records, reproduite de bout en
bout sur un cœur en une minute.
Parmi les variantes à départ glouton, la destruction aléatoire l'emporte et
cibler les défauts se retourne contre soi. Une destruction aveugle à la
géométrie qui soulève douze cases aléatoires termine à une moyenne de 402
(meilleur résultat 409) et continue de s'améliorer tard dans l'exécution. Tout
opérateur qui cible les cases dépareillées termine en dessous, et plus il se
fixe précisément, plus il fait mal : l'ancre des cases dépareillées atterrit à
366, une destruction par composante connexe plus large à 350. Sur un plateau
médiocre, il y a de l'amélioration disponible partout, si bien qu'explorer vaut
mieux qu'attaquer là où ça fait déjà mal. Cela s'inverse sur un plateau
quasi-record, où les quelques défauts restants sont la seule chose qu'il reste à
corriger.
Le plateau de départ fixe le plancher. Une construction gloutonne démarre
autour de 348 ; une construction aléatoire démarre près de 18, et bien que la
boucle la fasse gagner un spectaculaire 308 points, elle termine tout de même en
dessous de là où le départ glouton commençait. La construction est le levier,
la réparation est le polissage.
La règle d'acceptation est l'autre véritable levier. Le recuit simulé, qui
descend occasionnellement pour quitter un plateau, est la règle d'acceptation la
plus forte avec une nette marge (moyenne 377, meilleur résultat 394), bien devant
une montée de colline stricte (361). Le degré de tolérance accordé à un mouvement
non améliorant vaut un écart de seize points sur la même boucle.
Les raffinements astucieux ne rapportent rien ici. Une destruction de bande
entière est inerte (zéro amélioration sur neuf instances sur dix). Une
recomplétion exacte bornée d'un petit trou ne bat pas une recomplétion
gloutonne simple du même trou, un résultat négatif net : ses reconstructions
localement parfaites coûtent assez d'itérations pour que davantage de
reconstructions gloutonnes moins chères aillent tout aussi loin. Ni un coup de
pied aléatoire ni un retour-au-meilleur en cas d'enlisement ne décollent le score
de la référence sans redémarrage.
Chacun de ces points a son propre traitement : la manière dont le moteur est
construit et la signification de chaque statistique avancée sont sur la page
méthode, et les
comparaisons de destruction, réparation, acceptation, redémarrage et plateau de
départ sont détaillées sur la page des
résultats.
Chaque plateau est re-scoré par l'unique scoreur canonique, et le score
auto-déclaré d'aucun moteur n'est cru. La boucle maintient son score de manière
incrémentale à mesure qu'elle place et soulève des pièces, mais le nombre publié
est toujours un re-score canonique frais du plateau produit. Le débit est reporté
en itérations de réparation par seconde et n'est jamais comparé d'une famille à
l'autre, car une itération qui exécute une recomplétion exacte n'est pas la même
unité de travail qu'une itération qui exécute un remplissage glouton.
L'axe à surveiller est le plateau d'enlisement : l'itération à laquelle le
meilleur global s'est amélioré pour la dernière fois, face au nombre total
d'itérations exécutées. Quand la première est de quelques milliers et le second de
centaines de milliers, l'exécution a trouvé sa réponse tôt puis a rabâché le même
bassin pour le reste de la minute. Cet écart est la forme mesurée d'une
observation de longue date sur ce casse-tête : la destruction-réparation est une
superbe exploratrice de bassin et ne s'échappe pour ainsi dire jamais du bassin où
elle atterrit.
Tout l'appareillage (le moteur, les dix variantes, les résultats par exécution
commités et les scripts de la grille) réside sous le répertoire de
référence
de l'étude, et just experiments repair-study reconstruit le moteur et réexécute
toute la grille. Le plateau, le scoreur et la couche d'E/S proviennent d'une
bibliothèque
partagée
qu'utilise aussi l'étude DFS, de sorte qu'un plateau réparé et un plateau obtenu
par retour arrière sont scorés par exactement le même code.