Segunda Versión de Hipótesis

Aunque existen modelos del oponente dentro de la competencia de simulación RoboCup 2D, estos abarcan acciones sencillas e independientes que no conforman una estrategia como tal. Se pretende crear una extracción de patrones de juego que logre englobar las jugadas más comunes en los equipos que existen actualmente y generar una base de conocimiento (libro de jugadas) con las estrategias que se adapten a la estrategia del rival de forma que al momento del juego se puedan emplear para mejorar los resultados en la competencia.

Antecedentes

Los antecedentes directos a esta investigación están situados en las investigaciones aplicadas al evento RoboCup en el cual se organizan simulaciones de partidos de futbol para probar avances en los sistemas multi-agentes. Al ser un evento a nivel mundial y con rondas clasificatorias (como si fuera un verdadero torneo de futbol) se logra poner a prueba cada nueva teoría o implementación que se realiza en las diversas instituciones de educación superior alrededor del mundo.

Independientemente del uso de robots físicos o simulaciones dentro de las pruebas de RoboCup, todas las competencias se encuentran basadas en sistemas multi-agentes donde cada agente representa a un jugador, aunque en este caso las pruebas e investigación se encuentran enfocadas a la competencia de simulación en 2D.

Dentro de los avances encontrados, existe el uso del modelado del oponente como forma de evaluación en el modo de competencia de Coach debido a que se basa específicamente en los resultados que arroja dicho modelado. Sin embargo, en el caso particular de la competencia entre dos equipos sin el uso del agente Coach se ha hecho un modelado simplista y genérico en la mayoría de los casos.

Es importante recalcar que lo anterior ha sucedido debido al poco tiempo de interacción existente dentro de cada partido ya que las interacciones entre ambos equipos son limitadas e insuficientes para lograr crear un modelo realista y confiable de la forma de jugar del rival (Stone, Riley, y Veloso, 2000). Debido a esto el modelado del oponente se ha basado en dos aproximaciones, la primera es contemplar un modelo predefinido de comportamientos individuales posibles de los rivales excluyendo así las estrategias de equipo y por otro lado se crean estrategias que incluyan posiciones posibles de los rivales y se procesan de distintas formas teniendo como ejemplo un CBR (Case Based Reasoning).

De lo anterior se puede observar que existen limitantes que conciernen a la misma forma en que se realiza el modelado del rival. Aunque existe y se busca el ideal de crear una representación de cada oponente a un nivel apegado a la realidad, aún no se ha logrado llevar a cabo en periodos cortos de interacción aun con dominios acotados de forma que las acciones conformen un conjunto mínimo y por ende sea de cierta forma sencilla su predicción (Del Giudice y Gmytrasiewicz, 2007).

Al considerar estos factores, se encuentra como deseable un modelo del oponente apegado a situaciones que asemejen con cierta precisión a la realidad del juego actual y que puedan ayudar a que se comprenda no solo las acciones individuales del contrario sino un nivel superior en cuanto a entendimiento siendo en el caso de RoboCup, la estrategia que emplea el equipo. Siendo esta una posible generalización de un conjunto de estrategias con características similares pero que logren englobar algunas de las formas en que se desempeña el equipo de forma que se tenga información sobre la reacción del mismo y deseablemente la manera en que puede ser contrarrestada o respondida.

Reinforcement Learning of Player Agents in RoboCup Soccer Simulation

En esta lectura se establece el uso del aprendizaje por refuerzo como una posible técnica para la mejora del comportamiento de los agentes dentro de los sistemas multi-agentes debido a su capacidad de, en un determinado lapso de tiempo, desarrollar de cierta manera habilidades que permiten a los actores de los sistemas desempeñarse.

De esta forma utilizan este tipo de aprendizaje en el ambiente de simulación 2D de RoboCup para que los jugadores aprendan y en dado caso mejoren su habilidad de interceptar pases del rival. Se emplea el uso de recompensas en el que el acierto (en este caso la intercepción del balón) otorga una recompensa (un valor de 1) y en otro caso se da el valor mínimo (0).

De lo anterior el agente construye una serie de estados con cierta probabilidad de intercepción dependiendo del movimiento que realice el jugador. Los resultados mostraron que se puede apreciar de forma clara que la habilidad de intercepción mejoró respecto a la que ellos habían codificado manualmente a partir de una hora de constante entrenamiento con el método expuesto.

