017 — Juegos: minimax y poda alfa-beta

← Clase anterior · Índice de la parte · Clase siguiente →

Parte: 01 — IA simbólica, búsqueda, lógica y planificación
Nivel: fundamentos · Horas estimadas: 4
Laboratorio: search · Estado: EXECUTABLE_CORE

🎯 Propósito

Comprender juegos: minimax y poda alfa-beta dentro de la evolución de la inteligencia artificial, implementar un experimento mínimo verificable y distinguir qué parte constituye evidencia frente a una afirmación todavía no comprobada.

📚 Resultados de aprendizaje

Al finalizar podrás:

  1. Explicar juegos: minimax y poda alfa-beta usando los conceptos minimax, alfa-beta, adversarial, utilidad.
  2. Ejecutar el laboratorio con una semilla explícita y revisar su contrato JSON.
  3. Identificar al menos un supuesto, una limitación y un riesgo de aplicación.
  4. Comparar el enfoque con la etapa anterior de la ruta de aprendizaje.
  5. Producir una evidencia reproducible y una conclusión que no exceda los datos.

🧩 Conceptos centrales

minimax, alfa-beta, adversarial, utilidad

🗺️ Ubicación en el mapa de la IA

La búsqueda adversarial extiende la búsqueda en espacios de estados (clases 013-016) a entornos con un oponente que elige contra nosotros. Minimax formaliza la idea de von Neumann (teorema minimax, 1928) como algoritmo; el programa de damas de Samuel (1959) y Deep Blue (1997) son sus hitos. La línea evolutiva continúa: AlphaGo (2016) sustituyó la función de evaluación manual por redes neuronales y el barrido exhaustivo por búsqueda de árbol Monte Carlo, pero el esqueleto — explorar un árbol de jugadas alternadas y respaldar valores — sigue siendo el de esta clase.

📖 Fundamentos

🎲 Formulación de un juego

Un juego de suma cero, dos jugadores, turnos alternos e información perfecta se define con: estado inicial s0, TO-MOVE(s) (a quién le toca), ACTIONS(s), RESULT(s, a), IS-TERMINAL(s) y UTILITY(s, jugador) (valor numérico del estado terminal: p. ej. +1 victoria, 0 tablas, −1 derrota). Suma cero significa que lo que gana MAX lo pierde MIN, así que basta un solo número por estado.

♟️ Minimax

El valor minimax de un estado es la utilidad que obtiene MAX si ambos juegan perfectamente de ahí en adelante:

MINIMAX(s) =
    UTILITY(s, MAX)                                si IS-TERMINAL(s)
    max_{a ∈ ACTIONS(s)} MINIMAX(RESULT(s, a))     si TO-MOVE(s) = MAX
    min_{a ∈ ACTIONS(s)} MINIMAX(RESULT(s, a))     si TO-MOVE(s) = MIN

El algoritmo es un recorrido DFS del árbol de juego que respalda (backs up) los valores desde las hojas: cada nodo MAX toma el máximo de sus hijos, cada nodo MIN el mínimo. Es óptimo contra un oponente óptimo; contra un oponente que falla, garantiza al menos ese valor (puede existir otra línea que explote mejor los errores, pero minimax nunca hace peor que su garantía). Complejidad: tiempo O(b^m), memoria O(b·m) — inviable para ajedrez (b ≈ 35, m ≈ 80).

✂️ Poda alfa-beta

Idea: mantener durante el recorrido dos cotas del valor que los jugadores ya tienen garantizado en el camino desde la raíz:

Si en un nodo MIN el valor cae a v ≤ α, MAX nunca permitirá llegar aquí (ya tiene algo mejor): se poda el resto de hijos. Simétricamente en nodos MAX cuando v ≥ β.

función ALFA-BETA(s, α, β):
    si IS-TERMINAL(s): devolver UTILITY(s, MAX)
    si TO-MOVE(s) = MAX:
        v ← −∞
        para cada a en ACTIONS(s):
            v ← max(v, ALFA-BETA(RESULT(s,a), α, β))
            si v ≥ β: devolver v          # poda: MIN nunca dejará llegar aquí
            α ← max(α, v)
        devolver v
    si no:  # MIN
        v ← +∞
        para cada a en ACTIONS(s):
            v ← min(v, ALFA-BETA(RESULT(s,a), α, β))
            si v ≤ α: devolver v          # poda: MAX tiene algo mejor
            β ← min(β, v)
        devolver v

