Minimax: cómo piensa un rival que te desea lo peor

Teoría de juegos, parte 3 de 9

Mánchester, 1952. Alan Turing juega al ajedrez contra Alick Glennie, pero no elige él sus jugadas. Ejecuta un programa que había escrito unos años antes con David Champernowne. Todavía no existe una máquina capaz de ejecutarlo, así que el procesador es el propio Turing: lápiz, papel y decenas de minutos por jugada.

El programa, al que más tarde llamarían Turochamp, perdió la partida en 29 jugadas. Pero la regla que seguía Turing sobrevivió a él y a su época. Hoy la usan para elegir jugada la mayoría de los programas clásicos de ajedrez, y también el bot de damas de MindLounge. Esa regla se llama minimax.

Una jugada se juzga por su peor caso

La idea del minimax cabe en una frase: juzga tu jugada por la mejor respuesta del rival, no por la respuesta que esperas.

La forma más sencilla de verlo es una trampa que casi todo el mundo conoce cuando aprende a jugar, el mate del pastor:

1.e4 e5 2.Ac4 Cc6 3.Dh5

Las blancas amenazan 4.Dxf7, mate. Si las negras no ven la amenaza y juegan, por ejemplo, 3...Cf6??, la partida termina en una jugada. Hay quien pone esta trampa porque «¿y si sale bien?».

El minimax hace otra pregunta: ¿qué pasa si las negras encuentran la mejor respuesta? Así valora Stockfish 16, aproximadamente, las dos opciones (profundidad 28–30, en peones; el signo más indica ventaja blanca):

Tras 3...g6 la dama tiene que retirarse y las negras ganan tiempo para desarrollarse. La pequeña ventaja que las blancas tenían por mover primero pasa al rival. Es modesta, pero es un precio, y no merece la pena pagarlo por la esperanza de un error ajeno. Puedes analizar tú mismo la posición tras 3.Dh5.

¿De dónde viene el nombre? En cada posición, el rival elige la jugada que minimiza tu resultado. Entre tus jugadas, tú eliges aquella cuyo mínimo es el máximo. El máximo de los mínimos: minimax.

Por qué aquí el pesimismo no es una debilidad

En la vida diaria, a quien siempre espera lo peor rara vez se le llama sabio. ¿Por qué entonces es la estrategia correcta frente al tablero?

La respuesta la dio el matemático de origen húngaro John von Neumann. En 1928, la revista Mathematische Annalen publicó su artículo «Zur Theorie der Gesellschaftsspiele», «Sobre la teoría de los juegos de salón». Su idea clave es el juego de suma cero: lo que gana un jugador lo pierde el otro. El ajedrez, las damas, el go y el póquer a dos son juegos de suma cero.

En un juego así, el rival que te desea lo peor no es malvado. Simplemente juega para sí mismo. Lo peor para ti es exactamente lo mejor para él. Por eso suponer que encontrará la respuesta más fuerte no es pesimismo: es tomarse en serio sus intereses.

Von Neumann demostró algo más. Todo juego finito de dos jugadores y suma cero tiene un número: el valor del juego.

El primer jugador puede garantizarse al menos ese resultado, juegue como juegue el rival. El segundo puede garantizar que el primero no obtendrá más. La garantía «desde abajo» y la garantía «desde arriba» coinciden.

Hay una advertencia importante. En los juegos con información oculta, como piedra, papel o tijera, esa igualdad solo se cumple si los jugadores eligen sus jugadas al azar con ciertas probabilidades. Esas estrategias mixtas tendrán su propia parte en la serie.

En el ajedrez y las damas, donde todo está a la vista, el valor se alcanza con una secuencia normal de jugadas. Es lo que en la segunda parte llamamos «la respuesta del ajedrez».

En 1944, von Neumann y el economista Oskar Morgenstern publicaron Theory of Games and Economic Behavior (Teoría de juegos y comportamiento económico). Con ese libro, la teoría de juegos salió del tablero.

Cómo calculan las máquinas

El teorema dice que el valor del juego existe, pero no cómo encontrarlo. Como vimos en la parte anterior, el ajedrez no se puede calcular hasta el final. ¿Qué hace entonces un programa?

En 1950, Claude Shannon describió una receta que se sigue usando. El programa despliega un árbol de variantes unas cuantas medias jugadas hacia delante y ahí se detiene. Las posiciones finales las valora de forma aproximada con una función de evaluación: material, actividad de las piezas, seguridad del rey.

Después, esas valoraciones suben por el árbol según la regla del minimax. Donde mueve el programa se toma el máximo; donde mueve el rival, el mínimo.

El programa de Turing hacía exactamente eso, solo que sobre el papel. Miraba unas tres medias jugadas hacia delante y seguía las capturas hasta que no quedaba ninguna.

El segundo gran hallazgo fue la poda alfa-beta. Varios investigadores la descubrieron de forma independiente en los años cincuenta y sesenta; Donald Knuth y Ronald Moore publicaron un análisis completo en 1975. La idea le resultará familiar a cualquiera que haya tardado demasiado en elegir restaurante.

