MTCS Información

El Monte Carlo Tree Search, más conocido como MTCS, es una técnica de inteligencia artificial en la que se mezcla dos técnicas muy populares dentro de este campo:

1º Árboles Clásicos de Decisión.

2º Aprendizaje Por Refuerzo (Q-Learning).

 Este algoritmo tiene dos fases destacadas:

Fase de exploración, en la que el agente prueba diferentes situaciones ante el mismo estado y observa que pasa al tomar esa decisión, es decir, cuanto de buena es esa decisión para nuestro objetivo.

Y una fase de explotación, en la que el agente prueba continuamente las decisiones mejores para ver si realmente sirven para alcanzar nuestro objetivo. Y así cambiar las decisiones por otras que son mejores.

Entonces el agente tiene que:

1º Explorar todas las opciones potenciales en ese tiempo.

2º Identificar rápidamente cual es la mejor.

3º Tener en cuenta las otras opciones buenas para validar como es de buena la mejor.

Utilizando la técnica del Min Max tenemos el problema de que si el árbol es muy grande escala muy mal con respecto al coste computacional.

Para el ajuste de los pesos de los nodos de nuestro MTCS tenemos los procesos de Selección, expansión, simulación y “Backpropagation” (Recalculo de abajo a arriba de los pesos de cada nodo según si la decisión final ha sido buena o mala).

Unos ejemplos visuales de cada una de estas fases serian:

La fórmula matemática que encontramos dentro de este algoritmo seria la UCT (Upper Confidence Bound 1 applied to trees):

En la que el nodo que tenga el valor mayor a la hora de aplicarle esta fórmula será el que el se elegirá como decisión.

La fórmula esta compuesta de:

Wi = número de victorias después de haber cogido este nodo.

ni = número de simulaciones de ese nodo.

Ni = número total de simulaciones de nodos parentales.

c = parámetro de exploración por lo general suele ser √2.

Referencias de:

https://www.youtube.com/watch?v=lhFXKNyA0QA

https://en.wikipedia.org/wiki/Monte_Carlo_tree_search

Planificación del desarrollo de nuestro Agente (REACTIVO)

Para el diseño de nuestro agente, tengo que desarrollar un árbol de decisiones que realice dos funciones importantes a la hora de recibir el tablero del juego con el que se esté probando:

1º Detectar en qué tipo de juego estamos.

2º Aplicar reglas de comportamientos distintas dependiendo del tipo de juego que hayamos detectado antes.

Como en principio voy a probar solo con dos juegos parecidos clasificados por mi como “Objetivo” sin acción posible.

Enlace interesante sobre GVG-AI Example: https://core.ac.uk/download/pdf/77601843.pdf

Dentro de nuestra codificación con los booleanos E_enemigos y E_objetivos son los descriptores que nos servirán para utilizar como condición para nuestro árbol de decisión.

Dentro de cada bloque desarrollaremos las reglas que siga nuestro agente.

Quinto Artículo Científico Sobre Modelaje de Comportamientos

“La simulación basada en agentes: una nueva forma de explorar los fenómenos sociales”

Este artículo científico basando su investigación en el modelo de segregación urbana de Schelling, en el que se intenta explicar cómo en las ciudades los habitantes se organizan guetos donde estos individuos no tienen prejuicios étnicos.

Las aplicaciones de estas simulaciones con agentes se utilizarán para:

1º Solucionar los problemas de la infradeterminación empírica de las teorías sociológicas.

2º Explicar los fenómenos sociales a través de los fenómenos sociales que surjan por la acción de los individuos o las estructuras.

3º Crear una metodología para evaluar políticas sociales y prever sus resultados antes de aplicarlo en sociedades reales.

En el artículo se presenta como modelo de reproducción del modelo de agente de tres formas, mediante redes neuronales artificiales, sistemas de reglas de producción y lenguajes y entornos de programación.

Ejemplo de un sistema de Redes Neuronales Artificiales:

Ejemplo del modelo de segregación de Schelling introducido en los agentes:

Nota: El objetivo es que todos los vecinos(Agentes) acaben viviendo en zonas adecuadas a ellos.

Como resultado del experimento basado en agentes pueden concluir que la utilización de esta herramienta tiene muchas salidas en los aspectos sociales y sus estudios. Se puede emplear para evaluar, formalizar teorías sociológicas. Y así seleccionar entre varias teorías sobre un mismo fenómeno social cual es la mejor.

Realizado por: Jose Ignacio García-Valdecasas Medina

Enlace: https://dialnet.unirioja.es/descarga/articulo/3748058.pdf

