Modelado de Oponentes para el Entrenamiento de Modelos Basados en Búsqueda Arbórea de Monte Carlo en el Juego de Mesa Citadels

1. Introducción

La Búsqueda de Árboles Monte Carlo (MCTS) se ha consolidado como una técnica efectiva para la toma de decisiones en juegos de mesa, combinando adaptabilidad y bajo uso de conocimiento específico del dominio. Su rendimiento es notable en juegos deterministas con información perfecta, como el Go (SILVER et al., 2016).

Sin embargo, su aplicación encuentra limitaciones significativas en entornos con múltiples jugadores, información oculta y restricciones de tiempo, donde el alto costo computacional de las simulaciones y la dificultad de adaptación comprometen la capacidad de respuesta y la calidad de las decisiones (POWLEY et al., 2014).

En este contexto, los enfoques híbridos que integran MCTS y Aprendizaje por Refuerzo (RL) han mostrado ser prometedores al permitir que la fase de planificación se desacople de la ejecución. La construcción de estructuras de decisión persistentes, con almacenamiento previo de la búsqueda, permite la selección instantánea de acciones durante el juego, reduciendo la necesidad de simulaciones en línea y preservando la profundidad estratégica (BROWNE, 2012; SWIECHOWSKI, 2023).

En esta investigación, se probó y desarrolló un modelo híbrido de MCTS con técnicas de aprendizaje por refuerzo fuera de línea. El modelo se entrenó y probó utilizando diferentes oponentes en un entorno de simulación del juego de mesa Citadels (FAIDUTTI, 2016).

2. Objetivo General

El objetivo general de esta investigación es desarrollar un marco híbrido MCTS-RL capaz de operar eficientemente en juegos de mesa multijugador con información oculta, utilizando Citadels como caso de estudio.

La propuesta busca eliminar los cuellos de botella computacionales del MCTS tradicional mediante la construcción fuera de línea de una estructura de decisión persistente, permitiendo acciones rápidas y robustas en tiempo de ejecución.

3. Metodología

Esta investigación se caracteriza como un estudio experimental aplicado con análisis cuali-cuantitativo.

La primera etapa implicó el desarrollo y adaptación de un entorno de simulación digital para el juego de mesa Citadels. A esto le siguió el desarrollo de cinco agentes expertos con estrategias personalizadas, construidas para imitar estrategias reales utilizadas por jugadores humanos, y el desarrollo de un agente base que elige acciones al azar. Después de la validación del entorno y los agentes desarrollados, comenzó el desarrollo del marco híbrido MCTS-RL.

El modelo MCTS es, en esencia, un algoritmo de búsqueda heurística que opera mediante la ejecución de múltiples simulaciones. Para cada estado de juego distinto visitado durante estas simulaciones, se crea un nodo correspondiente en una estructura de datos de árbol. El estado inicial del juego representa el nodo raíz de este árbol.

Sin embargo, la propuesta de almacenar todo el árbol y conservarlo para decisiones futuras es inviable debido al factor de ramificación masivo. Para hacer esto posible, es necesario abstraer el árbol: el estado del juego se divide en sus características fundamentales (por ejemplo, el oro del jugador, el número de cartas en la mano) y cada característica se asigna a una tabla de datos independiente.

En esta estructura, las filas de una tabla representan los posibles valores de una característica del estado, y las columnas representan las posibles acciones que el agente puede tomar (por ejemplo, ganar oro, robar cartas). En cada celda se almacenan dos valores: el número de victorias logradas (n) después de tomar esa acción en ese estado, y el número total de veces que se exploró esta combinación (m). Estas tablas, cuando se completan mediante simulaciones de partidas de Citadels, configuran el modelo aprendido del agente.

