Árbol de búsqueda Monte Carlo
En ciencias de la computación el árbol de búsqueda Monte Carlo (en inglés MCTS) es un algoritmo de búsqueda heurístico para algunos tipos de proceso de toma de decisiones, sobre todo los que trabajan con juegos. Un ejemplo destacado reciente es en los programas Go,[1] y también se ha utilizado en otros juegos de mesa, así como en videojuegos en tiempo real y juegos no deterministas como el póquer.
Modo de operación
editarEl enfoque del árbol de búsqueda Monte Carlo se encuentra en el análisis de los movimientos más prometedores, ampliando el árbol de búsqueda basado en un muestreo aleatorio del espacio de búsqueda. La aplicación de búsqueda de árbol de Monte Carlo en los juegos se basa en muchos playoffs. En cada emisión, el juego, se juega de salida hasta el final mediante la selección de movimientos al azar. El resultado final del juego de cada playout se utiliza para ponderar los nodos en el árbol del juego de manera que los mejores nodos son más propensos a ser elegidos en futuros playoffs.
La forma más básica de utilizar los playouts es aplicar el mismo número de playouts después de cada movimiento legal del jugador actual, a continuación, elegir el movimiento que llevó a la mayor cantidad de victorias.[2] La eficacia de este método llamado Búsqueda Pura de Juego Monte Carlo - a menudo aumenta con el tiempo a medida que más playouts se asignan a los movimientos que han dado lugar con frecuencia a la victoria del jugador (en playouts anteriores).Las plena búsqueda de árbol de Monte Carlo emplean este principio de forma recursiva en muchas profundidades del árbol de juego. Cada ronda de búsqueda de árbol de Monte Carlo consiste en cuatro pasos:[3]
- Selección: empezar desde la raíz R y seleccionar nodos hijos sucesivos hasta alcanzar un nodo hoja L. La sección de abajo describe más de una manera de elegir nodos hijos, que permiten que el árbol de juego se expanda hacia movimientos más prometedores, que es la esencia del árbol de búsqueda Monte Carlo .
- Expansión: a menos que L termine el juego con una victoria/pérdida para cualquiera de los jugadores, crear uno o más nodos hijos y elegir entre ellos un nodo C. Los nodos hijos son cualquier movimiento válido desde la posición del juego definida por L.
- Simulación: jugar una reproducción aleatoria desde el nodo C.
- Retropropagación: utilizar el resultado de la reproducción para actualizar la información en los nodos en el camino de C a R.
Pasos de ejemplo de una ronda se muestran en la siguiente figura. Cada nodo del árbol almacena el número de ganados/jugados playouts .
.svg)
Véase también
editar- AlphaGo, un programa Go equivalente a los humanos que utiliza tanto el árbol de búsqueda Monte Carlo y el aprendizaje profundo.
Referencias
editar- ↑ «MCTS.ai: Everything Monte Carlo Tree Search». Consultado el 19 de febrero de 2012.
- ↑ Brügmann, Bernd (1993). Monte Carlo Go. Technical report, Department of Physics, Syracuse University.
- ↑ G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, B. Bouzy (2008). «Progressive Strategies for Monte-Carlo Tree Search». New Mathematics and Natural Computation 4 (3): 343-359. doi:10.1142/s1793005708001094.
Datos: Q11785332
