La búsqueda de haz no es monótona, y contaminó mis mediciones
Una búsqueda de haz más ancha no es una búsqueda de haz estrictamente mejor. En un nivel de Sunny Sort, la anchura 45 encuentra una línea ganadora, la anchura 90 falla y la anchura 200 vuelve a encontrar una — y como todas las mediciones de dificultad del proyecto preguntaban "¿esto todavía se puede ganar?" con una sola anchura, la respuesta salía mal con la frecuencia suficiente para sesgar la curva entera.
Cómo salió a la luz
Un nivel aparecía como irresoluble durante el sondeo y con solución durante la generación. El mismo nivel, el mismo presupuesto de movimientos, dos veredictos distintos del mismo solucionador.
La diferencia era la anchura de haz que cada etapa usaba por casualidad.
| Anchura del haz | Resultado |
|---|---|
| 45 | lo resuelve |
| 90 | falla |
| 200 | lo resuelve |
Por qué un haz más ancho puede ser peor
La búsqueda de haz conserva los mejores k estados en cada profundidad y descarta el resto. Ensanchar k conserva más estados, pero también cambia qué estados están en la frontera, porque la frontera se ordena por una heurística, no por la verdad.
Una línea ganadora suele pasar por un estado que la heurística puntúa mal. Con anchura 45 ese estado sobrevive porque hay poca competencia a su profundidad. Con anchura 90 llegan más candidatos, todos con mejor puntuación heurística y ninguno que lleve a ninguna parte, y el estado que importaba queda expulsado de la frontera.
Más búsqueda, peor respuesta. La propiedad que la gente da por hecha —que añadir anchura solo puede ayudar— es una propiedad de la búsqueda exhaustiva, no de una truncada.
Lo que costó antes de que me diera cuenta
El modo de fallo es asimétrico, y eso es lo que lo hace peligroso. Una búsqueda de haz nunca informa de una victoria que no puede demostrar, así que un positivo es de fiar. Un negativo significa solo "esta anchura no encontró una línea", que se lee igual que "no existe ninguna línea".
Con lo cual las mediciones producían solo falsos negativos:
- niveles declarados imposibles que sí se podían ganar;
- anchura de decisión medida en el 76% frente a un 86% real en la misma configuración.
Ese segundo número es el que escuece. La anchura de decisión es la métrica sobre la que se apoyó toda la decisión de la presión: la fracción de movimientos legales que mantienen viva la victoria. Una subestimación de diez puntos empuja todos los juicios sobre cuánta libertad permite un nivel en la misma dirección, y nada en el resultado parece sospechoso. Es un número plausible, afirmado con seguridad, y equivocado.
La corrección
DepthProbe.Winnable y BestLine prueban ahora varias anchuras antes de concluir nada. Un nivel solo se declara invencible cuando han fallado todas las anchuras probadas; la mejor línea es la mejor que haya encontrado cualquiera de ellas.
Tanto el analizador como la comprobación de justicia del generador usan las versiones de varias anchuras. Ningún nivel se declara imposible por una peculiaridad del solucionador.
El coste es tiempo de búsqueda, pagado sin conexión durante la generación, por una máquina, una vez. La alternativa era publicar niveles que el jugador no puede ganar y a quien no se le puede explicar por qué.
La parte que merece generalizarse
Esto está registrado en el diario de diseño con su propia entrada, no porque la corrección sea interesante, sino por la clase de fallo que es.
Nunca rompió nada. Nunca lanzó una excepción. Produjo un número exactamente de la forma correcta, en el rango correcto, que una persona razonable leería y usaría. Toda decisión tomada por debajo de aquella medición heredó el error en silencio, y la única razón por la que se detectó es que dos etapas del mismo flujo usaban por casualidad anchuras distintas y discreparon en voz alta.
Si una herramienta responde a una pregunta buscando, la anchura de la búsqueda forma parte de la respuesta. Pregunta de más de una manera antes de creértela.