La búsqueda de árbol de Monte Carlo (MCTS) es un algoritmo heurístico de búsqueda en árboles utilizado en procesos de decisión, particularmente en software que juega juegos de mesa. Resuelve el árbol de juego centrándose en los movimientos más prometedores, expandiendo el árbol de búsqueda basándose en el muestreo aleatorio del espacio de búsqueda. MCTS se combinó con redes neuronales en 2016 y desde entonces se ha aplicado a juegos como Ajedrez, Shogi, Damas, Backgammon, Bridge de contrato, Go, Scrabble y Clobber, así como a videojuegos de estrategia por turnos y aplicaciones no relacionadas con juegos.
El algoritmo opera mediante repeticiones de jugadas, también llamadas roll-outs, donde el juego se juega hasta el final con movimientos aleatorios. Los resultados de estas jugadas se utilizan para ponderar los nodos del árbol de juego, haciendo que los nodos mejores sean más propensos a ser elegidos en futuras jugadas. Este enfoque difiere de la búsqueda minimax tradicional al evitar una función de evaluación estática, basándose en cambio en resultados simulados.
Historia
El método de Monte Carlo, que utiliza muestreo aleatorio para problemas deterministas, se remonta a la década de 1940. En 1987, Bruce Abramson combinó la búsqueda minimax con un modelo de resultado esperado basado en jugadas aleatorias, demostrando su precisión e independencia de dominio en tres en raya, Othello y ajedrez. En 1989, W. Ertel, J. Schumann y C. Suttner aplicaron métodos similares a la demostración automática de teoremas, mejorando los algoritmos de búsqueda no informados. En 1992, B. Brügmann utilizó por primera vez este enfoque en un programa de juego de Go. En 2002, Chang et al. propusieron el Muestreo Adaptativo de Múltiples Etapas (AMS), que introdujo la exploración y explotación basada en UCB en árboles de Monte Carlo, sentando las bases para UCT.
En 2006, Rémi Coulom acuñó el nombre de búsqueda de árbol de Monte Carlo, mientras que L. Kocsis y Cs. Szepesvári desarrollaron el algoritmo UCT (Límites de Confianza Superior aplicados a Árboles). S. Gelly et al. implementaron UCT en el programa MoGo, que alcanzó el nivel dan en Go 9×9 para 2008. El programa Fuego también comenzó a derrotar a fuertes aficionados en Go 9×9 alrededor de esa época. En enero de 2012, el programa Zen ganó 3:1 contra un jugador aficionado de 2 dan en un tablero de 19×19.
Google DeepMind desarrolló AlphaGo, que en octubre de 2015 se convirtió en el primer programa en vencer a un jugador humano profesional de Go sin ventajas en un tablero de tamaño completo. En marzo de 2016, AlphaGo derrotó a Lee Sedol 4:1, obteniendo un nivel honorario de 9 dan. AlphaGo combinó MCTS con redes neuronales artificiales, un método de aprendizaje profundo, para la evaluación de políticas y valores, marcando un hito significativo en el aprendizaje automático.
Principio de Funcionamiento
MCTS se centra en analizar los movimientos más prometedores expandiendo el árbol de búsqueda basándose en el muestreo aleatorio. Cada ronda consta de cuatro pasos:
- Selección: Comenzando desde el nodo raíz (estado actual del juego), se seleccionan nodos hijos sucesivos hasta alcanzar un nodo hoja. La selección está sesgada para favorecer movimientos prometedores, a menudo utilizando UCT.
- Expansión: A menos que el nodo hoja termine el juego, se crean uno o más nodos hijos que representan movimientos legales.
- Simulación: Se completa una jugada aleatoria desde un nodo hijo elegido, jugando hasta que el juego se decida.
- Retropropagación: Se actualizan los nodos en el camino desde el hijo hasta la raíz con el resultado de la jugada, incrementando los contadores de simulaciones y los contadores de victorias de manera apropiada.
En juegos con empates, un empate incrementa el numerador en 0.5 y el denominador en 1 para ambos jugadores. Esto asegura que las elecciones de cada jugador se expandan hacia movimientos que maximicen su propio valor.
Algoritmo UCT
El algoritmo UCT, introducido en 2006, aplica Límites de Confianza Superior a la búsqueda en árboles. Equilibra la exploración y la explotación seleccionando nodos hijos basándose en su recompensa promedio y una bonificación para nodos menos visitados. Esto permite que el árbol de búsqueda se expanda hacia los movimientos más prometedores mientras aún explora alternativas. UCT se convirtió en el estándar para implementaciones de MCTS, incluyendo en MoGo y programas posteriores.
Aplicaciones
MCTS se ha utilizado en programas para juegos de mesa como Hex, Havannah, Juego de las Amazonas y Arimaa, así como en videojuegos en tiempo real como Ms. Pac-Man y Fable Legends. También maneja juegos no deterministas como Skat, Póker, Magic: The Gathering y Settlers of Catan. En juegos de estrategia por turnos, Total War: Rome II utiliza MCTS en su IA de campaña de alto nivel. Más allá de los juegos, MCTS tiene aplicaciones en problemas de planificación y optimización.
La combinación de MCTS con redes neuronales, como en AlphaGo, ha demostrado ser particularmente efectiva. Este enfoque híbrido utiliza redes neuronales para guiar la selección y evaluar posiciones, reduciendo la necesidad de jugadas aleatorias extensas. Programas posteriores como AlphaZero han extendido esto a Ajedrez y Shogi, logrando un rendimiento sobrehumano.