Búsqueda de árbol de Monte Carlo

La búsqueda de árbol de Monte Carlo, abreviada MCTS, no intenta revisar todas las variantes con la misma profundidad. Construye un árbol poco a poco y usa los resultados acumulados para decidir dónde invertir la siguiente porción de cálculo. Una jugada visitada muchas veces no es automáticamente buena, pero sus estimaciones suelen estar mejor respaldadas.

Un ciclo de MCTS

1. Selección: parte de la posición inicial y recorre ramas existentes, equilibrando opciones que ya parecen fuertes con opciones todavía poco exploradas.
2. Expansión: agrega al árbol una posición o jugada que aún no había desarrollado.
3. Evaluación: estima el resultado desde esa nueva posición. Los métodos clásicos pueden completar partidas simuladas; los sistemas modernos también pueden usar una red neuronal, un modelo entrenado para reconocer patrones, que valore la posición.
4. Retropropagación: devuelve el resultado por la ruta recorrida y actualiza sus visitas y estimaciones.

La repetición de este ciclo combina explotación y exploración. Explotar significa profundizar donde ya hay buenas señales. Explorar significa comprobar alternativas inciertas para no descartar demasiado pronto una sorpresa. La regla exacta para equilibrarlas depende de la implementación.

A diferencia de minimax, MCTS suele decidir cuánto examinar una rama según la evidencia reunida durante la propia búsqueda, no solo según una profundidad uniforme. En algunos programas de ajedrez basados en redes neuronales, una red aporta una política, que sugiere jugadas probables, y un valor, que estima el resultado. Eso cumple una función relacionada con una función de evaluación, aunque el proceso completo sea distinto.