Tratar los desajustes como energía y la temperatura como tolerancia a empeorar las cosas. El recocido ostenta el récord más longevo del puzzle; el tempering paralelo cruza barreras que el recocido no puede. Ambos se detienen en el mismo muro.
El recocido simulado lee un tablero como un sistema físico: las aristas sin
emparejar son energía, los movimientos que reducen la energía se aceptan
siempre, y los que la aumentan se aceptan con probabilidad
e−ΔE/T. En caliente, la búsqueda deambula; al enfriarla, el
tablero se asienta en una disposición de baja energía, idealmente una profunda,
y no simplemente la más cercana. La trampa está en el calendario: enfría
demasiado rápido y te congelas en un óptimo local mediocre; enfría lo bastante
despacio para un puzzle de este tamaño y esperarás una eternidad.
El tempering paralelo (intercambio de réplicas) disuelve el problema del
calendario ejecutando toda la escalera a la vez. El método procede de la física
de los vidrios de espín: el
artículo de Monte Carlo por réplicas de 1986
de Swendsen y Wang es el precursor, el intercambio de réplicas en su forma
moderna suele atribuirse a Geyer (1991) y a Hukushima y Nemoto (1996), y la
revisión de 2005 de Earl y Deem es la
síntesis moderna de referencia. K copias del tablero ejecutan recocido
simulado a temperaturas fijas T1<T2<⋯<TK; periódicamente,
réplicas adyacentes proponen intercambiar sus estados, intercambio aceptado
según la regla de Metropolis
P(swap)=min(1,e(βi−βj)(Ei−Ej))=min(1,eΔβΔE),
con β=1/T, Δβ=βi−βj y
ΔE=Ei−Ej. Léela una vez con signos concretos: si la réplica i
es la más fría (Δβ>0) y la réplica más caliente tiene la energía
más baja (ΔE>0), el exponente es positivo y el intercambio se
acepta con certeza: el buen estado siempre se transmite escalera abajo de forma
gratuita. Las réplicas calientes recorren las barreras; las réplicas frías
explotan; los intercambios trasladan las configuraciones prometedoras escalera
abajo para ser refinadas. Ninguna cadena individual tiene que sobrevivir nunca a
un calendario de enfriamiento.
La afirmación que vale la pena ver es la comparación: la misma cadena fría, con
y sin una escalera por encima de ella. A continuación, cuatro réplicas exploran
un paisaje sintético accidentado cuyo mínimo global se esconde detrás de
barreras; un fantasma gris ejecuta a solas la dinámica fría idéntica. Observa los
destellos de intercambio (verde para los aceptados) llevar la cuenca de la
derecha hasta el peldaño frío, mientras el fantasma permanece para siempre en el
pozo de partida. Luego arrastra el deslizador de espaciado a ambos extremos y
reproduce los dos fallos clásicos de la escalera.
▶Interactivo: la escalera del tempering paraleloExplorar →
Cuatro temperaturas, una escalera — frente a una sola cadena fría
Un paisaje de energía accidentado con una cuenca poco profunda a la izquierda (donde todo comienza) y el mínimo global a la derecha, tras las barreras. Cuatro réplicas ejecutan Metropolis a temperaturas espaciadas geométricamente; los pares adyacentes proponen intercambiar sus estados de forma periódica. El fantasma gris es el control: la misma cadena fría, sola. La réplica fría escapa por la escalera — los peldaños calientes cruzan las barreras y los intercambios van cediendo los buenos estados hacia abajo. El fantasma no sale nunca.
El paisaje es sintético, el mecanismo es exacto: propuestas de Metropolis dentro de cada peldaño y la verdadera regla de intercambio de réplicas entre peldaños. Lleva el espaciado a sus extremos para reproducir los fallos que describe la página: demasiado estrecho y todo intercambio se acepta (los peldaños adyacentes son redundantes), demasiado amplio y ninguno lo hace (la escalera se deshace). Semilla determinista — Repetir reproduce la misma trayectoria.
Una ronda de tempering paralelo, tal como la ejecuta el laboratorio:
Barrido. Cada réplica realiza movimientos de Metropolis a su propia
temperatura fija: proponer un cambio local, calcular ΔE, aceptar si
va cuesta abajo, si no con probabilidad e−ΔE/Ti. En un tablero,
un movimiento de una sola pieza toca como mucho cuatro costuras, de modo que
el ΔE de cada movimiento es O(1).
Intento de intercambio. Elegir un par adyacente (i,i+1), calcular
ΔβΔE a partir de las dos energías en caché, aceptar con
min(1,eΔβΔE). Si se acepta, las dos réplicas
intercambian sus configuraciones (de forma equivalente: sus temperaturas);
nada más se mueve.
Contabilidad. Seguir la tasa de aceptación de intercambios por par de
peldaños. Ese número es el diagnóstico de la escalera: cerca del 100 %, los
peldaños adyacentes ven el mismo paisaje y uno de ellos se desperdicia; cerca
del 0 %, la escalera se ha desacoplado en cadenas independientes. Las
escaleras útiles se sitúan en las decenas de por ciento: frecuentes pero no
gratuitas, exactamente el régimen que recomiendan Earl y Deem y aquel al que
convergieron nuestras ejecuciones.
Repetir. Los buenos estados descienden los peldaños en caminata
aleatoria; los estados atascados suben, se sacuden hasta soltarse y regresan
distintos.
Por barrido:R réplicas × N sitios, cada movimiento con una evaluación
local O(1), así que O(R⋅N), exactamente R veces una sola cadena. La
memoria es O(R⋅N): cada réplica es un tablero completo.
Por fase de intercambio: los R−1 pares adyacentes necesitan cada uno
una exponencial de las energías en caché: O(R) en total, un error de redondeo
al lado de los barridos.
La ganancia está en el tiempo de mezcla, no en el coste del paso. Una
cadena fría aislada cruza una barrera de energía ΔE en aproximadamente
eΔE/Tcold intentos (la espera de Arrhenius; nuestro
cruce de 76 celdas medido se situaba en e−21 por intento a T=1). La
escalera reemplaza esa espera por difusión: una configuración camina
aleatoriamente a través de R peldaños, y con un espaciado geométrico ajustado
para una aceptación por peldaño constante, un viaje de ida y vuelta cuesta del
orden de R2 rondas de intercambio. Pagas un factor constante R por barrido
para convertir una espera exponencial en una lanzadera polinómica. Esa
asimetría es todo el argumento del método.
Sin garantías, igual que todos los muestreadores. El tempering paralelo no
es completo y no certifica nada; converge a la distribución correcta con el
tiempo, sin ninguna cota útil sobre ese «con el tiempo». Y allí donde el
paisaje ofrece empates en lugar de barreras, como en las mesetas de
iso-puntuación en lo alto de este puzzle, ΔE=0 hace que todos los
peldaños se comporten de forma idéntica, y la ventaja de la escalera se
desvanece por construcción, que es precisamente lo que informa el veredicto de
más abajo.
Las mediciones de este proyecto (sobre nuestro propio motor; no replicadas de
forma independiente) dan una razón inusualmente concreta. Entre un tablero fuerte
y otro mejor, el movimiento que los conecta es una única relocalización
entrelazada de docenas de piezas en la que todo subconjunto estricto del
movimiento pierde aristas: la estructura de σ-ciclos.
Una transición medida requirió un movimiento de 76 celdas cuyos estados
intermedios se situaban unas 21 aristas por debajo del punto de partida: a
T=1 la aceptación es del orden de e−21, sin esperanza. Con la
temperatura máxima de la escalera elevada a aproximadamente 30, el cruce ocurrió
realmente, y produjo lo que entonces era el mejor tablero de arranque en frío del
proyecto. La temperatura, empleada correctamente, es una palanca real contra
barreras reales.
El diseño de la escalera es donde la práctica muerde. Cuando espaciamos las
temperaturas demasiado juntas, el intercambio de réplicas aceptaba todos los
intercambios. Una tasa de aceptación del 100 % suena sana y significa lo
contrario: las réplicas adyacentes veían en la práctica el mismo paisaje, y la
escalera no añadía nada. Un espaciado geométrico con un peldaño superior
genuinamente caliente, ajustado para que los intercambios sean frecuentes pero no
gratuitos, es el consejo estándar de Earl y Deem, y coincidió con lo que
observamos.
El recocido tiene una historia distinguida en este puzzle. El récord más longevo
sobre el conjunto de piezas canónico (el 467 de 480 de Louis Verhaard en 2008,
invicto hasta los backtrackers de la era Blackwood de 2020) provino de un método
de recocido, y de uno inusual: como lo describió en la
lista de correo de la comunidad, recocía la
composición de un subconjunto de piezas, intercambiando piezas dentro y fuera
de un grupo candidato bajo una puntuación de teselabilidad, en lugar de recocer
posiciones sobre el tablero. La lección se generaliza: en Eternity II, la
elección de qué recocer importó más que el recocido en sí.
A partir de las mediciones de este proyecto, matizadas en consecuencia: el
tempering paralelo cruza mejor las barreras que el recocido simple, y en el tramo
intermedio de la subida esa diferencia es real y fiable. Cerca de la cima se
disuelve. Las mesetas de allí arriba son de iso-puntuación: empates por todas
partes, de modo que la aceptación ya no depende en absoluto de la temperatura, y
subir el calor en lugar de escalar solo aleatoriza el tablero, que después nunca
encuentra el camino de vuelta al territorio de los récords. Las réplicas lanzadas
desde un tablero de cabeza se estancan en la puntuación de la semilla, en cada
cadena, en cada escalera que probamos. El tempering te desplaza entre colinas; no
deroga el muro de rigidez.