Monte Carlo Tree Search (MCTS)
La búsqueda de árboles de Monte Carlo (MCTS) elige acciones construyendo un árbol de búsqueda a partir de simulaciones y centrándose en los movimientos prometedores. Se utiliza en AlphaGo y en robótica.
La búsqueda de árbol Monte Carlo (MCTS) es un algoritmo de planificación que elige la siguiente acción haciendo crecer un árbol de futuros posibles a partir de muchas simulaciones, y dedica más recursos a las jugadas que parecen más prometedoras. Solo necesita una forma de generar movimientos y resultados válidos, como las reglas de un juego o un simulador, y no requiere una función de evaluación escrita a mano. También es un algoritmo interrumpible en cualquier momento: detenerlo devuelve la mejor jugada encontrada hasta ese momento, y disponer de más tiempo mejora la respuesta. Rémi Coulom dio nombre al método en 2006, el mismo año en que Levente Kocsis y Csaba Szepesvári publicaron UCT, la regla de selección que se convirtió en su forma estándar. En pocos años, MCTS transformó el Go por ordenador, más tarde impulsó AlphaGo y AlphaZero, y ahora se utiliza para planificar el comportamiento de robots y vehículos, y para explorar pasos de razonamiento en modelos de lenguaje grandes (LLMs).
Cómo funciona MCTS#
La búsqueda mantiene un árbol cuya raíz es la posición actual y cuyos nodos guardan el número de visitas y cuántas de ellas acabaron en victoria. Cada iteración consta de cuatro fases:
- Selección: Desde la raíz, baja por los nodos explorados por completo y elige el hijo con la puntuación UCT más alta, que equilibra las tasas de victoria elevadas con las jugadas que se han probado pocas veces.
- Expansión: En el primer nodo con una jugada sin probar, añade esa jugada como nuevo hijo.
- Simulación: Juega desde el nuevo hijo hasta el final de la partida, tradicionalmente con movimientos aleatorios, para obtener un resultado.
- Retropropagación: Recorre de vuelta el camino y actualiza el recuento de visitas y el total de victorias de cada nodo con el resultado.
Cuando se agotan los recursos disponibles, el algoritmo juega el hijo de la raíz más visitado, una opción más estable que la que tiene el promedio más alto.
Equilibrio entre exploración y explotación#
UCT trata la elección en cada nodo como un problema del bandido multiarmed y aplica la fórmula UCB1: la puntuación de un hijo es su tasa de victorias w/n más c·√(ln N / n), donde n es el número de visitas del hijo, N el de su padre y c una constante de exploración, √2 en teoría y ajustada en la práctica. El segundo término disminuye a medida que se prueba más una jugada, de modo que unas pocas victorias afortunadas no desplazan a las demás y, con el tiempo, se vuelve a probar una jugada desatendida.
Este ejemplo de Python ejecuta MCTS en un juego sencillo: los jugadores retiran de una a tres piedras de un montón de 10, y gana quien retira la última piedra.
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")Retirar dos piedras obtiene 1889 de las 2000 visitas y gana el 91 % de sus simulaciones, frente a 68 visitas si se retira una y 43 si se retiran tres. Es la jugada ganadora: dejar 8, un múltiplo de 4, permite al primer jugador responder a cada jugada devolviendo el montón a un múltiplo de 4 hasta que se vacía. La búsqueda la encontró basándose únicamente en simulaciones aleatorias y estadísticas de visitas, sin codificar ninguna estrategia.
De AlphaGo a AlphaZero y MuZero#
El factor de ramificación medio del Go, de unos 250 movimientos legales frente a unos 35 en ajedrez, lo hacía inabordable para la búsqueda exhaustiva, y MCTS impulsó el aumento de la fuerza del Go por ordenador desde finales de la década de 2000. AlphaGo, de DeepMind, guio MCTS con una red de políticas que proponía movimientos probables y evaluaba posiciones mediante una red de valor y simulaciones rápidas, y en marzo de 2016 derrotó a Lee Sedol por 4-1. AlphaZero y MuZero fueron más allá. AlphaZero prescindió por completo de las simulaciones, puntuó las posiciones hoja con una red de valor y entrenó esa red con partidas que jugó contra sí misma, utilizando los recuentos de visitas de cada búsqueda como objetivo para su red de políticas, lo que convierte MCTS en un paso de mejora de políticas dentro del aprendizaje por refuerzo. MuZero ejecutó la misma búsqueda dentro de un modelo aprendido del entorno, por lo que jugó al Go, al ajedrez, al shogi y a juegos de Atari sin conocer sus reglas.
MCTS para planificación y razonamiento#
Los robots y los vehículos autónomos usan MCTS para planificar ante situaciones inciertas, como incorporarse al tráfico, y variantes como POMCP lo amplían a los procesos de decisión de Markov parcialmente observables mediante el seguimiento de una creencia sobre estados ocultos. Una búsqueda que planifica a partir de imágenes de cámara necesita un estado para su raíz: por ejemplo, un brazo robótico que juega al ajedrez puede usar un modelo Ultralytics YOLO26 entrenado con imágenes de tableros para localizar cada pieza, y la posición reconstruida se convierte en la raíz de la búsqueda.
En el razonamiento de los LLM, cada nodo representa una solución parcial y cada arista, un paso de razonamiento; un modelo de recompensa de proceso o una comprobación de la respuesta puntúa las ramas. El rStar-Math de Microsoft utilizó MCTS con un modelo de preferencias de proceso para elevar la puntuación de Qwen2.5-Math-7B del 58,8 % al 90,0 % en el benchmark MATH. Tree of Thoughts explora los pasos de razonamiento mediante búsqueda en anchura o en profundidad. MCTS ha sido más difícil de utilizar durante el entrenamiento: DeepSeek lo incluyó entre los intentos fallidos para DeepSeek-R1, porque el espacio de secuencias de tokens es mucho mayor que el de un juego de mesa y es difícil entrenar el modelo de valor que guía la búsqueda. En su lugar, entrenó R1 con aprendizaje por refuerzo con recompensas verificables.










