Búsqueda de árbol Monte Carlo: una revisión de desventajas, ventajas y limitaciones en juegos multijugador complejos

1. Introducción

La búsqueda en árbol de Monte Carlo (MCTS, por sus siglas en inglés) es una familia de algoritmos de búsqueda que construye un árbol de decisión en cuatro etapas: selección, expansión, simulación y retropropagación. En lugar de requerir una función de evaluación completa para cada estado, el método estima la calidad de las acciones a partir de numerosas simulaciones, equilibrando la exploración de alternativas poco visitadas con la explotación de acciones conocidas. Esta característica contribuyó a resultados expresivos en juegos como Go, Ajedrez y Shogi, especialmente en entornos de dos jugadores con información perfecta (BROWNE et al., 2012).

Sin embargo, los juegos digitales y de mesa contemporáneos presentan condiciones más complejas: varios oponentes, información oculta, aleatoriedad, grandes espacios de acciones y decisiones en tiempo real. En estas situaciones, una simulación adicional no siempre produce una mejor decisión. Un mayor número de jugadores amplía el árbol de búsqueda y dificulta modelar las respuestas de los oponentes. La información imperfecta puede causar fusión de estrategias cuando los estados ocultos se manejan de forma inadecuada, mientras que la presión de tiempo reduce el presupuesto computacional disponible. A pesar de la creciente aplicación de MCTS en estos escenarios, la literatura permanece fragmentada y concentrada en juegos clásicos.

2. Objetivos

El objetivo general de este trabajo fue identificar y organizar las limitaciones recurrentes de MCTS en juegos digitales y de mesa multijugador, especialmente en entornos con información imperfecta, estocasticidad y restricciones de tiempo.

Como objetivos específicos, el trabajo buscó reunir las estrategias que mitigan estas limitaciones e identificar vacíos de investigación que puedan guiar estudios futuros y favorecer evaluaciones más comparables y reproducibles.

3. Metodología

Se realizó una revisión de la literatura sobre estudios publicados entre 2013 y 2025, con búsquedas en las bases de datos IEEE Xplore, HAL Science Ouverte y Google Scholar. Las estrategias de búsqueda combinaron los términos "Monte Carlo Tree Search" y "MCTS" con expresiones relacionadas con juegos digitales, juegos de mesa y juegos multijugador. El cribado consideró trabajos cuyo título o resumen abordara MCTS, una variante directa o un método híbrido aplicado a juegos competitivos o cooperativos. Se excluyeron los estudios fuera del alcance, los documentos sin acceso al texto completo y los trabajos cuyo alcance no era compatible con los objetivos de la revisión.

Las búsquedas recuperaron 24 registros, de los cuales dos estaban duplicados entre consultas, lo que resultó en 22 trabajos únicos potencialmente relevantes (17 en inglés y cinco en francés). Tras el cribado, se seleccionaron 18 estudios para análisis completo y se excluyeron cuatro. El corpus final reunió 13 estudios de IEEE Xplore, tres de HAL y dos encontrados a través de Google Scholar, y entre los seleccionados, 15 textos estaban en inglés y tres en francés. Los trabajos se clasificaron por tipo de juego, algoritmo utilizado, restricciones del entorno, resultados reportados y estrategias de mitigación. El análisis temático se organizó en tres categorías estructurales de limitación, límites de rendimiento, puntos ciegos tácticos y compensaciones en el modelado de oponentes, y dos amplificadores dependientes del dominio, información imperfecta y decisiones en tiempo real.

4. Resultados y Discusión

Los estudios analizados indican que MCTS se desempeña de manera más consistente en juegos con estados bien definidos, un factor de ramificación moderado y un presupuesto computacional lo suficientemente grande para un alto número de simulaciones. Entre los 18 trabajos seleccionados, ocho abordaron juegos digitales, seis investigaron juegos de mesa o de tablero y los restantes analizaron juegos de cartas, entornos de juego general o aplicaciones relacionadas. Los algoritmos basados en MCTS se utilizaron en 14 estudios, a menudo combinados con redes neuronales, abstracciones del espacio de acciones, políticas de simulación y técnicas de ajuste de parámetros.

La primera limitación identificada se refiere al rendimiento de la búsqueda. Aunque aumentar el número de simulaciones suele mejorar la calidad de las decisiones, las ganancias marginales tienden a disminuir a medida que las nuevas simulaciones comienzan a revisitar trayectorias que ya están suficientemente exploradas. Los resultados obtenidos en Go, juegos de estrategia en tiempo real y juegos de mesa muestran que duplicar el presupuesto computacional puede producir beneficios reducidos o nulos después de cierto punto. Además, los estudios sobre profundidad de habilidad muestran que este límite depende tanto de la complejidad del juego como de la configuración del agente. Las estrategias de mitigación incluyen la abstracción del espacio de acciones, la simplificación de las simulaciones y el ajuste automático de políticas, constantes de exploración y estrategias de rollout mediante el N-Tuple Bandit Evolutionary Algorithm (NTBEA) (GOODMAN; PEREZ-LIEBANA; LUCAS, 2024).

