Minimax

¿Qué es Minimax?

Analogía: Imagina que juegas ajedrez contra alguien muy inteligente. Antes de mover, piensas: "Si yo muevo aquí, ¿qué hará mi oponente?". Tu oponente también piensa lo mismo. Tú quieres maximizar tu ventaja, y tu oponente quiere minimizarla. El algoritmo Minimax simula esta lógica: explora todas las posibilidades y elige el mejor camino asumiendo que ambos juegan perfectamente.

Diferencia con Sprague-Grundy

El algoritmo

minimax(posición, profundidad, esMaximizador):
    si es terminal o profundidad = 0:
        retorna evaluación de la posición

    si esMaximizador:
        mejor = -∞
        para cada movimiento posible:
            valor = minimax(siguiente posición, profundidad-1, false)
            mejor = max(mejor, valor)
        retorna mejor

    sino:
        mejor = +∞
        para cada movimiento posible:
            valor = minimax(siguiente posición, profundidad-1, true)
            mejor = min(mejor, valor)
        retorna mejor

Ejemplo: Juego de suma

Hay un arreglo de números. Dos jugadores se turnan para tomar el primer o último elemento. Gana quien acumule mayor suma. ¿Cuál es la diferencia óptima?

Arreglo: [5, 3, 7, 10]

Jugador 1 toma 10 → [5, 3, 7]
Jugador 2 toma 7  → [5, 3]
Jugador 1 toma 5  → [3]
Jugador 2 toma 3  → []

J1 = 10 + 5 = 15, J2 = 7 + 3 = 10
Diferencia = 5

Solución con Minimax + DP

#include <iostream>
#include <vector>
using namespace std;

int n;
int v[105];
int memo[105][105];
bool calculado[105][105];

// Retorna la máxima diferencia (mi_score - oponente_score)
// para el subarreglo v[l..r]
int minimax(int l, int r) {
    if (l > r) return 0;

    if (calculado[l][r]) return memo[l][r];
    calculado[l][r] = true;

    // Tomar el izquierdo: gano v[l], luego el oponente juega óptimo
    int tomarIzq = v[l] - minimax(l + 1, r);

    // Tomar el derecho: gano v[r], luego el oponente juega óptimo
    int tomarDer = v[r] - minimax(l, r - 1);

    memo[l][r] = max(tomarIzq, tomarDer);
    return memo[l][r];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> v[i];

    memset(calculado, false, sizeof(calculado));

    int diff = minimax(0, n - 1);

    // diff = score_J1 - score_J2
    // score_J1 + score_J2 = suma_total
    int sumaTotal = 0;
    for (int i = 0; i < n; i++) sumaTotal += v[i];

    int scoreJ1 = (sumaTotal + diff) / 2;
    int scoreJ2 = (sumaTotal - diff) / 2;

    cout << "Jugador 1: " << scoreJ1 << endl;
    cout << "Jugador 2: " << scoreJ2 << endl;

    return 0;
}

Tic-Tac-Toe con Minimax

#include <iostream>
using namespace std;

char tablero[3][3];

// +10: gana X, -10: gana O, 0: empate
int evaluar() {
    // Revisar filas y columnas
    for (int i = 0; i < 3; i++) {
        if (tablero[i][0] == tablero[i][1] &&
            tablero[i][1] == tablero[i][2]) {
            if (tablero[i][0] == 'X') return 10;
            if (tablero[i][0] == 'O') return -10;
        }
        if (tablero[0][i] == tablero[1][i] &&
            tablero[1][i] == tablero[2][i]) {
            if (tablero[0][i] == 'X') return 10;
            if (tablero[0][i] == 'O') return -10;
        }
    }
    // Diagonales
    if (tablero[0][0] == tablero[1][1] &&
        tablero[1][1] == tablero[2][2]) {
        if (tablero[0][0] == 'X') return 10;
        if (tablero[0][0] == 'O') return -10;
    }
    if (tablero[0][2] == tablero[1][1] &&
        tablero[1][1] == tablero[2][0]) {
        if (tablero[0][2] == 'X') return 10;
        if (tablero[0][2] == 'O') return -10;
    }
    return 0;
}

