El motor detrás del estudio DFS: un backtracker componible donde una variante es un cambio declarado sobre un padre, una capa IO compartida que cada algoritmo habla, y las definiciones de cada estadística que el estudio plantea: tasa de nodos, profundidad, rupturas.
por Raphaël Anjou
Esta página es el aparato detrás del estudio DFS: cómo está construido el motor, por qué una nueva variante cuesta poco añadir, y qué significa cada número entre los resultados. Nada de esto depende del motor del benchmark de un solo núcleo vecino. Todo el objetivo era reimplementar la familia desde cero, manteniendo la ingeniería de software limpia y el relato del «qué se apila sobre qué» explícito.
Cada algoritmo del estudio es el mismo backtracker recursivo en profundidad, parametrizado por cuatro elecciones independientes:
Una variante es un pequeño registro que nombra esas cuatro elecciones, junto con el padre del que deriva y una descripción de una línea del cambio único que añade. Añadir una variante equivale a añadir un registro al registro, sin nuevo código de búsqueda a menos que la idea sea una estrategia genuinamente nueva. La matriz del «qué se apila sobre qué» de la página de resultados se genera a partir de esas descripciones, de modo que no puede divergir del código que se ejecutó. Eso es lo que mantiene un estudio extenso, con decenas de variantes a un solo cambio de distancia, mantenible en lugar de un montón de solucionadores copiados y pegados.
Cada algoritmo del estudio consume un único tipo de instancia y emite una única
salida: el mejor tablero, su puntuación canónica, y una URL bucas. Alrededor de
eso se articula una capa IO compartida con convertidores sin pérdida entre los
formatos que hablan los demás motores del sitio: el JSON con el esquema del sitio
del benchmark, el CSV de los motores comunitarios autónomos, las URL bucas, y los
archivos de pistas. El estudio lee las mismas diez variantes con esquinas
fijadas que usa el benchmark de un solo núcleo, a través de esta capa, de modo que
los dos experimentos son directamente comparables. Una pequeña utilidad
dfs-convert expone las conversiones desde el shell, de modo que la salida de
cualquier motor del blog puede alimentar a cualquier otro.
Ningún score auto-reportado por un motor es digno de confianza. Cada tablero, estricto o roto, es re-puntuado por un único scorer canónico: las adyacencias interiores, no de borde, concordantes, contadas a la derecha y hacia abajo por cada celda. Es, byte por byte, la misma fórmula que la del scorer del sitio y la del benchmark, verificada por un test que re-puntúa un tablero de 469 conocido y exige 469. Esto es lo que permite que puntuaciones de variantes distintas, y las del benchmark vecino, se asienten sobre un solo eje.
Para cada ejecución, el motor registra, y los resultados los llevan hasta la página:
480 − #breaks.480 − score; en un parcial expirado el déficit cuenta además las aristas todavía
vacías, así que el estudio reporta en su lugar el verdadero número de rupturas. La
URL bucas de cada tablero hace ambos verificables en el visualizador.La variante más cruda, NAIVE-CLEAN, es un motor general legible: listas de
candidatos por celda sin centinela, indexadas por los dos vecinos ya colocados, una
caché de aristas resueltas para que ninguna rotación se recompute en el camino
caliente, y ninguna asignación dentro de la búsqueda. Su gemela, NAIVE-CODEGEN, es
el mismo algoritmo reexpresado como un bucle caliente especializado a mano, solo
16×16, por filas, mantenido como programa separado para que el motor general se
conserve limpio. Ponerlos a competir cara a cara pone precio a la ingeniería de bajo
nivel: en este puzzle compra una ganancia de rendimiento modesta y dependiente de la
instancia y, notablemente, ninguna mejor puntuación. Los números están en la
página de hallazgos.
La verificación hacia adelante, la arco-consistencia y el control de suministro por color son correctos por construcción. Cada uno solo rechaza un estado en el que alguna celda ya tiene un dominio vacío, una celda que ninguna pieza no usada puede rellenar, de modo que ninguno de ellos puede eliminar una rama que lleve a una finalización real. La revisión de arco-consistencia es deliberadamente prudente allí donde es imprecisa: dondequiera que pudiera estar insegura, poda menos en lugar de más, quedándose del lado seguro. Los propagadores son correctos solo bajo colocación estricta, porque bajo un presupuesto de rupturas una anticipación local puede podar una rama que el presupuesto global aún podría rescatar, así que las variantes con rupturas deliberadamente no ejecutan ningún propagador. El registro lo impone: una variante que empareja rupturas con un propagador reservado al modo estricto falla al compilar. Los tests del motor comprueban esa restricción así como la contabilidad de la puntuación y de las rupturas, aunque la corrección de la poda en sí descansa sobre el argumento anterior y no sobre un test.
El espacio de trabajo del motor, las diez variantes, los resultados por ejecución
commiteados y los scripts de la grilla viven todos bajo el
directorio de soporte
del estudio. just experiments dfs-study reconstruye el motor y reejecuta toda la
grilla; la ejecución es determinista con semilla fija, y la disposición de las
esquinas es el único eje de diversidad.