En las dos lecciones anteriores la furgoneta de NovaMarket buscaba su camino en un mundo pasivo: el mapa no cambiaba porque ella se moviera. Pero en 02-01 vimos que muchos entornos son multiagente, y algunos son competitivos: hay otro agente cuyos objetivos se oponen a los nuestros y que responde a cada decisión con la suya. En esa situación no basta con planificar un camino; hay que preguntarse "¿y qué hará el otro?" en cada paso. La rama de la IA que estudia esto es la búsqueda con adversario, y su algoritmo fundamental es minimax. Lo aprenderemos donde nació, en los juegos: veremos qué cambia respecto a la búsqueda de 03-02, cómo se representa una partida como árbol de juego, cómo minimax elige la mejor jugada suponiendo que el rival también juega perfectamente, y cómo la poda alfa-beta obtiene la misma respuesta explorando una fracción del árbol. Lo implementaremos para el tres en raya, contando nodos para medir cada mejora, y explicaremos por qué en ajedrez o go hace falta cortar la búsqueda y evaluar posiciones con heurísticas (el enlace con Deep Blue y AlphaGo de 01-01). Por último lo llevaremos a NovaMarket con una "guerra de precios" simplificada frente a un competidor, y discutiremos con honestidad dónde termina la utilidad de minimax cuando la información es imperfecta y el juego no es de suma cero.

1. Qué cambia cuando hay un adversario
2. Juegos de suma cero con información perfecta
3. El árbol de juego: niveles MAX y MIN
4. Minimax paso a paso sobre un árbol numérico
5. Minimax para el tres en raya en Python, contando nodos
6. Poda alfa-beta: idea, ejemplo numérico e implementación
7. Límite de profundidad y función de evaluación: de las damas a Deep Blue y AlphaGo
8. Aterrizaje en NovaMarket: la guerra de precios y el defraudador adaptativo
9. Límites de minimax: información imperfecta, suma no cero, incertidumbre

En la búsqueda de 03-02 el agente controlaba todas las decisiones: elegía un tramo, el mundo respondía de forma determinista y el siguiente tramo también lo elegía él. Cuando aparece un adversario, la mitad de las decisiones las toma otro, y las toma en nuestra contra. Esto tiene consecuencias directas:

Diego lo entendió con un ejemplo de su día a día: "cuando planifico una ruta, la ciudad no me la cambia nadie; cuando fijo un precio, el de enfrente lo ve y reacciona en una hora". Esa reacción convierte la decisión en un juego.

Minimax se formula para una clase concreta de juegos, la más simple y a la vez la más estudiada:

• Dos jugadores que alternan turnos. Los llamaremos MAX (nosotros, que queremos maximizar la utilidad) y MIN (el rival, que quiere minimizarla).
• Determinista: no hay dados ni cartas ocultas; el resultado de una jugada es siempre el mismo.
• Información perfecta: ambos ven el estado completo (el tablero) en todo momento.
• Suma cero: lo que gana uno lo pierde el otro. Si al final asignamos +1 a la victoria de MAX, −1 a la de MIN y 0 a las tablas, la utilidad de MIN es exactamente la opuesta a la de MAX, y por eso basta con una sola función de utilidad: MAX la maximiza y MIN la minimiza.

Tres en raya, damas, ajedrez y go cumplen las cuatro condiciones. El póker no (información imperfecta y azar), y muchas situaciones de negocio tampoco (lo veremos en la sección 9). La formulación de un juego como problema añade a la de 02-01 un elemento: la función jugador(estado) que dice a quién le toca. En resumen: estado inicial, jugador(s), acciones(s), resultado(s, a), terminal(s) y utilidad(s).