La segunda limitación corresponde a los puntos ciegos del razonamiento táctico. Dado que MCTS estima el valor promedio de las continuaciones muestreadas, el algoritmo puede fallar en posiciones que requieren reconocer secuencias tácticas específicas, amenazas a largo plazo o configuraciones poco frecuentes. En Go, situaciones como las escaleras y el semeai ilustran escenarios en los que una estructura táctica evidente para jugadores experimentados puede no ser identificada por la búsqueda.

La tercera limitación involucra el modelado de oponentes. En juegos con tres o más participantes, el proceso de búsqueda debe representar no solo las decisiones del jugador en la raíz del árbol, sino también las posibles respuestas de cada adversario. Los modelos que mantienen estructuras independientes para cada oponente tienden a representar mejor el comportamiento estratégico, aunque aumentan significativamente el costo computacional. En contraste, los enfoques simplificados, como Paranoid Search y las políticas generalizadas, reducen este costo pero pueden fallar en representar comportamientos relevantes. La literatura sugiere que los enfoques basados en enfoque selectivo, generalización de las respuestas de los adversarios y descomposición del árbol son alternativas prometedoras, aunque todavía están poco evaluadas en juegos con un gran número de participantes (BAIER; KAISERS, 2020).

La información imperfecta intensifica estas limitaciones. En juegos de cartas, Pokémon y otros entornos con estados ocultos, la determinización, que consiste en asumir una posible configuración de la información desconocida y buscar como si fuera verdadera, puede causar la fusión de estrategias incompatibles. Information Set MCTS, una variación de la búsqueda en árbol de Monte Carlo diseñada para manejar la incertidumbre, reduce este problema agrupando estados que el jugador no puede distinguir, preservando solo la información realmente disponible en el momento de la decisión (COWLING; POWLEY; WHITEHOUSE, 2012). Aun así, la aleatoriedad inherente al entorno y la necesidad de inferir el comportamiento de los oponentes continúan limitando la confiabilidad de las estimaciones producidas.

En entornos en tiempo real, como juegos de estrategia, MOBA y shooters en primera persona, las restricciones de tiempo se convierten en un factor crítico. MCTS debe seleccionar acciones en intervalos muy cortos mientras gestiona espacios de acciones combinatorios, múltiples unidades y observaciones parciales. En este contexto, las abstracciones jerárquicas, las macro-acciones, la poda de acciones y las políticas obtenidas mediante aprendizaje supervisado o aprendizaje por refuerzo aparecen como estrategias recurrentes (ONTAÑÓN, 2013). En algunas situaciones, los métodos alternativos pueden rendir mejor. El Rolling Horizon Evolutionary Algorithm (RHEA), por ejemplo, evoluciona secuencias cortas de acciones y realiza una replanificación continua, mostrándose particularmente adecuado para juegos cooperativos y entornos altamente estocásticos en los que el árbol de búsqueda cambia rápidamente (SFIKAS; LIAPIS, 2022).

También se identificaron aplicaciones de MCTS que dependen menos de las decisiones en tiempo real, como el balanceo automático, el playtesting y el apoyo al diseño de juegos. En estos escenarios, el tiempo de procesamiento deja de ser una restricción crítica, lo que permite explorar exhaustivamente diferentes configuraciones, identificar desequilibrios y evaluar alternativas de diseño. Aunque la mayoría de los estudios reportan resultados favorables a los enfoques propuestos, algunos trabajos observaron un rendimiento inferior de MCTS en comparación con técnicas competidoras, como en los juegos Kingdomino y Pandemic.

5. Conclusión

La revisión también identificó cinco oportunidades relevantes para investigación futura: (i) adopción y estandarización de benchmarks compartidos para juegos multijugador con información imperfecta; (ii) evaluación sistemática de técnicas de modelado de oponentes en juegos con un mayor número de participantes; (iii) investigación de la relación entre la complejidad percibida por los jugadores humanos y la profundidad efectiva de la búsqueda; (iv) estudio de series competitivas al mejor de tres y al mejor de cinco, considerando el historial de picks y bans; y (v) expansión de las aplicaciones de MCTS en balanceo automático, playtesting y generación procedural de contenido.