MiniMax

Metadatos

Tipo: Algoritmo · Nivel: Intermedio · Dificultad: 2.5 · Complejidad: O(n)

Requisitos: Backtracking 🏗️

Minimax es un algoritmo de búsqueda recursivo usado en juegos de dos jugadores de suma cero con información perfecta para minimizar la posible pérdida máxima. Se basa en la idea de que un jugador intenta maximizar su puntuación mientras el otro intenta minimizarla.

Idea

Este algoritmo asume que ambos jugadores juegan de manera óptima. Se construye un árbol de juego donde cada nodo representa un estado del juego y cada arista un posible movimiento. El algoritmo sigue una estrategia de backtracking para explorar todos los posibles movimientos y sus consecuencias, evaluando los estados terminales del juego para determinar el mejor movimiento inicial.

Código

C++Python

fullcleancontest

/**
 * Minimax algorithm for two-player zero-sum games with perfect information.
 *
 * Finds the optimal move for the player to move, assuming the opponent also
 * plays optimally: one player maximizes the score, the other minimizes it.
 *
 * The algorithm is generic. A concrete game (see test/driver.cpp for the Coins
 * game) provides its own State type and two functions:
 *   - possible_moves_funct(state): the states reachable in one move; an empty
 *     vector means `state` is terminal (the game is over).
 *   - score_funct(state): the score of a terminal state, from the maximizing
 *     player's point of view (higher is better for them).
 *
 * A move is identified by its index in the possible_moves list, so best_move is
 * the index of the chosen child (-1 if `current_state` is already terminal).
 *
 * Returns: {best_value, best_move}.
 * Complexity: O(b^d) time, O(d) space (b = branching factor, d = tree depth).
 */
#include <vector>
#include <functional>
#include <limits>
#include <utility>
using namespace std;

template <typename State>
pair<double, int> minimax(
    const State& current_state,
    int maximizing_player,
    const function<vector<State>(const State&)>& possible_moves_funct,
    const function<double(const State&)>& score_funct) {

    // Base case: a terminal state (no moves left) is scored directly.
    vector<State> next_states = possible_moves_funct(current_state);
    if (next_states.empty())
        return {score_funct(current_state), -1};

    // The maximizing player wants the highest score, the minimizing one the lowest.
    double best_value = (maximizing_player == 1)
        ? -numeric_limits<double>::infinity()
        :  numeric_limits<double>::infinity();
    int best_move = -1;

    // Try every move; the opponent moves next, so flip who is maximizing.
    for (int index = 0; index < (int) next_states.size(); ++index) {
        double value = minimax(next_states[index], -maximizing_player,
                               possible_moves_funct, score_funct).first;
        if (maximizing_player == 1) {
            if (value > best_value) { best_value = value; best_move = index; }
        } else {
            if (value < best_value) { best_value = value; best_move = index; }
        }
    }

    return {best_value, best_move};
}

#include <vector>
#include <functional>
#include <limits>
#include <utility>
using namespace std;

template <typename State>
pair<double, int> minimax(
    const State& current_state,
    int maximizing_player,
    const function<vector<State>(const State&)>& possible_moves_funct,
    const function<double(const State&)>& score_funct) {

    vector<State> next_states = possible_moves_funct(current_state);
    if (next_states.empty())
        return {score_funct(current_state), -1};

    double best_value = (maximizing_player == 1)
        ? -numeric_limits<double>::infinity()
        :  numeric_limits<double>::infinity();
    int best_move = -1;

    for (int index = 0; index < (int) next_states.size(); ++index) {
        double value = minimax(next_states[index], -maximizing_player,
                               possible_moves_funct, score_funct).first;
        if (maximizing_player == 1) {
            if (value > best_value) { best_value = value; best_move = index; }
        } else {
            if (value < best_value) { best_value = value; best_move = index; }
        }
    }

    return {best_value, best_move};
}