El árbol de juego es el árbol de búsqueda de 03-02 con una diferencia: los niveles se alternan entre decisiones de MAX y de MIN. La raíz es el estado actual con MAX al turno; sus hijos son las posiciones tras cada jugada de MAX, en las que le toca a MIN; los nietos, las posiciones tras cada respuesta de MIN, y así hasta las hojas, que son estados terminales con su utilidad. Para el tres en raya, desde el tablero vacío el árbol completo tiene 9 ramas en el primer nivel, 8 en el segundo, 7 en el tercero… hasta un total de 549.946 nodos, de los cuales 255.168 son hojas (partidas terminadas). Son menos hojas que las 9! = 362.880 formas de rellenar el tablero porque muchas partidas acaban antes de llenarlo, y hay más nodos que hojas porque contamos también todas las posiciones intermedias. Es lo bastante grande para que merezca la pena ser inteligente y lo bastante pequeño para que Python lo recorra entero en segundos: el vehículo didáctico perfecto.

Antes del tres en raya, un árbol abstracto de dos niveles con las utilidades ya puestas en las hojas. MAX mueve en la raíz A eligiendo entre B, C y D; MIN responde en cada una de ellas eligiendo entre tres hojas.

El razonamiento de minimax va de abajo arriba:

1. En B le toca a MIN. De las hojas 3, 12 y 8 elegirá la menor: B vale 3. Aunque B2 = 12 sea tentador para MAX, nunca lo obtendrá porque MIN no lo permitirá.
2. En C, MIN elige el mínimo de 2, 4, 6: C vale 2.
3. En D, MIN elige el mínimo de 14, 5, 2: D vale 2. Fíjate en la trampa de D1 = 14: la mejor hoja del árbol está ahí, pero MIN se encargará de que no se llegue.
4. En A le toca a MAX, que elige el máximo entre 3, 2 y 2: A vale 3, y la jugada correcta es ir a B.

Ese "3" es el valor minimax de la posición: la utilidad que MAX puede garantizarse si MIN juega perfectamente. Si MIN se equivoca, MAX obtendrá más; si MIN juega bien, MAX no obtendrá menos. En código, la recursión es de una transparencia total:

Observa que minimax es una búsqueda en profundidad (03-02): la recursión baja por la primera rama hasta las hojas antes de mirar la segunda, y solo necesita memoria para el camino actual. Su coste temporal es O(bᵐ), con b jugadas posibles por turno y m niveles de profundidad: para el ajedrez (b ≈ 35, m ≈ 80) es un número con más de 120 cifras. De ahí las secciones 6 y 7.

Ahora un juego real. Decisiones de representación (recuerda 03-01: la representación es media solución):

• El tablero es una lista de 9 casillas, índices 0-8 de izquierda a derecha y de arriba abajo, con "X", "O" o " " (vacía).
• Las líneas ganadoras son 8 tripletas de índices: 3 filas, 3 columnas y 2 diagonales.
• X es MAX y siempre empieza; O es MIN. Utilidad: +1 si gana X, −1 si gana O, 0 en tablas.

Y el algoritmo. Para poder comparar más tarde con alfa-beta, contamos en la variable global nodos cuántas veces se llama a minimax, es decir, cuántas posiciones se examinan:

Puntos importantes del código:

• Hacer y deshacer la jugada sobre la misma lista (t[m] = "X" … t[m] = " ") evita copiar el tablero en cada llamada. Es el patrón de backtracking típico de la búsqueda en profundidad; funciona porque, al volver de la recursión, restauramos exactamente el estado anterior.
• mejor_jugada es la "raíz" del árbol: aplica el mismo criterio que minimax, pero recordando qué jugada da el mejor valor, que es lo que de verdad necesitamos.
• Cada llamada a minimax recorre LINEAS en terminal; podríamos optimizarlo, pero para 550.000 posiciones Python tarda unos segundos, suficiente.

Probémoslo en tres situaciones:

Lectura de resultados:

1. Desde el tablero vacío el valor es 0: con juego perfecto por ambas partes el tres en raya acaba en tablas, algo que cualquier niño descubre jugando y que minimax demuestra explorando 549.945 posiciones (todas las del árbol salvo la raíz). Devuelve la casilla 0 porque es la primera con valor 0; en realidad las nueve aperturas valen 0. Si imprimes el valor de cada una verás que todas empatan y que la más "barata" de analizar es el centro (55.505 nodos frente a 59.705 de las esquinas y 63.905 de los laterales), porque la simetría del centro acorta más partidas.
2. Con O amenazando la columna central, X bloquea en 7; el valor sigue siendo 0 (tablas con buen juego), y solo hacen falta 205 nodos porque quedan pocas casillas.
3. En la tercera posición, X juega en la casilla 3 y el valor pasa a +1: minimax ha encontrado la doble amenaza (columna izquierda y fila central) contra la que O no tiene defensa. Este es el tipo de "visión" que un jugador humano necesita entrenar y que la búsqueda obtiene por pura enumeración.

Si dejas jugar a mejor_jugada contra sí misma desde el tablero vacío obtendrás siempre tablas: minimax nunca pierde y nunca deja escapar una victoria forzada.

Minimax examina el árbol entero, pero gran parte del trabajo es inútil: hay ramas cuyo resultado no puede cambiar la decisión, y podemos dejar de explorarlas en cuanto lo sepamos. Esa es la poda alfa-beta, que devuelve exactamente el mismo valor y la misma jugada que minimax, pero visitando muchos menos nodos.

Volvamos al árbol numérico de la sección 4 y sigamos el orden en que la búsqueda en profundidad lo recorre:

1. Se explora B entero: B1 = 3, B2 = 12, B3 = 8, así que B = 3. MAX ya sabe que en A puede garantizarse al menos 3. Ese "al menos" es alfa (α): la mejor opción encontrada hasta ahora para MAX en el camino desde la raíz.
2. Se empieza C. La primera hoja es C1 = 2. Como MIN elige el mínimo, C valdrá 2 o menos. Pero MAX ya tiene garantizado 3 en B; una rama que vale como mucho 2 nunca será elegida. No hace falta mirar C2 ni C3: se podan.
3. Se empieza D. D1 = 14: D vale como mucho 14, todavía podría superar a 3, seguimos. D2 = 5: D vale como mucho 5, todavía podría superar a 3, seguimos. D3 = 2: D vale como mucho 2, ya no puede superar a 3. Aquí no hemos ahorrado nada porque la hoja mala estaba la última.

Resultado: mismo valor (3, ir a B) explorando 11 nodos en lugar de 13. En el paso 3 se ve la clave del rendimiento: el orden importa. Si D3 hubiera estado primero, D se habría podado tras una sola hoja. Con un orden perfecto (probar primero las mejores jugadas), alfa-beta explora del orden de b^(m/2) nodos en lugar de bᵐ: puede mirar el doble de profundidad con el mismo esfuerzo. Con orden aleatorio la ganancia es menor pero sigue siendo grande.

Formalmente se mantienen dos valores durante la recursión: α = la mejor utilidad que MAX puede asegurarse hasta ahora (empieza en −∞ y solo crece), y β = la mejor utilidad que MIN puede asegurarse hasta ahora (empieza en +∞ y solo baja). En cuanto α ≥ β en algún nodo, el resto de sus hijos se descarta: MAX ya tiene algo mejor en otro sitio (o MIN ya tiene algo peor para nosotros en otro sitio) y esta rama nunca se jugará.

Comparación directa, misma jugada y mismo valor en los tres casos:

Y una comprobación del efecto del orden: si en movimientos devolvemos primero el centro, luego las esquinas y luego los laterales (el orden que cualquier jugador con experiencia probaría), la búsqueda desde el tablero vacío baja de 18.296 a 7.274 nodos, 75 veces menos que minimax puro. En los motores de ajedrez, ordenar bien las jugadas (capturas primero, jugadas que fueron buenas en búsquedas anteriores…) es tan importante como la poda misma.