bool hayMovimientos() {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (tablero[i][j] == '.') return true;
    return false;
}

int minimax(bool esMax) {
    int score = evaluar();
    if (score == 10 || score == -10) return score;
    if (!hayMovimientos()) return 0;

    if (esMax) {
        int mejor = -1000;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (tablero[i][j] == '.') {
                    tablero[i][j] = 'X';
                    mejor = max(mejor, minimax(false));
                    tablero[i][j] = '.';  // Deshacer
                }
            }
        }
        return mejor;
    } else {
        int mejor = 1000;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (tablero[i][j] == '.') {
                    tablero[i][j] = 'O';
                    mejor = min(mejor, minimax(true));
                    tablero[i][j] = '.';
                }
            }
        }
        return mejor;
    }
}

// Encontrar el mejor movimiento para X
pair<int,int> mejorMovimiento() {
    int mejorVal = -1000;
    pair<int,int> mejor = {-1, -1};

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (tablero[i][j] == '.') {
                tablero[i][j] = 'X';
                int val = minimax(false);
                tablero[i][j] = '.';

                if (val > mejorVal) {
                    mejorVal = val;
                    mejor = {i, j};
                }
            }
        }
    }

    return mejor;
}

Poda Alfa-Beta

Minimax puro es lento porque explora todas las ramas. La poda alfa-beta elimina ramas que sabemos que no afectarán el resultado.

• alfa: El mejor valor que el maximizador puede garantizar.
• beta: El mejor valor que el minimizador puede garantizar.
• Si alfa ≥ beta, podamos (no exploramos más hijos).

int alphabeta(int profundidad, int alfa, int beta, bool esMax) {
    if (profundidad == 0 || esTerminal()) {
        return evaluar();
    }

    if (esMax) {
        int valor = -INT_MAX;
        for (auto &mov : movimientos()) {
            hacer(mov);
            valor = max(valor, alphabeta(profundidad-1, alfa, beta, false));
            deshacer(mov);

            alfa = max(alfa, valor);
            if (alfa >= beta) break;  // Poda beta
        }
        return valor;
    } else {
        int valor = INT_MAX;
        for (auto &mov : movimientos()) {
            hacer(mov);
            valor = min(valor, alphabeta(profundidad-1, alfa, beta, true));
            deshacer(mov);

            beta = min(beta, valor);
            if (alfa >= beta) break;  // Poda alfa
        }
        return valor;
    }
}

// Llamada inicial:
// alphabeta(maxProfundidad, -INF, +INF, true)

En el mejor caso, alfa-beta reduce el número de nodos de $O(b^d)$ a $O(b^{d/2})$, donde $b$ es el factor de ramificación y $d$ la profundidad.

Resumen

Ejercicio

Hay N piedras en una pila. Dos jugadores se turnan. Puedes quitar 1 a 3 piedras. Cada piedra vale un punto. Ambos juegan para maximizar su puntaje. ¿Cuántos puntos obtiene cada uno?

#include <iostream>
#include <cstring>
using namespace std;

int memo[1005];
bool calc[1005];
int n;

// Retorna lo máximo que puede ganar el jugador actual
// cuando quedan `quedan` piedras
int solve(int quedan) {
    if (quedan <= 0) return 0;
    if (calc[quedan]) return memo[quedan];

    calc[quedan] = true;
    int mejor = 0;

    for (int tomo = 1; tomo <= 3 && tomo <= quedan; tomo++) {
        // Tomo `tomo` puntos, el oponente gana solve(quedan - tomo)
        // del resto (quedan - tomo) piedras
        int miGanancia = tomo + (quedan - tomo - solve(quedan - tomo));
        mejor = max(mejor, miGanancia);
    }

    memo[quedan] = mejor;
    return mejor;
}

int main() {
    cin >> n;
    memset(calc, false, sizeof(calc));

    int j1 = solve(n);
    int j2 = n - j1;

    cout << "Jugador 1: " << j1 << endl;
    cout << "Jugador 2: " << j2 << endl;

    return 0;
}