Juegos y adversarios: minimax, poda alfa-beta y Monte Carlo tree search

Un juego como problema de búsqueda, el árbol de juego, minimax, la poda alfa-beta, las funciones de evaluación y MCTS, con el tres en raya, donde se puede calcular todo, y el camino de Deep Blue a AlphaZero.

14 minutos Matěj Žalmánek 2026-10-15

Serie Fundamentos de IA Parte 22 de 52

1. Mapa de la inteligencia artificial: qué es cada cosa y cómo encaja todo
2. Breve historia de la inteligencia artificial: de Turing a los modelos de lenguaje
3. Datos, modelo, entrenamiento, inferencia: los conceptos básicos en un solo ejemplo
4. Cómo leer la notación matemática: símbolos, subíndices, sumatorios y cuantificadores
5. Conjuntos y relaciones: las piezas con las que se construyen las definiciones en IA
6. Funciones y aplicaciones: por qué todo modelo de IA es una función
7. Lógica y demostraciones: las reglas con las que se razona en IA
8. Grafos y árboles: la estructura sobre la que se apoyan la búsqueda y las redes neuronales
9. Álgebra lineal para aprendizaje automático: vectores, matrices y por qué la IA sobre todo multiplica
10. Derivadas, gradiente y regla de la cadena: cómo sabe un modelo en qué dirección aprender
11. Descenso de gradiente: cómo aprende un modelo
12. Qué es la probabilidad: del lanzamiento de un dado a los axiomas de Kolmogórov
13. Probabilidad condicionada y teorema de Bayes: cómo cambiar una estimación cuando te enteras de algo nuevo
14. Variable aleatoria y función de distribución: una sola función que lo dice todo sobre la distribución
15. Función de densidad y función de probabilidad: por qué una variable continua tiene probabilidad cero en cada punto
16. Esperanza, varianza y covarianza: dónde está una distribución, qué anchura tiene y qué se relaciona con qué
17. Resumen de las distribuciones de probabilidad: Bernoulli, binomial, Poisson, uniforme, normal y exponencial
18. Ley de los grandes números y teorema central del límite: por qué las medias se comportan de forma tan predecible
19. Estadística y estimación de parámetros: máxima verosimilitud, MAP e intervalos de confianza
20. Teoría de la información: entropía, entropía cruzada y divergencia KL, el origen de las funciones de pérdida
21. Búsqueda en el espacio de estados: BFS, DFS, UCS y A* con animaciones
22. Juegos y adversarios: minimax, poda alfa-beta y Monte Carlo tree search
23. Satisfacción de restricciones: backtracking, propagación de restricciones y AC-3 con un sudoku y un mapa de regiones checas
24. Lógica y sistemas basados en conocimiento: encadenamiento hacia delante y hacia atrás, resolución y sistemas expertos
25. Planificación: STRIPS, el mundo de bloques, heurísticas a partir de la relajación y la planificación en los agentes de IA
26. Búsqueda local y recocido simulado: un viajante por las capitales regionales checas
27. Algoritmos genéticos: población, cruce, mutación y selección en una mochila para la excursión
28. Estrategias evolutivas y programación genética: de la regla de un quinto a la ley de Kepler
29. Optimización por colonia de hormigas: cómo un rastro de feromona encuentra un camino corto
30. Optimización por enjambre de partículas: inercia, experiencia propia y experiencia del enjambre
31. Neuroevolución: evolución de los pesos y la forma de las redes neuronales, y el algoritmo NEAT
32. Conjuntos difusos y funciones de pertenencia: cómo escribir «algo cálido»
33. Lógica difusa y probabilidad: por qué «algo cálido» no significa «probablemente cálido»
34. Lógica difusa: t-normas, implicaciones y reglas SI–ENTONCES
35. Control difuso: Mamdani y Sugeno, del ventilador al péndulo invertido sobre un carro
36. Agrupamiento difuso: el algoritmo fuzzy c-means y los puntos entre clusters
37. Sistemas neuro-difusos (ANFIS): reglas difusas que aprenden de los datos
38. Cadenas de Markov: matriz de transición, distribución estacionaria y PageRank
39. Modelos ocultos de Márkov: el algoritmo de Viterbi y el casino deshonesto
40. Redes bayesianas: por qué está mojada la hierba y qué significa eso para el aspersor
41. El filtro de Kalman: cómo estimar a partir de mediciones imprecisas dónde está un coche y a qué velocidad va
42. Tipos de aprendizaje automático: supervisado, no supervisado, semisupervisado y más
43. Prompts, contexto y RAG: cómo darle a un modelo la información correcta
44. Autocodificadores variacionales (VAE): imágenes nuevas a partir de un espacio latente continuo
45. Redes generativas adversarias (GAN): el falsificador contra el detective
46. Modelos de difusión: cómo el ruido puro se convierte en una imagen
47. Procesos de decisión de Markov: estados, acciones, recompensas y ecuaciones de Bellman
48. Q-learning y DQN: aprender el valor de las acciones, de la tabla a la red neuronal
49. Gradiente de la política y PPO: aprender directamente la política
50. Cómo funciona un agente de IA: un modelo de lenguaje en un bucle con herramientas
51. Programación con agentes de IA: encargo, pruebas y revisión
52. Evaluación y seguridad de los sistemas de IA: cómo medir y cómo vigilar

