**IAIC 2024-25**
Búsquedas con incertidumbre
# Juegos Con Adversario
 Una de las fuentes más fructíferas de problemas que se pueden resolver por los procedimientos de búsqueda estudiados viene de la mano de los juegos unipersonales (o solitarios). Sin embargo, es difícil aplicar directamente estos procedimientos a juegos en los que intervienen dos jugadores que compiten, lo que se conocen como **Juegos con Adversario**.
!!!side:1
Desde el punto de vista de la búsqueda, intentamos decidir las jugadas que debe hacer uno de los dos jugadores, el otro actúa de forma independiente y hay incertidumbre frente a las decisiones que toma y las jugadas que realiza.
Hemos de tener en cuenta que el uso de la búsqueda es completamente distinta en ambos casos: mientras que en los solitarios los estados solo pueden alterarse por las acciones del jugador, en los juegos con adversario hay un contrincante que realiza cambios en el estado que no podemos controlar a priori $^1$.
John von Neumann dio la siguiente definición de lo que era un juego:
> _Un juego es una situación conflictiva en la que uno debe tomar una decisión
> sabiendo que los demás también toman decisiones, y que el resultado del
> conflicto se determina, de algún modo, a partir de todas las decisiones realizadas._
!!!side:2
Se considera *información perfecta* porque los dos jugadores tienen información completa del estado del juego en todo momento. Aunque cada jugador no tiene conocimiento de la jugada que hará el otro, sí tienen la misma información acerca del estado en el momento en que cada uno de ellos debe decidir.
!!!side:3
Es decir, el jugador presupone que el otro jugador será racional.
Y en 1926 demostró que siempre existe una forma racional (una estrategia óptima) de actuar en juegos de dos participantes si los intereses que los gobiernan son completamente opuestos. A este resultado se le conoce como **Teorema Minimax**. Junto a ese teorema proporcionó un algoritmo de decisión, llamado **Minimax**, para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta $^2$. El objetivo del jugador puede resumirse en: _elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor movimiento para ti_ $^3$.
!!!side:4
Aquellos en los que los intereses que los gobiernan son completamente opuestos, o lo que es lo mismo, que lo que gana un jugador lo pierde el otro.
Este resultado establece que en los **juegos bipersonales de suma cero** $^4$, donde además cada jugador conoce de antemano la estrategia de su oponente y sus consecuencias, existe una estrategia que permite a ambos jugadores minimizar la pérdida máxima esperada. En particular, cuando se examina cada posible estrategia, un jugador debe considerar todas las respuestas posibles del jugador adversario y la pérdida máxima que puede acarrear. El jugador juega, entonces, con la estrategia que resulta en la minimización de su máxima pérdida. Tal estrategia es llamada **óptima** para ambos jugadores sólo en caso de que sus **minimaxes** sean iguales (en valor absoluto) y contrarios (en signo). Si el valor común es cero el juego se convierte en un sinsentido. En los juegos de suma no nula, existe tanto la estrategia **Minimax** como la **Maximin**. La primera intenta minimizar la ganancia del rival, es decir, busca que el rival tenga el peor resultado, mientras que la segunda intenta maximizar la ganancia propia, es decir, busca que el jugador obtenga el mejor resultado.
Aunque la búsqueda con adversarios se usa normalmente en juegos en los que interviene más de un jugador, también la podemos encontrar en contextos distintos a los juegos en los que se han de tomar decisiones (acciones futuras) en entornos con cierta incertidumbre debido a cambios producidos por el azar o por condiciones no controladas por el agente.
En este apartado nos centraremos en ejemplos de juegos:
!!!note
Existen muchos tipos de juegos, pero vamos a considerar fundamentalmente aquellos en los que se verifican las siguientes condiciones:
* Es **determinista**.
* Participan dos jugadores.
* Está basado en **turnos**.
* Es de **suma nula**: lo que un jugador gana, lo pierde el otro.
* Tiene **información perfecta**: cada jugador tiene conocimiento completo del estado del mundo en todo momento.
!!!def:Juego Formal
La forma más directa de formalizar un juego de estas características es por medio de una tupla que es una variante de un espacio de estados, $(S,P,A,T,g,U)$, donde:
* $S$ es el conjunto de estados/nodos (normalmente, comenzando por una situación inicial, $s_0\in S$).
* Los jugadores se notarán por $P=\{1,\dots,n\}$ (normalmente, $n=2$).
* Las acciones/movimentos de cada jugador se notarán por $A$ (pueden depender del jugador y del estado).
* La función de transición: $T: S\times A \to S$, indica cómo cambian los estados bajo las acciones.
* $g: S\to \{true,false\}$ indica si un estado del juego es terminal (y ya no se puede continuar).
* $U: S\times P\to \mathbb{R}$ es una función de utilidad de estados terminales, que indica lo bueno que es un estado terminal para cada jugador.
Nuestro objetivo es disponer de algoritmos que nos ayuden a tomar la decisión de qué jugada hacer en cada momento. Formalmente:
!!!side:5
Contrasta con la devolución de un plan, que indicaría el procedimiento completo de juego de principio a fin. La razón es que no podemos planificar por completo una jugada, sino solo responder a las diferentes jugadas que el oponente puede realizar.
!!!def:Estrategia de Juego
Buscamos que un algoritmo de búsqueda adversario devuelva una **estrategia** (**política**) que, esencialmente, devuelve una acción para cada estado: $\pi: S\to A$, que indica la *jugada* a realizar $^5$.
## El algoritmo Minimax
!!!side:6
Si es posible, porque el juego lo permita, se desarrolla el árbol completo de juego hasta las posiciones finales.
La idea de **Minimax** consiste en comenzar en la posición actual del juego y usar el generador de movimientos legales para generar las posibles posiciones sucesivas hasta un cierto límite de niveles $^6$. A continuación, se aplica una función de evaluación estática a los últimos estados obtenidos, que indica lo bueno o malo que es cada estado, y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores.
Habitualmente, se suele trabajar con una función de evaluación que devuelve valores positivos para indicar buenas situaciones para el jugador que hace uso del algoritmo, y valores negativos para indicar buenas situaciones para el adversario. Así planteado, el objetivo es maximizar el valor de esta función estática sobre las posibles jugadas que se pueden hacer desde la posición actual del juego.
!!!side:7
Cada nivel (pares o impares) corresponde a estados producidos por la acción previa de un jugador, y donde el contrincante debe decidir el siguiente paso.
De este mecanismo es de donde viene el nombre del algoritmo: dada la función evaluadora estática, el jugador que hace uso del algoritmo intenta maximizar su valor, mientras que el adversario intenta minimizarlo. En un árbol de juego donde los valores de la función evaluadora se calculan en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro hasta llegar al nivel actual de juego $^7$.
!!!side:8
Si no podemos afrontar la generación del árbol completo, es posible aplicar los pasos siguientes sobre una sección del mismo, aunque entonces no podremos asegurar la optimalidad de los resultados.
!!!side:9
O las hojas que hayamos conseguido si no hemos podido construirlo entero.
!!!note
Formalmente, los pasos del algoritmo Minimax son:
1. **Generación del árbol de juego**: A partir del nodo que representa el estado actual, se generan todos los nodos hasta llegar a un estado terminal en cada rama de jugadas $^8$.
2. Se calculan los valores de la **función de evaluación** para cada nodo terminal $^9$ del árbol construido.
3. Se evalúan los nodos superiores a partir del valor de los inferiores. Según si estos nodos pertenecen a un nivel MAX o un nivel MIN, se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente.
4. Se repite el paso 3 hasta llegar al nodo superior (estado actual).
5. Se selecciona la jugada-nodo directamente accesible desde el nodo actual que maximiza el valor de la evaluación.
!!!side:10
El problema de muchos juegos (como el ajedrez o el Go) es que no es posible trabajar con el árbol completo de jugadas posibles (ya que requiere un árbol con una cantidad de nodos que supera los \(10^{40}\)), y tampoco se conoce una heurística que asegure una estrategia ganadora.
Debe destacarse que si no es posible realizar el árbol completo de jugadas, pero sí disponemos de una función que permite evaluar lo bueno que es un estado intermedio (por medio de una **heurística**), aún podemos hacer uso del algoritmo minimax para decidir cuál es el mejor movimiento posible a partir del estado actual. Por supuesto, dependerá de la calidad de la función heurística el que la estrategia que proporciona la ejecución del algoritmo sea ganadora o no $^{10}$.
Tal y como está definido, una de las formas más sencillas de implementar Minimax es por medio de un procedimiento recursivo de construcción del árbol. Cuando no es posible realizar la construcción completa, hay que decidir cuándo se realiza el corte, que puede venir dado por alguna de las condiciones siguientes:
* Gana algún jugador.
* Se han explorado \(N\) niveles (con \(N\) un parámetro prefijado).
* Se ha agotado el tiempo de exploración (parámetro prefijado).
* Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro.
Con las estructuras de datos adecuadas, es fácil implementar este algoritmo en cualquier lenguaje de programación. Por ejemplo, en Julia:
Ver código
~~~~~~~~Julia
struct JuegoGenerico
hijos::Function
evalua::Function
end
function minimax(nodo, prof, jugadorMax, g::JuegoGenerico)
if prof == 0 || isempty(g.hijos(nodo))
return g.evalua(nodo)
end
if jugadorMax
maxEval = -Inf
for n in g.hijos(nodo)
eval_hijo = minimax(n, prof - 1, false, g)
maxEval = max(maxEval, eval_hijo)
end
return maxEval
else
minEval = Inf
for n in g.hijos(nodo)
eval_hijo = minimax(n, prof - 1, true, g)
minEval = min(minEval, eval_hijo)
end
return minEval
end
end
~~~~
donde se supone que tenemos una estructura `JuegoGenerico` que contiene dos funciones imprescindibles: `hijos` (que devuelve los sucesores de un estado) y `evalua` (que evalúa un estado terminal) dependen del problema concreto a resolver.
La mayoría de juegos interesantes generan árboles de juego excesivamente grandes, de forma que no podemos expandir completamente el árbol hasta llegar a los nodos terminales. Por ello, suele ser común usar un algoritmo de profundidad limitada que solo expande algunos niveles del árbol, sin llegar a los nodos terminales. Pero en este caso, ¿cómo se calcula entonces la utilidad de un movimiento determinado?
Normalmente, para poder trabajar con una expansión limitada y poder usar algoritmos como Minimax se hace uso de **funciones de evaluación** que calculan la utilidad de estados no terminales, es decir, estiman el valor de una acción.
Otra posible generalización es hacia juegos donde no hay suma nula o hay más de 2 jugadores. En estos casos suele ser común considerar nodos que disponen de valores de utilidad como tuplas, y cada jugador intenta maximizar su propia componente, lo que a veces podría llevar a estrategias entre jugadores.
## Poda alfa-beta
El problema de la búsqueda Minimax es que el número de estados a explorar puede llegar a ser exponencial respecto al número de movimientos. Si $r$ es el factor de ramificación (cuántos hijos tiene cada nodo), y $m$ es el nivel de profundidad que vamos a alcanzar, entonces la complejidad en tiempo es del orden $O(r^m)$ y la complejidad en espacio del orden $O(rm)$.
La **Poda alfa-beta** es una técnica que reduce el número de nodos evaluados en el árbol de juego construido por el algoritmo Minimax. Para ello, la poda trata de eliminar partes grandes del árbol que se va construyendo de forma que se devuelva el mismo movimiento que devolvería este, podando ramas que se sepa que no van a influir en la decisión final.
La idea de esta técnica es que cada nodo se analiza teniendo en cuenta el valor que por el momento tiene el nodo y el valor que por el momento tiene su padre, lo que determina en cada momento un intervalo $(\alpha,\beta)$ de posibles valores que podría tomar el nodo. El significado intuitivo de estos parámetros en cada momento es:
* En los nodos MAX: $\alpha$ es el valor actual del nodo (que tendrá ese valor o superior), y $\beta$ es el valor actual del padre (que tendrá ese valor o inferior).
* En los nodos MIN: $\beta$ es el valor actual del nodo (que tendrá ese valor o inferior), y $\alpha$ es el valor actual del padre (que tendrá ese valor o superior).
* La poda se produce si en algún momento $\alpha \geq \beta$, y en ese momento no hace falta analizar los restantes sucesores del nodo. En nodos MIN, se denomina poda $\beta$, y en nodos MAX, poda $\alpha$.
El cambio que se introduce en el minimax habitual es que en esta nueva versión con poda se va actualizando el valor de los parámetros según se recorre el árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se está examinando sea peor que el valor actual de \(\alpha\) o \(\beta\) para MAX o MIN, respectivamente:
~~~~julia linenumbers
struct JuegoGenerico
hijos::Function
evalua::Function
end
function minimax_alphabeta(nodo, prof, α, β, jugadorMax, g::JuegoGenerico)
if prof == 0 || isempty(g.hijos(nodo))
return g.evalua(nodo)
end
if jugadorMax
maxEval = -Inf
for n in g.hijos(nodo)
eval_hijo = minimax_alphabeta(n, prof - 1, α, β, false, g)
maxEval = max(maxEval, eval_hijo)
α = max(α, eval_hijo)
if β <= α
break
end
end
return maxEval
else
minEval = Inf
for n in g.hijos(nodo)
eval_hijo = minimax_alphabeta(n, prof - 1, α, β, true, g)
minEval = min(minEval, eval_hijo)
β = min(β, eval_hijo)
if β <= α
break
end
end
return minEval
end
end
~~~~
donde usamos de una estructura de Juegos Genéricos similar a la del caso sin poda.
!!!ejemplo:Juego NIM
Supongamos que estamos implementando el juego de Nim, donde los jugadores toman entre 1 y 3 piedras de un montón de piedras. El jugador que tome la última piedra gana.
Una solución a este jego haciendo uso del algoritmo anterior podría ser:
Ver código
~~~~julia
# Función para obtener los hijos de un nodo
function hijos_nim(s)
return [s - i for i in 1:3 if s - i >= 0]
end
# Función para evaluar un estado del juego (aquí, +1 si el estado es favorable al jugador maximizante)
function evalua_nim(s)
return s == 0 ? -1 : 1
end
nim = JuegoGenerico(hijos_nim, evalua_nim)
# Uso del algoritmo Minimax con poda alfa-beta
function mov_optimo_nim(s, prof)
mejor_valor = -Inf
mejor_mov = nothing
α = -Inf
β = Inf
for n in hijos_nim(s)
valor = minimax_alphabeta(n, prof - 1, α, β, false, nim)
if valor > mejor_valor
mejor_valor = valor
mejor_mov = n
end
end
return mejor_mov
end
~~~~
donde, tal y como está programada la función `evaluate_nim`, favorece al jugador maximizante y penaliza al minimizante.
!!!side:11
Esto significa que en el caso perfecto, una búsqueda que haga uso de la poda alfa-beta proporciona una ganancia considerable, ya que permite explorar con igual coste la mitad de los nodos finales de un árbol con el doble de profundidad.
Es interesante estudiar cómo mejora el rendimiento del algoritmo en el mejor de los casos para saber si realmente se ha mejorado de alguna forma el algoritmo original. Según Knuth y Moore, si los nodos están perfectamente ordenados, el número de nodos terminales considerados en una búsqueda de profundidad \(m\) con poda alfa-beta es el doble de los nodos terminales considerados en una búsqueda de profundidad \(m/2\) sin poda alfa-beta $^{11}$.
Hay otras opciones para realizar podas como, por ejemplo, dejar de explorar un subárbol que ofrece pocas posibilidades de mejora sobre otros caminos que ya han sido explorados, es decir, que su evaluación sea solo ligeramente más favorable que otra rama ya explorada.
!!!ejemplo:3 en raya
Vamos a resolver el juego 3 en raya con Minimax pero haciendo uso de una heurística intermedia (no necesariamente para estados terminales).
La heurística evaluará el número de líneas potenciales (filas, columnas y diagonales) que pueden ser completadas por 'X' y 'O'. A cada jugador se le asignará un puntaje basado en cuántas de sus fichas hay en las líneas que todavía están abiertas (es decir, no contienen fichas del oponente):
* $+3$ puntos por cada línea en la que 'X' tiene $2$ fichas y la tercera posición está vacía.
* $+1$ punto por cada línea en la que 'X' tiene $1$ ficha y las otras posiciones están vacías.
* $-3$ puntos por cada línea en la que 'O' tiene $2$ fichas y la tercera posición está vacía.
* $-1$ punto por cada línea en la que 'O' tiene $1$ ficha y las otras posiciones están vacías.
# Incertidumbre como Adversario
En muchos problemas el resultado de una acción no es determinista y conlleva un cierto grado de incertidumbre. Hay algunas formas de abordar este problema, pero una de las más comunes, y que reutiliza lo que hemos presentado hasta aquí, es considerar que nos enfrentamos a un adversario que juega al azar (o con cierto grado de azar).
Mientras que en el Minimax clásico se presupone que el adversario va a hacer la mejor jugada posible para él (la peor para nosotros), en este caso consideramos que el resultado será el promedio de los resultados posibles, es decir, la esperanza de la utilidad, y por eso el método se llama **ExpectiMax**.
En este caso, la utilidad de un nodo se calcula como la media (ponderada) de las posibles salidas de sus hijos. Como no tomamos el máximo, sino la media, no podemos usar podas al estilo alfa-beta vistas anteriormente.
Si mezclamos adversarios reales y cierto grado de azar, podemos dar una extensión mezcla de las dos anteriores que se denomina **ExpectiMinimax**.
De todas formas, veremos en la siguiente sección otra forma de abordar este tipo de problemas por medio de un procedimiento inspirado en búsquedas aleatorias en el árbol de jugadas: **Monte Carlo Tree Search**.
Como hemos comentado, el problema que presenta un algoritmo como Minimax, y otros algoritmos similares, es que el tamaño del árbol de jugadas/estados puede ser tan grande que tanto la construcción como la búsqueda dentro del árbol se vuelva impracticable, algo que ocurre con relativa facilidad si el juego tiene un mínimo de complejidad (por ejemplo, un alto promedio de movimientos disponibles por turno), haciendo que el tamaño del árbol crezca exponencialmente por niveles. Hemos visto que para minimax se han proporcionado métodos para mitigar este problema, como por ejemplo **acotar la profundidad de búsqueda hacia adelante** (y posteriormente usar una función de evaluación para estimar cómo de buena es esa vía, aunque no hayamos llegado a un estado final del juego), o **podar ramas** para evitar visitar aquellas opciones de juego que, a priori, puedan resultar menos beneficiosas.
Sin embargo, la mayoría de estas técnicas requieren de un conocimiento previo del juego que puede resultar difícil de obtener, y podemos encontrar casos que cubren todas las opciones, desde juegos en los que esta aproximación es óptima (como en el caso del 3 en raya), hasta aquellos para los que es posible generar jugadores artificiales de una calidad aceptable (como en el caso del ajedrez), o incluso algunos en los que estas técnicas se muestran claramente insuficientes (como en el caso del Go, sobre todo en sus versiones con tableros completos de tamaño $19\times 19$).
# Monte Carlo Tree Search
Como respuesta a este tipo de aproximaciones 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 **juegos 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 jugadores más fuertes;
* **no requiere** necesariamente de un **conocimiento específico del juego**, por lo que puede ser utilizado como motor de juego general;
* y es **adaptable a juegos** que incorporan **aleatoriedad** en las reglas.
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 de jugadas 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. 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.
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:12
Esta técnica de muestreo recibe el nombre de MonteCarlo.
![](./img/chessmcts.gif width=400px align="left")La idea de ir haciendo jugadas al azar desde la posición actual para muestrear cómo se comportan las distintas acciones que podemos tomar no es nueva $^{12}$. El problema es que no se sabía cómo muestrear el árbol de jugadas para que los resultados obtenidos representasen con cierta fiabilidad la bondad de las acciones posibles.
Esencialmente, podemos ver **cada uno de los movimientos posibles como una variable aleatoria cuyo muestreo nos informa acerca de lo bueno o malo que es dicho movimiento**. Pero, ¿qué ocurre si el árbol de jugadas se ramifica tanto (como suele ser habitual en la mayoría de los juegos 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é jugadas 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 hemos encontrado 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**.
!!!note
**Edición**: Tras la escritura de esta entrada se ha publicado [un post similar](https://int8.io/monte-carlo-tree-search-beginners-guide/) que quizás también pueda interesar al lector, ya que introduce algunas notas acerca de cómo se ha usado esta técnica para crear los famosos Alpha Go (que se [enfrentó con Lee Sedol](https://es.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol)) y [Alpha Zero](https://deepmind.com/blog/alphago-zero-learning-scratch/) (que generaliza el método para otros juegos de tablero, consiguiendo niveles increíblemente altos a partir de un conocimiento inicial nulo del juego).
## 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:13
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 $^{13}$.
## Aplicación a Búsquedas
![](./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 juegos, las jugadas válidas), y los premios de las máquinas se cambian por la bondad del camino encontrado (en juegos, por la recompensa de la sucesión de movimientos realizados).
En un proceso estándar de MonteCarlo aplicado a un juego:
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, para cualquier turno, puede haber muchos movimientos posibles pero sólo uno o dos que son buenos, por lo que, si se elige un movimiento aleatorio en cada turno, 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:14
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 nodo/estado alcanzado como un problema de tragaperras múltiples. Comenzando por el nodo raíz, que representa el estado actual del juego/problema, seleccionamos recursivamente el nodo más urgente de acuerdo a una función de utilidad (en nuestro caso, por medio del algoritmo UCB1), hasta que se alcanza un nodo que, o bien representa un estado terminal, o bien no está completamente extendido $^{14}$.
2. La segunda fase, **Expansión**, ocurre cuando ya no se puede aplicar la fase anterior. Para ello, se elige aleatoriamente una posición sucesora no visitada del nodo que no estaba completamente extendido y se añade un nuevo nodo al árbol de estadísticas con el fin de completar dicha información.
!!!side:15
Para juegos con un factor de ramificación pequeño, como el 3 en raya, 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 partida 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 $^15$. Junto a la partida completa se obtiene un valor (premio, recompensa, etc) que determina la utilidad de esa rama para el jugador.
4. Finalmente, la cuarta fase es la de **Actualización** o **Retropropagación**. Con el estado final de juego alcanzado en la fase anterior se actualizan las estadísticas de todas las posiciones previas visitadas durante la simulación completa que se ejecutó a partir del nuevo nodo (incluyendo la cuenta de ganancias si el jugador ganó 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 el sucesor con mayor ganancia, el que ha sido visitado en mayor número de partidas ganadoras, el 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.
* En la fase de Expansión: Estrategia de **creación de nuevos nodos**. 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é nodo se crea).
* En la fase de Simulación: Estrategia de **generación de una partida completa** a partir del nuevo nodo creado. Aquí es relativamente común introducir, si se considera necesario, algún conocimiento específico del dominio del problema (juego).
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 el movimiento que finalmente se elija converge hacia el movimiento óptimo real (aunque esta convergencia puede requerir muchísimo tiempo, dependiendo del juego), como ocurre en el problema de las tragaperras múltiples.
Cuando se aplica el algoritmo UCB1 como estrategia de selección del nodo 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**):
$$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 nodo $s_0$ (el padre de $s$) ha sido visitado, $N(s)$ es el número de veces que el nodo 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 jugadas.
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 tiende al árbol Minimax y por tanto es óptimo.
## 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₀)
G ← Simula(s(n))
Retropropaga(n,G)
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,G)
Mientras n no sea nulo
N(n) ← N(n) + 1
Q(n) ← Q(n) + G
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 jugador gana; $0$, cuando el jugador pierde; y $0.5$, cuando se produce un empate entre ambos jugadores.
Puedes encontrar en [este link](https://citeseerx.ist.psu.edu/pdf/c37f1baac3c8ba30250084f067167ac3837cf6fd) un estudio muy interesante sobre MCTS y sus variantes y aplicaciones. La [página de la wikipedia](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) (fuertemente basada en el estudio anterior) puede ser también un primer punto de contacto para aprender algo más sobre el método.
## Implementación en Julia
!!!side:16
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 $^{16}$. 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 juego, aparte de sus jugadas legales y condiciones finales; esto significa que, como hemos visto más arribe, 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 juegos 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 jugadas 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 juego**: 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 juego modelado puede aprovecharse en el árbol para filtrar jugadas inverosímiles o en las simulaciones para producir jugadas que se parezcan más a las jugadas que se producirían entre oponentes humanos. Esto significa que los resultados de las jugadas 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 jugadas ganadoras 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.
## Más allá de los Juegos con Adversario
Como hemos visto, MCTS es una técnica muy potente que modela adecuadamente los juegos con adversario, pero su uso va más allá de este pasatiempo y la misma idea se puede usar para modelar y apoyar la toma de decisiones bajo incertidumbre en agentes. Cuando ampliamos su uso a contextos generales de toma de decisiones, entran en juego conceptos que modelan secuencias de decisiones en entornos estocásticos, es decir, entornos donde las acciones pueden tener resultados inciertos.
Como hemos comprobado, en lugar de resolver problemas de forma exacta, MCTS usa simulaciones para explorar posibles futuros. La idea clave en el entorno de la toma de decisiones es que el agente puede probar diferentes secuencias de acciones simulando posibles desenlaces y, a partir de los resultados de esas simulaciones, mejorar los resultados de sus acciones.
Para agentes que deben actuar en entornos inciertos, se trata de un ciclo de percepción-acción-recompensa, donde el agente:
1. **Percibe** el estado del entorno.
2. **Toma una acción** que lo lleva a un nuevo estado.
3. **Recibe una recompensa** que informa cómo de buena fue la acción tomada.
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.
Los **Procesos de Decisión de Markov (MDP)** son uno de los marcos matemáticos desarrollados para modelar decisiones secuenciales bajo incertidumbre. Un MDP está definido por (nótese la semejanza con la definición de Espacio de Estados y Juego formal que dimos anteriormente):
- **Estados**: Una representación del entorno en un momento dado.
- **Acciones**: Decisiones que el agente puede tomar.
- **Transiciones**: Probabilidades de moverse de un estado a otro dado una acción.
- **Recompensas**: Las ganancias inmediatas que obtiene el agente tras cada acción.
El objetivo de un agente en un MDP es encontrar una política óptima que le guíe en la secuencia de acciones que maximiza la recompensa esperada acumulada a largo plazo (valor esperado). En este sentido, **MCTS** puede utilizarse siguiendo los mismos pasos para aproximar la política óptima en MDPs cuando:
- El espacio de estados es muy grande.
- No se tiene información completa sobre las transiciones o recompensas.
!!!ejemplo: Aplicación en un MDP
Imagina un robot que debe decidir entre moverse hacia diferentes habitaciones en un entorno donde las transiciones tienen incertidumbre (hay una probabilidad de que choque o se desvíe, o puede haber incertidumbre en el entorno que el agente percibe). El robot necesita encontrar una política que maximice las recompensas (por ejemplo, energía recogida, tiempo minimizado, etc.).
1. **Estado**: La posición actual del robot.
2. **Acciones**: Moverse hacia una habitación específica.
3. **Transiciones**: Probabilidades de éxito o fallo de los movimientos (posiblemente basadas en sensores imprecisos).
4. **Recompensas**: Energía encontrada en una habitación, o tiempo minimizado.
MCTS puede usarse para simular múltiples secuencias de movimientos, considerando los posibles errores de navegación y las recompensas acumuladas, y luego elegir la mejor acción.
Los beneficios de usar MCTS en entornos estocásticos son inmediatos:
- **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 equilibra la exploración de acciones nuevas y la explotación de las conocidas.
- **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, podemos concluir que MCTS es 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.