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.
por Raphaël Anjou
La búsqueda heurística conjetura; nunca sabe si tiene la mejor terminación posible. Los experimentos que se recogen aquí adoptan la postura contraria para una región pequeña: la enumeran desde dos extremos, unen las mitades allí donde los colores de su costura coinciden y sus conjuntos de piezas no se solapan, y obtienen la mejor terminación exacta junto con una prueba de que nada puntúa más alto. Es el clásico intercambio meet-in-the-middle de tiempo por espacio, apuntado al final de partida del puzzle.
Estos no son intentos de superar la puntuación. Responden a una pregunta distinta de la de las combination pipelines y de los estudios de búsqueda: no hasta qué altura puede trepar una heurística, sino cuál es la verdadera mejor terminación de esta región y en qué punto los métodos exactos dejan de ser asequibles. Una respuesta exacta sobre una región pequeña vale aquí más que otro casi acierto sobre el tablero completo.
El primer y por ahora único experimento de esa clase es BANDSAW. Resolvió con exactitud una banda de filas en un banco de pruebas de 10×10, demostró en qué punto el presupuesto de desajustes deja de ser asequible, y dejó como subproducto un tablero de 437 sin marco (contado en aristas emparejadas), la única página de este cuaderno con rigor demostrado. La sección lleva el nombre de la técnica en lugar del de la única página, porque más ideas exactas de final de partida deberían acompañarla a medida que vayan llegando.