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

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