Tema
Minimax
- IA clásica
- Nivel intermedio
- Con simulador interactivo
En un juego de dos jugadores, suma cero e información perfecta, el valor minimax de un nodo es el máximo de los valores de sus hijos si le toca mover al jugador que maximiza, y el mínimo si le toca al oponente.
Nombre en inglés
Minimax
Intuición
Conviene leer el árbol de abajo hacia arriba suponiendo que el rival juega tan bien como uno mismo. Cada capa alterna entre elegir lo mejor y sufrir lo peor, de modo que el valor de la raíz es lo que se garantiza contra un oponente perfecto. Como el árbol completo rara vez cabe en memoria, en la práctica se corta a una profundidad fija y las hojas se sustituyen por una función de evaluación del tablero.
Fórmula
minimax(n) = eval(n) si n es hoja; max_{h hijo} minimax(h) si mueve MAX; min_{h hijo} minimax(h) si mueve MIN
Ejemplo resuelto
Un árbol de profundidad 2 tiene una raíz MAX con tres hijos MIN. El primer hijo MIN tiene las hojas 3, 12 y 8, el segundo tiene 2, 4 y 6 y el tercero tiene 14, 5 y 2. Los nodos MIN toman el mínimo de sus hojas, de modo que valen 3, 2 y 2. La raíz MAX toma el máximo de 3, 2 y 2, que es 3, y su mejor jugada es la primera. El valor 12 de la primera rama no sirve de nada, porque el oponente nunca dejaría llegar ahí.
Errores frecuentes
- Evaluar las hojas desde el punto de vista del jugador al que le toca mover en esa hoja, cuando la función de evaluación debe medir siempre desde la perspectiva del mismo jugador para que las comparaciones tengan sentido.
- Ignorar el efecto horizonte, es decir, cortar la búsqueda justo antes de una captura decisiva y tomar por buena una posición que se derrumba un movimiento después.
- Suponer que duplicar la profundidad mejora siempre el juego, cuando con una función de evaluación mal calibrada una profundidad mayor propaga con más fuerza el mismo sesgo.
Ejercicio
La raíz es un nodo MIN con dos hijos MAX. El primer hijo tiene las hojas 7 y 2 y el segundo tiene las hojas 5 y 9. Calcula el valor minimax de la raíz.
Ver la solución
Los dos hijos son nodos MAX, así que toman el máximo de sus hojas. El primero vale max(7, 2) = 7 y el segundo vale max(5, 9) = 9. La raíz es un nodo MIN y toma el mínimo de 7 y 9, que es 7. Conviene notar que la hoja de valor 9, la mayor del árbol, no influye en el resultado porque el jugador que minimiza nunca elegiría esa rama.
Respuesta: 7
Temas relacionados
Cursos a los que prepara
Simulador
Este tema tiene un simulador interactivo en la guía.