Temario completo de la serie 52 de 83 temas publicados

En el laberinto de la parte anterior, el muñeco estaba solo. El mundo no se movía y cada jugada llevaba adonde debía. En un juego, en cambio, frente a ti se sienta alguien que quiere exactamente lo contrario, y a cada jugada tuya responde con la que más te duele. Buscar un camino hasta la meta ya no basta: tienes que buscar una estrategia que aguante frente a cualquier respuesta. El ajedrez, las damas y el go fueron durante décadas la vara de medir de la inteligencia artificial, y los algoritmos de esta parte están detrás tanto de Deep Blue como de AlphaGo.

Continúa las partes Búsqueda en el espacio de estados y Grafos y árboles.

1. Un juego como problema de búsqueda

Definición — juego de dos jugadores

Un juego es una séptupla Γ = (S, s₀, jugador, A, T, K, U), donde

• S, s₀, A(s) y T son los estados, el estado inicial, las acciones y la función de transición, como en un problema de búsqueda,
• jugador : S → {MAX, MIN} indica a quién le toca mover en cada estado,
• K ⊆ S es el conjunto de estados terminales, donde el juego termina,
• U : K → ℝ es la utilidad de un estado terminal desde el punto de vista de MAX.

El juego es de suma cero: lo que gana MAX lo pierde MIN, así que la utilidad de MIN es −U. Los jugadores se alternan, las jugadas son deterministas y ambos ven el estado completo (información perfecta).

La diferencia con la búsqueda es fundamental. La solución ya no es un camino: no lo eliges tú, porque una de cada dos jugadas la hace el rival. La solución es una estrategia: una regla que dice cómo responder a cada jugada que el rival pueda hacer.

2. El árbol de juego

Definición — árbol de juego

El árbol de juego es un árbol con raíz cuya raíz es s₀ y cuyos hijos de un nodo s son los sucesores {T(s, a) : a ∈ A(s)}. Las hojas son los estados terminales. Los nodos en los que mueve MAX los dibujamos como un triángulo con la punta hacia arriba; los de MIN, con la punta hacia abajo.

Si el juego tiene un factor de ramificación b y dura como mucho m jugadas, el árbol tiene hasta b^m hojas.

El tres en raya en un tablero de 3 × 3 es un juego pequeño y, aun así, su árbol tiene 549 946 nodos y 255 168 hojas: ese es el número de partidas distintas que se pueden jugar. Posiciones distintas, en cambio, solo hay 5 478: a la misma posición se llega por muchos órdenes de jugadas. El ajedrez tiene un factor de ramificación de unos 35 y una partida dura decenas de jugadas; Claude Shannon estimó en 1950 su árbol en 10¹²⁰ partidas. El go, con un factor de ramificación de unos 250, está todavía muchos órdenes de magnitud más allá. Así que el árbol entero solo lo recorremos en juegos pequeños; en los grandes tenemos que aprender qué ramas saltarnos.

3. Minimax

Definición — valor minimax

El valor minimax de un estado s es

• MM(s) = U(s), si s ∈ K,
• MM(s) = max_{a ∈ A(s)} MM(T(s, a)), si jugador(s) = MAX,
• MM(s) = min_{a ∈ A(s)} MM(T(s, a)), si jugador(s) = MIN.

La jugada óptima de MAX en el estado s es argmax_a MM(T(s, a)).

El nodo MIN de la izquierda elige 4 entre las hojas 4, 6 y 9; el del centro elige 2 entre 2, 7 y 8; el de la derecha elige 3 entre 5, 3 y 9. MAX, en la raíz, elige entonces entre 4, 2 y 3 y juega la jugada de la izquierda, con valor 4. Fíjate en que la rama derecha esconde un nueve, pero MAX nunca llegará a él, porque MIN jugaría el tres en su lugar.

Teorema — qué garantiza minimax

Si MAX juega de forma óptima, obtiene al menos MM(s₀) frente a cualquier estrategia de MIN. Si MIN también juega de forma óptima, MAX obtiene exactamente MM(s₀).

Minimax recorre el árbol en profundidad: tiempo O(b^m), memoria O(b · m).

4. Minimax en el tres en raya

