La idea más importante de la búsqueda combinatoria difícil: reducir el espacio que se explora vence, por un margen exponencial, a explorarlo más rápido. Eternity II está diseñado para que apenas puedas reducirlo.
Imagina la búsqueda como un árbol. Desde el tablero vacío eliges una pieza para
la primera celda; a partir de ahí una pieza para la segunda; y así
sucesivamente, hasta 256 celdas de profundidad. El número de hojas en la base
es el factor de ramificación elevado a la profundidad, un número
astronómicamente grande. Para demostrar que una región no tiene solución, una
búsqueda tiene que recorrer ese árbol.
Ahora bien, hay dos maneras de hacer menos trabajo. Puedes ir más rápido: un
motor mejor, más núcleos, bucles internos afinados a mano. O puedes hacer el
árbol más pequeño, podando las ramas que no pueden llevar a ninguna
solución, de modo que el factor de ramificación efectivo disminuya. Suenan
parecidas. Ni siquiera se acercan.
Una aceleración es un divisor constante. Haz la máquina 1000× más rápida y
esperarás 1000× menos, lo mismo tanto si el árbol tiene diez niveles de
profundidad como si tiene diez mil. Te compra un múltiplo fijo, punto.
Una poda, en cambio, se compone. Recorta aunque sea un pequeño porcentaje del
factor de ramificación y ahorrarás esa fracción en cada uno de los niveles. A lo
largo de 256 niveles, los ahorros se multiplican entre sí: reducir el factor de
ramificación de b a b′ divide el trabajo por (b/b′)256. Un recorte del
5 %, aplicado hasta el fondo, vale (1/0.95)256≈5×105, el
equivalente a una aceleración de quinientas mil veces, a partir de una sola idea
estructural barata. Eso vence a casi cualquier aceleración que una máquina real
pueda ofrecer.
Pon una aceleración bruta en la balanza frente a una pequeña poda por nivel y
observa cómo la poda gana por varios órdenes de magnitud.
▶Interactivo: poder de la poda frente a velocidad brutaExplorar →
La velocidad divide; la poda divide exponencialmente
Trabajo base para agotar el árbol
10^45
…dividido por la aceleración
10^42
…dividido por la poda
10^43
Con este ajuste, la poda hace el trabajo de una aceleración de 27×.
Una aceleración es un divisor constante: aporta un múltiplo fijo, sin importar la profundidad de la búsqueda. Una poda reduce el factor de ramificación en cada uno de los ~64 niveles de aquí, así que su efecto se compone: (reducido ⁄ original) elevado a la 64. Incluso restar unos pocos por ciento al factor de ramificación empequeñece una gran aceleración bruta. Por eso los solucionadores récord ganan por lo que podan, no por la frecuencia de reloj, y por eso un puzzle diseñado para resistir la poda es tan difícil.
Árbol ilustrativo: factor de ramificación 5, profundidad 64. El de Eternity II es mucho más profundo (256), así que la diferencia es aún mayor.
Si la poda es la palanca que importa, los puzzles difíciles son aquellos que no
se pueden podar. Eternity II fue calibrado para ser precisamente eso. Cuatro de
sus muros dicen, en el fondo, lo mismo: no hay nada local que podar.
Sin jugadas forzadas: cada celda interior
aún tiene de 73 a 137 vecinos legales, así que la propagación casi nunca reduce
una celda a una sola opción. El factor de ramificación se mantiene
obstinadamente alto.
En el pico de dificultad: los recuentos
de piezas y colores se sitúan donde se espera alrededor de una solución, sin
dejar ninguna región densa en soluciones a la que apuntar un atajo
estadístico, el truco que hizo caer Eternity I.
La ley de área: el recuento de tableros
parciales genuinamente distintos se desploma más allá de ~80 celdas, pero
ninguna señal de puntuación local puede ver ese colapso global, así que no
puedes podar hacia él de forma barata.
La rigidez: incluso a partir de un tablero
récord, el salto a uno mejor es enorme e indivisible, sin gradiente que seguir
ni nada cercano que podar.
Esta es la lente para toda la sección de investigación. Un motor mucho más
rápido hace la misma búsqueda más barata, no más pequeña, y no mueve el récord.
Cada experimento que sí movió la aguja cambió en su lugar la forma de la
búsqueda: un orden de recorrido distinto, un a priori aprendido sobre dónde se
sitúan las piezas, una región confinada para los desajustes. Y cada callejón sin
salida es, en el fondo, una poda que la estructura global del puzzle se niega a
honrar. La velocidad al principio da sensación de productividad; casi nunca es
ahí donde se esconde la distancia hasta 480.
La mitad contraintuitiva de esto es que incluso la poda legal a menudo pierde.
Una comprobación que detecta un tablero parcial condenado y retrocede pronto
suena como una victoria gratis, pero si la comprobación cuesta más que el
subárbol que ahorra, un backtracker simple que sigue avanzando sin más es más
rápido. Peter McGavin expuso sin rodeos la opinión asentada en la lista de
groups.io: los métodos que intentan detectar una colocación parcial condenada y
retroceder pronto "generalmente se consideran demasiado costosos para que
merezcan la pena". Un recién llegado que ejecutaba un solucionador de diagramas
de decisión, @95A31, lo confirmó después desde cero: tras construir toda una
batería de comprobaciones de factibilidad, informó de que "todas las
comprobaciones de factibilidad que implementé resultaron inútiles", con una
búsqueda 8×8 completa todavía abriéndose paso a través de 953 mil millones de
nodos durante 17 horas. La lección no es que la poda sea mala, sino que una poda
solo compensa si es más barata que la búsqueda que elimina, y en este puzzle
casi nada local supera ese listón.
Los números del árbol en la demo son ilustrativos: un factor de ramificación y
una profundidad elegidos para ser parecidos a E2 y legibles, no la medición de
un solucionador concreto. La curva de dificultad y los recuentos de nodos, en
cambio, son mediciones reales de motor sobre puzzles pequeños, deterministas y
reproducibles con just research-prune-vs-speed. El principio en sí, divisor
constante frente a divisor exponencial, es exacto.