#include <vector>
#include <functional>
#include <limits>
#include <utility>
using namespace std;
template <typename State>
pair<double, int> minimax(
    const State& current_state,
    int maximizing_player,
    const function<vector<State>(const State&)>& possible_moves_funct,
    const function<double(const State&)>& score_funct) {
    vector<State> next_states = possible_moves_funct(current_state);
    if (next_states.empty())
        return {score_funct(current_state), -1};
    double best_value = (maximizing_player == 1)
        ? -numeric_limits<double>::infinity()
        :  numeric_limits<double>::infinity();
    int best_move = -1;
    for (int index = 0; index < (int) next_states.size(); ++index) {
        double value = minimax(next_states[index], -maximizing_player,
                               possible_moves_funct, score_funct).first;
        if (maximizing_player == 1) {
            if (value > best_value) { best_value = value; best_move = index; }
        } else {
            if (value < best_value) { best_value = value; best_move = index; }
        }
    }
    return {best_value, best_move};
}

fullcleancontest

"""Minimax algorithm for two-player zero-sum games with perfect information.

Finds the optimal move for the player to move, assuming the opponent also plays
optimally: one player maximizes the score while the other minimizes it.

The algorithm is generic — it knows nothing about a specific game. A concrete
game only provides two functions and an initial state (see `test/driver.py` for
the Coins game used in the example):

- `possible_moves_funct(state)`: the list of states reachable from `state` in one
  move. An empty list means `state` is terminal (the game is over).
- `score_funct(state)`: the score of a terminal `state`, from the maximizing
  player's point of view (higher is better for them).

A *move* is identified by its index in the list returned by
`possible_moves_funct`, so `best_move` is the index of the chosen child.

Args:
    current_state: the current game state (any value the game functions accept).
    maximizing_player (int): +1 if the player to move maximizes, -1 if minimizes.
    possible_moves_funct (callable): state -> list of next states.
    score_funct (callable): terminal state -> float score.

Returns:
    tuple[float, int]: the optimal score, and the index of the best move
    (None if `current_state` is already terminal).
"""

def minimax(current_state, maximizing_player: int, possible_moves_funct, score_funct) -> tuple[float, int]:

    # Base case: a terminal state (no moves left) is scored directly.
    next_states = possible_moves_funct(current_state)
    if not next_states:
        return score_funct(current_state), None

    # The maximizing player wants the highest score, the minimizing one the lowest.
    best_value = float('-inf') if maximizing_player == 1 else float('inf')
    best_move = None

    # Try every move; the opponent moves next, so flip who is maximizing.
    for index, next_state in enumerate(next_states):
        value, _ = minimax(next_state, -maximizing_player, possible_moves_funct, score_funct)

        if maximizing_player == 1:
            if value > best_value:
                best_value, best_move = value, index
        else:
            if value < best_value:
                best_value, best_move = value, index

    return best_value, best_move

def minimax(current_state, maximizing_player: int, possible_moves_funct, score_funct) -> tuple[float, int]:

    next_states = possible_moves_funct(current_state)
    if not next_states:
        return score_funct(current_state), None

    best_value = float('-inf') if maximizing_player == 1 else float('inf')
    best_move = None

    for index, next_state in enumerate(next_states):
        value, _ = minimax(next_state, -maximizing_player, possible_moves_funct, score_funct)

        if maximizing_player == 1:
            if value > best_value:
                best_value, best_move = value, index
        else:
            if value < best_value:
                best_value, best_move = value, index

    return best_value, best_move

def minimax(c, e, h, i):
    g = h(c)
    if not g:
        return (i(c), None)
    b = float('-inf') if e == 1 else float('inf')
    a = None
    for d, f in enumerate(g):
        j, _ = minimax(f, -e, h, i)
        if e == 1:
            if j > b:
                b, a = (j, d)
        elif j < b:
            b, a = (j, d)
    return (b, a)

Cómo funciona

El algoritmo recorre el árbol de juego en profundidad (backtracking):

1. Si el estado es terminal (no hay movimientos posibles), devuelve su puntuación con score_funct: es el valor real de esa hoja.
2. Si no, genera los estados hijos con possible_moves_funct y llama a minimax sobre cada uno, alternando el jugador (-maximizing_player).
3. El jugador que maximiza se queda con el hijo de mayor valor; el que minimiza, con el de menor valor. Ese valor "sube" al nodo padre.