Sarje, A., Chawre, A., & Nair, S. (2004). Reinforcement Learning of Player Agents in RoboCup Soccer Simulation. Fourth International Conference on Hybrid Intelligent Systems (págs. 480-481). Kitakyushu, Japan: IEEE.

Heuristic Reinforcement Learning applied to RoboCup Simulation Agents

Se menciona el creciente uso de técnicas de aprendizaje por refuerzo para diversas áreas y en particular el uso del Q-Learning debido al interés que genera por una característica intrínseca del mismo que consiste en que en algún momento se convergerá al estado óptimo de aprendizaje.

Sin embargo, como la mayoría de algoritmos, este requiere cierto número de interacciones para lograr llevar a cabo el aprendizaje las cuales sobrepasan el número natural de encuentros dentro de un juego de un ambiente como lo es el de RoboCup. Por ello, en este artículo se propone el uso de una evolución de Q-Learning llamado HAQL (Heuristic Accelerated Q-Learning).

Este algoritmo en principio comparte una cantidad significante de características con el Q-Learning original pero con una mejora al momento de llevar a cabo el aprendizaje ya que este es guiado por una heurística que influye en las decisiones que toma el agente durante el mismo periodo de aprendizaje de modo que se define una política de heurísticas que permite que el aprendizaje se lleve a cabo en un menor tiempo.

Para las pruebas realizadas en un ambiente que incluye a un equipo defendiendo su portería y otro atacándolo en el que se empleo el aprendizaje para la parte defensora, se logra ver que el uso de HAQL permite que los resultados positivos lleguen en una menor cantidad de interacciones que empleando Q-Learning. Sin embargo, mientras se aumenta el número de interacciones, los resultados se vuelven simulares debido a que el aprendizaje en Q-Learning converge.

Celiberto, L., Ribeiro, C., Reali Costa, A. H., & Bianchi, R. (2008). Heuristic Reinforcement Learning applied to RoboCup Simulation Agents. En RoboCup 2007: Robot Soccer World Cup XI (págs. 220-227). Berlin: Springer Berlin / Heidelberg.

Opponent Modeling in Scrabble

En este artículo se toma como base al juego del Scrabble para mostrar lo útil que puede llegar a ser tener un modelo del oponente para poder hacer una elección de jugadas. El juego en sí comprende un medio parcialmente observable debido a que lo único que cada jugador puede observar son sus fichas y las acomodadas en el tablero, teniendo como incógnita las que se encuentran del lado del oponente y las restantes halladas en un saco.

Como indica el autor lo natural parece ser emplear un POMDP (Partially Observable Markov Decision Process) pero este se convierte en un problema intratable al no contener cantidades reducidas de estados como lo es el juego del Scrabble. Debido a lo anterior, se asume el uso de otra técnica que si bien sacrifica precisión en la solución del problema, implica también una mayor simplicidad y más relevante, una manera de modelar en un tiempo razonable.

Para efectos del experimento se asume que el juego será llevado a cabo entre dos computadoras (por ende entre dos jugadores), no se utilizan estrategias como lo es el Bluff, se emplean solo palabras que son legales en este tipo de juego y el paso a un ambiente con información conocida no se toma en cuenta (esto ocurre al final del juego cuando no quedan fichas en la bolsa o saco de reserva).

Se utiliza el teorema de Bayes para llevar a cabo las funciones de probabilidad sobre las posibles fichas con las que cuenta el oponente basado en las tiradas que ha realizado. Es decir, si ha formado una palabra y al tener en cuenta que el oponente no es humano, se considera que su salida o tiro se basa únicamente en que se realizó intentando obtener el mayor puntaje en dicha jugada. Teniendo lo anterior en cuenta, se descartan las letras que pudieron haber formado una palabra con mayor puntaje armando así una posible combinación de las letras que se acaban de poner en juego y las que posiblemente aun tengan en su conjunto el rival.

Basado en las posibles combinaciones de fichas que puede tener en el momento actual el rival, se procede a hacer las jugadas que el propio jugador crea convenientes y en los resultados en la experimentación realizada, se encontró que el promedio tanto de puntos como de juegos ganados aumento respecto a emplear otras estrategias tradicionales.

