Algoritmo Minimax

El algoritmo Minimax es un método de decisión para juegos por turnos entre dos adversarios: elige la jugada que maximiza la ganancia mínima que el jugador puede garantizarse, suponiendo que el rival juega de forma óptima. Equivale a minimizar la pérdida máxima, de ahí su nombre.

Cómo funciona

Minimax explora el árbol del juego y propaga valores desde las posiciones finales hacia la jugada actual, alternando dos papeles: en los nodos donde decide el jugador (MAX) se toma el valor máximo de las opciones, y en los nodos donde decide el rival (MIN), el mínimo. Esa alternancia da nombre al algoritmo y determina la mejor jugada asumiendo el peor rival posible.

Sus supuestos

El Minimax básico solo aplica bajo unos supuestos concretos: un juego de dos jugadores, por turnos, de suma cero (lo que uno gana el otro lo pierde), determinista (sin azar) y de información perfecta (ambos ven todo el estado). El ajedrez, las damas o el tres en raya lo cumplen; el póker, con información oculta, o el backgammon, con dados, exigen variantes como expectimax.

Relación con la teoría de juegos y eficiencia

Conviene un matiz que se suele confundir. Existe un teorema minimax, demostrado por John von Neumann en 1928, que es un resultado matemático: garantiza que todo juego finito de dos jugadores y suma cero tiene un valor bien definido, y en ese caso su solución coincide con un equilibrio de Nash. Pero el algoritmo de búsqueda en árbol es un procedimiento de decisión, no una derivación del equilibrio de Nash: no conviene presentar a Nash como su «fundamento directo». En cuanto a la eficiencia, el coste de Minimax crece de forma exponencial con la profundidad; la poda alfa-beta lo reduce sin cambiar el resultado, descartando ramas que no pueden influir en la decisión, y en juegos enormes como el ajedrez o el Go se corta la búsqueda a cierta profundidad y se emplea una función de evaluación.