La hermana del estudio DFS, para la otra manera en que se ataca Eternity II: destruir parte de un tablero, reconstruirla, conservar el cambio si ayuda. Una pregunta, planteada con cuidado. Qué aporta cada decisión de ese bucle: qué región destruir, cómo reconstruirla, cuándo conservar un movimiento, cuándo reiniciar, y desde qué tablero partir.
Hay dos maneras concretas en que se ataca Eternity II. La primera consiste en
construir un tablero celda a celda y retroceder cuando falla; el estudio
DFS lo disecciona. La segunda
consiste en sostener un tablero entero y repararlo: arrancar una región,
reconstruirla, conservar el cambio si ayudó, y repetir. La reparación es la
última etapa de las cadenas construir-y-luego-refinar que hay detrás de los
tableros casi récord de este proyecto, y es el método al que recurre la
literatura en cuanto un tablero es demasiado bueno para que el desplazamiento de
una sola pieza lo mejore. Este estudio disecciona el bucle de reparación de la
misma manera en que su hermana diseccionó el backtracking: una decisión a la vez,
sobre las mismas diez variantes con esquinas fijadas, un núcleo, sesenta segundos
por ejecución. La puntuación máxima es de 480 aristas apareadas.
El bucle en sí es corto. Una iteración, recorrida a continuación.
Cargando…
El objetivo no es ganar. La mayoría de las variantes terminan entre 360 y 379, y
la que mejor lo hace (446) lo logra partiendo de un tablero sólido obtenido por
backtracking en lugar de uno construido, lo que constituye en sí la lección
central del estudio. Reparar un simple tablero voraz en un núcleo durante un
minuto es poca cosa frente a las cadenas que emplean los récords; lo que el
estudio mide es cuánto vale cada decisión del bucle, cambiando una cosa a la vez
y midiendo el resultado con el mismo puntuador canónico que usan el estudio DFS y
el resto del sitio.
Cinco familias, dispuestas de modo que las vecinas difieran por una sola
decisión, todas ramificándose de un mismo bucle ancla depurado (arranque voraz,
destruir las celdas desapareadas, rellenado voraz, conservar el resultado salvo
que pierda puntuación, nunca reiniciar). El tablero de partida cambia el punto
donde el bucle comienza. El operador de destrucción cambia qué celdas levanta
cada iteración. La reparación cambia la manera en que se reconstruye el hueco.
La aceptación cambia el momento en que se conserva un movimiento no
mejorante. El reinicio cambia lo que ocurre una vez que el bucle se estanca.
La clasificación — puntuación final media por variante
Puntuación media (aristas coincidentes) del tablero con el que terminó cada variante, sobre diez variantes con esquinas fijadas del puzzle oficial, un solo núcleo, 60 s por ejecución. El color marca la familia, nombrada en cada barra: el color nunca es la única señal.
Dibujando…
tablero de partidaoperador de destrucciónreparaciónaceptaciónreinicio
Lo que el bucle añadió sobre su tablero de partida
Las mismas ejecuciones, pero mostrando solo la mejora: la ganancia media que cada variante logró sobre el tablero del que partió. Esto aísla la contribución propia del bucle de reparación de la construcción con la que empezó — una variante que parte alto puede añadir poco y aun así terminar alto.
Dibujando…
mejora media (aristas coincidentes)
Dónde se detiene la mejora
Para cuatro variantes representativas, la mejor puntuación hasta el momento frente al número de iteraciones (muestreada cada 200 iteraciones, medianas sobre las diez instancias). El sentido del estudio en una sola imagen: sobre un buen tablero de partida, el bucle guiado por conflictos se aplana en pocos miles de iteraciones y los cientos de miles restantes no mueven nada, mientras que la destrucción aleatoria ciega sigue encontrando ganancias durante mucho más tiempo.
Cada variante es el mismo bucle de destrucción y reparación declarado como un único cambio sobre su padre. Esta tabla se genera a partir del registro del motor, por lo que siempre coincide con el código que se ejecutó. «último mejor» es la iteración media en la que el mejor global mejoró por última vez; compárala con «iter.» para leer cuán pronto se estancó cada ejecución.
variante
familia
el único cambio que añade sobre su padre
media
mejora
último mejor
iter.
acept.
START-RANDOM
tablero de partida
start from a random board instead of a greedy construction
325.6
+307.6
2K
17.3M
0.147
START-RARE
tablero de partida
start from a rarest-color-first greedy construction (Selby/Riordan rarity)
373.3
+15.6
1K
19.4M
0.136
START-DFS
tablero de partida
start from a 20 s break-DFS board, then repair it (construct-then-refine)
446
+6.6
3K
12.7M
0.309
GREEDY-MISMATCH
operador de destrucción
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
operador de destrucción
destroy random cells instead of mismatched ones (geometry-blind control)
402
+53.8
6.1M
16.7M
0.741
BAND-DESTROY
operador de destrucción
destroy the worst band of two rows instead of scattered mismatched cells
348.6
+0.4
0
5.4M
0
COMPONENT-DESTROY
operador de destrucción
destroy one connected mismatch component plus a one-cell halo
351.8
+3.6
66
4.8M
0.017
REPAIR-JITTER
reparación
break greedy-refill score ties with a seeded coin (controlled exploration)
364.9
+16.7
455
18.7M
0.252
REPAIR-SMALL
reparación
destroy at most six mismatched cells instead of twelve (small-hole baseline)
362.9
+14.7
3K
33.4M
0.651
REPAIR-EXACT
reparación
rebuild the small hole exactly by bounded assignment instead of greedily
359.6
+11.4
620
5.0M
0.997
ACCEPT-STRICT
aceptación
keep only strict improvements (no sideways moves)
360.6
+12.4
13K
18.2M
0
ACCEPT-ANNEAL
aceptación
accept worsening moves under a cooling simulated-annealing temperature
376.6
+28.4
15K
22.7M
0.69
ACCEPT-LATE
aceptación
accept against the score 40 iterations ago (late-acceptance hill climbing)
369.4
+21.2
2K
20.8M
0.303
RESTART-KICK
reinicio
after 400 stalled iterations, randomly kick 24 cells to escape the basin
364.9
+16.7
524
15.3M
0.186
RESTART-REVERT
reinicio
on a stall, revert to the best board so far instead of kicking (softer perturbation)
Partir de un tablero sólido obtenido por backtracking gana el estudio
entero. La variante que dedica sus primeros veinte segundos a ejecutar el
break-DFS del estudio DFS, y luego repara el tablero de poco más de 440 que
resulta, termina la más alta de todas, con una media de 446 (mejor resultado
449). La reparación solo añade un puñado de aristas por encima de ese tablero,
pero el tablero del que parte vale cien puntos más que una construcción voraz, y
eso se propaga hasta el final. Es la división del trabajo construir-y-luego-refinar
que emplean los récords, reproducida de principio a fin en un núcleo en un
minuto.
Entre las variantes con arranque voraz, la destrucción aleatoria se impone y
apuntar a los defectos resulta contraproducente. Una destrucción ciega a la
geometría que levanta doce celdas aleatorias termina en una media de 402 (mejor
resultado 409) y sigue mejorando bien entrada la ejecución. Todo operador que
apunta a las celdas rotas termina por debajo, y cuanto más precisamente se
fija, peor lo hace: el ancla de las celdas desapareadas aterriza en 366, una
destrucción por componente conexa más grande en 350. Sobre un tablero mediocre
hay mejora disponible en todas partes, de modo que explorar vale más que atacar
donde ya duele. Eso se invierte en un tablero casi récord, donde los pocos
defectos restantes son lo único que queda por corregir.
El tablero de partida fija el suelo. Una construcción voraz arranca en torno
a 348; una aleatoria arranca cerca de 18, y aunque el bucle la eleva unos
espectaculares 308 puntos, aun así termina por debajo de donde el arranque voraz
comenzaba. La construcción es la palanca, la reparación es el pulido.
La regla de aceptación es la otra palanca real. El recocido simulado, que
desciende de vez en cuando para dejar una meseta, es la regla de aceptación más
fuerte por un margen claro (media 377, mejor resultado 394), muy por delante de
una escalada de colina estricta (361). Cuánto se permite un movimiento no
mejorante vale una diferencia de dieciséis puntos sobre el mismo bucle.
Los refinamientos ingeniosos no aportan nada aquí. Una destrucción de banda
entera es inerte (cero mejoras en nueve de diez instancias). Un rellenado
exacto acotado de un hueco pequeño no supera a un rellenado voraz simple del
mismo hueco, un resultado negativo limpio: sus reconstrucciones localmente
perfectas cuestan suficientes iteraciones como para que más reconstrucciones
voraces y más baratas lleguen igual de lejos. Ni una patada aleatoria ni un
retorno-al-mejor ante un estancamiento despegan la puntuación de la referencia
sin reinicio.
Cada uno de estos puntos tiene su propio tratamiento: cómo está construido el
motor y qué significa cada estadística presentada están en la página de
método, y las
comparaciones de destrucción, reparación, aceptación, reinicio y tablero de
partida se desarrollan en la página de
resultados.
Cada tablero se vuelve a puntuar con el único puntuador canónico, y no se confía
en la puntuación autodeclarada de ningún motor. El bucle mantiene su puntuación de
forma incremental a medida que coloca y levanta piezas, pero el número publicado
es siempre una nueva puntuación canónica del tablero producido. El rendimiento se
reporta en iteraciones de reparación por segundo y nunca se compara entre
familias, porque una iteración que ejecuta un rellenado exacto no es la misma
unidad de trabajo que una que ejecuta un rellenado voraz.
El eje a vigilar es el estancamiento: la iteración en la que el mejor global
mejoró por última vez, frente al total de iteraciones ejecutadas. Cuando la
primera es de unos pocos miles y la segunda de cientos de miles, la ejecución
encontró su respuesta pronto y luego molió la misma cuenca durante el resto del
minuto. Esa brecha es la forma medida de una observación de larga data sobre este
rompecabezas: la destrucción-reparación es una exploradora de cuencas soberbia y
prácticamente nunca escapa de la cuenca en la que aterriza.
Todo el aparato (el motor, las diez variantes, los resultados por ejecución
commiteados y los scripts de la grilla) reside bajo el directorio de
referencia
del estudio, y just experiments repair-study reconstruye el motor y reejecuta
toda la grilla. El tablero, el puntuador y la capa de E/S provienen de una
biblioteca
compartida
que usa también el estudio DFS, de modo que un tablero reparado y uno obtenido por
backtracking se puntúan con exactamente el mismo código.