La fascinante IA en “Dicey Dungeons” (2019)

Estuve jugando mucho Dicey Dungeons últimamente, un dungeon-crawler tipo roguelike creado por Terry Cavanagh. Uno de los aspectos que más me atrajo es la manera en la que funciona su inteligencia artificial. Afortunadamente, el creador tenía algunas cosas para decir al respecto.

***

Seis desafortunados participantes

La historia –que es más bien una excusa– va por este lado. Seis desafortunados concursantes han sido seleccionados para participar en Dicey Dungeons, el misterioso programa de juegos presentado por Lady Luck.

Transformados en antropomórficos dados, tienen que explorar mapas aleatorios llenos de monstruos y luchar hasta el fondo, armados solo con un puñado de dados para lanzar cada turno, y una selección de cartas/equipos.

Hay seis personajes principales (más algunos secretos) que brindan modos de juego completamente diferentes. Éste es un excelente “pick up and play”, porque es bien minimalista, carga rápidamente y las partidas pueden durar 30 minutos como máximo.

Curiosamente, es bastante extenso. Completar las seis rondas principales (una por cada uno de los seis dados) te puede llevar unas 3 horitas. Pero luego se abren muchos nuevos y originales desafíos que alargan la duración notablemente. Llevo 36 horas en Steam y estoy cerquita de terminarlo. No me aburrí en ningún momento.

Todas las clases de personajes cuentan con un mismo sistema: recorrer cinco pisos, eliminando enemigos y levantando ítems, hasta llegar al sexto donde se encuentra un final boss aleatorio.

Pero el feeling de la corrida es muy distinto si utilizamos al Ladrón (que “toma prestada” una carta al azar del enemigo), el Robot (que puede lanzar tantos dados como su CPU lo permita) o el Inventor, que al final de cada batalla pierde una carta porque la convierte en otra cosa. Cada jugador trae algo distinto a la mesa.

Cartas y dados combinados

Su fuerte es el sistema de combate, que posiblemente sea el elemento más atractivo de Dicey Dungeons. Turno tras turno, jugador y enemigos lanzan una finita cantidad de dados que sirven para “activar” las cartas de nuestro mazo. Dichas cartas pueden atacar, defendernos, generar efectos de status, curarnos, etc.

Cada pieza de equipo ofrece muchísimas formas ingeniosas de utilizar nuestros dados, y cada personaje tiene una serie de estrategias que debemos considerar cuidadosamente para superar los desafíos. Esto hace que un juego que depende muchísimo de la suerte, pueda ganarse fácilmente si somos inteligentes con nuestras decisiones.

Mientras jugaba me puse a pensar en lo difícil que debe haber sido programar la inteligencia artificial de los enemigos. No soy programador (y mi experiencia en ese área es muy simple) pero es un tema que me gusta mucho y que, además, me toca de cerca en el ámbito profesional.

Como consultor funcional SAP (por un lado) y docente universitario en el área de Investigación Operativa (por el otro) la programación es algo con lo que cruzo miradas todos los días.

En mi trabajo de consultor, por ejemplo, diariamente tengo contacto con los programadores para el análisis y creación de nuevos desarrollos, y tuve que hacerme con un mínimo de conocimientos para poder debuggear programas o analizar problemas en el sistema.

En la cátedra de Investigación Operativa a la que pertenezco enseñamos diferentes modelos y herramientas para la toma decisiones, e inevitablemente siempre caemos en algunos tópicos de programación.  Así que, entusiasmado, me puse a investigar cómo Terry Cavanagh había resuelto estas cuestiones.

Dicey Dungeons y su inteligencia artificial

En su simpleza, Dicey Dungeons es un juego bastante complejo. Básicamente unifica la construcción de mazos con una experiencia RPG, donde cada enemigo tiene un pool de cartas que hacen cosas diferentes. Pero además, los enemigos tiran dados que pueden hacer todo tipo de efectos.

Veamos un ejemplo sencillo de una rana que utiliza una espada (que ataca) o un escudo (que coloca defensa). Acá la mejor decisión de una IA, en relación a los dados que salieron 1 y 3, tiene ramificaciones limitadas.

