Simcity

De acuerdo al video visto sobre el engine (GlassBox) de la nueva versión del videojuego Simcity próximo salir a la venta el siguiente año (Febrero 2013), este presenta un ambiente flexible basado en multi-agentes que permiten simular una o varias ciudades con varios elementos que interactúan dentro de ella(s).

Se incluyen cuestiones como el tráfico, la contaminación, los recursos de la ciudad y otros que son presentados de acuerdo a su función y activan su animación dependiendo de la acción que estén realizando o terminando de realizar.

Si bien la construcción de una ciudad y la generación de tráfico podrían servir para nuestro proyecto, se incluyen varios elementos que sobrarían o que afectarían cuestiones no relacionadas con el objetivo de la investigación.

Otro posible problema tiene que ver con la propiedad del engine, si bien lo poco que se ha mostrado del juego tiene información sobre su mantenimiento, al tener un motivo comercial no necesariamente se lanzará al mercado una versión que permita modificarlo.

Finalmente, la fecha de salida del juego puede ser otro problema ya que aunque tiene una fecha determinada, podría ser que fuese retrasado por problemas con en el desarrollo.

Notas sobre juegos urbanos serios

Se encontraron algunos ejemplos de este tipo de juegos, se ve que requieren definir previamente lo siguiente:

• Objetivos del juego
• Género del juego
• Usualmente se emplean juegos con ambientes abiertos que permiten la interacción con sus elementos
• Inmersión del jugador al juego
• Sistema de puntos para mantener el interés
• Promover la exploración

También fueron encontrados varios proyectos que lidian con el tráfico urbano o al menos con una parte del mismo. Estos ejemplos son los siguientes:

• Bus Training Game
• Terra Dynamica
• Serious Games for Traffic Modeling
• FIVIS Project
• IBM Innov8: CityOne
• Traffic Games

Por otra parte se encuentran los juegos dirigidos a la planeación urbana que incluyen otro tipo de factores ya que su fin es distinto. También se encontraron varios ejemplos de este tipo pero no se incluyeron porque distan de nuestro objetivo.

Por último se vieron algunas de las formas en que se pueden representar las redes de tráfico y los enfoques que conllevan (Macroscópico, Microscópico e Híbrido). Dependiendo de la profundidad que se requiera se tendrá que utilizar alguno de estos ya que depende directamente del alcance y tamaño del ambiente desarrollado.

Serious Urban Games. From play in the city to play for the city

Se empieza hablando de la creación y tendencia de los juegos serios además de brindar algunos ejemplos. Desde 2002 que se creo la Serious Game Initiative hasta los recientes proyectos y apoyos que se han brindado como el del juego Citzalia, un juego que simula y muestra el trabajo en el Parlamento Europeo y que recibió un apoyo de 275,000€ de parte de la Unión Europea.

Por otro lado se tiene a los juegos urbanos, son un subconjunto de los juegos penetrantes (Pervasive Games) en los que se presentan al jugador un entorno metropolitano y se le invita a moverse libremente e interactuar con los transeúntes y espectadores. En general se promueve más un ambiente de exploración, experimentación y uso creativo que uno competitivo.

Lo que se busca es combinar los conceptos anteriores para crear un nuevo conjunto que se denomina Serious Urban Games en los que se logre enseñar algo al usuario en un ambiente libre y dinámico como lo es una ciudad.

Se habla de la importancia de dos comportamientos TIAG (This Is A Game) y TINAG (This Is Not A Game) para la inmersión de los jugadores en el ambiente. Si se sigue el paradigma TIAG se entiende que el juego tiene sus reglas, sus características y que hay cosas que se permiten dentro del mismo que no serían posibles en la vida real. Mientras que por su parte TINAG asume que lo presentado dentro del juego permea en la realidad, los comportamientos dentro del mismo son algo que se presentan en la vida cotidiana, es la habilidad que permite a los jugadores pretender que no se encuentran en un juego, es una característica de los juegos penetrantes.

