Licencia YOLO
Volver al glosario de Ultralytics

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:

  1. 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.
  2. Expansión: En el primer nodo con una jugada sin probar, añade esa jugada como nuevo hijo.
  3. Simulación: Juega desde el nuevo hijo hasta el final de la partida, tradicionalmente con movimientos aleatorios, para obtener un resultado.
  4. 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.

Explora las soluciones

Visión artificial en el deporte

Visión artificial en el deporte

Descubre cómo Ultralytics YOLO impulsa la visión artificial en el deporte con el seguimiento de jugadores y balones, analíticas de rendimiento, información útil para entrenadores y rehabilitación de deportistas.
Más información
Visión artificial para imágenes aéreas

Visión artificial para imágenes aéreas

Convierte imágenes aéreas y de drones en información útil en tiempo real para la agricultura, la acuicultura, la conservación y el análisis geoespacial con Ultralytics YOLO.
Más información
Visión artificial en el sector aeroespacial

Visión artificial en el sector aeroespacial

Aplica la visión artificial en el sector aeroespacial con Ultralytics YOLO para inspeccionar aeronaves, detectar objetos extraños en pistas, gestionar operaciones en tierra y detectar defectos en materiales compuestos.
Más información
Visión artificial en seguridad

Visión artificial en seguridad

Protege todas tus instalaciones con los modelos Ultralytics YOLO. La IA visual permite supervisar perímetros, detectar amenazas, reconocer matrículas y mejorar la seguridad laboral.
Más información
Visión artificial en robótica

Visión artificial en robótica

Potencia máquinas más inteligentes con los modelos Ultralytics YOLO. La IA visual en robótica impulsa la navegación autónoma, la percepción, el seguimiento de objetos y el control en tiempo real.
Más información
Visión artificial en logística

Visión artificial en logística

Agiliza la logística con modelos Ultralytics YOLO. La IA visual permite inspeccionar paquetes, clasificarlos, realizar el seguimiento de vehículos y supervisar la seguridad del almacén en tiempo real.
Más información
Visión artificial en el comercio minorista

Visión artificial en el comercio minorista

Reinventa el comercio minorista con modelos Ultralytics YOLO. La IA visual permite realizar el seguimiento del inventario, supervisar estanterías, gestionar colas y obtener información más útil sobre los clientes.
Más información
Visión artificial en el sector sanitario

Visión artificial en el sector sanitario

Desarrolla soluciones sanitarias con modelos Ultralytics YOLO. La IA visual en el sector sanitario permite acelerar el diagnóstico por imagen, mejorar los diagnósticos y supervisar a los pacientes.
Más información
Visión artificial en la fabricación

Visión artificial en la fabricación

Optimiza la fabricación con modelos Ultralytics YOLO. La IA visual mejora el control de calidad, la detección de defectos, el cumplimiento de las normas de uso de EPI y la automatización de las líneas de montaje.
Más información
Visión artificial en la automoción

Visión artificial en la automoción

Aplica la visión artificial al sector de la automoción con modelos Ultralytics YOLO. La IA visual mejora la seguridad vial, la asistencia al conductor y la automatización de vehículos para lograr carreteras más inteligentes.
Más información
Visión artificial en la agricultura

Visión artificial en la agricultura

Incorpora la IA de visión a la agricultura inteligente con modelos Ultralytics YOLO. Impulsa la monitorización de cultivos, el seguimiento del ganado y la agricultura de precisión para obtener cosechas más abundantes e inteligentes.
Más información

¡Construyamos juntos el futuro de la IA!

Inicia tu recorrido hacia el futuro del aprendizaje automático