Raphaël Anjou

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 borde perfecto de 60 piezas no es un objeto rígido. Cada marco completamente apareado admite exactamente 45 intercambios libres a coste de borde cero; un tercio de los marcos perfectos ni siquiera pueden arrancar el interior, y un solo intercambio libre revive cada uno de ellos.

Un repaso verificado más mediciones apareadas: ninguna astucia por nodo supera la anchura bruta del haz a igual tiempo de reloj. Los dos únicos aditivos que sobreviven son aleatorizar las claves de truncado empatadas exactamente (gratis) y el remuestreo SMC de los supervivientes (pequeño pero significativo).

Cada tablero récord que tenemos está congelado en su sitio. No se puede progresar a base de pequeños retoques desde un tablero excelente hacia uno perfecto, y podemos demostrarlo.

Resolver exactamente una banda de filas encontrándose en el medio, para hallar el verdadero mejor final y medir hasta qué punto puede decidirse por anticipado una fin de partida.

Quince solucionadores, los nuestros y nuestras implementaciones de los dos backtrackers récord de la comunidad, cada uno ejecutado una vez sobre diez variantes del puzzle oficial con las esquinas fijadas, un solo núcleo, 60 segundos por ejecución. El hallazgo: el número de nodos no es la puntuación.

Construir un tablero desde cero, resolviendo los empates según la posición habitual de las piezas en los buenos tableros ya conocidos. Alcanza una puntuación alta sin ningún tablero de partida que copiar.

Un solo motor de propagación de restricciones, ejecutado bajo una docena de presets de ordenación y de propagadores, sobre las mismas diez variantes con esquinas fijadas que el ranking. Un estudio de lo que aporta cada ajuste, mantenido fuera del ranking principal porque el mejor preset alcanza menos de la mitad de la puntuación de un contendiente.

Construir un tablero desde cero, clasificando cada pieza siguiente según tres señales aprendidas de tableros fuertes anteriores. Alcanzó 460 en una familia de tableros que ninguna búsqueda previa había resuelto.

Una reimplementación desde cero del método eii de Louis Verhaard, ya que su propio binario no incluye código fuente y no se ejecuta aquí. Recocido por intercambio de composición de conjunto bajo la métrica de teselado 2×2; en el puzzle real de cinco pistas alcanza 438 de 480, en un solo núcleo.

Una brújula tenue para una búsqueda partida de cero: incitarla a comprometer las piezas raras pronto, allí donde se necesitan. No eleva el techo; hace que la búsqueda alcance de forma fiable la cima de su propio rango.

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.

Leer cada tablero fuerte para detectar los hábitos que, en silencio, limitan un tablero, y luego romperlos. Este experimento produjo el mejor tablero del proyecto: 463 de 480.

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.

Ejecutar la misma búsqueda en haz según nueve órdenes de recorrido distintos, para que aterrice en regiones diferentes en lugar de converger siempre a la misma. El orden en zigzag encontró un tablero 458 inédito.

Reconstruir de forma idéntica los tableros estrictos de 460 de la comunidad y descubrir, de paso, la jugada que los solucionadores corrientes no saben hacer: pagar dos desajustes en una misma celda.

Fijar un borde perfecto y luego explorar el interior tratando las aristas del borde como restricciones duras desde la primera celda.

Colocar primero un borde perfecto y resolver el tablero hacia adentro, anillo por anillo, cada anillo como un problema de asignación sobre las piezas restantes.

Decidir de antemano no cuándo puede romperse un tablero, sino dónde: confinar cada desajuste a una forma de celdas elegida, y buscar la mejor forma.

Lanzar cientos de búsquedas cortas y baratas sobre el tablero, conservar solo los arranques más profundos y hacer ascender a los supervivientes a través de rondas cada vez más largas.

Dividir el tablero en pequeños bloques, resolver cada uno hasta el óptimo demostrado y volver a pegarlos, pagando las costuras en lugar de prohibirlas. Partiendo de cero, sin ningún récord que copiar, el método alcanza 448.

Construir todo el tablero desde cero, sin marco prefijado, por etapas, dejando que el borde emerja al final a partir de las piezas restantes.

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 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.

Todos los formatos en los que un tablero o un puzzle de Eternity II circula en este sitio y en la comunidad: la cadena de letras board_edges y la lista de pistas hints, e2pieces.txt, el CSV de puzzle, el JSON Puzzle del sitio, y la URL de visor, con las reglas exactas a nivel de byte (cómo se codifica el borde gris en cada uno) y, sobre todo, qué puede y qué no puede recuperar cada formato.

Recuentos exactos de cuántas maneras válidas hay de rellenar un bloque pequeño en una posición dada del tablero oficial de Eternity II, bajo reglas cada vez más restrictivas: números fiables para contrastar el código de emparejamiento de aristas y de restricciones de tu solucionador.

El estándar editorial de este cuaderno abierto: cómo una investigación sobre Eternity II pasa de ser un trabajo no publicado a una página publicada. De qué tipo de contribución se trata, si se publica, en qué nivel y dónde reside. Un estándar común, concebido para escalar a muchos autores.

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.

El motor detrás del estudio de reparación: un único bucle componible de destrucción-reparación donde una variante es un cambio declarado sobre un padre, la IO y el scorer que comparte con el estudio DFS, un mapa de desajustes mantenido de forma incremental, y las definiciones de cada estadística que el estudio pone de relieve.

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.

El aparato detrás del estudio de las pistas: un generador paramétrico de tableros fiel a la receta de colores de Eternity II en todos los tamaños, la familia de backtrackers por orden de relleno, el único puntuador canónico, y la pieza de aritmética que mantiene significativo el eje del número, el suelo de costuras fijadas.

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.

Un cuaderno de experimentos de búsqueda sobre Eternity II, organizado en torno a los motores compartidos sobre los que se ejecutan, las pipelines de combinación que persiguen la puntuación, cuatro estudios que desmontan un paradigma de búsqueda una decisión a la vez, y resoluciones exactas de final de partida. Cada uno expone su idea, su mejor tablero y las preguntas que deja abiertas. El mejor alcanza 463 de 480.

Las cinco comparaciones en el corazón del estudio de reparación, desarrolladas: la destrucción aleatoria ciega gana mientras que todo operador que apunta a los conflictos pierde; la construcción fija el suelo; el recocido simulado es la regla de aceptación más fuerte; y los refinamientos ingeniosos (recarga exacta, reinicios) no aportan nada con este presupuesto.

Los resultados, desarrollados: en estos tableros las cinco pistas con forma de pistas oficiales nunca ayudan a un backtracker, van de un coste moderado a una catástrofe, y el orden de relleno decide cuánto daño hacen; las puntuaciones son bimodales, no un gradiente suave; y la pregunta por el número de pistas está confundida por un suelo gratuito de costuras fijadas.

Las tres comparaciones en el corazón del estudio DFS, llevadas hasta el final: el orden de relleno (el recorrido por filas gana, un mal orden es catastrófico), las heurísticas (MRV rescata el borde primero pero cuesta rendimiento; más propagación no aportó nada) y las rupturas (rompen el muro de profundidad; el calendario de rupturas es la palanca, no el tope por celda).

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.