El proceso de entrenamiento incluye un componente de aprendizaje por refuerzo: después de cada partida simulada, los resultados actualizan las tablas de decisión, influyendo en elecciones futuras. Las victorias actúan como recompensas y refuerzan las acciones efectivas, aumentando su probabilidad de ser elegidas nuevamente, mientras que las derrotas reducen esta posibilidad. Así, a lo largo de muchas simulaciones, el modelo se adapta continuamente, equilibrando la exploración de nuevas alternativas y la explotación de estrategias probadas, convergiendo gradualmente hacia comportamientos más efectivos.

4. Resultados y Discusión

Para evaluar el rendimiento del modelo MCTS propuesto, fue crucial comprender las dinámicas de poder entre las estrategias base (agentes expertos y agente aleatorio). Para lograrlo, cada una fue sometida a una ronda de 10,000 partidas contra cuatro oponentes idénticos.

El mapa de calor presentado en la Figura 1 ilustra el rendimiento de cada estrategia (eje Y) contra los diferentes oponentes (eje X). Las estrategias poseen fortalezas y debilidades distintas: los Expertos 1, 2 y 3 resultan competentes en la mayoría de los escenarios, mientras que los Expertos 4 y 5 son considerablemente menos efectivos. Como era de esperar, la estrategia completamente aleatoria muestra un rendimiento muy bajo contra cualquier oponente mínimamente estructurado.

Figura 1: Comparación entre estrategias.

El siguiente paso fue evaluar el modelo MCTS-RL. Se realizaron diferentes sesiones de entrenamiento, cada una centrada en uno de los oponentes, totalizando 100,000 partidas de entrenamiento para cada versión del modelo. Luego, se midió el rendimiento de cada modelo entrenado contra todo tipo de oponentes siguiendo el mismo modelo de prueba anterior, y contra oponentes variados seleccionados al azar.

El mapa de calor que se muestra en la Figura 2 presenta la tasa de victorias consolidada de cada modelo. El resultado más significativo fue el del modelo entrenado en el entorno variado, que logró un rendimiento consistente, superando a las otras versiones del modelo en casi todos los escenarios de prueba. Esto sugiere que la exposición a una diversidad de estrategias durante el entrenamiento fue fundamental para desarrollar una capacidad de juego más robusta y generalista.

Figura 2: Comparación entre modelos entrenados.

Los modelos entrenados contra los Expertos 4 y 5, considerados los oponentes más débiles, se convirtieron en agentes sorprendentemente efectivos. Por el contrario, el entrenamiento contra los Expertos 1 y 3, considerados oponentes fuertes, produjo modelos con un rendimiento general muy pobre.

Una posible explicación para este contraste es que las estrategias avanzadas de los expertos tienden a ser altamente especializadas, mientras que el modelo MCTS-RL, al inicio del entrenamiento, se aproxima a un comportamiento aleatorio. Contra oponentes fuertes, incluso las acciones potencialmente ventajosas pueden no resultar en suficientes victorias para que el modelo reconozca patrones de éxito; mientras que contra oponentes menos especializados, las victorias ocurren con mayor frecuencia, favoreciendo el aprendizaje. Aún así, esto sigue siendo una hipótesis que requiere confirmación.

5. Conclusión

Este estudio demostró la viabilidad del enfoque propuesto, que utiliza una abstracción del árbol MCTS para preservar el conocimiento adquirido entre movimientos. Los resultados confirmaron que el modelo es capaz de desarrollar estrategias robustas para el entorno.

El rendimiento superior del agente entrenado en el entorno variado muestra que la exposición a múltiples tácticas es fundamental para construir un modelo generalista. Además, la investigación indica que la calidad del agente final depende más de la diversidad que de la fuerza aparente de los oponentes de entrenamiento.

Como estudios futuros, sería interesante explorar más precisamente las razones reales por las cuales estrategias menos especializadas resultaron en modelos más eficientes que estrategias más fuertes. Además, una comparación del modelo propuesto con otros modelos MCTS también ayudaría a obtener una evaluación más precisa del enfoque.