La ciencia de los videjuegos: IA (I)

Texto escrito por Víctor Buendía Ruiz-Azuaga

El otro día Dani Martínez os hablaba de los retrovirus usando el juego Metal Gear como excusa. Hoy yo también vengo a hablar de ciencia en los videojuegos, pero desde una perspectiva distinta, y esta es cómo se aplican teorías matemáticas y físicas a uno de los apartados más complicados de desarrollar: la Inteligencia Artificial.

La inteligencia artificial en los videojuegos

La inteligencia artificial, cariñosamente llamada IA, es un componente fundamental en buena parte de los videojuegos que jugamos. En algunos, como puede ser algo del tipo Super Mario Bros, no es especialmente útil: los enemigos y bloques se mueven siguiendo un patrón sencillo determinado, que ponga obstáculos al jugador. Sin embargo, no es necesario “pensar” en el sentido en el que usualmente lo entendemos.

Sin embargo, en otros juegos una mala IA da como resultado una experiencia de juego horrible. Por ejemplo, si en Counter Strike, Halo o Call of Duty los personajes que controla el ordenador son tan idiotas como para salir a disparar a cuerpo descubierto, sin cubrirse, sin esquivar los disparos, o recargando el arma delante de nuestras narices, la diversión baja mucho. El jugador podrá eliminar a todos los enemigos sin ninguna clase de dificultad, lo que reducirá bastante la dificultad y por tanto el entretenimiento.

Por otro lado, una IA demasiado buena también puede ser un desastre. Pongamos por ejemplo un juego de lucha, como Tekken. Si queremos hacer a un luchador inteligente, podría añadir una lógica sencilla como “si el jugador pulsa un botón para atacar, cúbrete de inmediato, y en cuanto esté indefenso, ataca”. El problema es que al contrario que el jugador humano, el ordenador realizará esta acción sin margen de fallo. Siempre esquivará al jugador, y siempre sin excepción logrará contraatacar con éxito. El resulto es un luchador perfecto, al cual nuestros lentos reflejos humanos no pueden ganar. En este caso, hay que tratar de hacer “más idiota” al ordenador, de forma que nuestro jugador tenga alguna oportunidad contra él, o de otro modo no querrá seguir jugando. Asimismo, sería deseable incluir varios niveles de dificultad.

Hay otros juegos donde es directamente imprescindible para que el juego funcione, que es en los juegos de estrategia, tanto en tiempo real, (RTS, tipo Starcraft o Age of Empires) como por turnos (como el famoso Civilization V o Final Fantasy Tactics), en los que queremos indicar a nuestra pequeña civilización cómo crecer, cómo atacar, expandirse o defenderse. Pero esto no es, ni mucho menos, una tarea trivial.

Supongo que en este punto el lector ya tiene claro la vital importancia de desarrollar una IA decente en un videojuego de calidad. Hay una regla adicional, además, importantísima: “el ordenador no ha de ser inteligente, solo ha de parecerlo”. Con que el jugador tenga la sensación de que su rival piensa, será suficiente, aunque a veces haga comportamientos aleatorios o aunque no sean los mejor pensados. ¡Eso basta para dar diversión a nuestro juego!

Grafos, búsqueda de caminos y árboles de tecnologías

Uno de los objetos básicos que empleamos a la hora de diseñar inteligencia artificial son los grafos. Un grafo es un objeto matemático bastante divertido y fácil de explicar, al ser  bastante visual. Por ejemplo, un grafo es algo como lo siguiente:

Se trata simplemente de pequeños objetos, llamados nodos, unidos por enlaces. Podemos ir moviéndonos de un nodo a otro a través de su enlace. Por ejemplo, del 6 se puede ir al 4 pero a ningún otro. Del 4 podemos ir al 5, al 6 o al 3.

Se pueden hacer muchas variaciones de estas estructuras. Podemos, por ejemplo, añadir flechas que indiquen las direcciones en las cuales podemos ir. Entonces podría ser que se pudiera ir del 4 al 5 pero no del 5 al 4, y señalar una dirección preferente de viaje en el grafo.

¿Y estas “cositas” realmente tienen utilidad matemática? ¡Pues sí, la respuesta es que bastante! Por ejemplo, supongamos que convertimos a los nodos en las ciudades de España, y las unimos mediante enlaces que representan las carreteras. Nos quedaría un grafo como el de la imagen de arriba. Sin embargo, esto sería poco realista: no sabemos qué distancia hay de la ciudad 6 a la 4, ni de la 4 a la 5. Los enlaces son solo, digamos, ilustrativos de qué nodos están conectados.