Se busca tener cierta ambigüedad entre TIAG y TINAG de forma que las reglas de ambos mundos (real y el juego) se superpongan y creen un nuevo comportamiento en los jugadores. Se mencionan dos juegos que hacen uso de estas filosofías (Killer y Cruel 2 B Kind) y aunque que no son videojuegos, se puede ver que tienen fines distintos a pesar de tener la misma base.

Otro de los puntos que distingue a los juegos urbanos serios es la narrativa que conllevan. La mayoría de ellos asignan tareas a los participantes que requieren recolectar y volver a contar historias y anécdotas.

Al final se concluye en que esta es una rama que apenas se encuentra surgiendo y falta un poco de tiempo para su apogeo, se retoman las características de como involucrar aspectos de TIAG en la vida real y aspectos de la vida real en TIAG. Los juegos deben ser envolventes y atractivos para los jugadores, se toma en cuenta la narrativa y se expone que se puede crear una historia más grande de pequeños elementos distribuidos encontrados dentro del juego.

Urban Traffic Simulation for Games: A General Approach for Simulation of Urban Actors

Este artículo habla sobre un simulador para enseñar reglas de tráfico urbano a jóvenes mientras utilizan una bicicleta como medio de interacción. El armado total del simulador consiste en una bicicleta con 6 grados de libertad y un ambiente virtual de 3 paredes que la rodean para proveer la vista de lo que ocurre. Esto se muestra en la siguiente figura:

Se menciona el uso de diversos modelos para representar y simular el tráfico urbano pero se expone al enfoque microscópico (Microscopic Traffic Simulation MTS) como uno de los más usados recientemente. El MTS permite hacer una simulación detallada de los elementos que interactúan en el sistema debido a que se basa en un conjunto de agentes individuales que tienen características representativas del elemento representado.

Sin embargo el estar constantemente calculando las acciones e interacciones de cada agente dentro de una ciudad resulta muy costoso computacionalmente por lo que decidieron que solo se calcularía a detalle las características y comportamiento de los elementos que se encuentren a la vista del jugador mientras que al resto se le asigna un comportamiento genérico que permite predecir en que lugar se encuentra en determinado tiempo.

La lógica del juego se encuentra dividida en las siguientes 4 capas:

• Navegación (capa 3): Se encarga de la navegación entre el tráfico, elección de un destino y de calcular una buena ruta. Esta parte requiere conocimiento de la estructura general de la red de tráfico.
• Reglas de tráfico (capa 2): Conglomera las acciones como el derecho de paso, cambio de carriles, forma de estacionarse, etc. A diferencia del anterior, este requiere un conocimiento de las acciones de otros agentes.
• Comportamiento reflexivo (capa 1): Se implementan los comportamientos que no están descritos como reglas de tráfico como el bajar la velocidad cuando se acerca a un semáforo en rojo que este lejano o reaccionar ante el cruce de un peatón.
• Individualización (capa 0): Se encarga de dar variación a los parámetros de cada participante como su velocidad promedio y las rutas que utiliza. Esto con el fin de crear un ambiente más creíble para el usuario.

La red de tráfico es representada como un grafo dirigido en el que cada nodo representa ramas y objetivos y los arcos representan conexiones directas. De esta manera se puede llevar el cálculo de rutas de manera sencilla. Un ejemplo de una red de tráfico se muestra en la siguiente figura:

Es un trabajo preliminar que todavía no arroja conclusiones pero que su implementación ya se encuentra bastante avanzada.

Du, R. (2008). Urban Traffic Coordination Control System Based on Multi-Agent-Game. 2008 International Conference on Intelligent Computation Technology and Automation (ICICTA), 817-821. Ieee. doi:10.1109/ICICTA.2008.245

Strategy Games

Los juegos de tipo estrategia se han usado para el desarrollo de inteligencia artificial pero según lo que he encontrado no sé había dado un ambiente competitivo hasta ahora que esta surgiendo la competición AIIDE de Starcraft.

En trabajos previos se usa el ambiente ORTS (Open Real Time Strategy Game) para las pruebas puesto que es gratuito, el servidor actúa independientemente a los clientes que se conectan, se pueden unir de manera independiente y se da control total sobre los objetos en el campo.

