Algoritmul Minimax

Minimax este un algoritm de decizie folosit în teoria jocurilor și inteligența artificială pentru jocuri cu doi jucători, cu sumă zero și informație completă (ex: șah, X și 0, Connect 4).

Concepte de bază

Jocuri cu sumă zero

Într-un joc cu sumă zero, câștigul unui jucător este egal cu pierderea celuilalt:

• Dacă MAX câștigă +10, MIN pierde -10
• Scorul total este întotdeauna 0

Arborele de joc

                    MAX (rădăcină)
                   /    |    \
                MIN    MIN    MIN
               / \    / \    / \
             MAX MAX MAX MAX MAX MAX
              |   |   |   |   |   |
             3   5   2   9   1   6

Principiul Minimax

• MAX vrea să maximizeze scorul
• MIN vrea să minimizeze scorul
• Fiecare jucător joacă optim

Algoritm de bază

def minimax(stare, adancime, este_max):
    """
    Algoritmul Minimax.

    Args:
        stare: starea curentă a jocului
        adancime: adâncimea maximă de căutare
        este_max: True dacă e rândul lui MAX

    Returns:
        Scorul optim pentru jucătorul curent
    """
    # Condiții de oprire
    if adancime == 0 or este_stare_finala(stare):
        return evalueaza(stare)

    if este_max:
        max_eval = float('-inf')
        for mutare in genereaza_mutari(stare):
            stare_noua = aplica_mutare(stare, mutare)
            eval = minimax(stare_noua, adancime - 1, False)
            max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = float('inf')
        for mutare in genereaza_mutari(stare):
            stare_noua = aplica_mutare(stare, mutare)
            eval = minimax(stare_noua, adancime - 1, True)
            min_eval = min(min_eval, eval)
        return min_eval

Alegerea celei mai bune mutări

def gaseste_mutare_optima(stare, adancime):
    """Găsește cea mai bună mutare pentru MAX."""
    cea_mai_buna_mutare = None
    max_eval = float('-inf')

    for mutare in genereaza_mutari(stare):
        stare_noua = aplica_mutare(stare, mutare)
        eval = minimax(stare_noua, adancime - 1, False)

        if eval > max_eval:
            max_eval = eval
            cea_mai_buna_mutare = mutare

    return cea_mai_buna_mutare

Alpha-Beta Pruning

Optimizare care elimină ramurile care nu pot influența decizia finală.

• Alpha (α): cel mai bun scor garantat pentru MAX
• Beta (β): cel mai bun scor garantat pentru MIN