Richards, M., & Amir, E. (2007). Opponent Modeling in Scrabble. Twentieth International Joint Conference on Artificial Intelligence (págs. 1482-1487). Hyderabad, India: IJCAI.

Sitio Reinforcement Learning

Encontré un sitio en el cual se encuentran varios papers sobre aprendizaje por refuerzo que pueden ser útiles:

http://www.fei.edu.br/~rbianchi/publications-full.html

Improving Offensive Performance Through Opponent Modeling

Este artículo habla sobre la utilidad de emplear el modelado del oponente no solo a un nivel individual en el que se intente predecir los movimientos básicos de los rivales sino de reconocer y contrarrestar la estrategia del equipo contrario. Esto es aplicado al ambiente de futbol americano.

Se toman como antecedentes varias competiciones y entre ellas a RoboCup pero se menciona que el modelado del oponente se realiza tradicionalmente en la modalidad de Coach en la cual se hace aprendizaje offline y su utilidad radica más entre partido y partido que dentro de un solo juego.

Se divide al modelado del oponente en tres clasificaciones:

• Seguimiento Online – Aquí se desglosan los movimientos de más bajo nivel intentando predecir acciones individuales como el avance de un jugador, pases, etc.
• Reconocimiento de Estrategia Online – Este es un nivel más elevado del anterior ya que se intenta identificar las acciones del equipo rival como una estrategia enfocada a un objetivo.
• Revisión Offline – Esta es la fase de entrenamiento y aprendizaje que se realiza fuera del tiempo de juego.

El objetivo fundamental del desarrollo expresado en el artículo es aprovechar la parte del reconocimiento de estrategias para lo cual emplean un clasificador que les permite discriminar entre las opciones contenidas en su libro de jugadas y que resulte ser la mejor opción para llevar a cabo el ataque.

Se emplea una SVM (Support Vector Machine) de tipo multi-clase que a su vez contiene una colección binaria de 26 SVM binarias. Se elige la SVM multi-clase dependiendo del estado actual de los jugadores y el tiempo de la jugada. Con estos datos se procede a adaptar el equipo y que este adopte la formación que mayor ganancia signifique en cuanto a yardas obtenidas.

Los resultados demostraron una mayor efectividad en cuanto al ataque obteniendo una mejoría del 29% respecto a las yardas obtenidas comparando este tipo de estrategia contra métodos tradicionales que intentan maximizar el mismo parámetro.

Laviers, K., Sukthankar, G., Molineaux, M., & W. Aha, D. (2009). Improving Offensive Performance Through Opponent Modeling. Proceedings of the Fifth Artificial Intelligence for Interactive Digital Entertainment Conference (págs. 58-63). Stanford, California: AAAI.

Towards Strategic Kriegspiel Play with Opponent Modeling

Este es un artículo en el que muestran el uso del modelado del oponente en una situación en que no se conoce el estado actual del oponente como sucede en algunos tipos de problemas. Para lo anterior emplearon Kriegspiel que es una versión modificada del ajedrez tradicional en la cual cada jugador no conoce la ubicación de las piezas del contrario y los movimientos son evaluados por un árbitro que indica si estos son legales o no y que consecuencias producen.

Debido al costo computacional de llevar a cabo el modelado se decidió reducir tanto el tamaño del tablero (a tan solo una dimensión de cuatro por cuatro casillas) y el número de piezas (se empleo solo el rey y la reina). Aun con esta reducción se obtiene alrededor de 74 mil posibles combinaciones de estados a lo largo del juego.

Para el desarrollo del juego se emplean I-POMDP (Interactive Partially Observable Markov Decision Processes) para cada agente, lo cual está formalmente definido por:

I-POMDP = {IS, A, T, Ω, O, R}

• IS – Es el estado interactivo el cual está definido por el cruce entre los estados físicos (configuraciones del tablero S) y los posibles modelos del oponente.
• A – Es el cruce entre las acciones posibles del agente propio y el oponente.
• T: S x A x S --> {0,1} – Es la función de transición que representa la influencia de los agentes con el ambiente.
• Ω - Es el conjunto que contiene las respuestas posibles del referee.
• O: S x A x Ω -->{0,1} – Es la función de observación del referee que dicta que respuesta debe brindar.
• R: S x A --> R – Es la función de recompensa asociada a uno de los estados finales del juego (victoria, empate o derrota).