Las principales áreas de investigación sobre este tipo de ambientes son:

• Planeación en tiempo real frente a un ambiente adverso
• Toma de decisiones bajo incertidumbre
• Modelado y aprendizaje del oponente
• Razonamiento espacial y temporal
• Administración de recursos
• Colaboración
• Búsqueda y establecimiento de rutas

El tipo de ambiente es propicio para utilizar sistemas multi-agentes y de hecho su mejora también se toma como parte del objetivo de hacer este tipo de investigaciones.

Otro tipo similar de juego es el de estrategia pero por turnos en el que cada participante tiene cierto tiempo para llevar a cabo sus movimientos. Este ambiente es más fácil de utilizar ya que se tiene más tiempo pero a la vez pierde cierto interés puesto que es más sencillo llevar a cabo el procesamiento de lo que se quiera estudiar debido a las pausas en el juego.

Game Player Strategy Pattern Recognition and How UCT Algorithms Apply Pre-Knowledge of Player’s Strategy to Improve Opponent AI

En este artículo se habla sobre el reconocimiento de patrones de estrategia sobre un juego en el que el jugador usa a un gato que debe esquivar a dos perros para salir del lugar donde se encuentra y así ganar el juego como se ilustra en la siguiente figura.

Para llevar esto a cabo se hizo uso de los siguientes pasos:

• Se recolectaron los atributos usados para el PSPR (Player Strategy Pattern Recognition).
• Se recolectaron muestras de distintas estrategias de jugadores según los atributos definidos.
• Se crearon subconjuntos de acuerdo a los datos obtenidos en la muestra para mejorar el desempeño del sistema.
• Se proceso el ruido.
• Se entreno y se evaluó un clasificador KNN (k-nearest-neighbors) con el conjunto de datos de la muestra.

El resultado de lo anterior arrojo los siguientes datos:

Después se empleo el algoritmo UCT que se encuentra basado en el problema conocido como multi-armed bandit que a su vez se encuentra basado en la analogía de una maquina tragamonedas (estilo casino) pero con varias palancas. El objetivo del apostador se centra en obtener la mayor recompensa de emplear dichas palancas a lo largo de varias iteraciones.

En el caso de este dominio se considero a cada perro como una maquina y cada una de las posibles direcciones a las que se puede mover (norte, sur, este y oeste) como un brazo o palanca. En cada paso se reduce el número de movimientos posibles que puede llevar a cabo el perro podando el árbol de movimientos posibles reduciendo así el espacio de búsqueda.

Al final con el uso de este sistema se pudo logran un porcentaje de 52.17% de victorias sobre un jugador que solo utiliza UCT sin llevar a cabo el reconocimiento previo con KNN para catalogar las distintas estrategias que se pueden llevar a cabo.

He, S., Wang, Y., Xie, F., Meng, J., Chen, H., Luo, S., Liu, Z., et al. (2008). Game Player Strategy Pattern Recognition and How UCT Algorithms Apply Pre-knowledge of Player’s Strategy to Improve Opponent AI. 2008 International Conference on Computational Intelligence for Modelling Control & Automation, 1177-1181. Ieee. doi:10.1109/CIMCA.2008.82

Building a Player Strategy Model by Analyzing Replays of Real-Time Strategy Games

Dentro de este artículo se maneja el uso de un sistema que pueda llevar a cabo una estrategia dentro de un ambiente complejo como lo es un RTS en donde se requieren llevar diversas tareas como lo es recolectar recursos, llevar a cabo construcciones de edificios, creación de unidades, mejoras a las unidades y planeación estratégica de ataques y defensa.

Se menciona el uso del juego Starcraft desarrollado por Blizzard Entertainment en 1998 debido a que gracias a la gran popularidad del juego (dando solo un ejemplo en corea del sur existe una liga profesional en la que los jugadores pueden ganar un equivalente a $100,00 dólares al año) se han creado plataformas y herramientas que permiten el análisis de los juegos pasados así como se puede contar con una gran cantidad de información para su análisis.

