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