La solución, claro está, pasa por añadir el valor de longitud a cada enlace. Y tendremos un grafo con ciudades, enlazadas por líneas con un valor de longitud. Pues bien, empleando algoritmos matemáticos, puede calcularse cuál es la forma más rápida de viajar entre dos ciudades cualquiera del grafo, lo cual es bastante útil a la hora de diseñar rutas para viajar. Otras aplicaciones de los grafos son cosas como el diseño de algoritmos para recomendar amigos o contactos en redes sociales, o  búsquedas en bases de datos en informática.

¿Y cuál es la utilidad de esto en nuestro diseño de la IA? En todos los juegos de estrategia, y también en los de disparos, necesitamos personajes que se muevan por un escenario con cierta autonomía. Pongamos por ejemplo Age of Empires. Mi ordenador ha construido un ejército dispuesto a aplastarme, y tiene que llevarlo de una punta del mapa a la otra para atacarme. Una opción seria tratar de ir avanzando en línea recta e ir esquivando obstáculos según los vaya detectando, pero eso puede que le lleve por rutas muy extrañas o incluso a callejones sin salida.  La otra sería crear un grafo, con nodos en sitios clave del mapa. Después aplicaré el mejor algoritmo que tengo de búsqueda en grafos, llamado A*. El algoritmo seleccionará la ruta posible más corta entre mi ejército y la ciudad enemiga,  y solo tendré que ir guiando al ejército de nodo en nodo, siguiendo los enlaces, hasta llegar allí. 

Los algoritmos de búsqueda de rutas son complicados de explicar y no haré una digresión aquí sobre cómo funcionan en profundidad. Para el que tenga curiosidad por cómo funcionan estos algoritmos, Clara Grima tiene un ejemplo bastante ilustrativo por aquí, aunque utilizando el algoritmo de Dikstra, que es un poquito menos eficiente que el  A* a la hora de encontrar una ruta entre dos puntos, y por tanto, menos popular entre los programadores de videojuegos.

Podemos hacer tantas modificaciones como queramos para adaptar el algoritmo a nuestros intereses. Por ejemplo, en Counter Strike lo más deseable a menudo no será la ruta más corta, sino aquella donde avance más cubierto del fuego enemigo. Entonces la distancia entre nodos, el numerito que llevarán los enlaces no será la realmente distancia, sino también incluiremos la seguridad del nodo. Por ejemplo, supongamos que de un nodo A se puede ir a uno B y a otro C. B está situado a 1 metro de A, y C a 3 metros. Sin embargo, B es poco seguro, así que lo que hacemos es sumarle 5. C es muy seguro, así que se queda como está. Entonces, es como si nuestro nodo B estuviera a 5+1=6 metros, y C solo a 3. Cuando yo aplique mi A*, considerará que C está más “cercano” y usará este nodo, proporcionando la seguridad que necesitamos en lugar de quedar expuestos.

En juegos de tablero por turnos, a cada casilla se le asigna un número indicando lo fácil o difícil que es andar por allí, de modo que siempre se escoja la ruta óptima, yendo por los sitios por donde se avanza más rápido. 

Observamos que los grafos son una excelente herramienta para movernos por el mapa, en toda clase de situaciones. No solo encuentran la ruta más corta, o más rápida, sino que con ingenio se pueden tener en cuenta otros factores de interés para nuestro juego. Esto desde luego hace que el ordenador se mueva de forma inteligente. Por si eso fuera poco, hay algoritmos adaptables para situaciones cambiantes. Por ejemplo, en Age of Empires puede que se mientras mi ejército se mueve hacia la ciudad, por casualidad alguien haya construido una muralla que bloquea mi paso hacia el siguiente nodo del grafo. Pero mi ruta ya está escogida. Ir comprobando la ruta cada dos por tres para ver si ha cambiado puede ralentizar el juego cuando haya muchas unidades. Sin embargo, gracias a estos algoritmos adaptables mi ejército puede comprobar y modificar su ruta rápidamente para tratar de esquivar el nuevo obstáculo y tratar de llegar a la ciudad enemiga. ¡Otra idea, por supuesto, sería atacar la muralla y continuar nuestro camino!

Pero en los juegos donde la estrategia es un factor importante los grafos también juegan un papel fundamental. Por ejemplo, supongamos que en un juego de estrategia tenemos el siguiente árbol de tecnologías,

Este podría ser perfectamente el esquema de construcción de unidades de un videojuego de estrategia. Para hacer infantería necesito cuarteles, y para convertir mi infantería en héroes me hace falta un monje, que sale del templo.

Este árbol es en realidad un grafo, de modo que nuestro ordenador puede navegar a través de él. Supongamos que una unidad ha visto un buen sitio para defender y quiere construir allí una torre. Entonces el ordenador va al grafo de tecnología y avanza hacia atrás. Al hacerlo ve que para ello necesitará construir unos cuarteles, después infantería, y por último construir la torre.