def minimax_alpha_beta(stare, adancime, alpha, beta, este_max):
    """
    Minimax cu Alpha-Beta Pruning.

    Args:
        stare: starea curentă
        adancime: adâncimea de căutare
        alpha: cel mai bun scor pentru MAX
        beta: cel mai bun scor pentru MIN
        este_max: True dacă e rândul lui MAX
    """
    if adancime == 0 or este_stare_finala(stare):
        return evalueaza(stare)

    if este_max:
        max_eval = float('-inf')
        for mutare in genereaza_mutari(stare):
            stare_noua = aplica_mutare(stare, mutare)
            eval = minimax_alpha_beta(stare_noua, adancime - 1,
                                      alpha, beta, False)
            max_eval = max(max_eval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break  # Beta cut-off
        return max_eval
    else:
        min_eval = float('inf')
        for mutare in genereaza_mutari(stare):
            stare_noua = aplica_mutare(stare, mutare)
            eval = minimax_alpha_beta(stare_noua, adancime - 1,
                                      alpha, beta, True)
            min_eval = min(min_eval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break  # Alpha cut-off
        return min_eval

Vizualizarea Alpha-Beta

                    MAX α=-∞, β=+∞
                   /           \
            MIN α=-∞, β=+∞    MIN (tăiat)
           /    \
        MAX     MAX
         |       |
         3       5

La MIN: după evaluarea 3, β=3
La MAX: după evaluarea 3, α=3
La MIN: evaluează 5, min(3,5)=3
Înapoi la MAX: α=3

A doua ramură MIN: dacă găsește ≤3, MAX nu va alege
                   dacă găsește >3, MIN nu va alege
                   → ramură TĂIATĂ

Exemplu complet: X și 0

class XSi0:
    def __init__(self):
        # Tabla: 0=gol, 1=X, 2=0
        self.tabla = [[0, 0, 0],
                      [0, 0, 0],
                      [0, 0, 0]]

    def mutari_posibile(self):
        """Returnează pozițiile libere."""
        mutari = []
        for i in range(3):
            for j in range(3):
                if self.tabla[i][j] == 0:
                    mutari.append((i, j))
        return mutari

    def aplica_mutare(self, mutare, jucator):
        """Aplică o mutare pe tablă."""
        i, j = mutare
        self.tabla[i][j] = jucator

    def anuleaza_mutare(self, mutare):
        """Anulează o mutare."""
        i, j = mutare
        self.tabla[i][j] = 0

    def verifica_castigator(self):
        """
        Verifică dacă există un câștigător.
        Returnează: 1 (X câștigă), 2 (0 câștigă), 0 (în desfășurare), -1 (remiză)
        """
        # Verifică linii și coloane
        for i in range(3):
            if self.tabla[i][0] == self.tabla[i][1] == self.tabla[i][2] != 0:
                return self.tabla[i][0]
            if self.tabla[0][i] == self.tabla[1][i] == self.tabla[2][i] != 0:
                return self.tabla[0][i]

        # Verifică diagonale
        if self.tabla[0][0] == self.tabla[1][1] == self.tabla[2][2] != 0:
            return self.tabla[0][0]
        if self.tabla[0][2] == self.tabla[1][1] == self.tabla[2][0] != 0:
            return self.tabla[0][2]

        # Verifică remiză
        if not self.mutari_posibile():
            return -1  # Remiză

        return 0  # Jocul continuă

    def evalueaza(self):
        """Evaluează starea: +10 X câștigă, -10 0 câștigă, 0 altfel."""
        castigator = self.verifica_castigator()
        if castigator == 1:
            return 10
        elif castigator == 2:
            return -10
        else:
            return 0

    def minimax(self, adancime, este_max, alpha, beta):
        """Minimax cu Alpha-Beta pentru X și 0."""
        scor = self.evalueaza()

        # Stări terminale
        if scor == 10 or scor == -10:
            return scor
        if not self.mutari_posibile():
            return 0  # Remiză

        if este_max:
            max_eval = float('-inf')
            for mutare in self.mutari_posibile():
                self.aplica_mutare(mutare, 1)  # X
                eval = self.minimax(adancime + 1, False, alpha, beta)
                self.anuleaza_mutare(mutare)
                max_eval = max(max_eval, eval)
                alpha = max(alpha, eval)
                if beta <= alpha:
                    break
            return max_eval
        else:
            min_eval = float('inf')
            for mutare in self.mutari_posibile():
                self.aplica_mutare(mutare, 2)  # 0
                eval = self.minimax(adancime + 1, True, alpha, beta)
                self.anuleaza_mutare(mutare)
                min_eval = min(min_eval, eval)
                beta = min(beta, eval)
                if beta <= alpha:
                    break
            return min_eval

    def gaseste_mutare_optima(self, jucator):
        """Găsește cea mai bună mutare pentru jucătorul dat."""
        cea_mai_buna = None
        este_max = (jucator == 1)

        if este_max:
            best_val = float('-inf')
            for mutare in self.mutari_posibile():
                self.aplica_mutare(mutare, jucator)
                val = self.minimax(0, False, float('-inf'), float('inf'))
                self.anuleaza_mutare(mutare)
                if val > best_val:
                    best_val = val
                    cea_mai_buna = mutare
        else:
            best_val = float('inf')
            for mutare in self.mutari_posibile():
                self.aplica_mutare(mutare, jucator)
                val = self.minimax(0, True, float('-inf'), float('inf'))
                self.anuleaza_mutare(mutare)
                if val < best_val:
                    best_val = val
                    cea_mai_buna = mutare

        return cea_mai_buna

    def afiseaza(self):
        """Afișează tabla."""
        simboluri = {0: '.', 1: 'X', 2: '0'}
        for rand in self.tabla:
            print(' '.join(simboluri[c] for c in rand))
        print()


# Demonstrație
joc = XSi0()
joc.afiseaza()

# X mută primul (jucător AI)
mutare = joc.gaseste_mutare_optima(1)
joc.aplica_mutare(mutare, 1)
print(f"X mută pe {mutare}")
joc.afiseaza()

Funcții de evaluare

Pentru jocuri complexe unde nu putem căuta până la final, folosim funcții de evaluare euristice.

Exemplu: Evaluare pentru X și 0

def evalueaza_euristic(tabla):
    """
    Evaluează o poziție non-terminală.
    Scor pozitiv = avantaj X, negativ = avantaj 0
    """
    scor = 0

    # Evaluează toate liniile de 3
    linii = []
    # Linii orizontale
    for i in range(3):
        linii.append([tabla[i][0], tabla[i][1], tabla[i][2]])
    # Linii verticale
    for j in range(3):
        linii.append([tabla[0][j], tabla[1][j], tabla[2][j]])
    # Diagonale
    linii.append([tabla[0][0], tabla[1][1], tabla[2][2]])
    linii.append([tabla[0][2], tabla[1][1], tabla[2][0]])

    for linie in linii:
        x_count = linie.count(1)
        o_count = linie.count(2)

        # Doar X pe linie
        if o_count == 0:
            if x_count == 2:
                scor += 10
            elif x_count == 1:
                scor += 1

        # Doar 0 pe linie
        if x_count == 0:
            if o_count == 2:
                scor -= 10
            elif o_count == 1:
                scor -= 1

    return scor

Evaluare pentru Connect 4

def evalueaza_connect4(tabla, jucator):
    """Evaluează o poziție în Connect 4."""
    scor = 0

    # Centrul este valoros
    coloana_centru = [tabla[i][3] for i in range(6)]
    scor += coloana_centru.count(jucator) * 3

    # Evaluează toate ferestrele de 4
    # ... (similar cu X și 0, dar pentru ferestre de 4)

    return scor

Complexitate

Aspect	Minimax	Alpha-Beta
Timp (worst)	$O(b^d)$	$O(b^d)$
Timp (best)	$O(b^d)$	$O(b^{d/2})$
Spațiu	$O(d)$	$O(d)$

Unde $b$ = factorul de ramificare, $d$ = adâncimea.

Optimizări

1. Ordonarea mutărilor: Evaluează mai întâi mutările promițătoare
2. Tabel de transpoziție: Memorează pozițiile deja evaluate
3. Iterative Deepening: Caută progresiv mai adânc
4. Quiescence Search: Continuă căutarea în poziții "agitate"

Variante avansate

Negamax

Simplificare a Minimax exploatând simetria:

def negamax(stare, adancime, alpha, beta, culoare):
    """
    Negamax cu Alpha-Beta.
    culoare: 1 pentru MAX, -1 pentru MIN
    """
    if adancime == 0 or este_stare_finala(stare):
        return culoare * evalueaza(stare)

    max_eval = float('-inf')
    for mutare in genereaza_mutari(stare):
        stare_noua = aplica_mutare(stare, mutare)
        eval = -negamax(stare_noua, adancime - 1, -beta, -alpha, -culoare)
        max_eval = max(max_eval, eval)
        alpha = max(alpha, eval)
        if alpha >= beta:
            break
    return max_eval

Expectimax

Pentru jocuri cu element de șansă (zaruri, cărți):

def expectimax(stare, adancime, este_max):
    """Minimax pentru jocuri cu șansă."""
    if adancime == 0 or este_stare_finala(stare):
        return evalueaza(stare)

    if este_max:
        return max(expectimax(s, adancime-1, False)
                   for s in succesori(stare))
    else:
        # Nod de șansă: calculează valoarea așteptată
        total = 0
        for stare_noua, probabilitate in succesori_cu_probabilitati(stare):
            total += probabilitate * expectimax(stare_noua, adancime-1, True)
        return total

Aplicații

• Șah: Deep Blue, Stockfish
• Go: AlphaGo (combinat cu rețele neurale)
• Dame: Chinook
• Jocuri video: AI pentru inamici
• Economie: Teoria jocurilor, negociere