El tres en raya se agota entero. El ajedrez, con unas 35 jugadas legales por posición y partidas de 80 medias jugadas, tiene un árbol del orden de 35⁸⁰ ≈ 10¹²³ nodos; el go, con 250 jugadas por turno y partidas de 150 movimientos, del orden de 10³⁶⁰. Ni alfa-beta ni ningún ordenador concebible los recorren. La solución práctica tiene dos partes:

• Cortar la búsqueda a una profundidad máxima (por ejemplo, 6 medias jugadas) y tratar esas posiciones como si fueran hojas.
• Sustituir la utilidad exacta (que solo se conoce en posiciones terminales) por una función de evaluación heurística que estime lo buena que es una posición para MAX: en ajedrez, material (peón 1, caballo 3, torre 5…), movilidad, seguridad del rey; en go, territorio e influencia. Es la misma idea que la heurística h de A* en 03-02: una estimación barata que guía la búsqueda cuando lo exacto es inalcanzable.

Para el tres en raya podemos construir una evaluación sencilla: número de líneas todavía "abiertas" para X (sin ninguna O), ponderadas por cuántas X ya tienen, menos lo mismo para O. Con profundidad 1 esta evaluación ya prefiere el centro (valor 4, porque el centro está en cuatro líneas) sobre las esquinas (3) y los laterales (2). No demuestra nada, pero orienta bien, y en juegos grandes eso es todo lo que se puede pedir.

Esta combinación (alfa-beta + profundidad limitada + evaluación heurística + ordenación de jugadas + tablas de posiciones ya vistas) es exactamente la arquitectura de Deep Blue, que en 1997 venció a Kaspárov analizando unos 200 millones de posiciones por segundo con una función de evaluación diseñada a mano por grandes maestros e ingenieros, como recordamos en 01-01. Es una IA simbólica y de búsqueda pura (02-02): no aprendió a jugar; buscó más lejos y evaluó mejor que un humano. El go resistió veinte años más porque su factor de ramificación es demasiado grande incluso para alfa-beta y porque nadie supo escribir una función de evaluación buena a mano; AlphaGo (2016) resolvió justamente ese punto sustituyendo la evaluación manual por una red neuronal entrenada con partidas y con juego contra sí misma, y combinándola con una forma de búsqueda por muestreo. Cómo se entrena esa red es materia de aprendizaje por refuerzo (04-02) y de redes neuronales (módulo 5); lo que importa aquí es ver que la búsqueda con adversario sigue siendo el esqueleto y que lo que evolucionó fue de dónde sale la evaluación.

Diego y Marta quieren decidir el precio semanal de un televisor estrella sabiendo que su principal competidor reacciona a sus movimientos. Modelémoslo como un juego de dos niveles: NovaMarket (MAX) elige entre mantener el precio, bajarlo un 5 % o bajarlo un 10 %; el competidor (MIN) responde manteniendo, igualando o bajando aún más. En las hojas ponemos el margen semanal estimado de NovaMarket (en miles de euros) para cada combinación, obtenido de sus datos históricos de ventas:

Reutilizamos la recursión genérica de la sección 4 con nombres del negocio:

Minimax recomienda bajar un 5 %, no porque sea la opción con la mejor hoja (la mejor hoja, 14, también está en esa rama, pero eso es casualidad), sino porque es la que garantiza más en el peor caso: pase lo que pase, el margen no bajará de 5.000 €. Mantener el precio tiene la peor garantía (3) porque deja al competidor la iniciativa. Este razonamiento de "asegurar el suelo" es lo que aporta minimax a una decisión de negocio, y es especialmente valioso cuando el coste de equivocarse es alto.

