Los experimentos de Raphaël Anjou

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.

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.

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 aquí; los motores constructivos aún no están publicados.

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.

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.

Los experimentos de búsqueda con nombre propio que persiguen la puntuación. Cada uno es un pipeline más que un único algoritmo: construye un tablero con un motor y luego lo eleva o lo remata con otro. Cada uno deja constancia de su idea, de su mejor 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.

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.

Give a backtracker five correct pieces for free, in the puzzle's own clue geometry. It turns out not to help, and depending on the fill order it can hurt badly, because a pinned piece is a hard constraint a fixed fill order must satisfy on arrival. A family of fill paths, run on the same hinted boards, single core, measured against no hints at all.

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.