Para llevar a cabo el objetivo del documento decidieron hacer uso del razonamiento basado en casos (Case Based Reasoning CBR) tomando los juegos conseguidos como experiencias para formar la base de casos. Se hizo una división de los casos encontrados para que una parte se use para el entrenamiento del sistema y el resto para comprobar que se lleven a cabo las predicciones correctamente.

Los resultados obtenidos por el entrenamiento se observan en la siguiente tabla:

Y se menciona que al inicio del juego los jugadores parecen seguir una tendencia hacia las mismas estrategias mientras que en la mitad del desarrollo del juego no existe una estrategia dominante aunque hacia el final de nuevo se nota una tendencia claramente marcada. Un ejemplo de esto se muestra en la siguiente figura:

Siendo que este juego cuenta con tres razas distintas se tuvo que llevar a cabo un gran numero de casos para el entrenamiento (300 por raza) y se uso el 90% de estos para entrenar y el porcentaje restante para verificar la precisión del sistema mostrado en la siguiente tabla:

Sin embargo, las pruebas y comparaciones fueron hechas sobre un solo jugador por lo que en las conclusiones resaltan que hasta ahora el sistema solo fue probado para predecir estrategias individuales y además falta probar que el sistema pueda utilizar esta información para poder competir contra oponentes humanos.

Hsieh, J.-L., & Sun, C.-T. (2008). Building a player strategy model by analyzing replays of real-time strategy games. 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), 3106-3111. Ieee. doi:10.1109/IJCNN.2008.4634237

Evolving Explicit Opponent Models in Game Playing

En este trabajo se habla de la creación de un modelado del oponente explícito que permita no solo almacenar y analizar los comportamientos de los jugadores previos para próximos encuentros sino tenerlos a la mano para poder enfrentarse a oponentes desconocidos.

Se usa el juego Guess It como campo de prueba para el modelo propuesto. El juego consiste en tener dos jugadores con el mismo número de cartas (6 cartas por jugador en el caso del artículo) y tener una carta central que ninguno de los dos conoce. El objetivo del juego se centra en adivinar la carta central por lo que en cada turno se puede preguntar al oponente por una carta o tratar de adivinar la carta central. Si se pregunta por una carta que el oponente tiene, este la revela y la pierde. Si se pregunta por una carta que tu tienes (bluff) la debes mostrar y perder en el siguiente turno. Si se trata de adivinar la carta del centro y aciertas entonces ganas el juego, por lo contrario si se intenta y te equivocas pierdes el juego.

Se tomaron en cuenta cuatro tipos de jugadores cardinales (extremos):

• Always Ask: Siempre pregunta por una carta desconocida, nunca adivina y no hace bluff.
• Always Bluff: Siempre hace bluff con su propia carta y nunca adivina.
• Call Then Ask: Cree como carta central cualquier bluff potencial, de otra forma siempre pregunta por una carta desconocida y nunca hace bluff.
• Call Then Bluff: Cree como carta central cualquier bluff potencial, de otra forma siempre hace bluff con su carta y nunca adivina.

Después se empleo un enfoque mixto que puede asignar a un jugador la combinación del tipo de jugadores cardinales para tener una mejor aproximación. Para adaptarse a este tipo de jugadores se llevan a cabo los siguientes pasos:

• Identificar un conjunto de jugadores cardinales suficientes para describir a los oponentes.
• Entrenar una red neuronal o algún otro tipo de plataforma para identificar el tipo de mezcla de jugadores cardinales basado en el estilo de juego del oponente.
• Entrenar a un jugador que toma como entradas el estado del juego y la mezcla dados por la red en el segundo paso.

Esto se ilustra en la siguiente figura:

Al final de las pruebas se muestra que el modelado del oponente empleando una mezcla de las estrategias conocidas de los jugadores cardinales ayuda a identificar y derrotar a jugadores que no se conocían con anterioridad y esto es especialmente útil y funcional en ambientes donde los jugadores no tienen una visión global del estado del juego.

Lockett, A. J., Chen, C. L., & Miikkulainen, R. (2007). Evolving explicit opponent models in game playing. Proceedings of the 9th annual conference on Genetic and evolutionary computation - GECCO ’07 (p. 2106). New York, New York, USA: ACM Press. doi:10.1145/1276958.1277367