Pero la gran mayoría de los casos son más enredados. Este handyman, por ejemplo, tiene una llave inglesa, que le permite combinar dos dados (por lo que 3 + 2 le daría un solo 5, y un 4 + 5 le daría un 6 y un 3). También tiene un martillo, que aplica un “shock” al jugador si lo usa con un seis, y un pea shooter, que no hace mucho daño, pero que tiene una cuenta regresiva que persiste en los turnos.

Como puede verse, hacer que una computadora tome una buena decisión basándose en tantos caminos posibles ya no es tan fácil.

A esto hay que agregarle la complicación de los efectos de estado. El “shock” desactiva un equipo al azar, que puede desbloquearse usando un dado. El “burn” te prende fuego los dados, y para usarlos hay que sacrificar 2 HP.

Un handyman con todos sus dados quemados, diferentes cartas y dados arrojados al azar tiene que, en cuestión de milisegundos, tomar la decisión que maximice el daño realizado y minimice el riesgo propio. Es, en definitiva, un Problema de Optimización como los muchos que estudiamos en mi cátedra para la carrera de Ingeniería Industrial

Esto es lo que hizo una Inteligencia Artificial ingeniosa ante tal situación. ¿Pero… cómo llegamos a esa programación tan hermosa?

Los problemas de hardcodear el código

Terry Cavanagh se preguntó: ¿cómo se hace una IA que pueda descubrir lo mejor que puede hacerse en su turno? ¿Cómo sabe la computadora qué dados ardientes extinguir, qué dados usar para desbloquear y qué dados guardar para equipos importantes?

Durante las primeras etapas, la IA en Dicey Dungeons solo tenía una regla: miraba todo el equipo de izquierda a derecha, descubría los mejores dados para usar y los usaba. Esto funcionó muy bien, hasta que no lo hizo. 

Entonces, Cavanagh se vio obligado a agregar más reglas que tuvieran en cuenta otros condicionales como el shock y el burn.

Pero con el tiempo, este sistema de agregar más y más reglas a la IA realmente comenzó a romperse. Los testers descubrían hazañas consistentes para lograr que la IA hiciera cosas estúpidas. Con la configuración correcta, uno de los jefes podría ser engañado para que nunca te ataque, por ejemplo. Cuantas más reglas se agregaran para tratar de arreglar las cosas, sucedían cosas extrañas, porque las reglas comenzaron a entrar en conflicto con otras.

Este estilo de programación no es inteligencia artificial, sino una codificación basada en la fuerza bruta y el hardcodeo. Por eso, el desarrollador decidió tachar todo y comenzar desde cero.

La solución clásica: Minimax

El clásico algoritmo de toma de decisiones se llama Minimax, un concepto que explico en mis clases y que, tranquilamente, puede usarse para desarrollar la inteligencia artificial de la computadora jugando al Ajedrez.

La implementación supone poder listar todas las decisiones posibles por turno y armar una función de valor que permita medir qué tan bien va el juego para una configuración particular.

Para el Ajedrez, quizás un tablero donde todas las piezas están en sus posiciones iniciales vale 0 puntos. Un tablero donde capturaste a un Peón enemigo quizás valga 1 punto, y tal vez un tablero donde hayas perdido uno de tus Peones valga -1 puntos. En definitiva, lo que estamos haciendo es crear una gráfica de todos los movimientos posibles que ambos jugadores pueden hacer, y usar nuestra función de valor para medir cómo va el juego.

Aplicación de un algoritmo MiniMax a un tablero de Ajedrez

Acá es donde Dicey Dungeons se divide de Minimax, que es una teoría matemática del juego diseñada para descubrir la mejor serie de movimientos en un mundo donde el oponente está tratando de maximizar su propio puntaje. Se llama así porque trata de minimizar la pérdida cuando tu oponente juega para maximizar su ganancia.

Pero, en realidad, en Dicey Dungeons no importa (tanto) lo que esté haciendo mi oponente. Para que el juego sea divertido, sólo queremos que la IA haga movimientos que tengan sentido: descubrir la mejor manera de jugar sus dados en su equipo para que sea una pelea justa. En otras palabras, todo lo que importa es el Max, no el Min.

Si volvemos al ejemplo de la rana con dados 1 y 3, básicamente solo tiene dos opciones: colocar el 1 en la espada ancha y el 3 en el escudo, o al revés. Obviamente, decide que es mejor poner ese 3 en la espada que el 1. ¿Pero, por qué? Bueno, porque analizó todos los resultados.