Cuarto Artículo Científico Sobre Modelaje de Comportamientos

“A Computational Model of Emotions for Agent-Based Crowds in Serious Games”

En este artículo científico se desarrolla el comportamiento de la multitud (varios agentes) dentro de un mismo entorno. Ya que este fenómeno social emerge de manera compleja entre los individuos. El comportamiento individual es una emoción que juega un papel importante en todos los aspectos de las decisiones que hacemos los humanos. Por ejemplo, cuando tenemos estados emocionales muy acentuados pueden llevar a las personas a tomar decisiones inesperadas, igual que les pasaría a los agentes. 

Esto está siendo aplicado en películas como en videojuegos para generar personajes creíbles.

Se propone un motor de emoción basado en la evaluación moderna capaz de modelar varias características dentro de una multitud emocional. Es capaz de capturar de manera dinámica el contagio emocional y mostrarnos como diferentes composiciones de multitudes pueden conducir a diferentes patrones de contagio emocional.

Para probar esto utilizan HumDPM donde a cada agente se le dota de un set de experiencias que describen su comportamiento. Donde por cada stage se almacenan las nuevas experiencias y se utilizan para modificar el comportamiento de los agentes. Y volviendo a probarlos en otra stage y así sucesivamente.

Una experiencia seleccionada continua en ejecución en las siguientes stage hasta que ocurra una de dos cosas:

-       -Primero si se alcanza los objetivos de la etapa final.

-       -Segundo si se violan las expectativas de cualquier etapa.

En términos generales, esto sucede a través de la expectativa y las señales, es decir, del cambio emocional que puede hacer cambiar el comportamiento de nuestros agentes y también nos ayuda a selecciona los mejores para nuestro interés.

Como objetivo del experimento se explica y se afirma que se pueden simular diferentes tipos de personajes utilizando diferentes susceptibilidades y emociones semicompletas.

Realizado por: Heiko Aydt, Michael Lees, Linbo Luo, Wentong Cai, Malcolm Yoke Hean Low y Sornum Kabilen Kadirvelen.

Enlace: https://ieeexplore.ieee.org/abstract/document/6040757/authors#authors

Tercer Artículo Científico Sobre Modelaje de Comportamientos

“Behaviour Oriented Design for Real-Time-Strategy Games”

La base de este artículo científico es el desarrollo de inteligencia artificial en los videojuegos de hoy en día, es decir, en el diseño y plan para el comportamiento de los agentes usando estrategias en tiempo real. Basándose en Comportamientos orientados a diseños para implementar las estrategias en tiempo real.

Como ejemplo de demostración utilizan el juego de estrategia Starcraft, en el que el uso de este comportamiento en tiempo real ayuda a tomar decisiones más inteligentes cuando nuestro oponente toma decisiones como atacarnos una basa, acumular solados etc y nuestro agente debería según esos hechos cambiar su planificación en tiempo real por ejemplo moviendo tropas aliadas a esa zona que van a atacar o dedicar a expandir sus bases aprovechando que el enemigo se centra en acumular recursos.

Notación: BOD es una metodología para desarrollar el control complejo de los agentes. Combinando las ventajas del comportamiento basado en AI y el diseño orientado a objetos.

El comportamiento orientado a comportamientos (BOD): combina varios estados con aprendizaje y generación de planes de manera modular.

Esta forma modular ayuda a solventar los problemas de programación para los programadores ya que tienen que realizar la mayor parte del trabajo. Donde se sigue un diseño iterativo.

La arquitectura del BOD está formada por dos partes:

1º POSH selector de acciones:

Las acciones seleccionadas por BOD es un POSH (Enraizado en paralelo, ordenado en una pila deslizante jerárquica) donde los planes dinámicos son las estructuras para la selección de acciones (también conocidas como arbitraje o coordinación de comportamiento) en el diseño orientado a comportamientos.

La planificación dinámica (o planificación reactiva) es una forma de hacer una selección de una acción para un agente mediante el cual un sistema elige su próxima acción haciendo una búsqueda rápida en una estructura de datos existente.

2º Librería de comportamientos:

Donde existen dos primitivas: acciones y sensaciones. Que pueden ser llamadas por el mecanismo de selección de acciones, y cualquier estado asociado o memoria requerida para darle soporte. Donde la separación entre POSH y Behaviour Libraries debe ser clara, ya que facilita la reutilización del código, dando la posibilidad de técnicas especializadas más complejas y un conjunto de enfoques distintos. Ocultando la estructura del propio plan.

Realizado por: Swen Gaudl, Simon Davies y Joanna J.Bryson.

