El precio de una solución completa
Una búsqueda exacta del 16x16 con cinco pistas cuesta unos 2^134,4 nodos, y ninguna vía examinada cierra la brecha de 56 a 73 bits frente a presupuestos de 2^78 y 2^61,5 nodos. El trabajo queda aparcado, con las condiciones de reapertura declaradas. Esta página reúne las cifras fijas e indexa las diez páginas que las respaldan.
por Raphaël Anjou
Agotar una búsqueda simple, fila por fila, sobre las piezas reales de Eternity II con cinco pistas requiere unos 10^40,457 nodos (2^134,4), medido, y la predicción del modelo aleatorio cae a menos de 0,04 cifras. En esta estadística, el juego de piezas oficial es un miembro corriente de los tableros pintados con los mismos recuentos de colores. Esto fija el precio de la búsqueda completa; no encuentra ninguna forma de acortarla.
Refutar un marco completo falso de las piezas reales no sale barato: se cumple la línea de fracaso preregistrada, y refutar marcos parciales cuesta de 2,2 a 2,5 bits más de lo que ahorra. La información barata sobre el marco, unos 17,4 bits, está en las cuatro esquinas con pista. Si los marcos alejados de las esquinas se refutan barato sigue sin decidirse.
Con un barrido por filas, una ficha conocida quita entre 1 y 10 bits del árbol de búsqueda completo según la sola posición de su casilla en el barrido (mediana de 5,8 bits, en tableros 16x16 pintados), y varias fichas juntas valen menos que su suma. En esos tableros, 10 fichas bien repartidas dejan el árbol por encima de 10^15 nodos y de 16 a 24 lo bajan por debajo, una cifra comprobada solo de extremo a extremo. Nada de esto mide el puzle real, salvo dos comprobaciones de transferencia.
Un filtro añadido al barrido por filas solo puede ahorrar lo que su profundidad permite, y las comprobaciones que refutan casi todos los tableros erróneos solo empiezan a actuar en las profundidades 144 a 192, pasado el nivel más ancho del árbol (158). Un corte gratuito perfecto en la profundidad 144 ahorraría 2,4 bits de los 134,4 que cuesta el barrido: ningún filtro tardío cierra la brecha. La tabla de techos es aritmética derivada de un perfil medido, no un experimento.
Ninguna de las siete familias de enfoques (búsqueda que aprende, representaciones con pérdida, forma del árbol, órdenes adaptativos, estructura del conjunto de fichas, reformulación algebraica o del espacio de búsqueda), ni las ideas lejanas, los nogoods del marco o los otros órdenes de relleno, se valora en 10 bits o más con un mecanismo detrás. La mayor ganancia que sobrevive es de unos 5,5 bits, frente a una brecha de 56 a 73 bits; algunos cierres descansan en un solo lector o una sola familia de resolutores y se marcan como tales.
Diez pequeños experimentos de motor preinscritos, sobre tableros generados de 6x6 a 9x9, conservaron cinco y descartaron cinco. La única mejora medida es un nodo que cuesta de 5.3 a 6.1 veces menos con una búsqueda idéntica; ninguno de los tres métodos que cambian el árbol (retroceso por bloqueador, orden de valores por impacto, emparejamiento de Hall) lo redujo frente a su referencia. Nada de esto es progreso en Eternity II.
Cinco experimentos preinscritos sobre recordar e indexar los callejones sin salida no hallaron ninguna ganancia que importe para una resolución completa. Tres se descartaron (bandas del mapa de diferencias, repetición indexada por el corte, indexación con cinco pistas) y dos se conservaron como mediciones (indexación por cuota, y curva de cuota con cinco pistas). El resultado conservado sobre la cuota es un efecto de ritmo de 53 veces, unos 5.7 bits de ritmo, que no es un árbol más pequeño.
Nuestro port de un backtracker de tipo récord difería del motor publicado en siete puntos; los siete se corrigieron y se probaron, y las secuencias de nodos coinciden con el port anterior allí donde los interruptores heredados están activos. Con las cinco pistas, los valores fieles rinden peor que los antiguos (profundidad máxima 18 a 54 frente a 33 a 215 en ocho semillas), así que la corrección no es una mejora en ese caso.
En tableros de juguete generados, una relajación semidefinida del emparejamiento de aristas queda certificada limpia en tres tableros 5x5, indecisa en uno e inexacta en otro; no cabe en 16x16 y no dio ninguna lectura en 6x6. Su forma de rango bajo sí encuentra soluciones, pero como una búsqueda aleatoria que el recocido simple supera en coste. Nada de esto es un avance en Eternity II.
El aprendizaje de cláusulas no da ninguna ventaja creciente sobre la simple propagación por consistencia de arco en prefijos erróneos de las piezas reales: la línea de parada fijada de antemano se activó sobre el trabajo acumulado, y en recuentos el aprendizaje vale 0 bits más que la consistencia de arco. Los tableros de juguete (5x5 a 7x7) apuntan en el mismo sentido sin establecerlo. Nada de esto es progreso en Eternity II.
determinista: se reproduce bit a bit
just experiments approach-pricingReimprime en segundos la tabla del techo de un corte gratuito perfecto a partir del perfil de niveles versionado. No repite el perfil del barrido por filas, las pruebas en tableros pequeños ni las recomprobaciones, que están en las carpetas de experimentos citadas en las fuentes.
Seguir explorando
Citado por
- Un mapa de todos los enfoques conocidos
- Los experimentos de Raphaël Anjou
- El precio de una búsqueda completa
- Marco y esquinas: refutar un marco falso no sale barato
- Cuánto vale una ficha conocida con el barrido por filas
- Filtros tardíos: toda comprobación que funciona, funciona demasiado tarde
- Siete familias de enfoques valoradas frente al árbol del barrido por filas
- Diez experimentos de motor en tableros pequeños: nodos más rápidos, árboles no más pequeños