• El algoritmo mini-max es un algoritmo recursivo o de retroceso que se utiliza en la toma de decisiones y en la teoría de juegos. Proporciona un movimiento óptimo para el jugador suponiendo que el oponente también esté jugando de manera óptima.
• El algoritmo Mini-Max utiliza recursividad para buscar en el árbol del juego.
• El algoritmo Min-Max se utiliza principalmente para jugar en IA. Como ajedrez, damas, tres en raya, go y varios juegos de dos jugadores. Este algoritmo calcula la decisión minimax para el estado actual.
• En este algoritmo juegan dos jugadores, uno se llama MAX y el otro se llama MIN.
• Ambos jugadores luchan, ya que el jugador oponente obtiene el beneficio mínimo mientras que él obtiene el beneficio máximo.
• Ambos jugadores del juego son oponentes entre sí, donde MAX seleccionará el valor maximizado y MIN seleccionará el valor minimizado.
• El algoritmo minimax realiza un algoritmo de búsqueda en profundidad para la exploración del árbol de juego completo.
• El algoritmo minimax continúa hasta el nodo terminal del árbol y luego retrocede en el árbol como recursión.

Pseudocódigo para el algoritmo MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Llamada inicial:

Minimax(nodo, 3, verdadero)

Funcionamiento del algoritmo Min-Max:

• El funcionamiento del algoritmo minimax se puede describir fácilmente mediante un ejemplo. A continuación hemos tomado un ejemplo de árbol de juegos que representa el juego de dos jugadores.
• En este ejemplo, hay dos jugadores, uno se llama Maximizer y otro se llama Minimizer.
• Maximizer intentará obtener la máxima puntuación posible y Minimizer intentará obtener la mínima puntuación posible.
• Este algoritmo aplica DFS, por lo que en este árbol de juego, tenemos que atravesar todas las hojas para llegar a los nodos terminales.
• En el nodo terminal, se dan los valores terminales, por lo que compararemos esos valores y retrocederemos en el árbol hasta que ocurra el estado inicial. Los siguientes son los pasos principales necesarios para resolver el árbol del juego para dos jugadores:

Paso 1: En el primer paso, el algoritmo genera el árbol de juego completo y aplica la función de utilidad para obtener los valores de utilidad para los estados terminales. En el siguiente diagrama de árbol, tomemos que A es el estado inicial del árbol. Supongamos que el maximizador toma el primer turno que tiene el valor inicial en el peor de los casos = - infinito, y el minimizador tomará el siguiente turno que tiene el valor inicial en el peor de los casos = + infinito.

Paso 2: Ahora, primero encontramos el valor de las utilidades para el Maximizador, su valor inicial es -∞, por lo que compararemos cada valor en el estado terminal con el valor inicial del Maximizador y determinaremos los valores de los nodos más altos. Encontrará el máximo entre todos.

• Para el nodo D max(-1,- -∞) => max(-1,4)= 4
• Para el nodo E max(2, -∞) => max(2, 6)= 6
• Para el nodo F máx(-3, -∞) => máx(-3,-5) = -3
• Para el nodo G max(0, -∞) = max(0, 7) = 7

Paso 3: En el siguiente paso, le toca el turno al minimizador, por lo que comparará el valor de todos los nodos con +∞ y encontrará los 3.^tercerovalores de nodo de capa.

• Para el nodo B= min(4,6) = 4
• Para el nodo C= min (-3, 7) = -3

Etapa 4: Ahora es el turno de Maximizer, que nuevamente elegirá el valor máximo de todos los nodos y encontrará el valor máximo para el nodo raíz. En este árbol de juego, solo hay 4 capas, por lo que llegamos inmediatamente al nodo raíz, pero en juegos reales, habrá más de 4 capas.

• Para el nodo A max(4, -3)= 4

Ese fue el flujo de trabajo completo del juego minimax para dos jugadores.

Propiedades del algoritmo Mini-Max:

Completo-El algoritmo Min-Max está completo. Definitivamente encontrará una solución (si existe) en el árbol de búsqueda finito.Óptimo-El algoritmo Min-Max es óptimo si ambos oponentes juegan de manera óptima.Complejidad del tiempo-Como realiza DFS para el árbol de juegos, la complejidad temporal del algoritmo Min-Max es Transmisión exterior^metro) , donde b es el factor de ramificación del árbol del juego y m es la profundidad máxima del árbol.Complejidad espacial-La complejidad espacial del algoritmo Mini-max también es similar a DFS, que es O(bm) .

Limitación del algoritmo minimax:

El principal inconveniente del algoritmo minimax es que se vuelve muy lento para juegos complejos como el ajedrez, el go, etc. Este tipo de juegos tiene un factor de ramificación enorme y el jugador tiene muchas opciones para decidir. Esta limitación del algoritmo minimax se puede mejorar a partir de poda alfa-beta que hemos discutido en el siguiente tema.