Desarrollo de IA usando el ejemplo del juego Dicey Dungeons

Durante aproximadamente un mes, estuve resolviendo uno de los problemas técnicos más difíciles de mi nuevo juego, Dicey Dungeons : una IA mejorada para el lanzamiento final del juego. Fue un trabajo bastante interesante, y gran parte de esto era nuevo para mí, así que decidí escribir un poco sobre eso.

Para empezar, explicaré: no soy un experto en la teoría de las computadoras, sino uno de los que ha estudiado la programación lo suficiente como para crear videojuegos, después de lo cual terminé mis estudios comprendiendo solo lo que necesitaba. Por lo general, puedo resolver mis problemas por mi cuenta, pero un programador real probablemente no aprobaría mis decisiones.

Traté de escribir un artículo con un nivel de abstracción lo suficientemente alto como para que las ideas básicas fueran claras incluso para los no programadores. Pero no soy un experto en tales cosas, por lo que mis explicaciones de la teoría pueden ser erróneas. Escríbame sobre esto en los comentarios al original, ¡con gusto haré cambios!

Bueno, ¡comencemos explicando la tarea!

Desafío

En caso de que no hayas jugado a Dicey Dungeons, te contaré brevemente sobre el juego: este es un juego de rol con construcción de mazos, en el que cada enemigo tiene un conjunto de mapas de armas que realizan diferentes acciones. Además, ¡tiran dados! Luego ponen estos dados en el armamento para infligir daño, o crear varios efectos de estado, o sanar, o defenderse del daño, y cosas por el estilo. Aquí hay un ejemplo simple de cómo una pequeña rana usa una espada grande y un escudo pequeño:


Un ejemplo más complicado: este Jack de todos los oficios tiene una llave inglesa, que le permite juntar dos dados (es decir, 3 + 2 dará 5 y 4 + 5 dará 6 y 3). También tiene un martillo (Hammer), que impone un efecto de "choque" al jugador, si le aplicas seis, y un tirador de guisantes (Pea Shooter), que hace poco daño, pero tiene una "cuenta regresiva", entonces allí es válido para varios movimientos.


Otra complicación importante: el juego tiene efectos de estado que cambian las capacidades de los oponentes. El más importante de ellos es Shock, que deshabilita las armas al azar; el choque se puede eliminar usando un cubo adicional sobre él y "Burn", que prende fuego a los cubos. Mientras los cubos se queman, se pueden usar, pero cada uso costará 2 puntos de vida. Esto es lo que hace un manitas inteligente cuando pongo shock y quema en todas sus armas y cubos:


Por supuesto, hay mucho más en el juego, pero para tener una idea general, esto es suficiente.

Entonces, nuestra tarea: ¿cómo lograr que la IA elija la mejor acción para su movimiento? ¿Cómo puede averiguar cuál de los cubos en llamas apagar, qué cubo usar para aliviar el shock y cuál guardar para armas importantes?

Como lo hizo antes

Durante mucho tiempo, la IA en Dicey Dungeons solo tenía una regla: miró todas las armas de izquierda a derecha, determinó el mejor cubo que podía usarse en él y luego lo usó. Esto funcionó muy bien, pero hubo excepciones. Entonces agregué nuevas reglas.

Por ejemplo, me enfrenté a la conmoción mirando todas las armas que no estaban sujetas a la conmoción, y eligiendo qué cubo usaría cuando se quitara la conmoción, y luego marqué este cubo como "reservado" para el futuro. Trabajé con la quema de cubos como este: verifiqué si tenía suficiente salud para apagarlos y elegí al azar si hacer esto.

¡Agregué regla por regla para todo lo que podía imaginar, y como resultado obtuve una IA que parecía funcionar! De hecho, es sorprendente lo bien que se mostró esta combinación de diferentes reglas: la IA en Dicey Dungeons no siempre toma la decisión correcta, pero siempre fue al menos aceptable. Al menos para un juego aún en desarrollo.