Predicting Opponent Resource Allocations When Qualitative and Contextual Information is Not Available

El concepto de este artículo se sitúa en un escenario del juego Counter Strike en donde un grupo de terroristas tienen a cierto número de rehenes y un escuadrón anti-terrorista intenta liberarlos. Todo esto ocurre en un cuarto en el que existen 3 entradas (puerta principal, puerta trasera y ventana) y el objetivo general del juego es distribuir (ya sea los terroristas o el equipo anti-terrorista) a sus elementos en las entradas de forma que igualen o superen al rival. El juego termina cuando todos los rehenes son liberados, los miembros de algún equipo son eliminados o cuando se acaba el tiempo.

Las condiciones para la predicción del juego son similares a las del juego piedra, papel o tijeras en donde ninguna opción predomina sobre las otras ya que no se cuenta con información aparente que permita predecir el movimiento rival, de hecho se menciona que el mismo equilibrio de Nash para este juego simplemente consta en elegir al azar una opción.

Sin embargo, los jugadores humanos tienden a llevar una tendencia de manera subconsciente cuando se supone que deben llevar a cabo elecciones al azar. Debido a esto se decidió emplear el algoritmo Entropy Learning in Pruned Hypothesis Space (ELPH) que fue diseñado para llevar a cabo predicciones en base a un aprendizaje rápido sobre políticas no estacionarias como lo puede ser comportamiento que cambia frecuente y significativamente.

El algoritmo ELPH ha sido probado en el juego de piedra, papel o tijeras manteniendo un porcentaje de victorias del 65% (en juegos que no terminan en empate) sobre oponentes humanos.

En general el algoritmo crea una secuencia de acciones basado en los casos que van ocurriendo y los almacena como posibles patrones. Una vez guardados los patrones deduce a partir de la ocurrencia de ellos el siguiente movimiento del oponente.

Los resultados de las pruebas contra jugadores humanos se logro obtener en promedio 41% de los puntos posibles (con un rango desde 24% hasta 58%) y solo logro derrotar a dos jugadores mientras que perdió contra 10 (aunque se menciona que no fue por un amplio margen).

Más allá de los resultados numéricos, se hicieron encuestas a los jugadores en las que se vio reflejado que se vieron sorprendidos debido a que parecía que la inteligencia del juego aumentaba según se acercaban las rondas finales aunque esto no se encuentra apoyado por los resultados numéricos.

En general los jugadores se mostraron contentos con el nivel de la inteligencia del juego y también se encontraron sorprendidos en los casos en que sus estrategias fueron adivinadas.

Wetzel, B., Jensen, S., & Gini, M. (2009). Predicting opponent resource allocations when qualitative and contextual information is not available. Proceedings of the 4th International Conference on Foundations of Digital Games - FDG ’09 (p. 333). New York, New York, USA: ACM Press. doi:10.1145/1536513.1536572

Dynamic Game Difficulty Balancing for Backgammon

Una base fundamental de los juegos se encuentra en el nivel de dificultad que estos proporcionan a los jugadores. Esto puede afectar el grado en que un usuario disfruta y se inmersa en el juego por lo que es deseable encontrar un nivel apropiado que se adapte según el jugador lo requiera. La dificultad de los juegos comúnmente se deja a elección del jugador y se basa en un número fijo de opciones, sin embargo, si las opciones son muchas puede tomarle algún tiempo al jugador encontrar su nivel adecuado y si son muy pocas es posible que no encaje en ninguna sino que requiera un nivel intermedio inexistente.

La solución presentada emplea las siguientes dos funciones:

• Next State Ranking Function
  • Esta función brinda un clasificación de los estados basado en su calidad y a su vez la calidad se encuentra definida como el que tan posible es ganar el juego si se elige dicho estado.
• Game Status Function
  • Esa función brinda un marcador numérico que indica que jugador se encuentra ganando la partida y por cuanto lo esta haciendo.

El juego ajusta su siguiente movimiento basado en los siguientes pasos:

• Se ajusta el nivel de habilidad estimado del jugador basado en el estado actual del juego.
• Se genera una lista que contiene el conjunto de todos los posibles estados dado el estado actual del juego.
• Se hace una clasificación de los estados basados en la función definida.
• Se elige un estado para llevarlo a cabo basado en el nivel del oponente.

Dado lo anterior se logro que en los resultados obtenidos a lo largo de los experimentos llevados a cabo se observara que en el desarrollo del juego ambos jugadores tengan una gran posibilidad de ganar por lo que la adaptación al nivel del rival funciona como se había planeado.

Gomez-Hicks, G., & Kauchak, D. (2011). Dynamic game difficulty balancing for backgammon. Proceedings of the 49th Annual Southeast Regional Conference on - ACM-SE ’11 (p. 295). New York, New York, USA: ACM Press. doi:10.1145/2016039.2016115

Intelligent Anti-Grouping in Real-Time Strategy Games

Según se menciona los juegos de estrategia se vuelven divertidos e interesantes debido al balance que debe existir. Una forma de llevarlo a cabo es dar acceso a todos los jugadores el mismo tipo de recursos y de unidades.

La calidad y confianza de una estrategia presente en este tipo de juegos depende mucho de la estrategia del oponente al que estas enfrentando. Si la estrategia del rival cambia entonces la estrategia óptima que deberás usar también cambia y es debido a esto que no existe un óptimo global y por ende es infructuoso tratar de optimizar de forma global una sola estrategia.

Debido a lo anterior, un buen diseño de inteligencia artificial debe poder adaptarse a la estrategia del oponente y mejorar así su rendimiento. Una parte fundamental para llevarlo a cabo en este tipo de ambientes es el uso de grupos. El uso de grupos tiene 3 fines básicos como se describen a continuación:

• Tactical Attack
  • Mientras se ataca es deseable usar unidades que contrarresten las tropas usadas por el enemigo para maximizar el ataque y minimizar pérdidas.
• Tactical defense
  • Si se es atacado es deseable hacer que las unidades primero ataquen a los ofensores a los que tengan mayor probabilidad de derrotar con el fin de maximizar las pérdidas del enemigo.
• Strategic Build
  • Es importante que se tome en cuenta el tipo de unidades preferido por el adversario para llevar a cabo las construcciones, el desarrollo del árbol de tecnología y la reproducción de tropas.

Se reconoce que el intentar predecir los movimientos del rival puede tomar varios segundos y dentro de un ambiente dinámico como los RTS no se pueden desperdiciar ese tiempo para tomar las decisiones por lo que se utiliza aprendizaje fuera de línea y lo que sucede dentro del juego se reduce a una búsqueda.

El método usado para llevar a cabo el aprendizaje conlleva un tiempo muy corto y no es necesario tener una gran cantidad de casos sino una función objetivo cuidadosamente seleccionada. Las pruebas se hicieron sobre el caso de Tactical Defense.

Se emplea como técnica los mapas auto-organizados (SOM) debido a que a diferencia de las redes neuronales no se centran en un proceso de caja negra y permiten la visualización y entendimiento de las mismas. El entorno empleado para las pruebas es Glest, un RTS open source.

Un SOM mapea datos con muchas dimensiones en espacios de pocas dimensiones (usualmente 2 para efectos de visualización y reducción de complejidad). Los mapas mantienen una relación topológica y crean un mapa de regiones de similitud agrupando los datos similares.

Normalmente una SOM se emplea en conjunto a una distancia euclidiana pero en este trabajo se empleo una función de distancia distinta. En lugar de llevar a cabo una simulación tradicional que requiere de varias iteraciones para analizar lo que puede suceder al final de un encuentro entre unidades, se empleó una función que aprovecha el hecho de conocer los valores de de las unidades y de esa forma se calculó una fuerza relativa que permite llevar a cabo la función.

Se llevaron a cabo los siguientes 3 experimentos para probar el sistema:

• Proof-of-principle. ¿El sistema genera los resultados correctos en un escenario simplificado?
  • Se emplearon facciones balanceadas y solo 3 tipos de unidades para revisar el comportamiento del sistema. Los resultados arrojados muestran que el sistema trabaja bien al menos en este sistema y mientras mayor sea el número de iteraciones usado para el SOM mejores resultados se obtienen. Sin embargo, el número de patrones empleados para el aprendizaje parece no influir en el desempeño (o puede que su número mínimo sea suficiente que es 100 en este caso). También el sistema parece trabajar mejor con patrones homogéneos que con mixtos.
• ¿La función objetivo sustituta remplaza propiamente las simulaciones dentro del juego?
  • Los resultados de la función tuvieron variaciones respecto al entrenamiento clásico a base de simulaciones y esto se atribuye al hecho de los valores aleatorios que se emplean para calcular el daño a las unidades dentro del juego. Sin embargo, se encuentra como suficiente y hasta incluso deseable el uso de este tipo de funciones debido a su naturaleza determinística.
• ¿Los SOM tienen un buen desempeño en un ambiente real más complicado?
  • El comportamiento del sistema vario dependiendo del nivel de tecnología de las unidades empleadas para llevar a cabo la experimentación. Mientras que en el primer nivel se obtuvo un muy buen desempeño, en el segundo nivel este bajo debido al balance existente entre las unidades en dicho nivel. Aun tomando en cuenta lo anterior el desempeño fue bueno en general.

Beume, N., Hein, T., Naujoks, B., Piatkowski, N., Preuss, M., & Wessing, S. (2008). Intelligent anti-grouping in real-time strategy games. 2008 IEEE Symposium On Computational Intelligence and Games, 63-70. Ieee. doi:10.1109/CIG.2008.5035622

Dynamic Formations in Real-Time Strategy Games

Un elemento particular de los juegos se basa en la capacidad de la inteligencia artificial para adaptarse a lo que sucede en el entorno y como se adapta y afronta dicha situación. En algunos tipos de juego (como lo son RTS en este caso) se puede ver parte de esta adaptabilidad en el tipo de formaciones que se emplean.

Las formaciones de las unidades en el campo de batalla dentro de los juegos pueden ser basadas en forma estática haciendo que cada unidad tenga una posición fija dentro de la formación por lo que no se tiene mucha flexibilidad y en ocasiones hace que las formaciones sean inservibles en casos no contemplados con anterioridad. Este tipo de formaciones suele estar basado en formaciones usadas en batallas reales. Por otra parte existen formaciones dinámicas que se basan en la interacción de las unidades que participan en ella pero son difíciles de controlar y de predecir su comportamiento.

Se probó en Open Real Time Strategy (ORTS) como ambiente de juego ya que es un ambiente desarrollado con el propósito para la investigación sobre inteligencia artificial además de existir una competencia desde 2006 para probar las nuevas tecnologías desarrolladas.

Para obtener lo que ellos definen como una formación dinámica se deben cumplir las siguientes condiciones:

• La formación debe tener una figura dinámica (no previamente fijada).
  • La formación se basa sobre un líder y las unidades se acomodan a cierta distancia del mismo.
• Las unidades dentro de la formación deben posicionarse de forma correcta.
  • Si una unidad es destruida debe ser remplazada por alguno de sus vecinos y se recorren de forma que se pueda mantener cierta consistencia.
• Las unidades deben ser capaces de moverse como grupo.
  • Las unidades se mueven respecto a los movimientos del líder, se sigue su dirección y se varía la velocidad de cada unidad respecto a la del líder para mantener la formación.
• Las unidades dentro de la formación deben elegir de forma inteligente que unidades atacar.
  • El esquema de ataque básico se divide en cuatro opciones y se ilustra en la siguiente figura:

• Las unidades cooperan en sus comportamientos de batalla.
  • Los comportamientos de batalla se dividen en los siguientes:
    • Overrun: Se ataca continuamente al enemigo hasta desaparecerlo.
    • Hold: Se ataca al enemigo solo cuando se tiene en rango, no se persigue si sale del mismo.
    • Retreat: Estrategia hit and run (corre y pega), se ataca al enemigo y en el cooldown time (tiempo que pasa mientras una unidad puede volver a atacar) se retrocede.
    • Bounce: Similar al retreat pero solo se retrocede la mitad del cooldown time y después se anticipa a los movimientos del oponente adelantándose en lugar de retroceder.
    • Border: Las unidades se aseguran de permanecer fuera de rango de ataque del oponente mientras se encuentran en su cooldown time.