Así, el valor de cada nodo interno resume lo mejor que puede conseguir quien mueve ahí si ambos juegan de forma óptima. La llamada raíz devuelve el valor óptimo y, además, el índice del mejor movimiento (best_move).

La función es genérica: no sabe nada del juego concreto. Todo lo específico —cómo se representan los estados, qué movimientos hay y cómo se puntúa una posición final— vive en las dos funciones que le pasas (mira el driver del juego de las monedas en test/driver.py).

Complejidad

Minimax visita cada nodo del árbol de juego una sola vez, así que su coste es proporcional al número de estados que explora. Con un factor de ramificación b (movimientos por turno) y una profundidad d (jugadas hasta el final), el árbol tiene hasta bᵈ nodos:

Recurso	Coste
Tiempo	O(bᵈ) — es decir, O(n) en el número de nodos n
Memoria	O(d) — la pila de recursión

Es exponencial en la profundidad: por eso, en juegos grandes (ajedrez, Go) no se explora el árbol completo. Se limita la profundidad y se evalúan las posiciones intermedias con una heurística, y se recorta el árbol con poda alfa-beta (ver Variantes). Si un mismo estado se alcanza por varios caminos, memoizar su valor evita recalcular subárboles.

Ejemplos

Supongamos que estamos jugando al juego de las monedas, donde dos jugadores alternan turnos para tomar monedas de una pila. Cada jugador puede tomar una o dos monedas en su turno, y el objetivo es maximizar la cantidad de monedas que uno puede recoger. Dependiendo de la pila inicial, determina el máximo valor esperado y el mejor movimiento para el jugador que comienza asumiendo que el rival juega de manera óptima.

Pila inicial	Mejor resultado	Mejor movimiento
2 3 5 8	10	0 (Tomar 1 moneda)

Variantes

Minimax heurístico

Trabajo en curso

Esta página todavía no tiene contenido. ¿Te animas a escribirla? Sigue Cómo contribuir y añade el código, la explicación y los ejemplos.

Minimax con poda alfa-beta

Trabajo en curso

Esta página todavía no tiene contenido. ¿Te animas a escribirla? Sigue Cómo contribuir y añade el código, la explicación y los ejemplos.

Cuándo usarlo

• Juegos de dos jugadores de suma cero con información perfecta con un número limitado de estados (Tic-Tac-Toe, Coins, etc.).

Cuándo NO usarlo

Warning

Muchos juegos que se presentan como problema cuentan con una heurística o estrategia óptima que no requiere una exploración exhaustiva, por ejemplo: NIM. En esos casos, usar minimax no es la opción correcta.

• Árboles de juego enormes sin poda ni límite de profundidad: el coste O(bᵈ) se dispara (ajedrez, Go). Usa poda alfa-beta, límite de profundidad y una heurística de evaluación.
• Juegos con azar (dados) o información imperfecta (cartas ocultas): minimax asume determinismo e información perfecta. Para el azar se usa expectimax, con nodos de valor esperado.
• Más de dos jugadores o juegos que no son de suma cero: la dicotomía maximizar/minimizar deja de valer; hacen falta variantes como maxⁿ.
• Juegos con estrategia óptima conocida: si hay una fórmula o estrategia que garantiza la victoria, no hace falta explorar el árbol de juego.

Errores comunes

• No alternar el jugador en la llamada recursiva: hay que pasar -maximizing_player, no el mismo valor.
• Inicializar mal el mejor valor: -∞ para quien maximiza y +∞ para quien minimiza (si los intercambias, ningún movimiento supera el valor inicial).
• Puntuar nodos internos en vez de solo los terminales: score_funct únicamente tiene sentido en estados finales; el valor de un nodo interno sale de sus hijos.
• Confundir el movimiento con el estado: best_move es el índice del movimiento elegido, no el estado resultante.
• Juegos que pueden entrar en ciclos: sin estados terminales garantizados (o un límite de profundidad), la recursión no termina.

Referencias

• Minimax — Wikipedia
• Poda alfa-beta — Wikipedia