Pero con el tiempo, el sistema de agregar constantemente nuevas reglas comenzó a resquebrajarse. La gente ha descubierto hazañas que hicieron que la IA se comportara estúpidamente. Por ejemplo, con el enfoque correcto, podrías burlar a uno de los jefes para que nunca ataque al jugador. Cuantas más reglas agregué para corregir la situación, más cosas extrañas comenzaron a suceder: algunas reglas entraron en conflicto con otras, comenzaron a aparecer casos límite.

Por supuesto, una de las soluciones fue agregar nuevas reglas, considerar cada tarea una por una y crear nuevas construcciones if para procesarlas. Pero creo que de esta manera simplemente hice a un lado la verdadera solución al problema. La limitación del sistema era que solo preocupaba una pregunta: "¿Cuál será mi próximo movimiento?" Ella nunca miró hacia adelante y no trató de sugerir qué podría venir de una combinación inteligente particular.

Entonces decidí comenzar de nuevo.

Solución clásica

Intenta buscar información sobre IA para juegos, y lo más probable es que lo primero que encuentres sea una solución clásica: crear un algoritmo minimax . Aquí hay un video sobre cómo se usa en el desarrollo de IA para el ajedrez:


La implementación de minimax es la siguiente:

Primero, creamos la versión más simple y abstracta de nuestro juego, en la que hay toda la información necesaria para un momento específico del juego. Lo llamaremos un tablero . En el caso del ajedrez, estas son las posiciones actuales de todas las piezas. En el caso de Dicey Dungeons, esta es una lista de dados, armas y efectos de estado.

Luego creamos una función de valor que mide qué tan bien se está jugando el juego para una configuración de juego específica, es decir, para un tablero en particular. Por ejemplo, en el ajedrez, un tablero en el que las piezas se encuentran en sus posiciones originales tiene una calificación de 0 puntos. El tablero en el que te comiste el peón de tu oponente tiene un valor de 1 puntos, y el tablero en el que perdiste tu propio peón tiene un valor de -1 puntos. ¡Y el tablero en el que mateamos al oponente será evaluado en un número infinito de puntos, o algo así!

Luego, desde este tablero abstracto, simulamos todos los movimientos posibles que podemos hacer, lo que nos da nuevos tableros abstractos. Luego simulamos la finalización de todos los movimientos posibles en estos tableros, y así sucesivamente, tantos pasos como desee. Aquí hay una excelente ilustración de una solución similar de freecodecamp.org :


Creamos una gráfica de todos los movimientos posibles que ambos jugadores pueden hacer, y le aplicamos una función de valor para evaluar cómo va el juego.


Y en esto, Dicey Dungeons difiere de minimax: minimax proviene de la teoría matemática de los juegos, está diseñado para encontrar la mejor serie de movimientos en el mundo donde el oponente busca maximizar su puntaje. El algoritmo se llama así porque minimiza las pérdidas del jugador cuando el oponente juega para maximizar sus ganancias.

Pero, ¿qué pasa en las mazmorras de Dicey? En realidad, no me importa lo que haga mi oponente. Para que el juego sea emocionante, es suficiente que la inteligencia artificial haga movimientos lógicos para determinar la mejor manera de aplicar los dados a las armas, para que la batalla sea justa. En otras palabras, solo "max" es importante para mí, sin "mini".

Es decir, para que AI Dicey Dungeons haga un buen movimiento, es suficiente para mí crear este gráfico de posibles movimientos y encontrar el tablero que tenga la puntuación más alta, y luego hacer los movimientos que conducen a este punto.

El movimiento fácil del enemigo.

Bueno, pasemos a los ejemplos. Miremos de nuevo a la rana. ¿Cómo puede decidir qué hacer a continuación? ¿Cómo sabe ella que la acción elegida es la mejor?


De hecho, ella solo tiene dos opciones. Coloca 1 en la espada ancha y 3 en el escudo, o haz lo contrario. Obviamente, ella decide que es mejor poner 3 en lugar de 1. ¿Pero por qué? Porque estudió todos los resultados posibles:


Si pones 1 en la espada, obtendremos 438 puntos. Si le pones 3, obtenemos 558 puntos. Genial Entonces, obtengo más puntos al colocar en la espada 3, el problema está resuelto.

