Cómo programar Bots con Inteligencia Artificial para ganarte en los juegos: Un ejemplo con Bomberman & Pommerman

Hace unos años era muy fan de los videojuegos, en concreto de la serie Call of Duty y los NBA 2K. Pero mis andaduras en el mundo “friki” empezaron mucho antes, con la PlayStation 1 y 2: Bomberman y el Crash and Bandicoot. En esa época, mi frase favorita era “Malditos Bots” cuando perdía (tenía muy mal perder), y en meterme en el mundo de la inteligencia artificial… aprendí realmente a cómo se hacen esos bots. 

Figura 1:Cómo programa Bots con Inteligencia Artificial para ganarte en los juegos: Un ejemplo con Bomberman & Pommerman

Pero primero, empecemos con un poco de introducción al tema. Cuando escuchemos la palabra bots, y en el caso particular de "Bots de aprendizaje para videojuegos", os debe venir a la mente una tecnología: Reinforcement Learning (RL). 

Intro a los bots y sistemas multiagente

El RL o aprendizaje por refuerzo es una rama de investigación de la IA muy interesante, donde distintos agentes interaccionan entre sí bajo un escenario realizando acciones. El Reinforcement Learning se diferencia de otros sistemas Multiagente por distintos motivos, entre los cuáles se destaca que estos obtienen un score/reward por cada secuencia generada de acciones, y se aprende a partir de ese valor. Este score es utilizado para que redes neuronales profundas (Deep Learning) o Planificadores Automáticos clásicos (utilizando heurísticas como A*) predigan qué acción se debe realizar en cada momento en función del conjunto de acciones que mejor reward dé. 

Figura 2: Libro de Machine Learning aplicado a Ciberseguridad de
Carmen Torrano, Fran Ramírez, Paloma Recuero, José Torres y Santiago Hernández

Aunque es muy interesante todo lo relativo a las redes de neuronas, hablaremos más sobre heurísticas, ya que es el principal componente que hizo grandes avances. Por decirlo de alguna forma, uno no puede correr sin saber cómo se camina. Para definir lo que es una heurística, utilizaremos la RAE: 

“En algunas ciencias, manera de buscar la solución de un problema mediante métodos no rigurosos, como por tanteo, reglas empíricas, etc.”

Por tanto, queremos resolver el problema sin realizarlo realmente. Estas heurísticas se pueden ver en el mundo real, un ejemplo:

- Un bate y una pelota cuestan 1,10€. 

El bate cuesta 1 euro más que la pelota. ¿Cuánto cuesta el bate?

1,10€ - 1, la pelota cuesta 0,10€ y el bate 1€, ¿no? Error. Quién haya pensado 1€, ha sido rápido que no preciso, y ha utilizado una heurística de aproximación. Realmente el bate cuesta 1,05€ y la pelota 0,05€.

Aunque estos ejemplos nos pueden hacer pensar que las heurísticas son malas, se utilizan mucho en problemas de competición entre agentes. El agente simulará “en su cabeza” qué acciones debe realizar y las seleccionará en función de una heurística. Después realizará estas acciones y verá si su previsión se adecua a la realidad del reward. Esto permite que la Inteligencia Artificial prediga qué acción realizar en función de posibles escenarios futuros.

En los algoritmos basados en normas había un techo de aprendizaje basado en la cantidad de datos que un sistema podía aprender. Deep Blue, que no utilizaba sistemas de RL sino planificadores clásicos, fue capaz de ganar al famoso ajedrecista Garry Kasparov en 1996, algo que antes parecía imposible. Pero un algoritmo más nuevo y complejo como AlphaGo llegó al nivel de expertos en el famoso y complicado juego asiático Go. Pero no se utiliza únicamente redes neuronales, como si de magia se tratara: AlphaGo Zero por ejemplo utiliza internamente heurísticas para simular pasos a corto plazo (MCTS, que comentaremos luego). Si queréis ver una implementación muy divertida de esta tecnología, el caso más sonado fue el de OpenAI, donde los personajes rompieron el juego “surfeando” las cajas.


Figura 3: OpenAI juego del Hike and Seek, donde los agentes compiteny/o colaboran entre ellos para su objetivo particular (pillar o no ser pillados)

En otros sistemas Multiagente no competitivos, como esta simulación de un mundo con COVID que realicé, los agentes interaccionan con el entorno a partir de un modelo BDI (Belief, Desire and Intention): cada agente tienes unas creencias sobre el entorno (por ejemplo, creo que no tengo Covid), tiene unos deseos (quiero ir a trabajar y al bar los jueves) y realiza unas acciones (se desplaza al sitio y se toma una cerveza en su bar favorito). En este tipo de simulaciones, los agentes no aprenden qué acciones deben realizar en cada momento, sino que nos sirven para simular situaciones reales donde distintos agentes interaccionan y se comunican entre sí.

Figura 4: Rutinas para cada uno de los tipos de agente (Young y Adult) en un mundo con Covid. En este tipo de simulaciones, los agentes no aprenden qué acciones deben realizar. 

Pommerman

Trasteando con tecnología, encontré la implementación en Java de Pommerman, un juego que seguro que a mi hermano Victor Ibáñez le sonará mucho, ya que nos pasamos horas jugando a otro muy similar. A mi parecer, la primera implementación parecida a un Battle Royal estilo Fortnite. En ese juego, diferentes jugadores se posicionan en las 4 esquinas de un tablero y deben atacar a los adversarios insertando bombas en el tablero. Aquí tenéis el paper asociado.