El tres en raya de 3 × 3 es lo bastante pequeño como para que minimax recorra el árbol entero. El resultado lo conoce cualquiera que haya jugado más de unos minutos: el valor minimax del tablero vacío es 0; si los dos juegan sin errores, siempre es empate. Más interesante es lo que dice minimax de una posición concreta. Le toca a X (MAX) y en cada casilla libre aparece el valor de jugar en ella:

Solo una jugada gana: el centro. Con ella, X crea una horquilla: amenaza con completar la fila del medio y la diagonal, y O no puede bloquear las dos. La jugada abajo en el centro mantiene el empate. Las otras tres parecen inofensivas, pero pierden: O responde a ellas con su propia horquilla. Una persona tendría que pensarlo; minimax simplemente lo calcula.

def minimax(board):
    end = winner(board)                 # "X", "O", "draw" o None
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    values = [minimax(play(board, move)) for move in empty_squares(board)]
    return max(values) if to_move(board) == "X" else min(values)

5. Poda alfa-beta

Minimax recorre el árbol entero, aunque la mitad sea inútil. Vuelve a mirar la rama central: la primera hoja mostró 2. Así que MIN consigue en esa rama 2 o menos, y MAX ya tiene asegurada la rama izquierda, con valor 4. Sean como sean las dos hojas restantes, MAX no irá por la rama central. Ni siquiera necesita mirarlas.

Definición — alfa-beta

La búsqueda en profundidad lleva consigo dos cotas:

• α: el valor más alto que MAX ya se ha asegurado en algún punto del camino desde la raíz (al principio, −∞),
• β: el valor más bajo que se ha asegurado MIN (al principio, +∞).

En un nodo MAX, después de cada hijo se hace v ← max(v, valor del hijo) y α ← max(α, v); en un nodo MIN, de forma análoga, v ← min(…) y β ← min(β, v). En cuanto α ≥ β, los hijos restantes del nodo se podan: no se exploran.

Teorema. Alfa-beta devuelve en la raíz el mismo valor que minimax. Con el mejor orden de jugadas posible, explora solo O(b^m/2) nodos.

Alfa-beta llegó al mismo resultado (MAX juega a la izquierda y obtiene 4), pero solo evaluó 6 hojas de 9. En la rama central podó dos hojas justo después del dos; en la derecha, una después del tres. Por eso, en un nodo MIN podado solo aparece la cota «≤ 2» o «≤ 3»: el valor exacto no lo conocemos, y no nos hace falta.

En el tres en raya la diferencia es más espectacular. El minimax completo desde el tablero vacío visita 549 946 posiciones; alfa-beta, con el mismo orden de jugadas, solo 18 297, unas treinta veces menos, y devuelve el mismo cero. El exponente m/2 del teorema significa que, en el mismo tiempo, ves el doble de profundo. Por eso importa tanto el orden de las jugadas: los programas de ajedrez prueban primero las capturas y las jugadas que fueron buenas la vez anterior.

