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!
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!
No hay comentarios:
Publicar un comentario