¿De dónde vienen estas gafas? El sistema de evaluación en Dicey Dungeons actualmente tiene en cuenta los siguientes aspectos:

• Daño: el factor más importante es 100 puntos por cada punto de daño infligido.
• Veneno: un efecto de estado importante que AI considera casi tan importante como el daño: 90 por cada veneno.
• Crear otros efectos de estado: por ejemplo, shock, ardor, debilitamiento, etc. Cada uno de ellos cuesta 50 puntos.
• Efectos de estado de bonificación: agregar al jugador efectos de estado positivo, como defensa y similares, cuesta 40 puntos cada uno.
• Uso de armas: usar cualquier tipo de arma cuesta 10 puntos, porque si nada más tiene éxito, la IA solo tiene que intentar usar todo.
• Reducción de cuenta regresiva: para activar algunos tipos de armas (por ejemplo, para Pea Shooter), la cantidad total en los dados es suficiente. Por lo tanto, la IA recibe 10 puntos por cada punto de cuenta regresiva que reduce.
• Puntos en los dados: la IA obtiene 5 puntos por cada punto no utilizado en los dados, es decir, 1 cuesta 5 puntos y 6 cuesta 30 puntos. Esto se hace para que la IA prefiera no usar cubos que no necesita usar, por lo que sus movimientos se vuelven muy similares a los humanos.
• Duración: AI pierde 1 punto por turno, por lo que los movimientos largos tienen un valor ligeramente menor que los cortos. Esto se hace para que, en presencia de dos movimientos que de otro modo sean de igual valor, la IA elija el más corto.
• Tratamiento: cuesta solo 1 punto por un punto de salud restaurado, porque aunque quiero que la IA considere esto importante, en realidad no controlé mi salud. ¡Siempre hay cosas que hacer y más importantes!
• Puntos de bonificación: se pueden agregar a cualquier movimiento para obligar a la IA a hacer algo que nunca hubiera hecho de otra manera. Usado muy moderadamente.

Y finalmente, hay dos casos especiales: si el objetivo atacado se queda sin salud, entonces cuesta un millón de puntos. Si la salud termina con la IA, entonces cuesta menos un millón de puntos. Esto significa que la IA nunca se suicidará accidentalmente (por ejemplo, al pagar el dado con muy poca salud), o nunca perderá un movimiento en el que pueda matar al jugador.

Estos números no son ideales; tome, por ejemplo, los problemas abiertos actuales: 640 , 642 , 649 , pero esto no es muy importante. Incluso números aproximadamente exactos son suficientes para estimular a la IA a que haga más o menos correctamente.

Movimientos más difíciles del enemigo.

El caso de la rana es tan simple que incluso mi terrible código puede descubrir todas las opciones en solo 0.017 segundos. Pero entonces la situación se vuelve más complicada. Veamos nuevamente el ejemplo de Jack of all trades.


Su árbol de decisión es "un poco" más complicado:


Desafortunadamente, incluso en casos relativamente simples, una explosión de complejidad ocurre con bastante rapidez. En este caso, en nuestro gráfico obtenemos 2.670 nodos que deben examinarse, y esto lleva mucho más tiempo que en el caso de una rana, tal vez uno o dos segundos.

Esto se debe en gran medida a la complejidad combinatoria; por ejemplo, no importa cuál de los dos usamos para aliviar el shock inicialmente, el algoritmo considera esto como dos soluciones separadas y crea un árbol completo de soluciones de ramificación para cada una. Como resultado, obtenemos una rama cuya duplicación es completamente innecesaria. También hay problemas combinatorios similares al elegir bloques para la redención, para eliminar el impacto de las armas y el procedimiento para su uso.

Pero incluso si encontramos y optimizamos tales ramas innecesarias (lo que hago hasta cierto punto), siempre habrá un punto en el que la complejidad de todas las permutaciones posibles de soluciones conduzca a árboles de decisión enormes y lentos, cuya evaluación tomará una cantidad infinita de tiempo. Entonces, este es el primer problema serio de este enfoque. Aquí hay otro:


Llave maestra. Divide el cubo en dos.