Se emplea una red bayesiana para elegir la jugada que realizara el agente teniendo en cuenta las probabilidades y los pesos de elegir una opción respecto a que el oponente pueda elegir otra de forma que se cuantifica cada posibilidad.

Del Giudice, A., & Gmytrasiewicz, P. (2007). Towards Strategic Kriegspiel Play with Opponent Modeling. AAAI Spring Symposia. Stanford, California: AAAI.

Opponent Modeling by Analyzing Play

Este artículo presenta si bien una introducción al tema del modelado del oponente, también considera algunas ideas prácticas que se puede obviar en ciertos momentos pero que son fundamentales para saber si lo que se realiza se encuentra enfocado correctamente.

Las ideas básicas detrás del modelado del oponente se basan en lo que cualquier ser humano realiza cuando se enfrenta a algún contrincante en un juego por simple que este sea. Por ejemplo en el póquer, aunque no se conozca al rival conforme va avanzando el juego vas entendiendo su forma de apostar durante el juego y como contestar a ello.

También se menciona que se debe decidir qué características del oponente son las que se tomarán en cuenta para llevar a cabo el modelo ya que puede que existan algunas que no proporcionen información que permita llevar a cabo el entendimiento de su comportamiento y que sean simplemente insignificantes, por el contrario si se omite algún elemento relevante entonces posiblemente el modelo que se lleve a cabo sobre el contrario contenga información incompleta y menos útil que si se hubiese tomado la variable omitida.

Pasando estas bases se mencionan algunas formas de modelado entre las que se encuentran el uso del modelo de un oponente promedio, el modelado particular de cada oponente y otro que llamo en particular mi atención que consiste en después de haber realizado el modelado promedio de los rivales, complementarlo con acciones específicas que dependan de cada adversario con el que se encuentre compitiendo.

Para probar lo anterior hacen uso de un clasificador (C4.5) con el sistema TILDE basados en el juego Go. Realizaron pruebas básicas y midiendo los resultados dependiendo de cuantas jugadas fueron analizadas mostrando una mejoría cuando se alimento al sistema con más información.

Jan, R., Jacobs, N., & Blockeel, H. (2002). Opponent Modeling By Analysing Play. Proceedings of Workshop on agents in computer games. Edmonton, Canada: AAAI.

Aprendizaje por Refuerzo

En el aprendizaje por refuerzo se busca que una entidad aprenda cuál es la mejor decisión que puede tomar y llevarla a cabo mediante un sistema de recompensa. Debido a que no se indica inicialmente cuál es la mejor opción que se puede tomar, se deben llevar a cabo varias iteraciones de la tarea sobre la que se basa el aprendizaje para poder generar un conocimiento correcto.

Para el modelado de este tipo de aprendizaje se debe tomar en cuenta los estados y las acciones posibles. En los estados se determinan las posibles situaciones que se pueden presentar en el sistema, mientras que en las acciones se describen los actos que el sistema puede llevar a cabo en cada uno de los estados. El fin de lo anterior es encontrar la mejor acción posible para cada una de los estados del sistema y que este reaccione de la forma más conveniente a lo que se le puede presentar.

Una característica de este estilo de aprendizaje es que se considera al problema completo como dirigido a una meta y que se desenvuelve en un entorno incierto (posiblemente cambiante). Además se le considera como un aprendizaje basado en la interacción. Debido a esto también se le considera como aprendizaje no supervisado ya que es impráctico intentar obtener muestras representativas y útiles de las situaciones que se pueden presentar en los ambientes estudiados por este tipo de aprendizaje.

http://webdocs.cs.ualberta.ca/~sutton/book/ebook/the-book.html

Logs de Equipos

Encontré algunos logs de las competencias de RoboCup en línea por lo que es posible obtenerlos, falta analizarlos a detalle pero en general parecen incluir la comunicación con el servidor, entre los agentes y las acciones de los mismos.

Algunos sitios que encontré son:

http://202.141.161.27/results_09/
http://202.141.161.27/results/
http://www.ni.uos.de/index.php?id=990

Buscador Científico

Hoy durante la presentación de Sciende Direct y nos mencionaron su página accesible mediante las ligas en www.cem.itesm.mx/bibloteca y se nos mencionó otro buscador interesante de nombre Scirus que pueden ser útiles.