def alphabeta(board, alpha=-inf, beta=inf):
    end = winner(board)
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    maximizing = to_move(board) == "X"
    v = -inf if maximizing else inf
    for move in empty_squares(board):
        h = alphabeta(play(board, move), alpha, beta)
        if maximizing:
            v = max(v, h); alpha = max(alpha, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alpha >= beta:
            break                          # poda: el resto de la rama no cambia nada
    return v

6. Profundidad limitada y función de evaluación

Ni siquiera alfa-beta recorre el árbol del ajedrez hasta el final de la partida. Por eso los programas reales buscan solo hasta una profundidad fija y la posición en la que se detienen la estiman.

Definición — minimax con profundidad limitada

Una función de evaluación E : S → ℝ estima MM(s) y en los estados terminales coincide con U. Normalmente es una suma ponderada de características de la posición: E(s) = w₁f₁(s) + … + w_nf_n(s).

Minimax hasta la profundidad d: MM_d(s) = E(s), si s ∈ K o d = 0; en otro caso, el máximo o el mínimo de MM_d−1 de los sucesores.

La profundidad limitada tiene su trampa: el efecto horizonte. Si la búsqueda se detiene en mitad de un intercambio de piezas (acabas de capturar la dama y el rival te la recupera a la jugada siguiente), la función de evaluación solo ve la primera mitad y sobrevalora la posición. Los programas se defienden siguiendo la búsqueda en las posiciones «inquietas» hasta que se calman. Y como nunca saben cuánto tiempo tienen, buscan con la profundización iterativa de la parte anterior: profundidad 1, 2, 3, … hasta que se acaba el tiempo. Además, los resultados de las pasadas poco profundas sirven como orden de jugadas para las más profundas, y entonces alfa-beta poda mucho más.

7. Monte Carlo tree search

La función de evaluación del ajedrez se fue afinando durante décadas. Para el go no había manera de escribirla: una posición que parece tranquila puede estar perdida veinte jugadas después. Monte Carlo tree search (MCTS) renuncia por completo a la función de evaluación. En lugar de estimar la posición, la juega hasta el final: al azar, muchas veces, y mira con qué frecuencia salió bien.

Definición — una iteración de MCTS

El árbol crece desde la raíz s₀. Cada nodo i guarda su número de visitas n_i y la suma de resultados w_i desde el punto de vista del jugador que movió hasta ese nodo (victoria 1, empate ½, derrota 0). Una iteración tiene cuatro pasos:

1. Selección: desde la raíz, baja repetidamente al hijo con el mayor valor UCT hasta llegar a un nodo que todavía no tenga todos sus hijos.
2. Expansión: añádele un hijo por una jugada aún no probada.
3. Simulación: desde el nuevo nodo, juega la partida con jugadas aleatorias hasta un estado terminal.
4. Retropropagación: a todos los nodos del camino de vuelta a la raíz súmales n ← n + 1 y añade a w el resultado de la partida.

Cuando se acaba el tiempo, se juega la jugada de la raíz con mayor n.

Definición — UCT

En la selección, entre los hijos de un nodo con N visitas se elige el hijo i con el mayor valor

UCT(i) = w_i / n_i + c · √(ln N / n_i),

donde c > 0 es la constante de exploración, normalmente √2. A medida que crece el número de iteraciones, la jugada recomendada se acerca a la de minimax.

Lancemos MCTS sobre la posición que minimax resolvió más arriba. Los números de las casillas son las visitas tras 100, 300 y 1000 iteraciones, y debajo, el resultado medio para X:

Tras 100 iteraciones, el centro tiene 47 visitas y las demás jugadas juntas, más. Tras mil, tiene 856 y un resultado medio de 0,94; la jugada de empate abajo en el centro recibió 52 visitas, y las perdedoras, todavía menos. Y eso que MCTS no conoce ni el concepto de horquilla ni ninguna función de evaluación: solo las reglas y el azar. Aun así, encontró la misma jugada que minimax, que tuvo que recorrer todo el resto del árbol.

8. De Deep Blue a AlphaZero

• Deep Blue (1997) derrotó al campeón del mundo Garri Kaspárov. Por dentro había alfa-beta con una función de evaluación escrita a mano y hardware especializado capaz de analizar unos 200 millones de posiciones por segundo.
• Chinook ya jugaba a las damas contra campeones del mundo en los años 90, y en 2007 sus autores resolvieron el juego: recorrieron tantas posiciones que demostraron que una partida sin errores termina en empate, igual que el tres en raya de 3 × 3.
• AlphaGo (2016) derrotó a Lee Se-dol por 4 : 1. Combinó MCTS con redes neuronales: una red proponía jugadas prometedoras (en lugar de la elección aleatoria) y otra estimaba el valor de la posición (en lugar de toda una partida aleatoria hasta el final).
• AlphaZero (2017) prescindió incluso de las partidas humanas. Aprendió ajedrez, shogi y go solo jugando contra sí mismo (aprendizaje por refuerzo) y en cada uno de esos juegos derrotó al mejor programa existente hasta entonces.
• Los juegos con azar e información oculta necesitan más. En el backgammon decide el dado, así que al árbol se añaden nodos de azar con el valor esperado (expectiminimax). En el póquer no ves las cartas del rival; aun así, el programa Libratus (2017) derrotó a profesionales en el póquer de dos jugadores.

La idea de «mira hacia delante antes de hacer algo» no ha desaparecido de los tableros. Los agentes de lenguaje que planifican prueban varias formas de proceder, las evalúan y siguen con la más prometedora; solo que, en lugar de mover piezas, eligen pasos de la solución.

9. Resumen

• Un juego de dos jugadores de suma cero es un problema de búsqueda en el que te repartes las jugadas con un rival; la solución es una estrategia, no un camino.
• Minimax calcula el valor hacia atrás: MAX toma el máximo y MIN el mínimo. El resultado está garantizado frente a cualquier rival.
• Alfa-beta devuelve el mismo valor, pero poda las ramas que no pueden cambiar el resultado; con un buen orden de jugadas ve el doble de profundo.
• Los juegos grandes se exploran hasta una profundidad limitada con una función de evaluación, y ojo con el efecto horizonte.
• MCTS, en lugar de evaluar la posición, la juega al azar hasta el final muchas veces y desarrolla el árbol donde resulta prometedor; combinado con redes neuronales, dio lugar a AlphaGo.

¿Quieres probarlo tú mismo? Pide a un agente de IA que escriba un tres en raya con minimax y luego calcula cuántas posiciones ahorra alfa-beta si ordenas las jugadas del centro hacia los bordes.

¿Lo ves de otra manera? Escribe a support@coden-app.com.