También se toma en cuenta el comportamiento del oponente (opponent modeling) con parámetros básicos que son:

• Cantidad de formaciones del oponente
• Distribución de sus unidades
• Distancia entre sus unidades

Se calcula la posibilidad existente sobre lo que ocurre actualmente en el juego contra lo que se tiene guardado en experiencias previas para definir como se clasificará al rival.

La mayoría de los resultados fue favorable siendo que jugaron contra equipos previamente analizados y otros juegos generados contra equipos totalmente nuevos. Solo en un caso no se logro que la formación fuera determinante y lo atribuyeron a que era necesario utilizar como complemento técnicas de inteligencia artificial a un menor nivel para cubrir ciertos detalles.

van der Heijden, M., Bakkes, S., & Spronck, P. (2008). Dynamic formations in real-time strategy games. 2008 IEEE Symposium On Computational Intelligence and Games, 47-54. Ieee. doi:10.1109/CIG.2008.5035620

Case Learning and Indexing in Real Time Strategy Games

La manera en que se define la inteligencia artificial tradicionalmente en los juegos RTS parte de lo siguiente:

• Modo Dios:
  • Se conoce absolutamente todo en el juego desde las posiciones de cada unidad hasta las acciones actuales del jugador por lo que el problema cambia a ser de cierta forma un juego de información perfecta.
• Maquina de estados:
  • En este tipo las acciones que se van a realizar se encuentran codificadas en una sucesión de estados que dictan la conducta a seguir. El problema que conlleva el crear esa máquina de estados es que requiere que se anticipen el mayor número posible de opciones (deseablemente todas las opciones aunque esto puede ser imposible dependiendo del entorno) para que se sepa reaccionar en el momento. Este proceso requiere especial atención de los diseñadores y la máquina de estados puede cambiar o requerir ajustes dependiendo del entorno (mapa) en el que se esté jugando.
• Técnicas de machine learning:
  • Se han usado técnicas de machine learning en otras investigaciones mencionadas en el artículo para introducir comportamiento humano analizando juegos llevados a cabo entre jugadores profesionales para construir la base de casos.

Se eligió el juego de Tower Defense como escenario, en este tipo de juego existe un jugador ofensivo y uno defensivo. El deber del jugador ofensivo es avanzar sobre el mapa hacia la base del jugador defensivo y si logra cruzar este ganará. Por su parte el jugador defensivo coloca barreras, torres de defensa y otro tipo de obstáculos para impedir el avance del jugador ofensivo. El resultado de las rondas se define al cabo de cierto límite de tiempo.

El algoritmo básico del sistema propuesto se basa en que se utilizan las condiciones del terreno dadas para la colocación de las torres (o cañones) y se codifican como un cromosoma para ser usado como entrada para el algoritmo genético (GA). El resultado del uso del GA que dará la mejor distribución de las torres será la entrada para una red neuronal artificial (ANN) para su entrenamiento. Posteriormente se puede conseguir una predicción de las mejores zonas para colocar las torres en un terreno nuevo mediante el uso de la ANN. El algoritmo básico se muestra en la siguiente figura.

El uso de la red neuronal obedece a la necesidad de estar en un ambiente dinámico ya que al indexar los casos en ella permiten tener un rápido acceso y soporte a entradas incompletas o con ruido.

Dentro de las técnicas probadas dentro de la red neuronal se utilizaron Backpropagation (BP) y Radial Basis Network (RBF). Al final se empleo BP debido a que toma menor tiempo de consulta y que proporciona un desempeño similar a RBF.

Wang, H., Ng, P. H. F., Niu, B., & Shiu, S. C. K. (2009). Case Learning and Indexing in Real Time Strategy Games. 2009 Fifth International Conference on Natural Computation, 100-104. IEEE. doi:10.1109/ICNC.2009.729