Usos de predicción

Revisando artículos he encontrado que el uso de Machine Learning es muy variado y dentro de un mismo entorno las predicciones que se pueden llevar a cabo varían dependiendo del objetivo que al que se busca llegar.

Algunos ejemplos encontrados son los siguientes:

• Redes Sociales:
  • Existen varios artículos que hablan sobre este tema (la mayoría encontrados en el sitio de la AAAI) donde las predicciones van desde algo que puede parecer hasta cierto punto superficial como el identificar que temas pueden ser un trending topic en twitter hasta el buscar predecir las preferencias electorales y los resultados de una elección.
  • Predicción de que blogs pueden contener un contenido interesante.
  • Predicción de número de reproducciones de un video (en un sitio como Youtube).
• Bolsa de valores
  • Por su parte existen varios modelos que intentan llevar a cabo un comportamiento de la bolsa de valores o de acciones o segmentos específicos de esta.
• Videojuegos
  • Como se ha estado explorando existen varias competiciones y retos que promocionan el crecimiento de esta rama.
• Transportación
  • Existen trabajos que tratan de predecir las mejores rutas en un camino dadas ciertas condiciones de forma que se logre evitar el efecto del tráfico.
• Educación
  • En aplicaciones de educación se encontró el uso de predicción para poder modelar a un estudiante y los conocimientos que tiene en algún determinado tema.
• Seguridad computacional
  • Se han utilizado métodos de predicción para la detección de intrusos, ataques y otro tipo de riegos computacionales.

Existen otros campos en los que se lleva a cabo la predicción pero hasta ahora he podido revisar solo un poco de estos.

Detalles al elegir un RTS como ambiente de prueba

Un RTS (y los videojuegos en general pero específicamente este género por las características que lo comprenden) resulta ser un buen ambiente de prueba para temas relacionados con la inteligencia artificial y específicamente lo relacionado con machine learning y opponent modeling.

Si se busca desarrollar inteligencia artificial para que esta compita contra otra similar se busca crear los modelos más precisos y que las acciones dentro del juego las aprovechen al máximo para lograr vencerlo. Sin embargo, cuando se enfrenta a jugadores humanos el enfoque puede cambiar de cierto modo debido a que depende de lo que se desee proporcionar al jugador y el nivel que este busca para divertirse y adentrarse en el juego.

Para que un jugador encuentre un juego agradable y fascinante este necesita reunir ciertas características como lo son:

• El juego debe contener un tema interesante o al menos no desagradable al jugador
• El género del juego debe ser atractivo al usuario
  • El gameplay debe ser agradable y accesible al usuario
• La dificultad del juego debe ser suficiente para que el jugador encuentre un reto en él pero no al grado de resultar frustrante para el jugador.
  • Es deseable que se incremente gradualmente la dificultad conforme se avanza en el juego para que se adapte a las nuevas habilidades del jugador
• Debe existir suficiente variedad de elementos para que el juego sea variado pero no a un grado excesivo en el que se pierda atención en elementos más imperativos (como la defensa y el ataque) por estar buscando entre menús los elementos que se pueden desarrollar.
• Es deseable que exista un tutorial o algún medio de ayuda para el usuario tanto para aprender a jugar el juego (cuando no se conoce) como cuando se está jugando y se requieren pequeñas descripciones para los elementos en pantalla.
• Debe ser claro lo que ocurre en el ambiente y es bueno cumplir estándares sobre el género del juego para crear cierta familiaridad con el jugador.
• Si el juego esta diseñado para ser de un solo jugador debe contener varios niveles (escenarios) para mantener la atención del jugador.

Para el caso preciso de los RTS es conveniente seguir lo siguiente:

• Deben existir varios tipos de unidades en el juego para diversificar la experiencia del usuario.
• Es bienvenida la existencia de varias razas dentro del juego.
  • Estas razas pueden tener unidades totalmente distintas (como Starcraft) o unidades iguales pero con un árbol de tecnologías que las distingan (Age of Empires II aunque cada raza tiene al menos una unidad extra que los distingue) con el fin de crear cierto balance en el juego y mantenerlo entretenido.
  • El balance entre unidades puede ser un tema delicado y que puede requerir mucho tiempo y pruebas el llevarlo a cabo.
