**SVRAI**
MonteCarlo Tree Search
# Introducción
Como respuesta a las aproximaciones estocásticas hace unos años surgió la técnica de **Monte Carlo Tree Search** (**Búsqueda en Árboles con MonteCarlo**) que ofrece algunas ventajas inherentes:
* se puede aplicar a **espacios de estados con un factor de ramificación** tan **grande** que resultan inabordables con las técnicas tradicionales anteriores;
* se puede **configurar para que se detenga después de una cantidad de tiempo prefijada**, haciendo que con tiempos mayores se obtengan agentes con mejores capacidades de decisión;
* **no requiere** necesariamente de un **conocimiento específico del dominio**, por lo que puede ser utilizado como motor de acción general;
Y también algunas desventajas insalvables:
* es un **método probabilístico**, por lo que no siempre tiene porqué encontrar la solución óptima;
* si realizar simulaciones del modelo del mundo es costoso, el proceso completo puede ser inabordable.
El origen de este método se encuentra en la Tesis Doctoral de Bruce Abramson, de 1987, de título *"[The Expected-Outcome Model of Two-Player Games](http://academiccommons.columbia.edu/download/fedora_content/download/ac:142327/CONTENT/CUCS-315-87.pdf)"*, donde, en vez de usar una función de evaluación estática, combinaba una búsqueda minimax con un modelo probabilístico para generar al azar jugadas completas en juegos con adversario (que puede ser un modelo simplificado de toma de decisiones). Esta técnica fue depurada en trabajos posteriores, hasta que en 1992 se aplica por primera vez al juego del Go en una forma muy similar a como se entiende hoy en día. En 2006, inspirado por estos trabajos, [Remi Coulom](https://www.remi-coulom.fr/) ([Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search](https://www.remi-coulom.fr/CG2006/)) describe por primera vez la aplicación general del método de Monte Carlo aplicado a la búsqueda en árboles de juego, y acuña el término **Monte Carlo Tree Search**. Desde entonces ha sido aplicado a multitud de juegos, ampliado para trabajar sobre juegos con incertidumbre, y usado también para resolver problemas de búsqueda fuera del ámbito de los juegos, en problemas de planificación y de toma de decisiones general para agentes... que es el tema que nos ocupa aquí.
En esta sección mostraremos cómo funciona esta técnica, y nos centraremos específicamente en una variante llamada **UCBT** (**Upper Confidence Bound applied to Trees**, o en español **Cota de Confianza Superior aplicada a Árboles**).
!!!side:1
Esta técnica de muestreo recibe el nombre de MonteCarlo.
![](./img/chessmcts.gif width=400px align="left")La idea de ir seleccionando acciones al azar desde la posición actual para muestrear cómo se comportan las distintas acciones que podemos tomar no es nueva $^{1}$. El problema es que no se sabía cómo muestrear el árbol de acciones para que los resultados obtenidos representasen con cierta fiabilidad la bondad de las mismas.
Esencialmente, podemos ver **cada una de las acciones posibles como una variable aleatoria cuyo muestreo nos informa acerca de lo buena o mala que es dicha acción**. Pero, ¿qué ocurre si el árbol de evolución se ramifica tanto (como suele ser habitual en la mayoría de las situaciones interesantes) que no podemos estar seguros de que el muestreo puramente al azar realmente sea capaz de captar la estructura intrínseca del árbol? Lo ideal sería disponer de algún mecanismo que, tras el menor número posible de pruebas, indique qué acciones son más prometedoras y en las que merece la pena invertir más tiempo de explotación. Como se puede observar, el problema sigue siendo el mismo que podemos encontrar en los algoritmos de búsqueda más básicos: ¿cómo saber cuándo _explorar_ el árbol y cuándo _explotar_ una rama prometedora?
La respuesta a esta pregunta vino de la mano de UCBT, y para entender cómo funciona vamos a pasar a un problema que tiene una raíz equivalente y que se había estudiado con anterioridad en relación con la toma de decisiones: **el problema de las tragaperras múltiples**.
# Problema de las Tragaperras Múltiples
![](./img/one_arm_bandit.jpg align="right" width=400px)Imaginemos que nos enfrentamos a una fila de máquinas tragaperras (al estilo de las que hay en los casinos), cada una con características diferentes, tanto en probabilidad de generar un premio como en el valor de éstos. Lo ideal sería disponer de una estrategia que permitiera maximizar la ganancia total cuando jugamos con ellas. Supongamos, además, que no hay nadie cerca jugando a las mismas máquinas, por lo que no podemos obtener información adicional sobre cuál es la mejor máquina para jugar (es decir, no podemos definir una heurística óptima a priori). La única opción es recopilar esta información personalmente, intentando equilibrar la cantidad jugada en todas las máquinas y concentrando el mayor número de jugadas en la mejor máquina observada hasta el momento.
En su versión más simple, un problema de $K$ **tragaperras** se puede definir haciendo uso de conceptos básicos de estadística por medio de una sucesión de **variables aleatorias** $\{X_{i,n}:\ 1\leq i\leq K,\ n\geq 1\}$, donde $i$ es el índice de cada tragaperras. Las jugadas sucesivas de la máquina $i$ dan lugar a una sucesión $X_{i,1}$, $X_{i,2}$, ..., **independientes e idénticamente distribuidas** siguiendo una distribución desconocida de **media** $\mu_i$ que caracteriza esa tragaperras. Además, también pedimos que haya **independencia entre las máquinas**, es decir, que para cada $1\leq i < j\leq K$, y $s,t \geq 1$, se tiene que $X_{i,s}$ y $X_{j,t}$ son independientes (aunque, normalmente, no serán idénticamente distribuidas, ya que cada máquina puede seguir una distribución distinta).
En estas condiciones, una **estrategia** (**policy**) es un algoritmo $A$ que elige la siguiente máquina en la que jugar basándose en la secuencia de jugadas anteriores y en los premios recibidos. Si $T_i(n)$ es el número de veces que el algoritmo $A$ ha seleccionado la máquina $i$ durante las primeras $n$ jugadas, entonces la **pérdida esperada** de la estrategia $A$ (es decir, lo que no hemos ganado por no haber elegido siempre la mejor máquina posible) se puede calcular como:
$$\mu^* n - \sum_{i=1}^K \mu_i\ E[T_i(n)]$$
donde $\mu^*=max_{1\leq i\leq K}\mu_i$ representa la mejor jugada posible (desconocida).
Apoyándonos en algunos resultados de estadística, podemos hacer uso de una estrategia, llamada **UCB1** (**Upper Confidence Bound**, [Kocsis y Szepesvári](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.1296&rep=rep1&type=pdf)), que construye intervalos estadísticos de confianza para cada máquina de la forma:
$$\left[ \overline{X_i}(n) - \sqrt{\frac{2\ln n}{T_i(n)} }\ ,\ \overline{X_i}(n) + \sqrt{\frac{2\ln n}{T_i(n)} } \right]$$
donde, $\overline{X_i}(n)$ es la media de ganancias experimental que ofrece la máquina $i$ tras los $n$ pasos (que se puede calcular como la suma de los premios recibidos en esa máquina dividido entre el número de veces que se ha jugado en ella, si en un paso $j\leq n$ no se ha jugado esa máquina, entonces $X_{i,j}=0$): $$\overline{X_i}(n) = \frac{\sum_{j\leq n} X_{i,j} } {T_i(n)}$$
La [Ley de los Grandes Números](https://es.wikipedia.org/wiki/Ley_de_los_grandes_n%C3%BAmeros) nos asegura que $\lim_{T_i(n)\to \infty} \overline{X_i}(n) = \mu_i$. Por tanto, una estrategia válida sería escoger siempre la máquina que tenga el mayor límite superior de este intervalo. Al usar esa máquina, el valor medio observado en ella se desplazará a su valor real y su intervalo de confianza se reducirá (ya que en esta máquina $T_i(n)$ aumenta más rápido que $\ln n$), a la vez que todos los intervalos de las otras máquinas se van ampliando (ya que, para esas otras máquinas, el valor de $T_i(n)$ permanece constante mientras no las usemos, pero $\ln n$ crece). Eventualmente, alguna de las otras máquinas podrá tener un límite superior mayor al de la máquina seleccionada actual, y entonces lo mejor será cambiar a esa otra máquina.
!!!side:2
Existen otras estrategias que ofrecen un rendimiento similar, pero UCB1 es posiblemente la estrategia más simple con este buen comportamiento, así que será suficiente para la primera aproximación que estamos ofreciendo aquí.
Esta estrategia verifica que la diferencia entre lo que hubiéramos ganado jugando únicamente en la mejor máquina y las ganancias esperadas bajo la estrategia usada crece sólo como $O(\ln n)$ (es decir, perdemos poco respecto a la mejor jugada posible), que es la misma tasa de crecimiento que la mejor estrategia teórica para este problema (denominado **Problema de Tragaperras Múltiples**), y tiene el beneficio adicional de ser muy fácil de calcular, ya que basta llevar un contador para cada máquina $^{2}$.
# Aplicación a la Toma de Decisiones
![](./img/mc_integral.gif align="right" width=50%)Y aquí es donde entra en juego el **método de Monte Carlo aplicado a búsquedas** usando la estrategia anterior, donde el papel que juegan las diferentes tragaperras se cambian por las diversas acciones válidas en la búsqueda (en MDPs, las acciones válidas), y los premios de las máquinas se cambian por la bondad del camino encontrado (en MDPs, por la recompensa de la sucesión de movimientos realizados).
En un proceso estándar de MonteCarlo aplicado a un MDP:
1. Se generan un gran número de simulaciones aleatorias desde el estado actual para el que se desea encontrar el mejor movimiento siguiente;
2. se almacenan las estadísticas para cada movimiento posible a partir de este estado inicial y,
3. se devuelve el movimiento con los mejores resultados generales.
Así descrito, la desventaja de este método general es que, en cualquier estado, puede haber muchas acciones posibles pero sólo una o dos que son buenas, por lo que, si se elige una acción aleatoria, es extremadamente improbable que la simulación proporcione el mejor camino hacia la solución perfecta.
Ante este problema se han propuesto variantes, como la llamada **UCT** que presentaremos a continuación, que permite minimizar los riesgos, y que se basa en la idea de que, si tenemos estadísticas de bondad disponibles para todos los estados sucesores del estado actual, entonces podemos extraer una estadística de bondad para el mismo... de forma similar a como se hace en el problema de las tragaperras múltiples de la sección anterior.
En vez de hacer muchas simulaciones puramente aleatorias, esta variante hace muchas iteraciones de un proceso que consta de varias fases y que tiene como objetivo mejorar nuestra información del sistema (**exploración**) a la vez que potencia aquellas opciones más prometedoras (**explotación**):
!!!side:3
Es decir, un nodo en el que hay posibles movimientos o acciones que no han sido consideradas.
1. La primera fase, **Selección**, se realiza mientras tengamos las estadísticas necesarias para tratar cada estado alcanzado como un problema de tragaperras múltiples. Comenzando por el estado actual, seleccionamos recursivamente la acción más urgente de acuerdo a una función de utilidad (en nuestro caso, por medio del algoritmo UCB1), hasta que se alcanza un estado que, o bien es terminal, o bien no está completamente extendido $^{3}$.
2. La segunda fase, **Expansión**, ocurre cuando ya no se puede aplicar la fase anterior. Para ello, se elige aleatoriamente una acción no visitada del estado que no estaba completamente extendido y se añade un nuevo estado al árbol de estadísticas con el fin de completar dicha información.
!!!side:4
Para mundos con un factor de ramificación pequeño, una simple heurística de ponderación puede dar buenos resultados.
3. Tras la expansión, nos encontramos en la fase de **Simulación**, que sigue los mismos parámetros de una simulación típica de MonteCarlo. Es decir, partiendo del estado recién añadido se simula una evolución completa, ya sea al azar, con una simple heurística de ponderación, o utilizando heurísticas y evaluaciones computacionalmente costosas para una estrategia más elaborada $^{4}$. Junto a la traza completa se obtiene un valor de recompensa que determina la utilidad de esa rama para el agente.
4. Finalmente, la cuarta fase es la de **Actualización** o **Retropropagación**. Con el estado final alcanzado en la fase anterior se actualizan las estadísticas de todas las acciones y estados previos visitadas durante la simulación completa (incluyendo la recompensa conseguida por el agente en la simulación).
Obsérvese que en este proceso hay tres estrategias involucradas:
* En la fase de Selección: Estrategia de **selección de nodos del árbol** según su utilidad. Hay muchas opciones, por ejemplo: seleccionar la acción con mayor ganancia, la acción, o estado sucesor, que ha sido usada en mayor número de recompensas positivas, la que verifique las dos condiciones anteriores (si no lo hay, se sigue realizando la búsqueda hasta que haya uno que lo verifique), o el que maximiza la estrategia UCB1 explicada anteriormente, etc.
* En la fase de Expansión: Estrategia de **creación de nuevos estados**. Es normal elegir una creación aleatoria uniforme entre las acciones disponibles, pero si se dispone de alguna información adicional del problema se puede usar para decidir qué acción tomar (y, en consecuencia, qué estado se crea).
* En la fase de Simulación: Estrategia de **generación de una traza completa** a partir del nuevo estado creado. Aquí es relativamente común introducir, si se considera necesario, algún conocimiento específico del dominio del problema.
Este algoritmo se puede configurar para detenerse tras un período de tiempo deseado, o bajo cualquier otra condición que se considere oportuna. A medida que se van ejecutando más y más simulaciones, el árbol de estadísticas crece en memoria y la acción que finalmente se elija converge hacia la acción óptima real (aunque esta convergencia puede requerir muchísimo tiempo), como ocurre en el problema de las tragaperras múltiples.
Cuando se aplica el algoritmo UCB1 como estrategia de selección de la acción siguiente el objetivo es maximizar la fórmula equivalente siguiente (y que al aplicarla a la búsqueda en árboles pasa a llamarse **UCT**, **Upper Confidence on Trees**, que damos en el caso particular de toma de decisiones con conteo de estados terminales buenos/malos/indiferentes, como pasa en los juegos):
$$UCT(s)=\frac{Q(s)}{N(s)}+2 C_p\sqrt{\frac{\ln N(s_0)}{N(s)} }$$
donde $N(s_0)$ es el número de veces que el estado $s_0$ (el padre de $s$) ha sido visitado, $N(s)$ es el número de veces que el estado hijo, $s$, ha sido visitado, $Q(s)$ es la recompensa total de todas las jugadas que pasan a través del nodo $s$, y $C_p > 0$ es una constante adecuada.
!!!note
El término $\overline{X_i}(s)$ de UCB1 se reemplaza aquí por $\frac{Q(s)}{N(s)}$, que representa la recompensa media de todas las simulaciones.
Cuando $N(s)=0$, es decir, el sucesor nunca se ha visitado (todavía), el valor de UCT toma el valor infinito y, por tanto, el sucesor sería elegido por la estrategia. Esta es la razón por la que esta fórmula solo se utiliza en caso de que todos sus hijos hayan sido visitados al menos una vez.
Al igual que en la fórmula de UCB1, hay un equilibrio entre el primer término (explotación) y el segundo (exploración):
* La contribución del término de exploración decrece a medida que se visita cada estado (que se visita), ya que aparece en el denominador.
* Por otra parte, el término de exploración crece cuando se visita otro sucesor de su nodo padre (un hermano suyo). De esta forma, el término de exploración asegura que incluso sucesores con recompensas bajas sean seleccionados si se da el tiempo suficiente.
!!!teorema
La constante del término de exploración $C_p$ se puede escoger para ajustar el nivel de exploración deseado. Kocsis y Szepesvári demostraron que $C_p = 1/\sqrt{2}$ es un valor óptimo cuando las recompensas/ganancias se encuentran en el intervalo $[0, 1]$, pero en otros casos el valor adecuado de $C_p$ debe ser determinado experimentalmente.
!!!teorema
Además, Kocsis y Szepesvári también demostraron que la probabilidad de seleccionar una acción subóptima (es decir, no la mejor) para la raíz del árbol tiende a $0$ a velocidad polinomial si el número de iteraciones tiende a infinito, lo que significa que, con suficiente tiempo y memoria, UCT ofrece una política óptima.
## El Algoritmo
El algoritmo descrito informalmente puede expresarse en pseudocódigo como sigue: donde `n` es el nodo del árbol MCTS que se está construyendo; `s(n)` es el estado del problema asociado al nodo `n`; `A(s)` es el conjunto de acciones que se pueden aplicar en el estado `s`; y, si `a ∈ A(s)`, entonces `a(s)` es el estado resultante de aplicar la acción `a` sobre `s`.
!!!alg: Algoritmo UCT
~~~~~~none
Función: MCTS-UCT(s₀)
Crear nodo raíz n₀ con estado s₀
Mientras haya recursos computacionales
n ← Seleccion(n₀)
r ← Simula(s(n))
Retropropaga(n,r)
Devuelve a tal que a(s(n₀)) = MejorHijo(n₀)
Función: Seleccion(n)
Mientras s(n) no sea terminal
Si n no está completamente expandido, entonces
Devuelve Expande(n)
si n está completamente expandido, entonces:
n ← MejorSucesorUCT(n,c)
Devuelve n
Función: Expande(n)
a ← elige acción no probada de A(s(n))
Añadir un nuevo sucesor m de n
s(m) ← a(s(n))
a(m) ← a
Devuelve m
Función: MejorSucesorUCT(n)
Devuelve argmax UCT(n)
Función: Simula(s)
Mientras s no sea terminal
a ← un elemento de A(s)
s ← a(s)
Devuelve ganancia del estado s
Procedimiento: Retropropaga(n,r)
Mientras n no sea nulo
N(n) ← N(n) + 1
Q(n) ← Q(n) + r
n ← Padre de n
~~~~~~~~
Una versión simplificada de este algoritmo se consigue haciendo que la recompensa esté limitada a 3 posibles valores: $1$, cuando el agente gana; $0$, cuando el agente pierde; y $0.5$, cuando la situación es indiferente.
## Implementación en Julia para Juegos
!!!side:5
La damos por motivos de completitud y se pueda ver lo fácil que es implementar una versión sencilla del algoritmo anterior.
Una implementación en Julia relativamente general podría ser la siguiente $^{5}$. Observa que hace uso de una estructura general de Juegos que define las funciones mínimas necesarias para que MCTS pueda evaluar y adaptarse al juego concreto que necesita ser modelado:
~~~~~~~julia
# Estructura que define un juego genérico con funciones como campos
struct JuegoGenerico
acc_disponibles::Function # s -> colección de acciones aplicables a `s`
aplica_acc::Function # s,a -> estado resultante de aplicar `a` a `s`
es_terminal::Function # s -> true/false decide si `s` es terminal
resultado::Function # s,p -> Ganancia de `p` en el estado `s`
end
# Definición del Nodo de MCTS
mutable struct Nodo
estado # Estado del juego en este nodo
padre::Union{Nodo, Nothing} # Nodo padre
hijos::Vector{Nodo} # Hijos del nodo
visitas::Int64 # Número de veces que se visitó este nodo
recompensa::Float64 # Recompensa acumulada en este nodo
jugador::Int # Jugador que ha provocado este nodo
# Método de creación de nodos
function Nodo(estado, padre, jugador)
new(estado, padre, Nodo[], 0, 0.0, jugador)
end
end
# Función principal MCTS
# s0,g,n,p -> Mejor acción para el jugador p aplicando n pasos de MCTS en el
# juego g, y comenzando desde el estado s0
function mcts(s0, g::JuegoGenerico, n_iter::Int64, jugador_actual)
# Nodo inicial, con sus nodos hijo
n0 = Nodo(s0, nothing, jugador_actual)
# Bucle principal
for _ in 1:n_iter
# 1. Selección del nodo a explorar a partir de n0
n = seleccionaUCB1(n0)
# 2. Expansión del nodo seleccionado
expande(n, g)
# 3. Simulación
if !isempty(n.hijos)
n = rand(n.hijos) # Elige un hijo aleatoriamente para simular
end
r = simula(n.estado, g, n.jugador)
# 4. Retropropagación
retropropaga(n, r)
end
# Elegir la mejor acción (hijo con más visitas)
mejor_hijo = argmax(n -> n.visitas, n0.hijos)
return mejor_hijo.estado # Retorna el mejor estado siguiente
end
# Función UCB1 (Upper Confidence Bound) para la selección del nodo
function ucb1(n::Nodo, exp_p::Float64 = 1.414)
if n.visitas == 0
return Inf
else
return (n.recompensa / n.visitas) + exp_p * sqrt(log(n.padre.visitas) / n.visitas)
end
end
# Selección: Escoge el mejor nodo en base a UCB1. Si hay un árbol ya de
# descendientes, profundiza en el árbol usando UCB1 para seleccionar
# qué hoja desarrollar
function seleccionaUCB1(n::Nodo)
while !isempty(n.hijos)
n = argmax(n1 -> ucb1(n1), n.hijos)
end
return n
end
# Expansión: Añade todos los nodos hijos de n usando las acciones disponibles
# del juego. Si el nodo a expandir es terminal, no hace nada
function expande(n::Nodo, g::JuegoGenerico)
if !g.es_terminal(n.estado)
for a in g.acc_disponibles(n.estado) # Recorre las acciones
s = g.aplica_acc(n.estado, a) # las aplica
push!(n.hijos, Nodo(s, n, n.jugador)) # y crea el nodo hijo
end
end
end
# Simulación: Simula el resto del juego de manera aleatoria hasta llegar a un
# nodo terminal. Devuelve el resultado del estado terminal para el
# jugador que ha lanzado la exploración.
# Nota: Observa que no usa nodos, solo estados, porque es información
# que no queremos almacenar. Corresponde a un muestreo aleatorio
function simula(s, g::JuegoGenerico, p)
while !g.es_terminal(s)
a = rand(g.acc_disponibles(s)) # Selección aleatoria de acción
s = g.aplica_acc(s, a) # cálculo del estado obtenido
end
return g.resultado(s, p) # Devuelve la ganancia del jugador en s
end
# Retropropagación: Actualiza las estadísticas de los nodos desde el nodo hoja
# hasta la raíz
function retropropaga(n::Nodo, result::Number)
while n !== nothing
n.visitas += 1
n.recompensa += result
result = 1 - result # Esto vale para el caso 0/0.5/1
n = n.padre
end
end
~~~~~~~~~~~~~
Para usar esta implementación de MCTS, hay que definir las funciones asociadas al juego genérico que estemos simulando (fácilmente adaptable a otras situaciones que no provienen de juegos). Por ejemplo, para poder hacer un jugador automático de 3 en raya:
~~~~~~~julia
# Definir las funciones para el juego Tic-Tac-Toe
# Hemos elegido una representación lineal de los estados, como vectores de
# 9 posiciones rellenas con 1/-1 según el jugador, y 0 si la casilla
# está vacía.
# Una acción es simplemente el índice de la casilla que juega el jugador
# correspondiente.
function acc_disponibles_ttt(s)
return findall(x -> x == 0, s) # Casillas vacías
end
function aplica_acc_ttt(s, a)
s2 = copy(s)
jugador_actual = sum(s) == 0 ? 1 : -1 # Determina el jugador actual
s2[a] = jugador_actual
return s2
end
function ganador_ttt(s)
lineas = [(1,2,3), (4,5,6), (7,8,9), (1,4,7), (2,5,8), (3,6,9), (1,5,9), (3,5,7)]
for (i, j, k) in lineas
if s[i] != 0 && s[i] == s[j] && s[j] == s[k]
return s[i]
end
end
return 0 # Nadie ha ganado
end
function es_terminal_ttt(s)
return ganador_ttt(s) != 0 || all(x -> x != 0, s) # Si hay ganador o está lleno
end
function resultado_ttt(s,p)
g = ganador_ttt(s)
if g == 0
return 0.5
elseif g == p
return 1
else
return 0
end
end
# Crear una instancia de JuegoGenerico para Tic-Tac-Toe
ttt = JuegoGenerico(
acc_disponibles_ttt,
aplica_acc_ttt,
es_terminal_ttt,
resultado_ttt
)
# Estado inicial del juego (tablero vacío)
s0 = fill(0, 9)
~~~~~~~
## Características de MCTS
MCTS ofrece una serie de ventajas sobre los métodos tradicionales de búsqueda en árbol:
* **Aheurística**: No requiere ningún conocimiento estratégico o táctico sobre el dominio dado para tomar decisiones razonables. El algoritmo puede funcionar eficazmente sin conocer los entresijos del mundo, aparte de sus acciones legales y condiciones finales; esto significa que, como hemos visto más arriba, es factible dar una implementación general de MCTS que puede reutilizarse con cierta facilidad.
* **Asimétrico**: Realiza un crecimiento asimétrico del árbol que se adapta a la topología del espacio de búsqueda. El algoritmo visita más a menudo los nodos más interesantes y centra su tiempo de búsqueda en las partes más relevantes del árbol.
Esto hace que MCTS sea adecuado para dominios con grandes factores de ramificación (como el Go en tamaño $19×19$). Estos grandes espacios combinatorios suelen causar problemas a los métodos de búsqueda estándar basados en la profundidad o la amplitud, pero la naturaleza adaptativa de MCTS significa que convergerá a las acciones que parecen óptimas y centrará su esfuerzo de búsqueda en ellas.
Además, al algoritmo puede detenerse en cualquier momento para obtener la mejor estimación actual. El árbol de búsqueda construido hasta el momento puede descartarse o conservarse para reutilizarlo en el futuro. Y, como hemos visto, es fácil de aplicar.
Pero también presenta algunas desventajas. Por ejemplo:
* **Fuerza de decisión**: En su forma básica, puede fallar a la hora de encontrar jugadas razonables incluso para partidas de complejidad media en un tiempo razonable. Esto se debe principalmente al gran tamaño del espacio combinatorio y al hecho de que los nodos clave pueden no ser visitados suficientes veces commo para dar estimaciones fiables.
* **Velocidad**: la búsqueda MCTS puede tardar muchas iteraciones en converger a una buena solución, lo que puede ser un problema para aplicaciones más generales que son difíciles de optimizar. Por ejemplo, las mejores implementaciones de Go pueden requerir millones de jugadas junto con optimizaciones y mejoras específicas del dominio para realizar jugadas expertas. Para tiempos de respuesta razonables, si el juego es difícil de simular, el algoritmo apenas tiene tiempo de visitar cada movimiento legal y es poco probable que se produzca una búsqueda significativa.
Por suerte, el rendimiento del algoritmo puede mejorarse notablemente utilizando una serie de técnicas. Hasta la fecha se han sugerido docenas de mejoras del MCTS. En general, pueden agruparse en:
* **Conocimiento del dominio**: El conocimiento del dominio específico del problema modelado puede aprovecharse en el árbol para filtrar acciones inverosímiles o en las simulaciones para producir acciones que se parezcan más a las que se producirían entre agentes humanos. Esto significa que los resultados de las trazas serán más realistas que las simulaciones aleatorias y que los nodos requerirán menos iteraciones para producir valores de recompensa realistas. El conocimiento del dominio puede aportar mejoras significativas, a expensas de la velocidad y la pérdida de generalidad.
* **Independientes del dominio**: Las mejoras independientes del dominio se aplican a todos los dominios del problema. Normalmente se aplican en el árbol, aunque también algunas se aplican a las simulaciones (p. ej., preferir acciones con recompensa durante las simulaciones). Las mejoras independientes del dominio no vinculan la aplicación a un dominio concreto, sino que mantienen la generalidad, por lo que son el objetivo de la mayoría de los trabajos actuales en este campo.
MCTS encaja aquí simulando las secuencias de estados y recompensas a partir de un estado inicial, lo que permite a los agentes seleccionar acciones que maximicen recompensas a largo plazo.
A pesar de lo que hemos dicho en los párrafos anteriores, experimentalmente se han mostrado alguno beneficios de usar MCTS en entornos estocásticos:
- **No requiere un modelo completo del entorno**: MCTS no necesita conocer todas las transiciones o recompensas a priori, ya que puede aprenderlas a través de simulaciones.
- **Exploración eficiente**: Al usar una estrategia como UCT, MCTS puede equilibrar la exploración de acciones nuevas y la explotación de las conocidas de forma dinámica por medio de un solo parámetro.
- **Escalabilidad**: Aunque el espacio de estados y acciones sea muy grande, MCTS puede aproximar buenas políticas sin necesidad de recorrer todo el espacio.
Por ello, MCTS se presenta como una herramienta adecuada en uso conjunto con los MDPs, ya que permite abordar problemas de toma de decisiones secuenciales bajo incertidumbre de forma eficiente. Utilizando simulaciones, los agentes pueden navegar por entornos inciertos y descubrir políticas óptimas o casi óptimas sin requerir una modelización completa del entorno.