Explicacion sencilla de en qué consiste el algoritmo minimax

En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada.
La idea consiste en comenzar en la posición actual y usar el generador de movimientos plausibles para generar las posibles posiciones sucesivas hasta un cierto límite de niveles. A continuación se aplica la función de evaluación estática a las posiciones obtenidas y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores.
Se supone una función de evaluación estática que devuelve valores elevados para indicar buenas situaciones y valores negativos para indicar buenas situaciones para el oponente. Visto de esta manera, la meta es maximizar el valor de la función estática de la siguiente posición de tablero.
El nombre del algoritmo deriva de considerar que, dada una función estática que devuelve valores en relación al jugador maximizante, éste procura maximizar su valor mientras que su oponente procura minimizarlo. En un árbol de juego donde los valores de la función estática están en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro. La figura 1 muestra un ejemplo donde  la elección del siguiente movimiento según la búsqueda Minimax de tres niveles sería el nodo D.
El algoritmo Minimax es un procedimiento recursivo, y el corte de la recursión está dado por alguna de las siguientes condiciones:

• Gana algún jugador
• Se han explorado N capas, siendo N el límite establecido
• Se ha agotado el tiempo de exploración
• Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro

En el algoritmo MINIMAX detallado en breve la función de corte de recursión SUFICIENTE (posición, profundidad) sólo considera las dos primeras condiciones de corte.




El algoritmo MINIMAX( posición, profundidad, jugador) usa dos funciones:
 

• GENMOV (posición, jugador): devuelve la lista de movimientos posibles para el jugador a partir de la posición
• ESTÁTICA (posición, jugador): devuelve un número que representa la bondad de la posición desde el punto de vista de jugador.

A diferencia de los valores mostrados en el ejemplo de la figura 1, la función ESTÁTICA devuelve valores en relación al jugador actual en vez del jugador maximizante. Por esta razón, en lugar de realizar maximización y minimización alternativas, siempre se maximiza el valor que devuelve esta función. El algoritmo MINIMAX no necesita tratar diferente a los niveles maximizante y minimizante dado que invierte los valores de un nivel a otro.
La función Minimax devuelve una estructura con

• VALOR: valor propagado de la función estática
• CAMINO: camino para llegar a la solución desde la posición

La primera llamada a la función recursiva será: MINIMAX (posiciónactual, 0,  JUGADOR-UNO)