Los experimentos de Raphaël Anjou

Los motores compartidos que sustentan los experimentos de Raphaël Anjou. Los experimentos con nombre son estudios que se ejecutan sobre ellos; este es el aparato que comparten. Los preajustes CSP y la reimplementación de Verhaard están documentados por completo, junto al motor de referencia, el backtracker JIT, una guía de la velocidad y el arnés de la escalera de tamaños; los motores constructivos aún no están publicados.

El backtracker de Rust a WebAssembly que anima cada demo en vivo y verifica cada número de este wiki. No una máquina de récords sino un motor de referencia, portado cuatro veces y validado byte a byte, construido para que las afirmaciones de aquí puedan volver a ejecutarse.

Siete experimentos de búsqueda con nombre propio que persiguen la puntuación, cada uno un pipeline más que un único algoritmo: construye un tablero con un motor y luego lo eleva o lo remata con otro. Junto a ellos, dos hallazgos desmontan la maquinaria en la que los pipelines se apoyan. Cada página deja constancia de su idea, de su tablero y de las preguntas que deja abiertas.

Una sola pregunta, planteada con cuidado: entre los backtrackers en profundidad para Eternity II, ¿qué aporta realmente cada orden de relleno, cada heurística y el mecanismo de ruptura? Una familia de backtrackers escritos desde cero, separados cada uno por un único cambio, ejecutados sobre las mismas diez variantes con esquinas fijadas, en un solo núcleo, durante sesenta segundos.

Darle a un backtracker cinco piezas correctas gratis, en la geometría misma de las pistas del puzzle. Resulta que no ayuda, y según el orden de relleno puede dañar gravemente, porque una pieza fijada es una restricción dura que un orden de relleno fijo debe satisfacer al llegar. Una familia de órdenes de relleno, ejecutada sobre los mismos tableros con pistas, un solo núcleo, medida contra la ausencia total de pistas.

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.

Un estudio en cinco experimentos de una sola idea: en lugar de buscar Eternity II desde cero, extraer estructura del corpus de tableros fuertes ya encontrados y reinyectarla en una búsqueda. Un prior de posición, un voto de jugada aprendido, una brújula de demanda escasa, un minero de antipatrones y un decodificado de récord, ordenados de la señal más simple a la más sutil, y el único muro que los cinco alcanzan.

Experimentos exactos de final de partida que se encuentran en el medio: enumeran una región desde dos extremos y las unen por la costura, para hallar la verdadera mejor terminación con una prueba en lugar de la mejor conjetura de una heurística. Miden con exactitud una región pequeña en vez de perseguir la puntuación del tablero completo.

Algunos motores de Eternity II vuelcan su esfuerzo en recorrer el árbol de búsqueda lo más rápido posible; otros lo gastan en el criterio sobre dónde buscar. Este es el alegato a favor de los primeros - qué compra el rendimiento bruto, las tres cosas distintas que la gente llama «rápido» y por qué el motor más rápido jamás construido sigue sin poder resolver el rompecabezas.

Un backtracker Rust en profundidad, seguro y portable, especializado en tiempo de ejecución al emitir y compilar Rust propio de cada rompecabezas, llevado de 43 a 123 millones de nodos de búsqueda por segundo en un núcleo. Medido con justicia frente al C de Peter McGavin en la misma máquina: un empate en tableros difíciles y profundos como el Eternity II real, y alrededor del 44 % de su velocidad en los fáciles. Cada peldaño recorre el árbol idéntico; toda la ganancia es código, no algoritmo.

Llevar, color a color, la oferta de semiaristas frente a la demanda del frente en un DFS con presupuesto de rupturas, y podar en cuanto el déficit o su paridad superan las rupturas restantes. Correcto por construcción; la ganancia se compone con la profundidad.

Una energía libre de propagación de creencias, calculada sobre las piezas sobrantes de la última fila, predice el rango del mejor final posible. La señal no es un proxy del puntaje bruto, sobrevive a un cambio de productor y muere más allá de una fila.

Un banco que ejecuta cualquier solucionador, sin cambios, sobre tableros plantados totalmente resolubles con N = 8, 10, 12, 14, cada uno con un techo probado de 2N(N-1): el tamaño de colapso de un método se mide antes de gastar semanas en el 16×16 real.