Supón que ya has encontrado una jugada que te garantiza una posición igualada. Ahora revisas otra y ves que el rival tiene una respuesta tras la cual pierdes una pieza. No hace falta mirar el resto de respuestas a esa jugada: ya es peor que la que tienes. Con un orden de jugadas ideal, esta poda permite calcular hasta aproximadamente el doble de profundo en el mismo tiempo.

El Stockfish actual funciona igual: búsqueda alfa-beta más una función de evaluación. Solo ha cambiado la evaluación. Desde 2020 usa una red neuronal llamada NNUE, y no solo reglas escritas por personas.

El minimax en MindLounge

El bot de ajedrez de MindLounge es Stockfish, debilitado a propósito con su ajuste de nivel. Para las damas no existe un motor de esa categoría listo para usar, así que el bot de damas se escribió desde cero para el portal. Es minimax con poda alfa-beta en estado puro.

Esto es lo que muestra su código:

• los niveles solo se diferencian en la profundidad: el fácil calcula 2 medias jugadas, el medio 4 y el difícil 6;
• una ficha vale 1 punto y una dama 1,6, y se suman 0,05 por cada fila que avanza una ficha;
• entre dos caminos igual de ganadores, el bot elige el más corto.

En MindLounge se juega con reglas angloamericanas: damas que avanzan una sola casilla, captura obligatoria y obligación de completar las capturas múltiples.

¿Qué significa en la práctica una profundidad de 2? Tomamos una posición construida para este artículo y ejecutamos en ella el código del bot. El bot juega con negras («n»); mueven las negras:

8 · · · · 7 · · n n 6 · · · · 5 · · b n 4 · · · · 3 · · · b 2 · b · · 1 · · · · a b c d e f g h

El nivel fácil jugó e7-f6. Parece una jugada activa: las negras atacan la ficha de e5. Con profundidad 2, el bot ve su jugada y una respuesta de las blancas. Cuatro jugadas recibieron la misma valoración y, como indica su código, eligió la primera.

Pero las blancas responden g3-h4. Ahora las negras están obligadas a capturar: f6xd4. Esa captura deja libre f6, y las blancas se comen dos fichas de una vez, h4xf6xh8, y además coronan. La última ficha negra, en d4, cae en la jugada siguiente.

Los niveles medio y difícil jugaron g5-f4. La profundidad 4 vio que e7-f6 pierde una ficha. La profundidad 6 vio más: tras e7-f6 la partida está perdida.

La misma regla, el mismo código; la única diferencia es hasta dónde ve. Los programadores lo llaman efecto horizonte: lo que ocurre más allá de la profundidad de búsqueda, para el minimax, no existe.

Donde el minimax no ayuda

También conviene conocer los límites de esta forma de pensar.

El horizonte. El minimax es exactamente tan bueno como profundo. Una persona frente al tablero también tiene horizonte. Preguntarse antes de cada jugada «¿y si el rival encuentra la respuesta más fuerte?» es una manera de alejarlo al menos media jugada.

Un rival de carne y hueso. El minimax supone que el rival juega a la perfección. Las personas se equivocan, y los jugadores con experiencia a veces eligen la jugada que plantea más problemas prácticos. Pero un cálculo honesto pregunta primero si esa jugada empeora la posición frente a un juego preciso. Si la empeora, ya no es una estrategia, sino una apuesta por el error.

La suma distinta de cero. Es el límite principal. El minimax tiene sentido cuando tu ganancia es la pérdida del rival. En una negociación, en el trabajo o en la amistad no suele ser así. Si ahí actúas como si el otro te deseara lo peor, los dos pueden quedarse sin nada. De eso trata la próxima parte de la serie.

Ejercicio

1. Otra posición en la que probamos el bot. El nivel fácil (negras) jugó a7-b6. Encuentra la jugada de las blancas que gana material.

8 · · · · 7 n n · · 6 · · · · 5 · n b · 4 n · · · 3 b · b · 2 b · · · 1 · · · · a b c d e f g h

1. Eliges entre las jugadas A y B. Contra A, el rival tiene dos respuestas: tras una quedas en +3 y tras la otra en −1. Contra B, las dos respuestas te dejan en +1 y +2. ¿Qué jugada elige el minimax? ¿Y quien confía en un error del rival?
2. Juega contra el bot de damas de MindLounge en nivel fácil e intenta prepararle un golpe de «doy una, como dos». Después prueba lo mismo en el nivel medio.

Las respuestas están al final.

Preguntas para el debate

• ¿Alguna vez has puesto una trampa contando con el error del rival? ¿Cómo terminó?
• ¿En qué situaciones de tu vida es útil suponer la peor jugada del «rival» y en cuáles esa suposición hace daño?
• En el nivel fácil, el bot no calcula mal: simplemente no ve lejos. ¿Se parecen a eso tus propios errores en el tablero?

Próximamente en la serie: «El dilema del prisionero», un juego en el que cada uno actúa con sensatez para sí mismo… y los dos pierden.

Respuestas. 1) e3-d4. Las negras están obligadas a capturar con c5xe3, y las blancas responden con la captura doble a3xc5xa7. En esta posición, los niveles medio y difícil juegan c7-b6 y no permiten el golpe. 2) El minimax elige B: su peor caso es +1, mientras que el de A es −1. Quien confía en un error elige A por el +3. 3) Aquí no hay respuesta fija: el experimento es tuyo.