# Simulated annealing and parallel tempering > Treat mismatches as energy and temperature as tolerance for making things worse. Annealing holds the puzzle's longest-standing record; parallel tempering crosses barriers annealing can't. Both stop at the same wall. - Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/local-search/parallel-tempering/ - Updated: 2026-07-02 - Topics: local-search - Source: Swendsen & Wang, Replica Monte Carlo Simulation of Spin-Glasses (Physical Review Letters, 1986) — https://doi.org/10.1103/PhysRevLett.57.2607 - Source: Earl & Deem, Parallel tempering: Theory, applications, and new perspectives (Phys. Chem. Chem. Phys., 2005) — https://arxiv.org/abs/physics/0508111 - Source: The Eternity II mailing list, where Verhaard described his 2008 annealing method (groups.io) — https://groups.io/g/eternity2 --- Simulated annealing reads a board as a physical system: unmatched edges are energy, moves that lower the energy are always accepted, and moves that raise it are accepted with probability $e^{-\Delta E / T}$. Run hot and the search wanders; cool it and the board settles into a low-energy arrangement, ideally a deep one, not merely the nearest one. The catch is the schedule: cool too fast and you freeze into a mediocre local optimum, cool slowly enough for a puzzle this size and you wait forever. ## From one temperature to a ladder Parallel tempering (replica exchange) dissolves the schedule problem by running the whole ladder at once. The method comes from spin-glass physics: Swendsen and Wang's [1986 replica Monte Carlo paper](https://doi.org/10.1103/PhysRevLett.57.2607) is the precursor, replica exchange in its modern form is usually credited to Geyer (1991) and Hukushima and Nemoto (1996), and Earl and Deem's [2005 review](https://arxiv.org/abs/physics/0508111) is the standard modern survey. $K$ copies of the board run simulated annealing at fixed temperatures $T_1 < T_2 < \dots < T_K$; periodically, adjacent replicas propose to swap states, accepted with the Metropolis rule $$ P(\text{swap}) = \min\bigl(1,\; e^{(\beta_i - \beta_j)(E_i - E_j)}\bigr) = \min\bigl(1,\; e^{\Delta\beta\,\Delta E}\bigr), $$ with $\beta = 1/T$, $\Delta\beta = \beta_i - \beta_j$ and $\Delta E = E_i - E_j$. Read it once with concrete signs: if replica $i$ is the colder one ($\Delta\beta > 0$) and the hotter replica holds the *lower* energy ($\Delta E > 0$), the exponent is positive and the swap is accepted with certainty: the good state always gets handed down the ladder for free. Hot replicas roam across barriers; cold replicas exploit; the swaps shuttle promising configurations down the ladder to be refined. No single chain ever has to survive a cooling schedule. ## See the ladder beat one cold chain The claim worth seeing is the comparison: the same cold chain, with and without a ladder above it. Below, four replicas explore a rugged synthetic landscape whose global minimum hides behind barriers; a grey ghost runs the identical cold dynamics alone. Watch the swap flashes (green for accepted) carry the right-hand basin down to the cold rung, while the ghost sits in the starting well forever. Then drag the spacing slider to both extremes and reproduce the two classic ladder failures. > **[Figure]** Interactive: the parallel-tempering ladder — interactive: TemperingLadderLab. Rendered on the canonical page (link above); not shown in this markdown export. ## Step by step One round of parallel tempering, as the lab runs it: 1. **Sweep.** Every replica performs Metropolis moves at its own fixed temperature: propose a local change, compute $\Delta E$, accept if downhill, else with probability $e^{-\Delta E / T_i}$. On a board, a single-piece move touches at most four seams, so each move's $\Delta E$ is $O(1)$. 2. **Swap attempt.** Pick an adjacent pair $(i, i{+}1)$, compute $\Delta\beta\,\Delta E$ from the two cached energies, accept with $\min(1, e^{\Delta\beta \Delta E})$. On acceptance the two replicas exchange configurations (equivalently: temperatures); nothing else moves. 3. **Bookkeeping.** Track the swap-acceptance rate per rung pair. That number *is* the ladder diagnostic: near 100%, adjacent rungs see the same landscape and one of them is wasted; near 0%, the ladder has decoupled into independent chains. Useful ladders sit in the tens of percent: frequent but not free, exactly the regime Earl and Deem recommend and the one our runs converged to. 4. **Repeat.** The good states random-walk down the rungs; the stuck states ride up, get shaken loose, and come back different. ## What it costs - **Per sweep:** $R$ replicas × $N$ sites, each move $O(1)$ local evaluation, so $O(R \cdot N)$, exactly $R$ times one chain. Memory is $O(R \cdot N)$: every replica is a full board. - **Per swap phase:** the $R{-}1$ adjacent pairs each need one exponential of cached energies: $O(R)$ total, a rounding error next to the sweeps. - **The win is mixing time, not step cost.** A lone cold chain crosses an energy barrier $\Delta E$ in roughly $e^{\Delta E / T_{\text{cold}}}$ attempts (the Arrhenius wait; our measured 76-cell crossing sat at $e^{-21}$ per attempt at $T = 1$). The ladder replaces that wait with diffusion: a configuration random-walks across $R$ rungs, and with geometric spacing tuned for constant per-rung acceptance, a round trip costs on the order of $R^2$ swap rounds. You pay a constant factor $R$ per sweep to turn an exponential wait into a polynomial shuttle. That asymmetry is the entire argument for the method. - **No guarantees, same as all samplers.** Parallel tempering is not complete and certifies nothing; it converges to the right distribution eventually, with no useful bound on "eventually". And where the landscape offers ties instead of barriers, as on the iso-score plateaus at the top of this puzzle, $\Delta E = 0$ makes every rung behave identically, and the ladder's advantage vanishes by construction, which is precisely what the verdict below reports. ## Why this puzzle needs the ladder This project's measurements (on our own engine; not independently replicated) give an unusually concrete reason. Between one strong board and a better one, the connecting move is a single interlocking relocation of dozens of pieces in which *every* strict subset of the move loses edges: the [σ-cycle structure](/research/why/sigma-cycles). One measured transition required a 76-cell move whose intermediate states sat about 21 edges below the start: at $T = 1$ the acceptance is on the order of $e^{-21}$, hopeless. With the ladder's top temperature raised to roughly 30, the crossing actually happened, and produced what was then the project's best cold-start board. Temperature, used correctly, is a real lever against real barriers. Ladder design is where practice bites. When we spaced the temperatures too closely, replica exchange accepted every swap. A 100% acceptance rate sounds healthy and means the opposite: adjacent replicas saw effectively the same landscape, and the ladder added nothing. Geometric spacing with a genuinely hot top rung, tuned so that swaps are frequent but not free, is the standard advice in Earl and Deem, and it matched what we observed. ## The community record that annealing built Annealing has a distinguished history on this puzzle. The longest-standing record on the canonical piece set (Louis Verhaard's 467 of 480 in 2008, unbeaten until the Blackwood-era backtrackers of 2020) came from an annealing method, and an unusual one: as he described it on the [community mailing list](https://groups.io/g/eternity2), he annealed the *composition* of a piece subset, swapping pieces in and out of a candidate group under a tilability score, rather than annealing positions on the board. The lesson generalizes: on Eternity II, the choice of *what to anneal* mattered more than the annealing itself. ## The verdict From this project's measurements, hedged accordingly: parallel tempering is a better barrier-crosser than plain annealing, and on the mid-range of the climb that difference is real and bankable. Near the top it dissolves. The plateaus up there are iso-score: ties everywhere, so acceptance no longer depends on temperature at all, and cranking the heat instead of climbing just randomizes the board, which then never finds its way back to record territory. Replicas launched from a top board plateau at the seed's score, every chain, every ladder we tried. Tempering moves you between hills; it does not repeal the [rigidity wall](/research/why/rigidity-wall). ## Related - [The rigidity wall](https://eternity2.dev/research/why/rigidity-wall) — Every record board we have is frozen in place. You cannot nudge your way from a great board to a perfect one, and we can prove it. - [Why basin-hopping looks impossible](https://eternity2.dev/research/why/sigma-cycles) — If you can't improve a great board by polishing it, maybe you can jump to a different great board. On every record pair tested, you can't, and the structural reason why is worth seeing. - [Local search and ALNS](https://eternity2.dev/research/build/local-search/local-search-alns) — Destroy part of a board, rebuild it better, and let the algorithm learn which demolitions pay. Adaptive large-neighborhood search is the most reliable polisher this project has, and the cleanest demonstration of the wall where polishing ends.