Figura 5: Pommerman original (izquierda) y versión en Java (derecha)

A partir de comandos podéis definir bots, cada uno con sus características. Cada uno de los bots podrá realizar 5 acciones (poner una bomba y los movimientos izquierda, derecha, arriba, abajo), además de poder quedarse quieto. Los agentes inteligentes tendrán una heurística concreta para este problema, que en el paper mencionan como una diferencia entre el nodo de búsqueda inicial (nodo root) y el estado final, donde se consideran distintos factores: el número de compañeros vivos, el número de enemigos vivos, el número de bloques de madera existentes, la fuerza de explosión y la habilidad de poder chutar bombas (algunos objetos recogidos aumentan estas dos últimas capacidades).

Por ejemplo, a menos enemigos vivos en nuestro estado evaluado, mejor es esa solución. Según la “inteligencia” de cada uno de los bots, podemos encontrar las distintas tipologías de agentes:

• DoNothing (0): El agente no realiza acciones.

• Random (1): El agente selecciona acciones de su pool de forma aleatoria.

• OSLA (2): One Step Look Ahead, este tipo de agente calcula (a partir de la heurística comentada) el siguiente paso a realizar, y escoge el que dé mejor resultado.

• Simple Player (3): Este agente calcula con Dijkstra (máximo 10 steps) el path más corto a los objetos del entorno. Entonces se escapa en caso de estar en la potencial área explosiva de una bomba, deja una bomba en caso de estar adyacente a un jugador rival, se acerca a un enemigo en caso de estar cercano a 2-3 pasos y puede dejar una bomba en caso de estar cerca de un trozo de madera.

• RHEA 200 (4): o Rolling Horizon Evolutionary Algorithm, este algoritmo genera N individuos de L pasos/acciones a realizar, utiliza métodos de algoritmos genéticos (como mutación o elitismo) para generar nuevos individuos y a partir de la heurística mencionada escoge el primer paso del mejor individuo.

• MCTS (5): o Monte-Carlo Tree Search, es otro Stocastic Forward Planning. Como algunos recordaréis, Monte-Carlo se puede utilizar, por ejemplo, para aproximar PI a partir de N simulaciones del experimento, para estimar la probabilidad de que suceda un evento... MCTS balancea entre exploración-explotación para desplegar el árbol de búsqueda a partir de los nodos más prometedores (no lo despliega entero). Se simulan distintos escenarios des del nodo aún no expandido, y se selecciona la primera mejor acción a realizar.

Además, tenemos la opción de controlar a uno de los personajes (6), para jugar contra los bots en esta simulación, y seleccionar qué campo de visión tienen los personajes y si es una competición por equipos.

Si vemos la implementación del player DoNothing, observaremos el esqueleto que deben tener todos los otros jugadores. Debemos extender la clase Player y crear nuestras normas o algoritmos para la selección de acciones en la función act. En el caso de SinglePlayer, la norma de escaparse en caso de estar en una posición no safe, debemos movernos a una posición safe en la siguiente jugada.

Figura 6: Implementación del DoNothing player (izquierda) y acción de escaparse en SinglePlayer (derecha)

Una vez hemos compilado y ejecutamos el programa con los parámetros adecuados, podremos jugar contra los tipos de jugadores mencionados anteriormente o los que hayamos creado. Por ejemplo, un juego contra los 3 jugadores más sencillos (DoNothing, RandomPlayer y SimplePlayer) se ejecutaría como:

 .\run.jar 0 1 1 -1 0 1 2 6

Los primeros parámetros corresponden a qué tipo de juego se simula (individual o por equipos), la semilla del juego, repetición por cada semilla (queremos simular un juego) y el tipo de visibilidad (en nuestro caso -1 ya que queremos ver todo el tablero). Los últimos cuatro parámetros (0 1 2 6) corresponden a los tipos de jugadores, por lo que la distribución de los jugadores será: arriba-izquierda DoNothing, abajo-izquierda RandomPlayer, abajo-derecha OSLA y arriba-derecha el jugador que yo moveré. Veamos un juego:

Figura 7: Videojuego “sencillo”

Sí, me ganó el jugador DoNothing porque nos morimos a la vez el jugador OSLA y yo… Ahora escribo con el teclado roto. El jugador random, en cambio, se suicida en las primeras iteraciones dado que no aprende qué jugadas realizar, sino que escoge una del pool de posibles jugadas.

Si jugamos un juego contra los agentes más “inteligentes” (SimpleAgent, RHEA y MCTS) aumenta la dificultad. El comando es “.\run.jar 0 1 1 -1 3 4 5 6”, por lo que la distribución será arriba-izquierda SimpleAgent, abajo-izquierda RHEA, abajo-derecha MCTS y arriba-derecha mi jugador. Veamos un juego:

Figura 8: Vídeo juego modo “hard”

Entre mis amigos esto le llamamos la 13,14. Lo que sí que hemos podido aprender de hoy, a parte de la notable pérdida de mis habilidades jugando videojuegos, es un repaso sobre la IA en competiciones, qué es una heurística y cómo se programan bots para Bomberman con ellas. ¡No dudéis en descargaros el código, implementar algún bot y/o jugar!

Saludos,

Autor: Bruno Ibáñez, Investigador de Ciberseguridad e IA en Ideas Locas

Contactar con Bruno Ibáñez