Pero no solo eso. Para construir las cosas, hacen falta recursos, y eso permite hacer inducciones sobre el estado de la partida. Por ejemplo, si el ordenador detecta que el jugador ha realizado una herrería y múltiples mejoras de armas, quiere decir que el jugador ha optado por una rama del grafo, en detrimento de otra, y por tanto el número de unidades que tendrá no puede ser muy alto -probablemente sea el momento de realizar una expansíón, un ataque basado en la superioridad numérica, o potenciar la creación de unidades rápidamente.

También sirve para la toma de decisiones militares. Supongamos que lo que el ordenador ve del jugador es un monje y algunas unidades de caballería, mientras que él está realizando mejoras de unidades, infantería y torres. El que haya visto un monje implica, mediante un vistazo a los nodos vecinos por debajo de este, que las próximas tecnologías a desarrollar por su oponente son héroes y caballeros, muy superiores a las unidades que maneja, y por tanto debe activar rápidamente un plan de defensa si no quiere ser eliminado.

Todo esto puede hacerse muy sencillo gracias a la estructura de grafo. Por supuesto, tenemos además la ventaja de los grafos son bastante sencillos de programar, con lo cual se convierten en una herramienta excelente para bastantes cosas.

¿Tenemos suficiente con los grafos?

¡Parece que acabamos de encontrar la panacea a nuestros problemas de IA! ¡Alabados sean los grafos! Con ellos podemos hacer toda clase de movimiento inteligente por mapas complicados y también obtener información, realizar tomas de decisiones… ¿necesitamos realmente alguna herramienta más?

Y la respuesta, por desgracia, es que los grafos son sólo la punta del iceberg. Para comenzar, tienen algunos problemas. Calcular una ruta en un grafo es algo que consume tiempo. Si tengo muchos soldados en un mapa enorme y calculo trayectorias a largas distancias, mi juego necesitará mucho tiempo para calcular todas las rutas, haciendo que se congelen algunos fotogramas y causando el temido lag. Por otro lado, en un mapa con muchos espacios abiertos hay que poner muchos nodos muy juntos o el ordenador evitará espacios del mapa al moverse, puesto que no tienen asignados nodos. La única solución a esto es añadir más nodos para rellenar, pero esto podría hacer muy grande el tamaño del grafo incluso en mapas pequeños. Este problema se puede solucionar medianamente bien mediante la inclusión de los llamados “polígonos de navegación” o navmesh. Estos hacen las veces de grafo, pero se comportan de una forma mucho más eficiente a la hora de encontrar rutas en grandes espacios abiertos, mostrando las áreas transitables y caminos entre ellas. La siguiente figura es la misma que el anterior grafo, pero con un navmesh. Otra dificultad añadida, en el ejemplo de los ejércitos, es que normalmente los soldados avanzan en formación, un problema que a priori no podemos resolver con grafos.

Y esto es solo en el terreno del movimiento autónomo. En el caso de la toma de decisiones, aún no tenemos suficiente con los grafos. Sí, nuestro árbol de tecnologías es realmente muy informativo sobre la situación de la partida que manejamos. Sabemos que el rival tiene más fuerzas que nosotros, por ejemplo. ¿Que decisión tomamos? Un jugador humano podría replantearse varias opciones: hacer una fortificación de las defensas haciendo murallas en varios niveles y blindar su ciudad; intentar debilitar el ejército enemigo en pequeñas escaramuzas; tratar de hacer un ataque sobre los recursos del enemigo para minar su capacidad de construir y evitar el ataque. ¿Cuál de estas escogemos? Necesitamos que el ordenador intente pensar sobre cuál es la situación más favorable.

Por otro lado, esto es una IA global, digamos, una macro-inteligencia. Una vez hemos elegido una de las opciones anteriores, hay que hacer uso de otra IA diferente, una micro-inteligencia. Si vamos a atacar al ejército enemigo en escaramuzas, habrá que elegir cuánta gente dejamos defendiendo el campamento, cómo hacemos los equipos de combate, cómo y dónde vamos a mover cada y por qué. Si elegimos atacar a sus recursos, habrá que ver cómo los alcanzamos, porque seguro que no están desprotegidos.

Es decir, se trata de tomar decisiones muy complejas rápidamente, tarea una persona realiza con facilidad. Bien o mal, pero no duda en realizarlas. Y cuanto más juega, más aprende de los resultados y mejores son sus futuras decisiones. Pero este problema no lo podemos solucionar de una forma sencilla en el ordenador.

En la siguiente entrada sobre inteligencia artificial hablaré un poco de las técnicas que se emplean para conseguir mover colectividades de forma creíble, y también otras formas alternativas de mover personajes por el mapa y manejar la micro-inteligencia, ya que estos son los puntos “débiles” de nuestros grafos en la IA.

¡Nos vemos en la próxima!