Este importante tipo de armamento (y otros similares) causa problemas de IA porque el resultado de su uso es incierto . Si le pongo un seis, puedo obtener cinco y uno, o cuatro y dos, o tal vez dos triples. No lo sabré hasta que lo sepa, por lo que es muy difícil crear un plan que tenga esto en cuenta.

¡Afortunadamente, Dicey Dungeons tiene una gran solución para ambos problemas!

Solución moderna

El método Monte Carlo Tree Search (MCTS) es un algoritmo probabilístico de toma de decisiones. A continuación se muestra un video un poco extraño, que, sin embargo, explica muy bien el principio de toma de decisiones basado en el método de Monte Carlo:


De hecho, en lugar de agregar todos los movimientos posibles al gráfico, MCTS verifica las secuencias de movimientos aleatorios y luego rastrea los que han demostrado ser mejores. Gracias a una fórmula llamada Upper Confidence Bound, él puede determinar mágicamente qué ramas del árbol de decisión son las "más prometedoras":


Por cierto, tomé esta fórmula de un artículo muy útil sobre la búsqueda de árboles con el método de Monte Carlo . ¡No me preguntes cómo funciona!

Lo sorprendente de MCTS es que para encontrar la mejor solución, generalmente no necesitamos realizar una búsqueda tonta de todo, y podemos usar el mismo sistema de simulación de tablero / movimiento abstracto que en minimax. Es decir, usamos ambos algoritmos. Este es exactamente el esquema que utilicé en Dicey Dungeons. Primero, trata de completar un despliegue completo del árbol de decisión, que generalmente no toma mucho tiempo y conduce al mejor resultado. Pero si el árbol parece demasiado grande, entonces estamos volviendo a usar MCTS.

MCTS tiene dos características geniales que son perfectas para Dicey Dungeons:

En primer lugar, el método funciona idealmente con incertidumbre. Dado que se realiza una y otra vez, recolectando datos de cada ejecución, simplemente lo dejo simular movimientos indefinidos, por ejemplo, usando una clave maestra, de forma natural, y después de muchas ejecuciones, el método crea un rango bastante correcto de puntos obtenidos como resultado de este movimiento.

En segundo lugar, él puede darme una solución parcial. De hecho, cuando trabaja con MCTS, puede realizar tantas simulaciones como desee. Teóricamente, si se realiza sin fin, convergerá exactamente con los mismos resultados que minimax. Sin embargo, lo que es más importante para mí es que puedo usar MCTS para obtener una buena solución en un tiempo limitado de reflexión. Cuantas más búsquedas realicemos, mejor se encontrará la "solución", pero en el caso de Dicey Dungeons, a menudo solo bastan unos cientos de búsquedas, lo que lleva una pequeña fracción de segundo.

Temas relacionados interesantes

¡Así es como los enemigos en Dicey Dungeons deciden cómo matarte! ¡Quiero agregar este sistema a la próxima versión del juego v0.15!

¿De dónde provienen los gráficos que mostré, incluso en Twitter?


Los creé escribiendo un exportador para GraphML , un formato de archivo gráfico de código abierto que puede ser leído por muchas herramientas diferentes. (Utilicé el excelente yEd , que recomiendo encarecidamente).

Parte de la solución a este problema fue permitir que la IA simule movimientos, lo que en sí mismo es un rompecabezas interesante. Como resultado, implementé un sistema de secuencias de comandos de acción. Ahora que los oponentes están usando diferentes tipos de armas. ejecutan estos pequeños scripts:


Estos pequeños guiones son ejecutados por el analizador hscript y el intérprete de expresiones basado en haxe. Esta parte fue difícil de implementar, pero el esfuerzo valió la pena: hizo que el juego fuera muy conveniente para crear modificaciones. Espero que después del lanzamiento del juego, las personas puedan usar este sistema para desarrollar sus propias armas, es decir, puedan agregar al juego casi todo lo que puedan imaginar. Además, dado que la IA es lo suficientemente inteligente como para evaluar cualquier acción que se le transfiera, ¡los enemigos podrán descubrir cómo usar las armas modificadas que los jugadores crearán!