Búsqueda Monte Carlo en Árboles

“Instead of trying to find the perfect move, play a thousand random games and see which move wins most often.”

En el módulo 15 aprendimos a resolver juegos de forma exacta con minimax y poda alfa-beta — pero esos métodos colapsan cuando el árbol de juego es demasiado grande. En el módulo 12 descubrimos que muestrear y promediar puede estimar cualquier esperanza, y en el módulo 17 que UCB1 resuelve el balance entre exploración y explotación. Este módulo une las tres ideas: Monte Carlo Tree Search (MCTS) construye un árbol de forma selectiva, usa simulaciones aleatorias para evaluar posiciones y aplica la fórmula de bandidos para decidir qué ramas explorar. El resultado es un algoritmo que juega bien sin necesitar ninguna función de evaluación manual — la misma idea que llevó a AlphaGo a derrotar al campeón mundial de Go en 2016.

Contenido

Materiales y flujo de trabajo

Paso	Material	Colab	Descripción
1	18.1 Más allá de minimax	—	Por qué los métodos exactos fallan y cómo los rollouts los reemplazan
2	18.2 Hex: el juego	—	Reglas, tablero, componentes formales, teoremas
3	Notebook 01 — Hex y rollouts		Construir Hex, jugar partidas aleatorias, evaluación por rollouts
4	18.3 MCTS	—	Las cuatro fases, pseudocódigo, traza paso a paso
5	Notebook 02 — MCTS paso a paso		Implementar MCTS vanilla, traza manual, visualizar el árbol
6	18.4 UCT	—	UCB1 en árboles, constante de exploración
7	18.5 MCTS en acción	—	Experimentos y comparaciones en Hex
8	Notebook 03 — UCT y experimentos		UCT, presupuesto de iteraciones, ajuste de $c$
9	18.6 Más allá	—	RAVE, AlphaGo, AlphaZero, torneo
10	Notebook 04 — Torneo		Simulación de torneo: MCTS vs alpha-beta vs aleatorio

Objetivos de aprendizaje

Al terminar este módulo podrás:

1. Explicar por qué minimax y alpha-beta fallan en juegos con factor de ramificación alto y justificar la necesidad de métodos aproximados
2. Implementar evaluación por rollouts aleatorios y conectarla con el estimador Monte Carlo del módulo 12
3. Describir las reglas de Hex y por qué es un juego ideal para MCTS: sin función de evaluación conocida, sin empates, reglas simples
4. Implementar MCTS con las cuatro fases (selección, expansión, simulación, retropropagación) y trazar su ejecución paso a paso
5. Derivar la fórmula UCT como aplicación directa de UCB1 (módulo 17) a nodos de un árbol de búsqueda
6. Analizar el efecto de la constante de exploración $c$ y del presupuesto de iteraciones en la calidad de juego de MCTS
7. Comparar MCTS contra minimax, alpha-beta y jugadores aleatorios en Hex
8. Explicar la evolución de Deep Blue a AlphaZero como una progresión dentro del mismo marco de árbol + evaluación
9. Diseñar un agente de Hex basado en MCTS que compita contra otros agentes bajo restricciones de tiempo

Prerrequisitos

Mapa conceptual

graph TD
    A["Módulo 12: Monte Carlo"] --> B["Rollouts: muestrear y promediar"]
    C["Módulo 15: Minimax"] --> D["Árbol de juego + propagación de valores"]
    E["Módulo 17: UCB1"] --> F["UCT: UCB1 en cada nodo"]
    B --> G["MCTS: árbol + simulaciones"]
    D --> G
    F --> G
    G --> H["Hex 3×3: traza completa"]
    G --> I["Hex 7×7: experimentos"]
    G --> J["RAVE, redes neuronales"]
    J --> K["AlphaGo → AlphaZero"]
    I --> L["Torneo de agentes"]

Cómo ejecutar el script de imágenes

cd clase/18_montecarlo_search
python3 lab_mcts.py

Dependencias: numpy, matplotlib (ver requirements.txt).