La poda no altera el resultado: devuelve exactamente el valor minimax. Con ordenación perfecta de jugadas (probar primero la mejor) examina O(b^(m/2)) nodos — duplica la profundidad alcanzable con el mismo presupuesto (Knuth y Moore, 1975); con orden aleatorio, ≈ O(b^(3m/4)). Por eso los motores invierten tanto en ordenar jugadas (jugada de la tabla de transposición primero, capturas, killer moves).

⏱️ Búsqueda con recursos finitos

Ningún juego interesante se explora hasta las hojas. Se corta a profundidad d y se aplica una función de evaluación EVAL(s): una estimación de la utilidad esperada, típicamente lineal en rasgos (EVAL(s) = Σ wi·fi(s); en ajedrez: material, movilidad, estructura de peones). Problemas asociados: el efecto horizonte (una pérdida inevitable se "empuja" más allá del corte con jadeos tácticos) se mitiga con búsqueda de quiescencia (extender el corte hasta posiciones tranquilas, sin capturas pendientes); las tablas de transposición cachean valores de estados repetidos alcanzados por distinto orden de jugadas; la profundización iterativa da control de tiempo y mejora la ordenación con la mejor jugada de la iteración anterior.

🧮 Ejemplo trabajado

Árbol de profundidad 2: la raíz es MAX con tres jugadas (a1, a2, a3); cada hijo es un nodo MIN con tres hojas:

                MAX
       a1     /  a2 |  a3 \
       MIN B     MIN C     MIN D
      /3 12 8\  /2 4 6\   /14 5 2\

Minimax puro: B = min(3,12,8) = 3; C = min(2,4,6) = 2; D = min(14,5,2) = 2; raíz = max(3,2,2) = 3 → jugar a1. Hojas evaluadas: 9.

Alfa-beta (izquierda a derecha, raíz con α=−∞, β=+∞):

B: ve 3, 12, 8 → B = 3.  Raíz: α = 3.
C: primera hoja 2 → v = 2 ≤ α = 3 → PODA (no mira 4 ni 6). C ≤ 2, irrelevante.
D: primera hoja 14 → v = 14, β_D = 14... segunda hoja 5 → v = 5,
   tercera hoja 2 → v = 2 ≤ α = 3 → D ≤ 2, descartado.
Raíz = 3, jugar a1. Hojas evaluadas: 7 de 9.

Con ordenación óptima (explorar D en orden 2, 5, 14) la poda habría sido inmediata tras la primera hoja de C y de D: 5 hojas. La ganancia de alfa-beta depende del orden, no de la suerte del árbol.

📊 Propiedades y comparación

Propiedad Minimax Alfa-beta Alfa-beta + orden perfecto MCTS (contraste)
Resultado valor exacto idéntico a minimax idéntico estimación estadística
Tiempo O(b^m) ≈ O(b^(3m/4)) típico O(b^(m/2)) presupuesto fijo de simulaciones
Memoria O(b·m) O(b·m) O(b·m) árbol parcial en memoria
Requiere EVAL sí (con corte) sí (con corte) sí no (rollouts) o red de valor
Dónde brilla árboles pequeños juegos tácticos (ajedrez) con buenas jugadas-candidato b enorme, EVAL difícil (Go) 
flowchart TD
    R["MAX raíz<br/>α=−∞, β=+∞"] --> B["MIN B → 3"]
    R --> C["MIN C"]
    R --> D["MIN D"]
    B --> b1["3"] & b2["12"] & b3["8"]
    C --> c1["2"] & c2["4 ✂️ podada"] & c3["6 ✂️ podada"]
    D --> d1["14"] & d2["5"] & d3["2"]
    C -. "v=2 ≤ α=3 ⇒ corte" .-> R
    R --> A1["Decisión: a1, valor 3"]

⚠️ Errores conceptuales frecuentes

  1. "Alfa-beta es una aproximación que sacrifica exactitud por velocidad." Falso: devuelve exactamente el valor minimax. Lo aproximado es la función de evaluación al cortar profundidad, no la poda.
  2. "Minimax asume que el rival es perfecto, así que contra malos jugadores es malo." Contra un rival subóptimo minimax obtiene al menos su valor garantizado. Lo que sí es cierto: no modela al oponente, así que no explota sus debilidades.
  3. Podar comparando valores de hojas en vez de cotas del camino. α y β son garantías acumuladas desde la raíz; usarlas como valores locales del nodo produce podas incorrectas.
  4. Ignorar el orden de exploración. Alfa-beta con mal orden se acerca a minimax puro. La mitad de la ingeniería de un motor real es ordenación de jugadas.
  5. Evaluar en posiciones "calientes". Cortar en medio de un intercambio de capturas hace que EVAL mida ruido (efecto horizonte); la quiescencia existe precisamente para eso.