Lo que se hace es crear un Árbol de Decisión con los potenciales caminos, y cada efecto o uso tiene una serie de puntos asignados. Colocar el 1 en la espada da un puntaje de 438. Colocar el 3 en da un puntaje de 558. Entonces, la computadora elige la opción que maximiza el puntaje.

Por supuesto que ese puntaje es arbitrario y decidido por el creador. Se priorizaron daños de ataque y efectos de status como decisiones que maximizan el puntaje.

Finalmente, también hay dos casos especiales: si el objetivo del ataque está cerca de morir, vale un millón de puntos. Si la IA no tiene salud, vale menos un millón de puntos. Esto significa que la IA nunca se suicidará accidentalmente (al extinguir un dado cuando tienen muy poca salud, por ejemplo), o nunca dejará pasar un movimiento que mataría al jugador.

Sin duda, este puntaje no es perfecto, pero funciona para que las batallas se sientan desafiantes y los enemigos tengan un nivel de dificultad similar al que tendría un ser humano que piensa lógicamente. Son raras las ocasiones donde sentí que la IA no tomaba buenas decisiones con sus dados.

La solución moderna: Simulación

En paralelo con ese algoritmo de puntaje, Dicey Dungeons necesitó incorporar otro tipo de soluciones porque su modelo es, en definitiva, más probabilístico que determinístico. Algunas cartas, por ejemplo, tienen resultados inciertos. Hay una llamada “lockpick” que divide el dado en dos. Si colocamos un 6, podemos obtener un 1 y un 5, dos 3 o un 2 y un 4. Hasta que eso ocurra, la computadora no sabrá cómo actuar.

La solución consistió en aplicar técnicas de Simulación (de nuevo, parte del estudio de la Investigación Operativa). Monte Carlo Tree Search (o MCTS, para abreviar) es un algoritmo de toma de decisiones probabilístico que puede utilizarse.

Fases de la programación por Simulación de Montecarlo

Básicamente, en lugar de graficar cada movimiento posible que podamos hacer, MCTS funciona probando secuencias de movimientos aleatorios y luego haciendo un seguimiento de los que fueron los mejores. Con suficientes experimentos, puede decidir qué ramas de nuestro árbol de decisión son las “más prometedoras” gracias a una fórmula llamada “algoritmo Upper Confidence Bound”.

Lo maravilloso de MCTS es que generalmente puede encontrar la mejor decisión sin tener que forzar todos caminos posibles, lo cual reduce muchísimo el tiempo de procesamiento de la computadora.

Esto es lo que se terminó haciendo con Dicey Dungeons. La IA primero intenta hacer una expansión exhaustiva del árbol de decisión, que generalmente no lleva mucho tiempo y conduce al mejor resultado, pero si eso parece demasiado grande, recurre al uso de MCTS.

El método MCTS es genial para lidiar con la incertidumbre. Debido a que se está ejecutando una y otra vez, agregando datos de cada ejecución, simplemente se lo deja que simule movimientos inciertos como usar un lockpick de forma natural y, en ejecuciones repetidas, obtendrá un rango bastante bueno de puntajes.

***

Entonces, ¡así es cómo los enemigos en Dicey Dungeons deciden cómo matarte! Me encantó leer sobre Terry Cavanagh programando la inteligencia artificial de su juego, que realmente le funciona de maravilla.

UPDATE (28.06.2020)

Terminé el juego con unas 42 gloriosas horas contabilizadas. 100% recomendado. ¡El final fue súper épico!

……………………………………………………………

=>> Otros posts sobre VIDEOJUEGOS en el blog: “Into the Breach y el arte de perder”; “10 grandes juegos de Sega Genesis”; “Exploración y comercio en Moonlighter”; “La asistencia al jugador en Celeste”; “El océano de referencias pop en Alan Wake”; “El emotivo viaje de Brothers: A tale of Two Sons”.

……………………………………………………………

► Podés seguir las nuevas notas y novedades (además de humor y críticas de cine) en mi fan-page: http://www.facebook.com/sivoriluciano. Si te gustó, ¡compartilo o dejá un comentario!