Voir les désaccords comme de l'énergie et la température comme une tolérance à la dégradation. Le recuit détient le plus ancien record du puzzle ; le tempérage parallèle franchit des barrières que le recuit ne passe pas. Les deux butent sur le même mur.
Le recuit simulé lit un plateau comme un système physique : les arêtes non
appariées sont de l'énergie, les mouvements qui abaissent l'énergie sont
toujours acceptés, et ceux qui l'augmentent le sont avec une probabilité
e−ΔE/T. À chaud, la recherche vagabonde ; en refroidissant, le
plateau se fige dans un arrangement de basse énergie, idéalement un arrangement
profond, et pas seulement le plus proche. Toute la difficulté tient au
calendrier de refroidissement : refroidissez trop vite et vous gelez dans un
optimum local médiocre ; refroidissez assez lentement pour un puzzle de cette
taille et vous attendez indéfiniment.
Le tempérage parallèle (échange de répliques) dissout le problème du
calendrier en faisant tourner toute l'échelle d'un coup. La méthode vient de
la physique des verres de spin : l'
article de Monte-Carlo par répliques de 1986
de Swendsen et Wang en est le précurseur, l'échange de répliques sous sa forme
moderne est généralement attribué à Geyer (1991) puis à Hukushima et Nemoto
(1996), et la revue de 2005 d'Earl et
Deem en est la synthèse moderne de référence. K copies du plateau exécutent
un recuit simulé à des températures fixes T1<T2<⋯<TK ;
périodiquement, des répliques adjacentes proposent d'échanger leurs états,
échange accepté selon la règle de Metropolis
P(swap)=min(1,e(βi−βj)(Ei−Ej))=min(1,eΔβΔE),
avec β=1/T, Δβ=βi−βj et
ΔE=Ei−Ej. Lisons-la une fois avec des signes concrets : si la
réplique i est la plus froide (Δβ>0) et que la réplique la plus
chaude détient l'énergie la plus basse (ΔE>0), l'exposant est
positif et l'échange est accepté avec certitude : le bon état est toujours
transmis gratuitement en descendant l'échelle. Les répliques chaudes parcourent
les barrières ; les répliques froides exploitent ; les échanges font descendre
les configurations prometteuses le long de l'échelle pour qu'elles soient
raffinées. Aucune chaîne unique n'a jamais à survivre à un calendrier de
refroidissement.
L'affirmation qui vaut d'être vue est la comparaison : la même chaîne froide,
avec et sans une échelle au-dessus d'elle. Ci-dessous, quatre répliques
explorent un paysage synthétique accidenté dont le minimum global se cache
derrière des barrières ; un fantôme gris exécute seul la dynamique froide
identique. Observez les éclairs d'échange (vert pour accepté) faire descendre
le bassin de droite jusqu'au barreau froid, tandis que le fantôme reste
éternellement dans le puits de départ. Puis faites glisser le curseur
d'espacement vers ses deux extrêmes et reproduisez les deux échecs classiques
de l'échelle.
▶Interactif : l'échelle du tempérage parallèleExplorer →
Quatre températures, une échelle — contre une seule chaîne froide
Un paysage d'énergie accidenté : un bassin peu profond à gauche (où tout démarre) et le minimum global à droite, derrière des barrières. Quatre répliques font du Metropolis à des températures espacées géométriquement ; les paires adjacentes proposent périodiquement d'échanger leurs états. Le fantôme gris est le témoin : la même chaîne froide, seule. La réplique froide s'échappe par l'échelle — les barreaux chauds franchissent les barrières, les échanges font descendre les bons états. Le fantôme, lui, ne sort jamais.
Le paysage est synthétique, le mécanisme est exact : propositions de Metropolis dans chaque barreau, et la vraie règle d'échange de répliques entre barreaux. Poussez l'espacement aux extrêmes pour reproduire les pannes décrites par la page : trop serré, tout échange est accepté (les barreaux adjacents sont redondants) ; trop large, plus aucun ne l'est (l'échelle se disloque). Graine déterministe — Rejouer reproduit la trajectoire à l'identique.
Un tour de tempérage parallèle, tel que le laboratoire l'exécute :
Balayage. Chaque réplique effectue des mouvements de Metropolis à sa
propre température fixe : proposer un changement local, calculer ΔE,
accepter si cela descend, sinon avec une probabilité e−ΔE/Ti.
Sur un plateau, un mouvement d'une seule pièce touche au plus quatre coutures,
de sorte que le ΔE de chaque mouvement est en O(1).
Tentative d'échange. Choisir une paire adjacente (i,i+1), calculer
ΔβΔE à partir des deux énergies mises en cache, accepter
avec min(1,eΔβΔE). En cas d'acceptation, les deux
répliques échangent leurs configurations (de manière équivalente : leurs
températures) ; rien d'autre ne bouge.
Comptabilité. Suivre le taux d'acceptation des échanges par paire de
barreaux. Ce nombre est le diagnostic de l'échelle : proche de 100 %, les
barreaux adjacents voient le même paysage et l'un d'eux est gaspillé ; proche
de 0 %, l'échelle s'est découplée en chaînes indépendantes. Les échelles
utiles se situent à quelques dizaines de pour cent : fréquentes mais pas
gratuites, exactement le régime qu'Earl et Deem recommandent et celui vers
lequel nos exécutions ont convergé.
Recommencer. Les bons états descendent les barreaux en marche aléatoire ;
les états bloqués remontent, sont secoués pour se libérer, et redescendent
différents.
Par balayage :R répliques × N sites, chaque mouvement demandant une
évaluation locale en O(1), soit O(R⋅N), exactement R fois une seule
chaîne. La mémoire est en O(R⋅N) : chaque réplique est un plateau
complet.
Par phase d'échange : les R−1 paires adjacentes nécessitent chacune une
exponentielle des énergies en cache : O(R) au total, une erreur d'arrondi à
côté des balayages.
Le gain porte sur le temps de mélange, pas sur le coût du pas. Une chaîne
froide isolée franchit une barrière d'énergie ΔE en environ
eΔE/Tcold tentatives (l'attente d'Arrhenius ; le
franchissement de 76 cellules que nous avons mesuré se situait à e−21 par
tentative à T=1). L'échelle remplace cette attente par de la diffusion :
une configuration se promène aléatoirement à travers R barreaux, et avec un
espacement géométrique réglé pour une acceptation par barreau constante, un
aller-retour coûte de l'ordre de R2 tours d'échange. Vous payez un facteur
constant R par balayage pour transformer une attente exponentielle en une
navette polynomiale. Cette asymétrie constitue tout l'argument de la méthode.
Aucune garantie, comme tous les échantillonneurs. Le tempérage parallèle
n'est pas complet et ne certifie rien ; il converge finalement vers la bonne
distribution, sans borne utile sur ce « finalement ». Et là où le paysage
offre des égalités plutôt que des barrières, comme sur les plateaux à
iso-score au sommet de ce puzzle, ΔE=0 fait se comporter tous les
barreaux à l'identique, et l'avantage de l'échelle s'évanouit par
construction, ce qui est précisément ce que rapporte le verdict ci-dessous.
Les mesures de ce projet (sur notre propre moteur ; non répliquées de manière
indépendante) donnent une raison inhabituellement concrète. Entre un plateau
solide et un meilleur, le mouvement qui les relie est une unique relocalisation
imbriquée de dizaines de pièces dans laquelle tout sous-ensemble strict du
mouvement perd des arêtes : la
structure en σ-cycles. Une transition mesurée a
exigé un mouvement de 76 cellules dont les états intermédiaires se situaient
environ 21 arêtes sous le point de départ : à T=1, l'acceptation est de
l'ordre de e−21, sans espoir. Avec la température maximale de l'échelle
portée à environ 30, le franchissement a réellement eu lieu, et a produit ce
qui était alors le meilleur plateau à démarrage à froid du projet. La
température, employée correctement, est un vrai levier contre de vraies
barrières.
La conception de l'échelle est là où la pratique mord. Lorsque nous avons
espacé les températures trop étroitement, l'échange de répliques acceptait
chaque échange. Un taux d'acceptation de 100 % a l'air sain et signifie
l'inverse : les répliques adjacentes voyaient en pratique le même paysage, et
l'échelle n'ajoutait rien. Un espacement géométrique avec un barreau supérieur
véritablement chaud, réglé pour que les échanges soient fréquents mais pas
gratuits, est le conseil standard d'Earl et Deem, et il correspondait à ce que
nous avons observé.
Le recuit a une histoire distinguée sur ce puzzle. Le record le plus durable
sur le jeu de pièces canonique (le 467 sur 480 de Louis Verhaard en 2008,
invaincu jusqu'aux backtrackers de l'ère Blackwood en 2020) provenait d'une
méthode de recuit, et d'une méthode inhabituelle : comme il l'a décrit sur la
liste de diffusion communautaire, il recuisait
la composition d'un sous-ensemble de pièces, échangeant des pièces à l'entrée
et à la sortie d'un groupe candidat sous un score de pavabilité, plutôt que de
recuire des positions sur le plateau. La leçon se généralise : sur Eternity II,
le choix de ce que l'on recuit comptait davantage que le recuit lui-même.
À partir des mesures de ce projet, nuancées en conséquence : le tempérage
parallèle franchit mieux les barrières que le recuit ordinaire, et sur la
tranche intermédiaire de la montée cette différence est réelle et fiable.
Près du sommet, elle se dissout. Les plateaux de là-haut sont à iso-score :
des égalités partout, de sorte que l'acceptation ne dépend plus du tout de la
température, et pousser la chaleur au lieu de grimper ne fait que randomiser le
plateau, qui ensuite ne retrouve jamais le chemin du territoire des records.
Les répliques lancées depuis un plateau de tête plafonnent au score de la
graine, à chaque chaîne, à chaque échelle que nous avons essayée. Le tempérage
vous déplace entre les collines ; il n'abroge pas le
mur de rigidité.