Emotion-based Norm Enforcement and Maintenance in Multi-Agent Systems: Foundations and Petri Net Modeling

Este artículo brinda una base para la modelación de los sistemas multi-agentes empleando emociones y la forma en que estas intervienen en el accionar social del sistema.

Se emplean redes Petri para mostrar los modelos de los agentes involucrados en el sistema en el que se incluye la representación de las normas sociales y la forma en que se reacciona si alguna acción relacionada con ellas es llevado a cabo, por ejemplo el violar alguna de las mismas.

El objetivo de emplear emociones en un sistema multi-agente es el poder hacer que los agentes reaccionen de modo distinto dependiendo de los eventos producidos a lo largo de la ejecución del sistema y que esto a su vez sea provechoso para el agente y el sistema a la vez, brindando otro mecanismo de adaptación para los SMA.

Fix, J., von Scheve, C., & Moldt, D. (2006). Emotion-based norm enforcement and maintenance in multi-agent systems: foundations and petri net modeling. Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems (págs. 105-107). Hakodate, Japón: ACM.

Effective Short-Term Opponent Exploitation in Simplified Poker

En esta lectura se aborda el tema parecido al anterior, el modelado del oponente con pocos datos de entrada para realizar el aprendizaje sobre sus estrategias. En este caso se emplea el póquer como base (una versión simplificada en la que solo se usan las figuras de las cartas J, Q y K).

El hecho de emplear una versión simplificada del póquer en el que solo se incluyen las tres figuras de la baraja inglesa y las opciones de apostar (en este caso las apuestas son de 1 ficha o unidad solamente, no se involucran variables para reducir aún más la complejidad del modelado) o pasar (que en ocasiones puede convertirse en retirarse de la mano como opción) se usa para demostrar que a pesar de ser condiciones simples se involucra un proceso complejo al momento de aprender una estrategia sobe el mismo.

El desarrollo del juego se basa en dos partes, una de aprendizaje y exploración y otra de solo exploración empleando las estrategias aprendidas. A pesar de haber empleado algoritmos para aprendizaje, la convergencia del mismo no llegaba sino hasta haber sido jugadas cincuenta manos con el oponente para poder predecir sus acciones.

Hoehn, B., Southey, F., Holte, R., & Bulitko, V. (2005). Effective Short-Term Opponent Exploitation in Simplified Poker. The Twentieth National Conference on Artificial Intelligence. Pittsburgh, Pennsylvania: AAAI.

Defining and Using Ideal Teammate and Oponent Agent Models

Este artículo resulta ser de gran utilidad a pesar de su antigüedad debido a la mención que hace sobre la forma en que se toma en cuenta al rival dentro de la competición de RoboCup y la forma en que ellos planearon modelarlo.

Se menciona que el modelado del oponente de forma dinámica durante un partido es una tarea difícil y de cierta forma inapropiada para este estilo de competencia debido al poco tiempo de interacción que se tiene con cada equipo rival (solo la duración del partido). Es posible que por esta razón se limite el uso de un modelado del oponente de forma exhaustiva solo en las competencias de Coach en las que se tienen los datos del rival con anterioridad para entrenar al equipo.

La forma en que los autores de este artículo decidieron llevar a cabo el modelado del oponente parte de una base estática pero posiblemente eficaz asumiendo que el rival tiene cierto comportamiento (previamente definido por ellos) en el cual se considera que es muy probable que tenga una habilidad semejante o superior a la de los agentes propios para llevar a cabo acciones dentro del terreno de juego.

Se prueban las anteriores suposiciones con dos acciones básicas en el ataque dentro del juego, la decisión de tiro y los pases que se realizan a los compañeros. En ambos se asume que el rival tiene cierta capacidad para bloquear el tiro o el pase y en el caso del portero se emplearon varios modelos en los que se observa que el agente reacciona de forma inmediata a la posición del balón y en algunas ocasiones cuando se acerca a cierto radio se aventura a por él o en otras espera hasta el último momento (justo después del disparo del delantero) para lanzarse por el balón.

Stone, P., Riley, P., & Veloso, M. (2000). Defining and Using Ideal Teammate and Opponent Agent Models. Proceedings of the Twelfth Annual Conference on Innovative Applications of Artificial Intelligence. Austin, Texas: AAAI.