• Debe existir un límite claro de unidades para no sobresaturar la computadora que se encuentre ejecutando el juego entre otros temas a facilitar.
• Existencia de estándares precisos para este juego como el mini mapa, las formaciones de unidades, ayudas, el uso del mouse para seleccionar y controlar, etc.

Por su parte en cuanto a la rama de Machine Learning, Opponent Modeling y Predicción se debe considerar lo siguiente:

• Debe poder obtenerse datos del entorno, mientras mayor sea el número de datos se tiene más posibilidades de encontrar patrones y elegir los datos significativos.
• Deben existir una cantidad considerable de registros de juegos para poder llevar a cabo el análisis, en los papers analizados se mencionan hasta 300 juegos por raza para llevar a cabo un análisis.
• Se debe saber a que se va a enfocar el proceso de machine learning:
  • La recolección eficiente de recursos (posicionamiento de las bases, asignación de unidades para la recolección, priorización de recursos dependiendo de las tropas o edificios que se requieran construir).
  • Estrategias defensivas (creación de tropas, establecimiento de edificios defensivos, desarrollo del árbol de tecnología).
  • Estrategias ofensivas (creación de tropas, desarrollo del árbol de tecnologías, formaciones, estrategias).
  • Un sistema que englobe a los puntos anteriores.
• Por otro lado para la predicción y opponent modeling se puede llevar a cabo como parte complementaria de los puntos anteriores o como una rama que permita conocer de antemano las acciones y estrategias del rival.
  • Se puede intentar predecir la estrategia global del rival, el tipo de unidades que esta creando, los recursos que esta recolectando (en base al tipo de juego que lleva a cabo), el posicionamiento de sus defensas, posicionamiento de sus tropas, posicionamiento de bases extra, la forma en que actúan sus tropas en batalla (ofensiva y defensivamente).

Hay que considerar el ambiente en que se llevaran a cabo las pruebas y experimentos para las técnicas de inteligencia artificial, en este caso se propone el uso de un juego serio (actualmente en desarrollo) sobre alguna otra plataforma establecida lo que me da la siguiente tabla de ventajas y desventajas:

Ventajas	Desventajas
Es un entorno que al ser creado desde cero ofrece un completo control sobre el mismo.	Es necesario aprender un poco sobre la programación del juego para poder manipularlo.
Se puede modificar lo que sea necesario para cubrir las necesidades de la investigación.	Aunque los modelos para el juego pueden ser enviados por externos es posible que en caso de no ser del agrado no sean fáciles de modificar.
Se puede combinar con otras investigaciones.	Para poder ser empleado como ambiente de pruebas primero debe ser completado el juego.
El conocimiento adquirido en el diseño del juego puede ayudar en temas como el modelado del oponente (saber cosas de antemano como los valores de las unidades y contra que son efectivas).	No existen registros (logs) de juegos pasados que puedan ser analizados.
Se tiene un conocimiento profundo sobre las mecánicas del juego así como los objetivos y los elementos que lo comprenden.	Lograr un balance entre unidades no parece ser una tarea trivial.
	No se tiene asegurado que al jugador le sea atractivo el juego y no se conocerá hasta tener alguna versión armada.
	La falta de existencia de un estado del juego (meta game) hace difícil poder definir las estrategias que usan los jugadores.

Al tener en cuenta esas razones creo que es conveniente buscar un poco sobre que se ha hecho sobre predicción en otro tipo de ambientes para poder tomar una decisión sobre el entorno en que se basará mi tesis.

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

Papers Encontrados

Para la búsqueda de papers para esta semana me base en encontrar básicamente dos temas:

• Papers relacionados con aprendizaje en los videojuegos (para entender un poco mejor el funcionamiento de los Serious Games), se encuentran en este archivo http://db.tt/L9DIRVPP
• Papers en general relacionados con Machine Learning, Opponent Modeling y temas relacionados a la Inteligencia Artificial en los juegos (algunos directamente sobre el tipo Real Time Strategy) y se encuentran en este archivo http://db.tt/xCPxTiIR