Esta publicación describe el generador de niveles para mi
juego de rompecabezas
Linjat . Se puede leer una publicación sin preparación, pero es más fácil de asimilar si juegas en varios niveles.
Publiqué el código fuente
en github ; todo lo discutido en el artículo está en el
src/main.ccEjemplo de plan postal:
- Linjat es un juego de lógica en el que debes cerrar todos los números y puntos de la cuadrícula con líneas.
- Los acertijos se generan mediante procedimientos mediante una combinación de solucionador, generador y optimizador.
- Solver intenta resolver los acertijos de la manera en que lo haría una persona, y asigna a cada acertijo una calificación de interés.
- El generador de rompecabezas está diseñado para que sea posible cambiar fácilmente una parte del rompecabezas (número) y, al mismo tiempo, todas las demás partes (puntos) cambian para que el rompecabezas permanezca solucionable.
- El optimizador de rompecabezas resuelve repetidamente los niveles y genera nuevas variaciones de las más interesantes que se encuentran en este momento.
Las reglas
Para entender cómo funciona el generador de niveles, desafortunadamente, necesitas entender las reglas del juego. Afortunadamente, son muy simples. El rompecabezas consiste en una cuadrícula que contiene cuadrados vacíos, números y puntos. Un ejemplo:
El objetivo del jugador es dibujar una línea vertical u horizontal a través de cada uno de los números, sujeto a tres condiciones:
- Una línea a través de un número debe tener la misma longitud que el número.
- Las líneas no pueden cruzarse.
- Todos los puntos deben cerrarse con líneas.
Solución de ejemplo:
¡Hurra! El diseño del juego está listo, la interfaz de usuario está implementada y ahora lo único que queda es encontrar varios cientos de acertijos buenos. Y para tales juegos, por lo general, no tiene sentido intentar crear tales rompecabezas manualmente. Este es un trabajo de computadora.
Requisitos
¿Qué hace que el rompecabezas de este juego sea bueno? Me inclino a creer que los juegos de rompecabezas se pueden dividir en dos categorías. Hay juegos en los que exploras un espacio de estado complejo de principio a fin (por ejemplo,
Sokoban o
Rush Hour ), y en los que puede no ser obvio qué estados existen en el juego. Y hay juegos en los que todos los estados se conocen desde el principio, y gradualmente formamos el espacio de estados utilizando el proceso de eliminación de los innecesarios (por ejemplo,
Sudoku o
Picross ). Mi juego definitivamente cae en la segunda categoría.
Los jugadores tienen requisitos muy diferentes para estos diferentes tipos de rompecabezas. En el segundo caso, esperan que el rompecabezas solo pueda resolverse por deducción, y que nunca necesitarán regresar / adivinar / prueba y error
[0] [1] .
No es suficiente saber si un rompecabezas solo se puede resolver mediante la lógica. Además, necesitamos entender de alguna manera lo buenos que son los rompecabezas creados. De lo contrario, la mayoría de los niveles serán solo escorias triviales. En una situación ideal, este principio también podría usarse para crear una curva de progreso suave, de modo que a medida que el jugador avanza en el juego, los niveles gradualmente se vuelven más difíciles.
Solucionador
El primer paso para cumplir con estos requisitos es crear un solucionador de juegos optimizado para este propósito. El solucionador de retroceso le permite determinar de forma rápida y precisa si el rompecabezas es solucionable; Además, se puede modificar para determinar si la solución es única. Pero no puede dar una idea de lo complicado que es realmente el rompecabezas, porque la gente los resuelve de manera diferente. El solucionador debe imitar el comportamiento humano.
¿Cómo resuelve una persona este rompecabezas? Aquí hay un par de movimientos obvios que enseña el tutorial del juego:
- Si se puede llegar a un punto desde un solo número, entonces para cerrar un punto necesita dibujar una línea desde ese número. En este ejemplo, se puede llegar al punto solo desde los tres, pero no desde los cuatro:
Y esto lleva a esta situación:
- Si la línea no cabe en una dirección, entonces debe colocarse en otra. En el ejemplo anterior, los cuatro ya no se pueden colocar verticalmente, por lo que sabemos que será horizontal:
- Si se sabe que la línea de longitud X debe estar en una posición determinada (vertical / horizontal) y no hay suficiente espacio vacío para colocar una línea de X celdas vacías en ambos lados, entonces debe cubrir varios cuadrados en el medio. Si los cuatro fueran tres en el ejemplo que se muestra arriba, entonces no sabríamos si se extiende hacia la derecha o hacia la izquierda. Pero sabríamos que la línea debe cubrir dos cuadrados medios:
Un razonamiento similar es la base del juego. El jugador busca formas de estirar una pequeña línea y luego examina el campo nuevamente, porque puede darle información para llegar a otra conclusión lógica. Crear un solucionador que siga estas reglas será suficiente para determinar
si una persona puede resolver el rompecabezas sin retroceder.
Sin embargo, esto no nos dice nada sobre la complejidad o el interés del nivel. Además de la capacidad de solución, de alguna manera necesitamos cuantificar la complejidad.
Una primera idea obvia para la función de calificación: cuantos más movimientos necesites para resolver el rompecabezas, más difícil será. Esta es probablemente una buena métrica en otros juegos, pero la mía, muy probablemente, es más importante que la cantidad de movimientos permitidos que tiene un jugador. Si un jugador puede sacar 10 conclusiones lógicas, lo más probable es que encuentre una de ellas muy rápidamente. Si solo hay un movimiento correcto, tomará más tiempo.
Es decir, como primera aproximación, necesitamos que el árbol de decisión sea profundo y estrecho: existe una larga dependencia de los movimientos de principio a fin, y en cada momento solo hay un pequeño número de formas de ascender en la cadena
[2] .
¿Cómo determinamos el ancho y la profundidad de un árbol? Una solución única para el rompecabezas y la evaluación del árbol creado no dará una respuesta exacta. El orden exacto en el que se realizan los movimientos afecta la forma del árbol. Necesitamos considerar todas las soluciones posibles y hacer con ellas algo como la optimización para los mejores y peores casos. Estoy familiarizado con la técnica de
búsqueda aproximada de gráficos de búsqueda en juegos de rompecabezas , pero para este proyecto quería crear un solucionador de un solo paso, y no una búsqueda exhaustiva. Debido a la fase de optimización, traté de asegurarme de que el tiempo de ejecución del solucionador no se midiera en segundos, sino en milisegundos.
Decidí no hacerlo. En cambio, mi solucionador en realidad no hace un movimiento a la vez, sino que resuelve el rompecabezas en capas: tomando un estado, encuentra todos los movimientos válidos que se pueden hacer. Luego aplica todos estos movimientos al mismo tiempo y comienza de nuevo en un nuevo estado. El número de capas y el número máximo de movimientos encontrados en una capa se usan como valores aproximados de la profundidad y el ancho del árbol de búsqueda en su conjunto.
Aquí se explica cómo resolver uno de los acertijos difíciles con este modelo. Las líneas punteadas son líneas extendidas en esta capa del solucionador, las líneas continuas son aquellas que no han cambiado. Las líneas verdes tienen la longitud correcta, las rojas aún no están completas.
El siguiente problema es que todos los movimientos realizados por el jugador son iguales. Lo que enumeramos al comienzo de esta sección es solo sentido común. Aquí hay un ejemplo de una regla de deducción más compleja, cuya búsqueda requerirá un poco más de reflexión. Considere el siguiente campo:
Los puntos en C y D pueden estar cubiertos solo por los cinco y los cuatro del medio (y ni un solo número puede cubrir ambos puntos al mismo tiempo). Esto significa que los cuatro en el medio deben cubrir uno de los dos puntos y, por lo tanto, no se pueden usar para cubrir A. Por lo tanto, el punto A debe cerrar los cuatro en la esquina inferior izquierda.
Obviamente, sería una tontería considerar esta cadena de razonamiento igual a la simple conclusión "este punto solo puede ser alcanzado desde este número". ¿Es posible dar más peso a estas reglas más complejas en la función de evaluación? Desafortunadamente, en un solucionador basado en capas, esto no es posible, porque no se garantiza que encuentre una solución al costo más bajo. Este no es solo un problema teórico: en la práctica, a menudo sucede que parte del campo puede resolverse mediante un argumento complejo único o mediante una cadena de movimientos mucho más simples. De hecho, un solucionador basado en capas encuentra la ruta más corta y no la menos costosa, y esto no puede reflejarse en la función de evaluación.
Como resultado, tomé esta decisión: cambié el solucionador para que cada capa constara de un solo tipo de razonamiento. El algoritmo omite las reglas de razonamiento en un orden aproximado de complejidad. Si la regla encuentra algunos movimientos, se aplican y la iteración finaliza, y la siguiente iteración comienza la lista desde el principio.
Luego, a la decisión se le asigna una evaluación: a cada capa se le asignan costos en función de una regla que se utilizó en ella. Esto todavía no garantiza que la solución sea la más económica, pero si los pesos se seleccionan correctamente, el algoritmo al menos no encontrará una solución costosa si es barata.
Además, es muy parecido a la forma en que las personas resuelven acertijos. Primero intentan encontrar soluciones fáciles y comienzan a mover activamente sus cerebros solo si no hay movimientos simples.
Generador
La sección anterior determinó si un nivel particular era bueno o malo. Pero esto no es suficiente, aún necesitamos generar niveles de alguna manera para que el solucionador pueda evaluarlos. Es muy poco probable que un mundo generado aleatoriamente tenga solución, por no mencionar interesante.
La idea principal (de ninguna manera es nueva) es el uso alternativo del solucionador y el generador. Comencemos con un rompecabezas, que probablemente no se pueda resolver: simplemente coloque de dos a cinco números en cuadrados aleatorios de la celda:
Solver funciona hasta que pueda desarrollarse más:
Luego, el generador agrega más información al rompecabezas en forma de un punto, después de lo cual la ejecución del solucionador continúa.
En este caso, el punto agregado al solucionador no es suficiente para un mayor desarrollo. Luego, el generador continuará agregando nuevos puntos hasta que satisfaga al solucionador:
Y luego el solucionador continúa su trabajo habitual:
Este proceso continúa hasta que se resuelva el rompecabezas o hasta que quede más información para agregar (por ejemplo, cuando cada celda que se puede alcanzar desde el número ya contiene un punto).
Este método solo funciona si la nueva información agregada no puede hacer que ninguna de las conclusiones hechas anteriormente sea incorrecta. Esto sería difícil de hacer al agregar números a la cuadrícula
[3] . Pero agregar nuevos puntos al campo tiene esta propiedad; al menos para las reglas de razonamiento que uso en este programa.
¿Dónde debería agregar puntos el algoritmo? Al final, decidí agregarlos al espacio vacío, que se puede cerrar en el estado inicial con tantas líneas como sea posible, de modo que cada punto busque dar la menor información posible. No intenté colocar específicamente el punto en el lugar donde sería útil para avanzar en la resolución del rompecabezas en el momento en que el solucionador se atasca. Esto crea un efecto muy conveniente: la mayoría de los puntos al comienzo del rompecabezas parecen completamente inútiles, lo que hace que el rompecabezas sea más difícil de lo que realmente es. Si todo esto son muchos movimientos obvios que un jugador puede hacer, pero por alguna razón, ninguno de ellos no funciona correctamente. Como resultado, resultó que el generador de rompecabezas se comporta un poco como un cerdo.
Este proceso no siempre crea una solución, pero es bastante rápido (aproximadamente 50-100 milisegundos), por lo que para generar un nivel, simplemente puede repetirlo varias veces. Desafortunadamente, generalmente crea rompecabezas mediocres. Desde el principio, hay demasiados movimientos obvios, el campo se llena muy rápidamente y el árbol de decisión resulta ser poco profundo.
Optimizador
El proceso descrito anteriormente creó rompecabezas mediocres. En la última etapa, uso estos niveles como base para el proceso de optimización. Funciona de la siguiente manera.
El optimizador crea un grupo que contiene hasta 10 opciones de rompecabezas. El grupo se inicializa con un nuevo rompecabezas aleatorio generado. En cada iteración, el optimizador selecciona un rompecabezas del grupo y realiza su mutación.
La mutación elimina todos los puntos y luego cambia ligeramente los números (es decir, disminuye / aumenta el valor de un número seleccionado al azar o mueve el número a otra celda de la cuadrícula). Puede aplicar varias mutaciones al campo al mismo tiempo. Luego ejecutamos el solucionador en el modo de generación de nivel especial descrito en la sección anterior. Agrega suficientes puntos al rompecabezas para que pueda resolverse nuevamente.
Después de eso, comenzamos el solucionador nuevamente, esta vez en modo normal. Durante esta ejecución, el solucionador monitorea a) la profundidad del árbol de decisión, b) la frecuencia de la necesidad de diferentes tipos de reglas, c) el ancho del árbol de decisión en diferentes momentos. El rompecabezas se evalúa según los criterios descritos anteriormente. La función de evaluación prefiere soluciones profundas y estrechas, y los niveles de mayor complejidad también agregan más peso a los acertijos en los que se requieren reglas de razonamiento más complejas.
Luego se agrega un nuevo rompecabezas a la piscina. Si el grupo contiene más de 10 acertijos, se descarta lo peor.
Este proceso se repite varias veces (aproximadamente 10,000-50000 iteraciones me llevaron). Después de eso, la versión mejor calificada del rompecabezas se guarda en la base de datos de nivel de rompecabezas. Así es como se ve el progreso del mejor rompecabezas en una ejecución de optimización:
Intenté usar otras formas de estructurar la optimización. En una versión, se usó el recocido simulado; otros fueron algoritmos genéticos con varias operaciones de cruce. Ninguna de las soluciones funcionó tan bien como un algoritmo ingenuo con un conjunto de opciones que regresan a la cima.
Solución única única
Cuando un rompecabezas tiene una solución única y única, surge una dificultad interesante. ¿Es posible permitir que el jugador asuma que hay una solución y sacar conclusiones basadas en esto? ¿Sería justo si el generador de rompecabezas sugiriera que el jugador lo hiciera?
En una publicación en HackerNews, dije que hay cuatro opciones para abordar esta situación:
- Declare la unicidad de la solución desde el principio y obligue al generador a crear niveles que requieran este tipo de razonamiento. Esta es una mala decisión porque complica la comprensión de las reglas. Y generalmente estos son los detalles que la gente olvida.
- No garantice la singularidad de una decisión: potencialmente tenga muchas decisiones y tome todas ellas. De hecho, esto no resuelve el problema, sino que lo aleja.
- Simplemente asuma que este es un evento muy raro, que en la práctica no es importante. (Esta es la solución que se utilizó en la implementación inicial).
- Cambie el generador de rompecabezas para que no genere rompecabezas en los que el conocimiento de la singularidad de la solución ayudaría. (Probablemente la solución correcta, pero requiere trabajo adicional).
Inicialmente, elegí la última opción, y ese fue un terrible error. Resultó que tomé en cuenta solo una forma en que la singularidad de la solución condujo a la fuga de información, y en realidad es bastante raro. Pero hay otros; De hecho, uno de ellos estaba presente en todos los niveles que generé y a menudo condujo al hecho de que la solución se volvió trivial. Por lo tanto, en mayo de 2019, cambié los modos Hard y Expert usando la tercera opción.
El caso más molesto es un deuce con una línea discontinua en este campo:
¿Por qué un jugador astuto puede llegar a tal conclusión? Un deuce puede cubrir cualquiera de los cuatro cuadrados vecinos. Ninguno de ellos tiene puntos, por lo que no tienen que estar cubiertos por una línea. Y el cuadro de abajo no tiene superposiciones con ningún otro número. Si hay una única solución, entonces este debería ser el caso cuando otros números cubren los tres cuadrados restantes, y los dos cierran el cuadrado debajo de él.
La solución es agregar algunos puntos más al reconocer estos casos:
Otro caso común es un guión con una línea de puntos en este campo:
Los cuadrados a la izquierda y arriba de los dos no son diferentes. Ninguno de ellos tiene un punto, y ninguno puede ser alcanzado desde ningún otro número. Cualquier solución en la que un deuce cubra el cuadrado superior tendrá una solución correspondiente en la que cerrará el cuadrado izquierdo, y viceversa. Si hubiera una única solución única, entonces esta no podría ser, y el deuce debería haber cubierto el cuadrado inferior.
Decidí este tipo de caso de la forma "si duele, entonces no lo toques". Solver aplicó esta regla en una etapa temprana de la lista de prioridades y asignó a tales movimientos un gran peso negativo. Los acertijos con esta característica generalmente son descartados por el optimizador, y los pocos restantes se descartan en la etapa de la selección final de niveles para el juego publicado.
Esta no es una lista completa. Durante las pruebas de juego con una búsqueda deliberada de errores, encontré muchas otras reglas para soluciones únicas. Pero la mayoría de ellos parecían raros y eran suficientes para encontrar, por lo que no simplificaron mucho el juego. Si alguien resuelve el acertijo usando tal razonamiento, entonces no lo culparé a ellos.
Conclusión
Inicialmente, el juego se desarrolló como un experimento en la generación procesal de acertijos. El diseño y el generador del juego iban de la mano, por lo que las técnicas en sí mismas son difíciles de aplicar directamente a otros juegos.
La pregunta a la que no tengo respuesta: ¿se ha justificado la inversión de tales esfuerzos en la generación procesal?
Los comentarios de los jugadores sobre el diseño del nivel fueron muy controvertidos. En comentarios positivos, generalmente se decía que siempre se siente algún truco complicado en los rompecabezas. En la mayoría de las críticas negativas, me escribieron que el juego carece de un gradiente de complejidad.Todavía tengo un par de acertijos en su infancia, y me gustó tanto el generador que probablemente utilizo un enfoque de procedimiento similar para ellos. Solo cambiaré una cosa: desde el principio realizaré pruebas de juego activas con la búsqueda de errores.Notas
[0] O, al menos, me pareció a mí. Pero cuando vi a los jugadores en vivo, casi la mitad de ellos solo hizo conjeturas y luego los iteraron. Oh bien[1] Los lectores de mi artículo también deberían leer el artículo Solucionando Buscaminas y haciéndolo mejor Magnus Hoff.[2] Aclararé que la profundidad / estrechez de un árbol es una métrica que consideré importante para mi juego, y no para todos los otros acertijos. Por ejemplo, hay un buen argumento de que el rompecabezas de la Hora Punta es interesante si tiene varios caminos para resolver casi, pero no exactamente la misma longitud. Pero sucedió porque Rush Hour es un juego para encontrar la solución más corta, y no cualquier solución.[3] Excluyendo la adición de unidades. No había puntos en la primera versión del rompecabezas, y el plan era que el generador agregara unidades si fuera necesario. Pero eso parecía demasiado restrictivo.