**SVRAI**
Síntesis, Verificación y Razonamiento sobre Agentes Inteligentes
Máster Universitario en Lógica, Computación e Inteligencia Artificial
Dpto. Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
# SMA y Videojuegos
*Claudio Bustamante*
# Sistema multiagente (SMA o MAS)
Sistema compuesto por múltiples agentes inteligentes que interactúan entre ellos.
Ofrecen la posibilidad de resolver problemas que son muy difíciles o imposibles de resolver utilizando un enfoque de agente o programa individual.
No es lo mismo que un modelo basado en agentes (Agent Based Model, ABM), cuyo objetivo es simular las acciones e interacciones de agentes autónomos con el objetivo de comprender el comportamiento de un sistema y cómo se definen sus resultados. En cambio, un SMA busca diseñar un sistema basado en agentes utilizando esta metodología de diseño para resolver problemas específicos.
### Concepto
El sistema se divide entre los agentes y su entorno. Los agentes pueden ser software, redes, robots, humanos o equipos de humanos. Además, existen dos opciones respecto al comportamiento de los agentes: pueden tener un objetivo en común (no es necesario compartir conocimiento) o un objetivo diferente.
Se pueden definir 3 tipos de agentes:
- Pasivos: no tienen un objetivo (por ejemplo, un obstáculo, una caja, una puerta)
- Activos: tienen un objetivo simple (flocking, prey-predator)
[Coding Adventure: Boids](https://www.youtube.com/watch?v=bqtqltqcQhw)
- Cognitivos: resuelven cálculos complejos
### Características de agentes:
- Autonomía: por lo menos parcialmente independiente y autónomo.
- Vista Local: ningún agente tiene una vista global completa del entorno, o bien el sistema es muy complejo como para que un agente aproveche ese conocimiento.
- Descentralización: Ninguno de los agentes es designado como el controlador.
### Tipos de entornos:
- Discretos: si el número de acciones es finito
- Contínuos: si el número de acciones es infinito y la información cambiante
- Nivel de accesibilidad: si es posible obtener información completa o parcial del entorno
- Determinista o Estocástico: si las acciones tiene un efecto definitivo
- Episodicidad: Si las acciones de un agente en un período de tiempo afectan períodos subsiguientes
- Dimensionalidad: si las características espaciales del entorno juegan un papel importante y el agente debe considerarlas al tomar decisiones.
## Agente Autónomo
No existe actualmente un concenso respecto a la definición de un agente debido a la universalidad de la palabra. Pueden existir físicamente como robots o como redes computacionales. Además, el alcance de aplicaciones es vasto y variado, y no se puede generalizar.
La definición más aceptada es la de Russel y Norvig: *entidad flexible y autónoma capaz de percibir su entorno a través de sensores y capaz de actuar en su entorno a través de actuadores*.
Este agente está situado en un entorno (natural o virtual) y puede obtener información o estados mediante sensores, y actúa en base a esta información para lograr sus propios objetivos. El agente puede actuar directamente en base a sus sentidos para hacer un cambio en el entorno o su estado, sin necesidad de un intermediario.
Un agente inteligente es autónomo porque sus acciones y preferencias dependen de su experiencia en vez de conocimieno externo. Esto protege su estado interno de influencias externas (humanas o de otros agentes)
Es capaz de ejecutar acciones flexibles, considerando que el **nivel de flexibilidad** depende de los siguientes factores:
- Un sistema **reactivo** mantiene una relación continua con su entorno y responde a sus cambios
- Un sistema **proactivo** enfoca su comportamiento en lograr ciertos objetivos. Por eso, no está solo controlado por eventos, sino que también puede tomar iniciativa.
- Tiene **sociabilidad**, definida como el hecho que en un enorno multiagente, hay ciertos objetivos que no se pueden resolver sin coperación intra-agentes. Esto puede corresponder a una interacción con fuentes externas o con otros agentes.
[](https://imgur.com/Ehyb1gY)
### Características y clasificación
La implementación de sistemas multiagente puede tener varios beneficios incluyendo: **aumento de velocidad y eficiencia** de operaciones gracias a paralelismo y operaciones asíncronas; **evitar fallos del sistema completo** si hay un fallo de un agente; **escalabilidad y flexibilidad** al ser posible agregar agentes a medida que sea necesario; **costo reducido**, ya que agentes individuales son más baratos que una arquitectura centralizada y finalmente **reusabilidad** debido a la estructura modular.
Sin embargo, esto conlleva una serie de dificultades:
- Entorno: las acciones de cada agente cambian el entorno para todos los otros, por lo que surge la necesidad de que los agentes predigan las acciones de otros para decidir su acción óptima.
- Percepción: cada agente tiene una vista limitada del entorno, por lo tanto sus acciones podrían no ser óptimas al no tener toda la información.
- Abstracción: en SMAs, no todos los agentes experimentan todos los estados, por lo que es necesaria una buena comunicación para lograr un aprendizaje conjunto.
- Resolución de conflictos: definir cuándo comunicar la información y cuáles agentes para evitar situaciones de conflicto al modificar valores comunes
- Inferencia: es difícil obtener un mecanismo de inferencia en casos en que los agentes son heterogéneos (tienen distintos objetivos y capacidades)
### Arquitectura interna
Un SMA puede tener una estructura **homogénea** (todos los agentes tienen la misma arquitectura interna, objetivos, sensores, etc) o **heterogénea** (agentes pueden variar en habilidades, estructura y funcionalidades.
### Auto-organización y Auto-dirección
A pesar del comportamiento simple de sus agentes, un SMA puede manifestar auto-organización y auto-dirección. Cuando los agentes tienen la capacidad de compartir información utilizando algún lenguaje en común y considerando las restricciones del sisteme, puede producirse una mejora común entre los agentes.
[Complex Behaviour from Simple Rules: 3 Simulations](https://www.youtube.com/watch?v=kzwT3wQWAHE&t=124s)
[Coding Adventure: Ant and Slime Simulations](https://www.youtube.com/watch?v=X-iSQQgOd1A)
### Otras Aplicaciones
[Películas](https://www.massivesoftware.com/about.html), sistemas de defensa, transporte, logística, sistemas de informacióon geográfica, etc.
# SMA en Videojuegos
## Pac-Man: comportamiento emergente en base a reglas simples
Los fantasmas de Pac-Man son de los primeros ejemplos de agentes virtuales en videojuegos con personalidad, acompañando al mismo Pac-Man considerado como uno de los primeros personajes “mascota” de la industria.
Los fantasmas del juego tienen un comportamiento base muy sencillo, con pequeñas variaciones que hacen una gran diferencia en la percepción de su inteligencia. Todos comparten el objetivo de dirigirse hace una casilla en particular, pero cada uno elige esa casilla de manera diferente.
- Blinky, el fantasma rojo, siempre apunta directamente a la casilla donde está Pac-Man
- Pinky, rosado, apunta 4 casillas frente al movimiento de Pac-Man
- Inky, celeste, usa a Blinky como referencia para su casilla objetivo y por lo tanto parece trabajar en conjunto con él para acorralar a Pac-Man
- Clyde, naranjo, persigue a Pac-Man hasta acercarse a 8 casillas, y luego escapa de él
[Ejemplo en Unity para visualización](https://github.com/cebustama/Claudio-Pacman.git)
## FPS y la ilusión de colaboración entre NPCs contrincantes
[The F.E.A.R. AI](https://www.youtube.com/watch?v=KQN3yKYkFmE)
F.E.A.R. y **Goal Oriented Action Planning** derivada de AI Planning o **planificación automática**.El sistema busca una serie de acciones (plan) que eventualmente llegarán a un objetivo. Para hacerlo, el sistema almacena hechos y estados, así como las acciones posibles.
Planificar una **acción**:
- **Objeto**s involucrados en la acción
- Precondiciones: **hechos** que deben ser **tru**e para que la acción funcione
- **Efectos**, o cómo la acción afectará el **estado del entorno**.
La implementación de **G.O.A.P.** en F.E.A.R fue ideada por el Dr. Jeff Orkin en su publicación asociada a su PHd en el MIT. El sistema utiliza una **máquina de estados finitos** (FSM) con 3 estados:
- Goto: reproduce una animación de movimiento (caminar, correr, saltar, escalar, etc) al mismo tiempo que el agente se mueve hacia esa dirección.
- Animate: reproduce alguna animación
- Use Smart Object: reproduce una animación ligada a un objeto, por ejemplo, volcar una mesa.
[](https://imgur.com/SxsALeZ)
Todo personaje en el juego (incluso las ratas) que utiliza una AI debe tener asociados objetivos. El juego tiene 70 objetivos en su código, los cuales pueden asignarse a cualquier NPC que utilice el sistema. El sistema de planificación recibe estos objetivos y calcula su nivel de prioridad dependiendo de sus prerequisitos, por ejemplo, el objetivo “MatarJugador” tendrá una prioridad 0 si el personaje no sabe dónde está el jugador, y el objetivo “Patrullar” tendrá una mayor prioridad.
Según la prioridad de los nodos objetivos asociados a cada personaje, el sistema de planificación realiza una búsqueda para escoger el plan, es decir, la secuencia de acciones que debe realizar. Hay hasta 120 acciones disponibles en el juego, pero cada personaje tiene distintas disponibles. Al haber desarrollado un plan, el sistema lo valida según el estado del juego, y luego se debe revalidar periódicamente debido al carácter contínuo de los videojuegos.
Esta reevaluación constante curiosamente generó un problema de overhead debido a las ratas, que utilizan el mismo sistema de los NPC enemigos.
[](https://imgur.com/EOQHSlr)
Los agentes en este ejemplo no tienen sociabilidad ni saben de la existencia de otros, y solo siguen independientemente sus objetivos, por lo que toda cooperación entre ellos es una ilusión en la que se alinean sus objetivos momentáneamente.
## Survival Horror y Director AI
### Left 4 Dead 2
Juego multijugador desarrollado por Valve el año 2008. Se puede jugar hasta 4 jugadores y cada misión se basa en llegar a un punto final sobreviviendo a hordas de zombies, además de zombies especiales con habilidades únicas.
La AI de los zombies no tiene mucha innovación, simplemente siguen al jugador hasta morir. Lo que sí fue innovador fue la introducción de un **AI Director** que colabora con el resto de las AI del mundo. En este sistema de juego, se puede considerar la AI Director como un agente y al resto de los enemigos como agentes de otro tipo.
El **director** tiene el objetivo de mejorar la experiencia de los jugadores. No es un adversario ni busca derrotarlos. Se encarga de controlar el **flujo de juego**, tratándolo como una narrativa tradicional con puntos altos y bajos. De este modo, el sistema detecta los momentos propicios para lanzar un ataque sorpresa a los jugadores, y sabe cuando dejarlos descansar luego de un momento particularmente intenso. Internamente, la AI maneja un ciclo de 3 fases: *Build-up*, *Peak* y *Relax*. El momento en que se repite del juego se basa en el **nivel de estrés** percibido de cada uno de los jugadores, individualmente. Es decir, el sistema busca mejorar la experiencia de los 4 jugadores por separado y por lo tanto, en conjunto.
Para calcular el estrés, el sistema mide qué tantos zombies hay en la pantalla, qué tan cerca están de los jugadores, y si hay algún zombie especial atacando (lo cuál sube el estrés al máximo inmediatamente). En base a esto, el director decide cuándo, dónde y cuántos enemigos hacer aparecer. Respecto a los enemigos especiales, solo uno de cada uno puede estar en el mapa a la vez.
Finalmente, los objetos en el nivel (municiones, botiquines, armas, etc) también se otorgan según el mismo criterio, siempre buscando mantener el flujo de juego.
### Alien Isolation
[Revisiting the AI of Alien: Isolation | AI and Games](https://www.youtube.com/watch?v=P7d5lF6U0eQ&t=6s)
Alien Isolation es un juego de supervivencia/horror basado en la serie de películas Alien. El objetivo del juego es escapar de una nave espacial en la cuál estás atrapado con un xenomorfo, la famosa criatura extraterrestre de la franquicia. El gran factor que diferencia a este juego de otros es la aplicación novedosa de técnicas de AI para generar la ilusión de que el alien siempre te está persiguiendo y aprendiendo de tus decisiones como jugador.
El sistema funciona mediante la interacción de dos agentes con funciones diferentes:
**AI del alien** que funciona con un árbol de decisiones complejo. Es un sistema basado en sensores de audio y visión (multiples conos de visión), además de tacto (por ejemplo si el jugador toca la cola). El comportamiento que tiene la criatura es explorar las habitaciones buscando al jugador. El sistema va almacenando algunas variables del comportamiento del jugador, como por ejemplo cuántas veces se esconde en armarios, y en base a estos datos, se modifica el árbol de decisiones del alien. También se van agregando nuevos comportamientos a medida que progresa la historia.
**AI Director**. El segundo agente en el sistema corresponde a una inteligencia que actúa como director de la “acción” del juego. El comportamiento del alien por su cuenta puede llevar a situaciones en que el jugador queda acorralado en rincones del mapa, o que el jugador logre escapar y alejarse mucho del monstruo, eliminando la tensión. El AI Director tiene conocimiento tanto del alien como del jugador, y periódicamente le dice la dirección general del jugador, dejando la tarea final de “cazar” al jugador a la AI propia del alien.
Front Stage, en que el alien está activamente buscando al jugador, Menace Gauge que mide la intensidad de la presencia del alien. Cuando este valor llega a un punto de corte, el alien pasa al Backstage Mode, en que regresa a los conductos de ventilación para dar un respiro al jugador, pero también prepara emboscadas.
## Mundo abierto: Un caso general
Un ejemplo de cómo estructurar una ciudad de un videojuego de mundo abierto puede encontrarse en [Multi-agent Systems and Sandbox Games](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.4115&rep=rep1&type=pdf). En ese caso, se propone una jerarquía en que la ciudad misma actúa como el cerebro del sistema y a su vez como un agente que responde a diferenes estímulos. Luego siguen los sistemas de control, incluyéndo el control de trafico, de policía, de peatones, etc. Luego están los NPCs individuales (non player characters), cada uno con sus objetivos y personalidad, y finalmente otras entidades como animales. Agentes pueden comunicarse con su entorno y entre ellos (sistema de mensajes)
Tambien es importante el concepto de Nivel de Detalle o Level of Detail (LOD). Normalmente es aplicado a los entornos 3D para ahorrar procesamieno en los objetos más lejanos, pero también puede aplicarse a los agentes según su relevancia en cada momento. Esto se puede implementar mediante un sistema controlador de agentes del tipo overlord y mastermind.
En este sistema, los agentes en el nivel mas alto se mantienen completamente funcionales. Al pasar al segundo nivel, pierden su personalidad y pasan a ser controlados por un overlord (nuevo tipo de agente). Finalmente, la mastermind se encarga de controlar a los overlords y decidir en qué momento los agentes cambian de jerarquía.
### Watchdogs 2 y la Fábrica de Anécdotas
Juego de mundo abierto ambientado en la ciudad de San Francisco, en que el jugador toma control de un hacker con la habilidad de ingresar al teléfono y obtener información de cualquier personaje en el mundo del juego.
Para potenciar esta experiencia, los desarrolladores de Ubisoft crearon lo que llamaron la Fábrica de Anécdotas, un sistema diseñado para que las interacciones con los personajes y entre los personajes parecieran orgánicas y novedosas, buscando otorgar a cada personaje una personalidad y comportamiento distintivo. Lo complejo de este problema es hacer que las situaciones tengan lógica interna dentro del mundo del juego, y no parezcan simplemente momentos aleatorios.
Existen 2 sistemas interactuando constantemente.
- Reactive Agent System, cada personaje como agente tiene un ciclo de estados de ánimo: Feliz, Relajado, Nervioso y Enojado (Máquina de estados finitos) con temporizadores. Por ejemplo, si haces algo para enojar un NPC y luego lo dejas tranquilo, seguirá caminando pero su estado de ánimo seguirá siendo enojado por un tiempo. Cada personaje tiene un porcentaje de cada tipo de personalidad (violento, pesimista, optimista, neutral o heróico) que determina las condiciones de cambio de estado y por lo tanto cómo reaccionan ante estímulos. Para esto, se creo una enorme hoja de cálculo que actúa como matriz de reacción, tomando en cuenta la personalidad de personaje, el estímulo ante el que reacciona, y lo que estaba haciendo en el momento.
- Provocative Agents, cuyo objetivo es ser la fuente de eventos para que otros NPCs reaccionen a ellos. Estos agentes se introducen mediante atractores, actividades distintivas creadas a mano que ocurren en el mundo del juego (por ejemplo alguien tocando guitarra) y atractores dinámicos, creados por un administrador de eventos (peleas, amoríos, encuentros entre amigos, etc.)
### Shadow of Mordor y agentes narrativos
Juego de mundo basado en el universo del Señor de los Anillos de J.R.R. Tolkien. Su estructura es bastante estándar dentro del género (explorar el mapa, escalar torres para descubrir areas nuevas, derrotar campamentos de enemigos, ir a ciertos puntos del mapa para avanzar la historia, etc.)
La gran novedad que introdujo el juego fue el sistema Némesis. Es un sistema diseñado para crear narrativas emergentes en base a las experiencias del jugador.
El ejército de Sauron, compuesto por orcos o *uruks* tiene una jerarquía cambiante durante el juego.
El sistema puede seguir a cualquier *uruk* que haya tenido un encuentro memorable con el jugador (por ejemplo si lo derrotó o si sobrevivió) y va subiendo de rango en el ejército. Además, recuerda lo que sucedió en encuentros anteriores y se ven reflejados en su apariencia, habilidades, debilidades y comentarios. Por ejemplo, si la última vez fue derrotado con fuego, en el siguiente encuentro podría ser resistente a éste o tenerle fobia. De este modo el jugador forma sus propias narrativas en base a estos personajes, únicas para cada jugador.
## Juego Sistémico y Sistema como agente
### The Legend of Zelda: Breath of the Wild
Este es el último juego de la franquicia de **Legend of Zelda**, y representó un gran salto para la serie por su cambio de género. Anteriormente los juegos de **Zelda** eran relativamente lineales, y esta versión apuntó a un mundo abierto completamente libre casi desde el comienzo del juego.
Lo más interesante del diseño de este juego es la interacción de sus múltiples sistemas para ofrecer una experiencia de juego emergente, sopresiva, y permitiendo al jugador usar su creatividad.
Por ejemplo, cada arma del juego puede ser de metal o de madera, y existen tres efectos elementales: fuego, hielo y electricidad. Si un arma de madera toca fuego se encenderá, pero no las de metal. Las de metal por su parte conducen la electricidad, por lo que en una tormenta eléctrica atraerán rayos, lo mismo si Link lleva alguna armadura o escudo de metal.
Ciertas piedras, al ser golpeadas con un arma metálica, producen chispas. Si hay algún objeto de madera cerca de esas chispas, se producirá una fogata, que Link puede usar para calentarse y descansar cuando se encuentra en un lugar frío.
Todas las superficies del mundo del juego son escalables, sin embargo, si llueve, se volverán resbalosas, por lo que habrá que esperar para escalar. Así hay muchísimos ejemplos de interacciones entre sistemas, cada uno funcionando como un agente con sus reglas, creando momentos de jugabilidad emergente.
[Resolviendo un puzzle de la forma incorrecta](https://www.youtube.com/watch?v=iq4UqlgXoQo)
### Juegos de simulación
Los juegos de simulación son una categoría extremadamente diversa cuyo diseño generalmente se basa en simular algúna actividad del mundo real. Sus temáticas pueden ir desde construcción de ciudades (**SimCity*, *Cities: Skyline*), colonias de hormigas (*SimAnt*), aeropuertos (*Airport CEO*), zoológicos (*Zoo Tycoon*, *Planet Zoo*), la evolución (*Spore*), parques de diversiones (*Roller Coaster Tycoon*) o la vida misma (*Los Sims*).
Son quizás el ejemplo más directo de sistemas multiagente convertidos en juegos, con una arquitectura que casi siempre incluye interacción entre sistemas controladores y múltiples agentes individuales.
Por ejemplo, en Roller Coaster Tycoon (un simulador de construcción de parques de diversiones), cada persona que ingresa al parque tiene sus propias características (tolerancia al mareo, dinero, hambre y sed, opinión sobre la limpieza del parque, etc) que en conjunto determinan el éxito del parque.
### Colony Sims, Rimworld y las IA Cuenta Cuentos
Una subcategoría de los juegos de simulación son los Colony Sims o simuladores de colonias. Estos se basan en la premisa de administrar un número de individuos, casi siempre en circunstancias apocalípticas, cada uno con sus necesidades, objetivos y personalidades. Sus interacciones van formando narrativas emergentes, siempre diferentes para cada jugador y cada vez que juega.
Un ejemplo interesante de este género es Rimworld, ambientado en un futuro en que la humanidad establece colonias en otros planetas, en que cada partida comienza con un grupo de sobrevivientes que caen en un nuevo planeta.
Tu objetivo como jugador es simplemente sobrevivir lo más posible en este mundo hostil, considerando el clima, la flora y fauna salvajes, otros humanos en el planeta, enfermedades, y las personalidades específicas de cada persona. Estos agentes tienen un estado de ánimod cambiante afectado por todo su entorno, y puede variar tanto por comer sin una mesa, como tener envidia de que el dormitorio de otro personaje está mejor decorado que el suyo.
Además de la interacción entre estos agentes individuales, este juego utiliza una versión de un Director AI llamado *IA Cuenta Cuentos*.
Al comenzar una partida, el jugador puede escoger entre 3 narradores. Cada uno se encargará de generar eventos narrativos, y el tipo de eventos, su dificultad, su aleatoreidad y su frecuencia dependerán de este narrador. Estos son los siguientes:
**Cassandra Classic** - La experiencia básica de Rimworld, "normal".
**Phoebe Chillax** - Para los jugadores que prefieran una experiencia más relajada, con más espaciado entre eventos, lo cual permite un mayor enfoque en la construcción de bases y la microgestión.
**Randy Random** - Los eventos son lanzados aleatoriamente y sin atender a si son positivos o negativos, pudiendo resultar en una experiencia muy diferente a los otros directores.
Así, Rimworld tiene una interacción interesante entre un Agente Director Narrativo, además de las interacciones entre los múltiples agentes individuales de la colonia.
### Dwarf Fortress y la muerte de los gatos
Finalmente, un ejemplo muy famoso es el de **Dwarf Fortress**, un simulador de mundos con el objetivo de construir y sobrevivir en una colonia de enanos. Es probablemente uno de los juegos más complejos en existencia, simulando cada aspecto de la personalidad de cada individuo (incluyendo los animales), además de interacciones entre cada casilla del mundo, incluyendo simulaciones de flujo (agua, lava u otros líquidos). Además, al comienzo de cada juego se crea el mundo completo, con otras culturas, ciudades, con un sistema de creencias y religiones, política, sistema de nobleza, vampirismo, un sistema de magia único a cada mundo, etc.
[Why Dwarf Fortress Started Killing Cats](https://www.youtube.com/watch?v=6yWf6BHqiWM)
Un ejemplo curioso del caos generado por todos estos sistemas fue que luego de una actualización algunos jugadores se dieron cuenta de que estaban muriendo todos los gatos de sus colonias. **Tarn Adams**, el creador y único programador del juego, pudo rastrear el error: cuando los enanos tomaban cerveza en los bares y hacían bríndis, chocando las copas, algo de alcohol caía al suelo. Los gatos estaban programados para lamer alimentos u otras sustancias desde el suelo, por lo tanto, los gatos ingerían la cerveza que caía al suelo. El problema era que por un error de programación, los gatos estaban consumiendo una porción completa de cerveza, por lo tanto, por su tamaño, morían instatáneamente por envenenamiento por alcohol.
# Fuentes
[(PDF) An Introduction to Multi-Agent Systems](https://www.researchgate.net/publication/226165258_An_Introduction_to_Multi-Agent_Systems)
[Multi-agent Systems and Sandbox Games](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.4115&rep=rep1&type=pdf)
[Three States and a Plan: The AI of FEAR](https://alumni.media.mit.edu/~jorkin/gdc2006_orkin_jeff_fear.pdf)
[Simple complexity: How Breath of the Wild’s simple systems generate infinite fun](https://zeldauniverse.net/features/simple-complexity-how-breath-of-the-wilds-simple-systems-generate-infinite-fun/)