Algoritmo Minimax en Teoría de Juegos | Serie 1 (Introducción)

Minimax es una especie de algoritmo de retroceso que se utiliza en la toma de decisiones y la teoría de juegos para encontrar el movimiento óptimo para un jugador, suponiendo que su oponente también juega de manera óptima. Es ampliamente utilizado en juegos por turnos de dos jugadores como Tic-Tac-Toe, Backgammon, Mancala, Ajedrez, etc.
En Minimax, los dos jugadores se denominan maximizador y minimizador. El maximizador intenta obtener la puntuación más alta posible, mientras que el minimizador intenta hacer lo contrario y obtener la puntuación más baja posible.
Cada estado del tablero tiene un valor asociado. En un estado dado, si el maximizador tiene ventaja, la puntuación del tablero tenderá a ser un valor positivo. Si el minimizador tiene la ventaja en ese estado del tablero, tenderá a ser un valor negativo. Los valores del tablero se calculan mediante unas heurísticas que son únicas para cada tipo de juego.

Ejemplo: 
considere un juego que tiene 4 estados finales y las rutas para alcanzar el estado final van desde la raíz hasta las 4 hojas de un árbol binario perfecto como se muestra a continuación. Suponga que usted es el jugador que maximiza y tiene la primera oportunidad de moverse, es decir, está en la raíz y su oponente en el siguiente nivel. ¿Qué jugada harías como jugador maximizador teniendo en cuenta que tu oponente también juega de manera óptima?

Dado que este es un algoritmo basado en retroceso, prueba todos los movimientos posibles, luego retrocede y toma una decisión. 

• El maximizador va a la IZQUIERDA: Ahora es el turno de los minimizadores. El minimizador ahora puede elegir entre 3 y 5. Al ser el minimizador, definitivamente elegirá el menor entre ambos, es decir, 3.
• El maximizador va a la DERECHA: Ahora es el turno de los minimizadores. El minimizador ahora puede elegir entre 2 y 9. Elegirá 2 porque es el menor entre los dos valores.

Siendo el maximizador, elegiría el valor más grande que es 3. Por lo tanto, el movimiento óptimo para el maximizador es ir a la IZQUIERDA y el valor óptimo es 3.

Ahora el árbol del juego se ve a continuación:

El árbol de arriba muestra dos puntajes posibles cuando el maximizador realiza movimientos hacia la izquierda y hacia la derecha.

Nota: aunque hay un valor de 9 en el subárbol derecho, el minimizador nunca lo seleccionará. Siempre debemos asumir que nuestro oponente juega de manera óptima.

A continuación se muestra la implementación de la misma. 

// A simple C++ program to find
// maximum score that
// maximizing player can get.
#include<bits/stdc++.h>
using namespace std;
 
// Returns the optimal value a maximizer can obtain.
// depth is current depth in game tree.
// nodeIndex is index of current node in scores[].
// isMax is true if current move is
// of maximizer, else false
// scores[] stores leaves of Game tree.
// h is maximum height of Game tree
int minimax(int depth, int nodeIndex, bool isMax,
            int scores[], int h)
{
    // Terminating condition. i.e
    // leaf node is reached
    if (depth == h)
        return scores[nodeIndex];
 
    //  If current move is maximizer,
    // find the maximum attainable
    // value
    if (isMax)
       return max(minimax(depth+1, nodeIndex*2, false, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, false, scores, h));
 
    // Else (If current move is Minimizer), find the minimum
    // attainable value
    else
        return min(minimax(depth+1, nodeIndex*2, true, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, true, scores, h));
}
 
// A utility function to find Log n in base 2
int log2(int n)
{
  return (n==1)? 0 : 1 + log2(n/2);
}
 
// Driver code
int main()
{
    // The number of elements in scores must be
    // a power of 2.
    int scores[] = {3, 5, 2, 9, 12, 5, 23, 23};
    int n = sizeof(scores)/sizeof(scores[0]);
    int h = log2(n);
    int res = minimax(0, 0, true, scores, h);
    cout << "The optimal value is : " << res << endl;
    return 0;
}

// A simple java program to find maximum score that
// maximizing player can get.
 
import java.io.*;
 
class GFG {
   
 
// Returns the optimal value a maximizer can obtain.
// depth is current depth in game tree.
// nodeIndex is index of current node in scores[].
// isMax is true if current move is of maximizer, else false
// scores[] stores leaves of Game tree.
// h is maximum height of Game tree
 static int minimax(int depth, int nodeIndex, boolean  isMax,
            int scores[], int h)
{
    // Terminating condition. i.e leaf node is reached
    if (depth == h)
        return scores[nodeIndex];
 
    // If current move is maximizer, find the maximum attainable
    // value
    if (isMax)
    return Math.max(minimax(depth+1, nodeIndex*2, false, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, false, scores, h));
 
    // Else (If current move is Minimizer), find the minimum
    // attainable value
    else
        return Math.min(minimax(depth+1, nodeIndex*2, true, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, true, scores, h));
}
 
// A utility function to find Log n in base 2
 static int log2(int n)
{
return (n==1)? 0 : 1 + log2(n/2);
}
 
// Driver code
 
