La búsqueda de árboles de Monte Carlo (MCTS) es un algoritmo de búsqueda heurística en árboles utilizado para 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 un muestreo aleatorio del espacio de búsqueda. El MCTS se combinó con redes neuronales en 2016 y desde entonces se ha aplicado a juegos como ajedrez, shogi, damas, backgammon, bridge, Go, Scrabble y Clobber, así como a videojuegos de estrategia por turnos y otros dominios.
El algoritmo opera mediante simulaciones repetidas, llamadas playouts o rollouts, donde el juego se simula hasta el final con movimientos aleatorios. Los resultados de estas simulaciones se utilizan para ponderar los nodos del árbol de juego, guiando selecciones futuras hacia movimientos más prometedores. Cada ronda de MCTS consta de cuatro pasos: selección, expansión, simulación y retropropagación.
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 playouts aleatorios, demostrando su eficacia en el tres en raya y otros juegos. En 1989, W. Ertel, J. Schumann y C. Suttner aplicaron métodos similares a la demostración automática de teoremas, mejorando los tiempos de búsqueda. En 1992, B. Brügmann utilizó el enfoque en un programa de Go. En 2002, Chang et al. propusieron el Muestreo Adaptativo Multietapa (AMS), que introdujo la exploración y explotación basadas en UCB en árboles de Monte Carlo, sentando las bases para UCT.
En 2006, Rémi Coulom acuñó el término búsqueda de árboles de Monte Carlo, mientras que L. Kocsis y Cs. Szepesvári desarrollaron el algoritmo UCT (Límites Superiores de Confianza aplicados a Árboles). S. Gelly et al. implementaron UCT en el programa MoGo, que alcanzó nivel dan en Go de 9x9 en 2008. En 2012, el programa Zen ganó una partida contra un jugador amateur de 2 dan en un tablero de 19x19. El AlphaGo de Google DeepMind, que utiliza MCTS con redes neuronales, se convirtió en el primer programa en vencer a un jugador profesional de Go en 2015 y derrotó a Lee Sedol en 2016.
Principio de funcionamiento
El enfoque de MCTS se centra en analizar los movimientos más prometedores expandiendo el árbol de búsqueda basándose en un muestreo aleatorio. Cada playout simula un juego hasta el final, y los resultados ponderan los nodos para que los mejores movimientos se elijan con mayor frecuencia. La Búsqueda Pura de Monte Carlo aplica playouts iguales a cada movimiento legal y selecciona el que obtiene más victorias.
Cada ronda de MCTS implica cuatro pasos:
- Selección: Comenzando desde la raíz, se seleccionan nodos hijos sucesivos hasta llegar a un nodo hoja.
- Expansión: Se crean uno o más nodos hijos desde la hoja, a menos que el juego haya terminado.
- Simulación: Se completa un playout aleatorio desde el nuevo nodo.
- Retropropagación: Se actualizan las estadísticas de los nodos a lo largo del camino desde el nuevo nodo hasta la raíz.
Algoritmo UCT
El algoritmo UCT equilibra exploración y explotación mediante la fórmula de Límites Superiores de Confianza. Selecciona nodos hijos basándose en su tasa de victorias promedio y una bonificación para nodos menos visitados, lo que permite que el árbol se expanda hacia movimientos prometedores mientras sigue explorando alternativas. Este enfoque es central para la eficiencia de MCTS.
Aplicaciones
MCTS se ha utilizado en programas para juegos de mesa como Hex, Havannah, Game of the Amazons y Arimaa, así como en videojuegos en tiempo real como Ms. Pac-Man y Fable Legends. También se aplica a juegos no deterministas como skat, póker, Magic: The Gathering y Settlers of Catan. Más allá de los juegos, MCTS se ha explorado en problemas de planificación y optimización.
Importancia
La combinación de MCTS con redes neuronales profundas, como en AlphaGo, marcó un hito en la inteligencia-artificial y el aprendizaje-automático. Demostró cómo la búsqueda heurística puede integrarse con el aprendizaje-profundo para lograr un rendimiento sobrehumano en dominios complejos, influyendo en investigaciones posteriores en ia-generativa y otras áreas.