El caso 3 (fraude en devoluciones) es otro entorno con adversario: cuando NovaMarket endurece una regla ("bloquear devoluciones sin ticket a partir de la tercera al mes"), los defraudadores la aprenden y cambian de táctica (reparten devoluciones entre varias cuentas, bajan de tres). El detector que se diseña pensando solo en el comportamiento pasado es como un jugador que no mira las respuestas del rival. Pensar en modo minimax significa preguntarse, para cada regla candidata, "¿cuál es la mejor respuesta del defraudador a esta regla y cuánto fraude se me cuela entonces?", y elegir la regla cuya peor respuesta es la menos dañina. En la práctica no se construye un árbol explícito, pero el hábito mental es el mismo, y volveremos sobre él cuando hablemos de la evaluación de modelos de fraude en el módulo 4.

La guerra de precios de 8.1 es útil como ejercicio de pensamiento, pero conviene ser honestos sobre en qué se aleja de un juego de tablero. Cada diferencia señala una herramienta distinta:

Un ejemplo concreto de la primera fila: si además del margen de NovaMarket estimamos el margen del competidor en cada hoja y suponemos que él maximiza el suyo en lugar de minimizar el nuestro, la respuesta prevista a "bajar 5 %" pasa de "bajar 10 %" (que a él le deja 6.000 €) a "igualar" (que le deja 9.000 €), y el margen que deberíamos esperar es 8, no 5. En este caso la decisión no cambia (bajar 5 % sigue siendo lo mejor), pero la valoración sí, y en otros casos podría cambiar también la decisión. Minimax da el suelo garantizado; el modelo del rival da la expectativa realista. Un buen analista mira los dos.

Lo que sí es universal es la lección de fondo: cuando hay otro agente que reacciona, una decisión no se puede evaluar sola, hay que evaluarla junto con la mejor respuesta del otro. Ese principio, con o sin árbol explícito, es la aportación de esta lección al resto del curso.

• Olvidar deshacer la jugada (t[m] = " ") tras la llamada recursiva: el tablero queda corrompido y los resultados son absurdos. Si prefieres evitar el riesgo, crea una copia (nuevo = list(t)) a costa de más memoria y tiempo.
• Confundir el valor de una posición con la jugada: minimax devuelve un número; hay que envolverlo (mejor_jugada) para saber qué movimiento produce ese número.
• Poner las condiciones de poda al revés: MAX actualiza α y poda si α ≥ β; MIN actualiza β y poda con la misma condición. Un error habitual es actualizar β en MAX. Compruébalo siempre con el árbol de la sección 4: debes obtener 3 podando C tras C1.
• Creer que alfa-beta cambia el resultado: nunca. Si obtienes valores distintos entre minimax y alfabeta, hay un error en la implementación de la poda.
• No inicializar alfa y beta en la raíz a −∞ y +∞: cualquier otro valor puede podar ramas válidas.
• Aplicar minimax a un problema que no es de suma cero sin darse cuenta: como en la guerra de precios, la respuesta será excesivamente pesimista. Pregúntate siempre si "lo que yo pierdo lo gana el otro" es literalmente cierto.
• Función de evaluación con la escala equivocada: si las posiciones terminales valen ±1 y la evaluación heurística devuelve valores como 4 o −3, una posición "prometedora" puede parecer mejor que una victoria segura. Escala la utilidad terminal (por ejemplo ±100) para que domine.

Dado el árbol siguiente (MAX en la raíz, MIN en el segundo nivel, hojas con utilidades), calcula el valor minimax de la raíz y la jugada elegida. Después aplica alfa-beta recorriendo los hijos de izquierda a derecha e indica qué hojas se podan.

Modifica movimientos para que devuelva las casillas en el orden centro, esquinas, laterales ([4, 0, 2, 6, 8, 1, 3, 5, 7] filtrando las ocupadas) y compara los nodos explorados por mejor_jugada_ab desde el tablero vacío con el orden original. Comprueba que el valor y la jugada recomendada (ahora la casilla 4) siguen valiendo 0. ¿Cambia el número de nodos de mejor_jugada (minimax sin poda) al reordenar? ¿Por qué?