🚀 Del aprendizaje a la operación

Entre este laboratorio y un motor de juego real median: función de evaluación calibrada (hoy, redes NNUE entrenadas con millones de posiciones), tablas de transposición con gestión de memoria y colisiones, control de tiempo por jugada con profundización iterativa, paralelización (Lazy SMP) y bancos de pruebas de regresión (miles de partidas contra versiones anteriores para validar cada cambio con significancia estadística). Además, para juegos con azar o información oculta (backgammon, póker) minimax puro no basta: hacen falta expectiminimax o equilibrios de teoría de juegos.

🧪 Laboratorio

python lab.py

El laboratorio llama a ai_evolution.labs.run_lab("search"). Esta decisión evita 183 implementaciones divergentes: cada clase tiene un entrypoint propio, pero los motores didácticos se prueban como una biblioteca común.

🔍 Evidencia esperada

📓 Notebooks

📝 Evaluación

Criterio Peso
Comprensión conceptual 25 %
Ejecución reproducible 25 %
Interpretación basada en evidencia 25 %
Riesgos, límites y mejora propuesta 25 %

Consulta assessment.md para preguntas y criterio de aceptación.

⚠️ Errores comunes

Síntoma Causa probable Corrección
El código corre, pero no hay conclusión Se confundió ejecución con aprendizaje Explica qué demuestra y qué no demuestra
El resultado cambia sin explicación No se registró semilla o configuración Conserva semilla, versión y parámetros
Se promete uso real Se extrapoló desde una demo educativa Declara entorno, datos, límites y revisión humana
Se copia una métrica aislada No existe baseline ni costo de error Añade comparación y criterio de decisión

❓ Preguntas frecuentes

¿Debo usar una API comercial?
No. El núcleo funciona localmente. Las extensiones LIVE se documentan por separado.

¿El laboratorio representa una implementación industrial?
No por sí solo. Enseña el contrato y el patrón; producción exige integración, seguridad, observabilidad, pruebas y operación.

¿Dónde profundizo?
Revisa las especializaciones enlazadas en el README raíz y la ruta siguiente.

🔗 Referencias

📜 Papers que fundamentan esta clase

Bloque generado por python scripts/link_papers_to_classes.py. La fuente es papers/catalog/papers.json.

Paper Año Qué desbloqueó Miniatura
P27 · Dominar el go con redes neuronales profundas y búsqueda en árbol 2016 Une las dos tradiciones de la IA: la búsqueda simbólica de la parte 01 y el aprendizaje profundo de la parte 04, en un solo sistema. notebook

Cada ficha explica el problema anterior, la matemática mínima, los límites y los errores de atribución más frecuentes. Para leerlas con método: cómo leer un paper de IA · anexos matemáticos.

📚 Bibliografía de apoyo

Bloque generado por python scripts/link_sources_to_classes.py. Cada obra lleva su localizador verificado en sources/bibliography.json.

Los papers dicen de dónde salió el mecanismo. Estas obras lo desarrollan con el espacio que una clase no tiene: teoría completa, demostraciones y ejercicios.

Obra Edición Localizador Papel en esta clase
Russell, Stuart J. y Norvig, Peter — Artificial Intelligence: A Modern Approach 4.ª · 2020 ISBN 9780134610993 · web de la obra citada en las referencias de esta clase · cap. 5 · obra de referencia de la parte 01
Nilsson, N. J. — Principles of Artificial Intelligence 1980 ISBN 9780387113401 obra de referencia de la parte 01 · representación por espacios de estados

⬅️ Clase anterior

016 — Diseño y validación de heurísticas

➡️ Siguiente clase

018 — Problemas de satisfacción de restricciones

📝 Evaluación completa

❓ Preguntas

  1. Define juegos: minimax y poda alfa-beta sin usar una marca o framework como definición.
  2. Explica la relación entre minimax, alfa-beta, adversarial, utilidad.
  3. Ejecuta lab.py dos veces con la misma semilla. ¿Qué debe conservarse?
  4. Identifica una afirmación permitida y una afirmación exagerada sobre el resultado.
  5. Propón una prueba negativa o un caso límite.

🏆 Reto verificable

Amplía el resultado del laboratorio con una clave student_extension que incluya:

✅ Criterio de aceptación