    public static void main (String[] args) {
            // The number of elements in scores must be
    // a power of 2.
    int scores[] = {3, 5, 2, 9, 12, 5, 23, 23};
    int n = scores.length;
    int h = log2(n);
    int res = minimax(0, 0, true, scores, h);
    System.out.println( "The optimal value is : "  +res);
         
    }
}
 
// This code is contributed by vt_m

// A simple C# program to find maximum score that
// maximizing player can get.
using System;
 
public class GFG
{
     
// Returns the optimal value a maximizer can obtain.
// depth is current depth in game tree.
// nodeIndex is index of current node in scores[].
// isMax is true if current move is of maximizer, else false
// scores[] stores leaves of Game tree.
// h is maximum height of Game tree
static int minimax(int depth, int nodeIndex, bool isMax,
            int []scores, int h)
{
    // Terminating condition. i.e leaf node is reached
    if (depth == h)
        return scores[nodeIndex];
 
    // If current move is maximizer, find the maximum attainable
    // value
    if (isMax)
    return Math.Max(minimax(depth+1, nodeIndex*2, false, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, false, scores, h));
 
    // Else (If current move is Minimizer), find the minimum
    // attainable value
    else
        return Math.Min(minimax(depth+1, nodeIndex*2, true, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, true, scores, h));
}
 
// A utility function to find Log n in base 2
static int log2(int n)
{
    return (n==1)? 0 : 1 + log2(n/2);
}
 
// Driver code
static public void Main ()
{
 
    // The number of elements in scores must be
    // a power of 2.
    int []scores = {3, 5, 2, 9, 12, 5, 23, 23};
    int n = scores.Length;
    int h = log2(n);
    int res = minimax(0, 0, true, scores, h);
    Console.WriteLine( "The optimal value is : " +res);
     
}
}
 
// This code is contributed by ajit.

# A simple Python3 program to find
# maximum score that
# maximizing player can get
import math
 
def minimax (curDepth, nodeIndex,
             maxTurn, scores,
             targetDepth):
 
    # base case : targetDepth reached
    if (curDepth == targetDepth):
        return scores[nodeIndex]
     
    if (maxTurn):
        return max(minimax(curDepth + 1, nodeIndex * 2,
                    False, scores, targetDepth),
                   minimax(curDepth + 1, nodeIndex * 2 + 1,
                    False, scores, targetDepth))
     
    else:
        return min(minimax(curDepth + 1, nodeIndex * 2,
                     True, scores, targetDepth),
                   minimax(curDepth + 1, nodeIndex * 2 + 1,
                     True, scores, targetDepth))
     
# Driver code
scores = [3, 5, 2, 9, 12, 5, 23, 23]
 
treeDepth = math.log(len(scores), 2)
 
print("The optimal value is : ", end = "")
print(minimax(0, 0, True, scores, treeDepth))
 
# This code is contributed
# by rootshadow

<script>
 
// Javascript program to find maximum score that
// maximizing player can get.
 
// Returns the optimal value a maximizer can obtain.
// depth is current depth in game tree.
// nodeIndex is index of current node in scores[].
// isMax is true if current move is of maximizer, else false
// scores[] stores leaves of Game tree.
// h is maximum height of Game tree
 function minimax(depth, nodeIndex, isMax,
            scores, h)
{
    // Terminating condition. i.e leaf node is reached
    if (depth == h)
        return scores[nodeIndex];
   
    // If current move is maximizer, find the maximum attainable
    // value
    if (isMax)
    return Math.max(minimax(depth+1, nodeIndex*2, false, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, false, scores, h));
   
    // Else (If current move is Minimizer), find the minimum
    // attainable value
    else
        return Math.min(minimax(depth+1, nodeIndex*2, true, scores, h),
            minimax(depth+1, nodeIndex*2 + 1, true, scores, h));
}
   
// A utility function to find Log n in base 2
 function log2(n)
{
return (n==1)? 0 : 1 + log2(n/2);
}
   
 
// Driver Code
 
    // The number of elements in scores must be
    // a power of 2.
    let scores = [3, 5, 2, 9, 12, 5, 23, 23];
    let n = scores.length;
    let h = log2(n);
    let res = minimax(0, 0, true, scores, h);
    document.write( "The optimal value is : "  +res);
         
                       
</script>

Producción: 

The optimal value is:  12

Complejidad temporal: O(b^d) b es el factor de ramificación y d es el conteo de profundidad o capa de gráfico o árbol.

Complejidad espacial: O (bd) donde b es el factor de ramificación en d es la profundidad máxima del árbol similar a DFS.

La idea de este artículo es presentar Minimax con un ejemplo simple. 

• En el ejemplo anterior, solo hay dos opciones para un jugador. En general, puede haber más opciones. En ese caso, necesitamos repetir para todos los movimientos posibles y encontrar el máximo/mínimo. Por ejemplo, en Tic-Tac-Toe, el primer jugador puede hacer 9 movimientos posibles.
• En el ejemplo anterior, se nos dan las puntuaciones (hojas de Game Tree). Para un juego típico, necesitamos derivar estos valores

Pronto cubriremos Tic Tac Toe con el algoritmo Minimax.
Este artículo es una contribución de Akshay L. Aradhya. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.