Añade el diccionario MARGEN_COMP con el margen del competidor en cada hoja (usa estos valores: mantener → 10, 11, 9; bajar_5 → 7, 9, 6; bajar_10 → 5, 7, 4, en el mismo orden que las hojas de ARBOL_PRECIOS) y escribe una función respuesta_racional(opcion) que devuelva la hoja donde el competidor maximiza su margen. Para cada opción de NovaMarket imprime la respuesta prevista, nuestro margen y el suyo, y compara la recomendación con la de minimax.

Solución 1. E = min(5, 9, 4) = 4; F = min(2, 7, 8) = 2; G = min(6, 11, 3) = 3. Raíz = max(4, 2, 3) = 4, jugada E. Con alfa-beta: se explora E entero (α pasa a 4). En F, la primera hoja es 2 ≤ α, así que F no puede superar a 4: se podan 7 y 8. En G, la primera hoja es 6 > 4 (seguimos), la segunda 11 (seguimos), la tercera 3 hace G = 3 < 4; no hay poda porque la hoja mala llegó al final. Total: 7 hojas examinadas de 9 (se ahorran 2), mismo resultado que minimax. Si el orden dentro de G hubiera sido 3, 6, 11, también se habrían podado 6 y 11 y bastarían 5 hojas.

Solución 2.

Alfa-beta baja de 18.296 a 7.274 nodos y recomienda ahora la casilla 4 (el centro; sigue valiendo 0 como todas). Minimax sin poda explora exactamente los mismos 549.945 nodos: sin poda, el orden solo cambia cuándo se visita cada nodo, no si se visita. La ordenación solo tiene efecto cuando hay algo que podar.

Solución 3.

El competidor racional responde a "mantener" bajando un 5 % (le da 11), y a nuestras bajadas igualándolas. La mejor opción para NovaMarket sigue siendo bajar un 5 %, con un margen esperado de 8 frente al suelo de 5 que garantizaba minimax. Las dos formas de razonar coinciden en la decisión, pero no en la cifra: minimax es un seguro contra el peor caso; el modelo del rival, una predicción de lo probable.

Hemos añadido a la búsqueda un ingrediente nuevo: un adversario que decide en nuestra contra. Hemos visto que en los juegos de suma cero con información perfecta una solución ya no es un camino sino una estrategia, y que el árbol de juego alterna niveles MAX y MIN. El algoritmo minimax recorre ese árbol en profundidad y propaga hacia arriba, desde las hojas, el valor que cada jugador puede garantizarse; lo hemos seguido a mano en un árbol numérico y lo hemos implementado para el tres en raya, comprobando que el juego es tablas y que hacen falta 549.945 nodos para demostrarlo. La poda alfa-beta obtiene el mismo resultado explorando 18.296 nodos (7.274 con una buena ordenación de jugadas), y el límite de profundidad con función de evaluación es lo que permite jugar al ajedrez o al go, el camino que va de Deep Blue a AlphaGo. Con la guerra de precios de NovaMarket hemos visto que el hábito de "evaluar cada decisión junto con la mejor respuesta del rival" es útil también en el negocio, y hemos delimitado con claridad cuándo minimax deja de ser el modelo adecuado (suma no cero, información imperfecta, azar, repetición).

Nos queda el tercer gran problema anunciado al abrir el módulo. Hasta ahora hemos buscado caminos (03-02) y jugadas (03-03) explorando el espacio de estados de forma sistemática. Pero el problema completo de la furgoneta (elegir el orden de todas las entregas del día) tiene, como vimos en 03-01, n! soluciones candidatas, y ninguna búsqueda sistemática lo agota. En la última lección del módulo, Algoritmos de Optimización, cambiaremos de enfoque: en lugar de construir la solución paso a paso, partiremos de una solución completa cualquiera y la iremos mejorando con ascenso de colina, recocido simulado y algoritmos genéticos, para resolver el problema del viajante de la furgoneta y la asignación de pedidos a los almacenes de Zaragoza y Getafe.