Árbol de búsqueda Monte Carlo

From FdIwiki ELP
Jump to: navigation, search

Monte Carlo Tree Search (MCTS) es un metodo para toma optima de decisiones en problemas de Inteligencia Artificial. Combina la generalidad de simulaciones aleatorias con la precisión de una búsqueda en el árbol de posibilidades. MCTS no requiere una función de evaluación de posición, en contraste con la búsqueda alfa beta. Esta basado en una exploración aleatoria del espacio de búsqueda, pero usa los resultados de previas exploraciones. Para ello, MCTS construye gradualmente un árbol en memoria, que mejora sucesivamente estimando los valores de los movimientos mas prometedores.


Modo de operación

MCTS consiste en cuatro etapas principales, repetidas tantas veces como tiempo se disponga. En cada una de las iteraciones se parte de la situación actual del juego.

  • Selección: El árbol se recorre desde el nodo raíz hasta alcanzar un nodo hoja. Se toma una rama u otra dependiendo de la estrategia de selección que se emplee y la información almacenada en el nodo en ese momento, como el valor y el numero de visitas. Dentro de las diferentes opciones, UCT (Upper Confidence bounds applied to Trees) es la mas utilizada por su simplicidad y eficiencia. La estrategia UCT calcula para cada uno de los movimientos posibles una combinación de dos valores, la tasa de éxito de ese nodo y la relación entre el numero de veces que se ha visitado el nodo padre y el numero de veces que se visitó dicho nodo (hijo). El primer valor está relacionado con la explotación y el segundo con la exploración . A través de un coeficiente C utilizado en la combinación de ambos valores, se puede dar mayor prioridad a la explotación o exploración. Un punto importante a favor de la estrategia UCT, es su independencia del dominio de aplicación.
    UCT: ValUCT(Ni) = tasaExitoi + C ∗ raíz cuadrada de (ln(np)/ni)
    Donde: np y ni son el numero de visitas al nodo padre y al nodo Ni respectivamente, C es el coeficiente de exploración. 
  • Expansión: Se añaden nodos al árbol MCTS según una estrategia de expansión. Según el criterio, se puede expandir siempre que se visite un nodo, o cuando se alcanza un determinado numero de visitas mínimo, lo que permite ahorrar espacio en memoria, regulando cuanto crece el árbol en relación al numero de ciclos del algoritmo. Además, se pueden tomar dos caminos a la hora de expandir: en cada expansión añadir un solo nodo hijo de todos los posibles movimientos o añadir directamente todos los nodos hijos.
  • Simulación: Se simula una partida a partir del nodo hoja alcanzado en las fases anteriores. Durante esta partida, el programa juega solo, realizando los movimientos de todos los jugadores que intervienen hasta que finalice y se obtenga un resultado. Las estrategias que se utilizan consisten o bien utilizar movimientos aleatorios o combinar la aleatoriedad con una heurística asociada al problema concreto. En estos casos es necesario buscar un equilibrio entre la exploración, que da la aleatoriedad, y la explotación, que dirige hacia un movimiento mas prometedor.
  • Retropropagación: El resultado de la simulación se propaga hacia los nodos atravesados previamente. Partiendo del nodo hoja y subiendo por la relación con los nodos padres hasta llegar a la raíz, se actualiza cada nodo, incrementando en una unidad el numero de visitas y actualizando su valor con el resultado de la simulación. Por ultimo, a la hora de seleccionar el movimiento final, se considerar ´ a el mejor hijo del nodo raíz, es decir, el movimiento mas prometedor de acuerdo a la información recaudada. Para determinar qué nodo “es mejor” se pueden tomar diferentes criterios, considerando la tasa de éxito, o el numero de visitas, etc.


                      MCTS (English).png

Referencias