Cómo generan niveles de puzle los ordenadores

En 2011, Julian Togelius, Georgios Yannakakis, Kenneth Stanley y Cameron Browne cartografiaron un campo que crecía deprisa y le pusieron nombre: generación procedimental de contenido basada en búsqueda. Su revisión clasifica los generadores según lo que crean, cómo se representa ese contenido dentro del programa y, sobre todo, cómo se evalúa su calidad. El enfoque basado en búsqueda trata el diseño de niveles como un problema de optimización. Se generan candidatos, se puntúa cada uno con una función de evaluación, se conservan los mejores, se modifican y se repite, a menudo con algoritmos evolutivos tomados de la biología.

La función de evaluación es donde vive el diseño. Puede medir un nivel directamente (cuántas piezas, cuánto espacio vacío), mediante simulación (dejar que un jugador artificial lo intente y ver qué pasa) o de forma interactiva (preguntando a jugadores reales). Cada opción tiene un coste. Las medidas directas son baratas pero superficiales. La simulación es más fiel, pero necesita un programa capaz de jugar de verdad. Preguntar a personas es lo más fiel y, con diferencia, lo más lento.

En un rompecabezas de bloques deslizantes es fácil de imaginar. Un candidato es una cuadrícula con ladrillos colocados. Una variación mueve, añade o quita un ladrillo. Una medida directa podría contar lo lleno que está el tablero; una medida basada en simulación le pasa el tablero a un solucionador y anota si se puede despejar y lo larga que es la ruta que encuentra. Te quedas con los tableros que puntúan bien, los vuelves a modificar y, tras miles de rondas, el generador ha derivado hacia lo que premie la función de evaluación. Ese es su poder y su peligro: encontrará exactamente lo que le pediste, incluidos tableros que cumplen los números y aburren al jugador.

Fuentes1Fuente 1Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186.

Otra escuela empieza por el otro extremo. En lugar de hacer evolucionar tableros y esperar que surjan buenos, Adam Smith y Michael Mateas propusieron describir explícitamente el espacio de diseños aceptables, como un conjunto de restricciones lógicas, y dejar que un solucionador de propósito general encuentre tableros que las cumplan. Con una técnica llamada programación de conjuntos de respuestas (answer set programming), un diseñador puede escribir reglas como «la salida tiene que ser alcanzable» o «esta pieza tiene que moverse al menos dos veces» y recibir solo tableros que las cumplan.

El atractivo para el diseño de puzles es evidente. Muchas de las cosas que hacen interesante un tablero son restricciones: este ladrillo tiene que estar bloqueado por aquel, esta llave tiene que ser necesaria. Escribirlas obliga al diseñador a decir qué quiere en realidad, una disciplina tan útil para las personas como para las máquinas.

Fuentes2Fuente 2Smith, A. M., & Mateas, M. (2011). Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 187–200.

Sea cual sea el generador, un puzle tiene que tener solución antes que nada, y demostrarlo suele ser el paso más difícil. Noor Shaker, Mohammad Shaker y Julian Togelius se toparon con esto en Cut the Rope, un puzle de física con tiempo y espacio continuos, donde la búsqueda por fuerza bruta no tiene ninguna posibilidad. Su respuesta fue un agente razonador que en cada estado solo proponía movimientos sensatos, lo que redujo la búsqueda lo suficiente como para que una sencilla búsqueda en profundidad encontrara soluciones y confirmara que los niveles generados se podían jugar.

Bilal Kartal, Nick Sohre y Stephen Guy tomaron otro camino con Sokoban, el clásico puzle de empujar cajas. Su generador construye los puzles mediante partidas simuladas con búsqueda de árbol Monte Carlo, así que cada puzle que produce tiene solución por construcción. Los rompecabezas de bloques deslizantes también son un caso difícil: el problema general es PSPACE-completo, como explica nuestra historia de los rompecabezas de bloques deslizantes, así que no se conoce ningún atajo que resuelva rápido cualquier tablero.

Fuentes3Fuente 3Shaker, N., Shaker, M., & Togelius, J. (2013). Evolving playable content for Cut the Rope through a simulation-based approach. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 9(1), 72–78.4Fuente 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.

Un tablero puede tener solución y aun así ser aburrido, o tenerla solo por una ruta que ninguna persona encontraría. Kartal y sus colegas lo abordaron de frente. Hicieron un estudio con usuarios para encontrar características del tablero que fueran baratas de calcular y estuvieran correlacionadas con lo difíciles que les parecían los puzles a las personas, las combinaron en una función de puntuación y luego confirmaron en un segundo estudio que los puzles con más puntuación se percibían como más difíciles. Es decir, la dificultad había que aprenderla de las personas, no suponerla.

Yannakakis y Togelius generalizan la idea en su marco de generación procedimental de contenido guiada por la experiencia: modelar la experiencia del jugador, ya sea a partir de su comportamiento, de lo que cuenta o de su fisiología, y generar contenido para moldearla. Es un objetivo ambicioso, y lo honesto es reconocer que los modelos de diversión y frustración siguen siendo toscos. En un puzle, cualidades como la elegancia, el satisfactorio «¡ajá!» y la justicia siguen siendo más fáciles de reconocer que de calcular. Vemos qué significa la justicia para los jugadores en qué hace que un puzle parezca justo.

Fuentes4Fuente 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.5Fuente 5Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3), 147–161.

Para los jugadores, de todo esto se desprende una regla práctica. «Niveles infinitos» te dice que existe un generador; no te dice cómo se prueban sus niveles. Busca juegos que expliquen cómo comprueban sus tableros, y desconfía cuando la dificultad salta al azar, que a menudo es señal de que nada la está modelando.

Otras señales de un conjunto de puzles bien hecho, generado o no: las ideas nuevas se presentan de una en una, como recomienda la investigación sobre el ritmo de los puzles; los tableros se sienten distintos y no como copias casi idénticas con una pieza movida; y cuando te atascas, crees que existe una solución. Esa última es la más difícil de fingir, y la que más les ha costado ganarse a los generadores.

Los 2000 tableros de OutBrick son un conjunto fijo y diseñado, no un flujo generado en tu dispositivo, y la ruta para despejar cada uno se volvió a reproducir con las reglas del propio juego antes del lanzamiento. Contamos ese proceso, incluido por qué un solucionador que se queda sin presupuesto significa «desconocido» y no «imposible», en cómo verificamos 2000 tableros de bloques deslizantes. Un solucionador demuestra que existe una ruta; no demuestra que el tablero sea divertido, y por eso el ritmo se juzga aparte. Puedes ver el resultado por ti mismo en el Tablero del día.