Enlace: http://www.cs.bath.ac.uk/~jjb/ftp/GaudlFDG13.pdf

Segundo Artículo Científico Sobre Modelaje de Comportamientos

“Evolution of Human-Competitive Agents in Modern Computer Games”

En este artículo se lo presenta la evolución de los jugadores artificiales (Agentes) en los juegos de la actualidad. Como podemos observar en la actualidad el mundo de los videojuegos ha avanzado a pasos enorme. Y con ello ha provocado que los juegos sean más sofisticados, realistas y orientados a juego en equipo.

Los juegos de ordenador modernos ofrecen problemas interesantes y desafiantes para la investigación de inteligencia artificial. Presentan entornos dinámicos y virtuales y representaciones muy gráficas que no soportan los problemas de las aplicaciones del mundo real pero que aún tienen una gran importancia práctica. Lo que hace que los juegos de computadora sean aún más interesantes es el hecho de que los humanos y los jugadores artificiales interactúan en el mismo entorno.

“Laird et al. Han propuesto un enfoque interesante para dicho agente. Sus agentes intentan anticipar las acciones de los otros jugadores evaluando qué haría su propio mecanismo de planificación, si estuvieran en la misma posición. En una versión posterior, el aprendizaje por refuerzo se agregó a su enfoque. Hawes utiliza técnicas de planificación para un agente. Utiliza tiempos de baja actividad para planificar comportamientos extensos y genera solo planes cortos si no hay tiempo disponible. Nareyek , también ha implementado un agente que utiliza la planificación y la búsqueda local. Norling ha aplicado otro enfoque interesante, en el que se utiliza un modelo BDI (Belief-Desire-Intention) para modelar un agente humano.”

Otros ejemplos de investigaciones interesantes para esta aplicaciond e comportamientos seria:

-Thurau : Con la creación de agentes que intentan aprender de comportamientos de deseos basado en la imitación de otros jugadores. (Basado en redes neuronales).

-Priesterjahn: introdujo la imitación arbitraria de jugadores. Donde se generan las reglas con entradas y salidas, y se ordenan de mayor importancia a menor con el uso de algoritmos evolutivos.

El modelaje se realizaría con un “grind” que sería una representación en plano del terreno donde el agente juega a un videojuego. Especificando que posiciones están ocupadas, que zonas están vacías y cuales están ocupadas por enemigos.

Importante: Esta representación del modelaje será aplicada en primer plano dentro del proyecto de GVG-AI

Y para la definición de acciones utilizara 3 parámetros especificando la utilidad de cada uno:

F = para movimiento vertical y permanecer quieto

R = para movimiento horizontal y permanecer quieto

A = atacar o no atacar

& = Alteración del ángulo de inclinación.

Enlace del artículo:  https://ieeexplore.ieee.org/abstract/document/1688390

Realizado por: S. Priesterjahn Department of Computer Science, University of Paderborn.

Primer Artículo Científico Sobre Modelaje de Comportamientos

“CogBox – Combined Artificial Intelligence Methodologies to Achieve a Semi-realistic Agent in Serious Games”

En este artículo científico se justifica la utilización híbrida de un agente con metodología de inteligencia artificial como lógica difusa, redes neuronales o Creo-Deseo-Intención. Provocara un comportamiento semi-realista con una implementación simple.

Además, se desarrollará las limitaciones de la utilización de cada una en el comportamiento de los agentes y las ventajas de utilizar la opción híbrida propuesta.

El núcleo de esta técnica se basa en:

1º Belief Desire Intention (BDI - Creer/Desear/Intención): es un modelo de comportamiento racional en agentes. En el que se proporciona al agente de tres actividades mentales mostrándolo como la información, la motivación y la deliberación de estados del agente.

Se utiliza en campos de la filosofía y las ciencias cognitivas, incluyendo la racionalidad de los agentes.

2º Finite State Machines (Máquina de estados finita): Este método es el más utilizado dentro de los juegos de ordenadores como método para generar comportamiento de inteligencia artificial. En la que el agente se sitúa en un estado y tiene varias condiciones o acciones para pasar de un estado a otro. La desventaja es que a mayor número de estados que implicaría una mejora del comportamiento la complejidad del código también aumenta.

3º Hybrid Method: Lo que se propone es crear nuestros agentes con un control primario por BDI obteniendo una simulación del razonamiento humano. Y se deja el control al FSM cuando las decisiones de acciones del BDI se deben de tomar sin deliberación, dotando así a nuestros agentes de una simulación de los instintos humanos.

Referencias: 2010 Book Artifical Intelligence And SoftC

Por David Irvine y Mario A.Gongora