Salta el contingut

Cerca amb adversari: Minimax i poda alfa-beta

En jocs de dos jugadors amb informació completa (escacs, dames, tic-tac-toe) cal decidir el moviment òptim tenint en compte que l'adversari també juga de manera òptima en contra nostra.

Minimax

Minimax: explora l'arbre de jugades possibles fins a un cert nivell, avaluant els estats finals com a positius si guanya el jugador MAX i negatius si guanya MIN. El valor es propaga cap amunt: als nivells MAX es tria el fill amb valor més alt, als nivells MIN el de valor més baix.

def minimax(estat, profunditat, es_torn_max, obtenir_fills, es_terminal, avaluar):
    """Minimax generic. es_torn_max=True al node arrel si l-IA mou primer."""
    if es_terminal(estat) or profunditat == 0:
        return avaluar(estat)

    fills = obtenir_fills(estat)
    if es_torn_max:
        return max(
            minimax(f, profunditat - 1, False, obtenir_fills, es_terminal, avaluar)
            for f in fills
        )
    else:
        return min(
            minimax(f, profunditat - 1, True, obtenir_fills, es_terminal, avaluar)
            for f in fills
        )

Poda alfa-beta: optimització de Minimax que talla branques que no poden canviar el resultat final, sense sacrificar l'optimalitat de la decisió. Manté dos valors:

  • α (alfa): la millor puntuació que MAX té garantida fins ara en el camí explorat (un mínim que MAX ja assegura).
  • β (beta): la millor puntuació que MIN té garantida fins ara en el camí explorat (un màxim que MIN ja assegura).

Mentre es baixa per l'arbre, cada node hereta i actualitza α i β dels seus avantpassats. La poda es produeix quan α ≥ β en un node: en aquest punt, el jugador del nivell superior ja té una alternativa almenys tan bona en una altra branca, de manera que no cal seguir explorant els fills restants d'aquest node — per bo que sigui el resultat, el jugador contrari mai el deixarà escollir aquest camí. La poda no canvia mai la jugada finalment escollida: només estalvia exploració de branques que ja sabem que no influiran en el resultat.

L'ordre en què s'exploren els nodes afecta molt l'eficiència de la poda: com millor ordenats estiguin (millors moviments primer), més branques es podran descartar — en el cas ideal, la poda alfa-beta redueix la complexitat de O(r^p) a O(r^(p/2)), és a dir, permet explorar el doble de profunditat amb el mateix cost computacional.

Cas real: Minimax i poda alfa-beta al Connecta 4

El Connecta 4 (Connect Four) és un dels exemples més utilitzats per ensenyar Minimax i poda alfa-beta a la pràctica, perquè és prou senzill de programar però prou complex perquè calgui optimitzar-lo de debò.

Per què el Connecta 4 necessita poda alfa-beta

  • El tauler té 6 files × 7 columnes = 42 caselles, i cada jugada només pot "deixar caure" una fitxa en una de les 7 columnes (si no és plena) — la gravetat fa que la fitxa caigui fins a la primera posició lliure.
  • El factor de ramificació és com a màxim 7 (7 columnes possibles a cada torn), i la partida pot durar fins a 42 jugades.
  • L'espai d'estats complet té més de 4,5 bilions de posicions possibles. Explorar-lo sencer amb Minimax pur és inviable en temps real; calen poda alfa-beta, una profunditat d'exploració limitada i una funció heurística que avaluï posicions no terminals.
  • El joc va ser "resolt" matemàticament per Victor Allis el 1988: amb joc perfecte, el primer jugador sempre guanya si comença jugant la columna central.

Representació del tauler

Es representa com una graella de 6×7 (llista de llistes), on cada casella val 0 (buida), 1 (fitxa del jugador 1) o 2 (fitxa del jugador 2). Les files s'indexen de baix (fila 0) cap amunt, seguint la gravetat.

FILES, COLUMNES = 6, 7
JUGADOR, IA = 1, 2

def crear_tauler():
    return [[0] * COLUMNES for _ in range(FILES)]

def columna_valida(tauler, col):
    """Una columna admet una fitxa si la fila superior encara està buida."""
    return tauler[FILES - 1][col] == 0

def fila_disponible(tauler, col):
    """Retorna la fila més baixa lliure d'aquella columna (efecte de la gravetat)."""
    for fila in range(FILES):
        if tauler[fila][col] == 0:
            return fila

def posar_fitxa(tauler, fila, col, peça):
    tauler[fila][col] = peça

Detecció de la victòria (test terminal)

Cal comprovar, després de cada jugada, si s'han alineat 4 fitxes iguals en horitzontal, vertical o en qualsevol de les dues diagonals:

def hi_ha_victoria(tauler, peça):
    # Horitzontal
    for fila in range(FILES):
        for col in range(COLUMNES - 3):
            if all(tauler[fila][col + i] == peça for i in range(4)):
                return True
    # Vertical
    for col in range(COLUMNES):
        for fila in range(FILES - 3):
            if all(tauler[fila + i][col] == peça for i in range(4)):
                return True
    # Diagonal ascendent (/)
    for fila in range(FILES - 3):
        for col in range(COLUMNES - 3):
            if all(tauler[fila + i][col + i] == peça for i in range(4)):
                return True
    # Diagonal descendent (\)
    for fila in range(3, FILES):
        for col in range(COLUMNES - 3):
            if all(tauler[fila - i][col + i] == peça for i in range(4)):
                return True
    return False

Funció heurística per a posicions no terminals

Com que no es pot explorar tot l'arbre, cal aturar la cerca a una profunditat màxima (per exemple, 5-7 jugades endavant) i estimar la qualitat de la posició amb una heurística. La tècnica habitual és recórrer totes les finestres de 4 caselles consecutives (horitzontals, verticals i diagonals) i puntuar-les segons quantes fitxes de cada jugador contenen:

Contingut de la finestra (4 caselles) Puntuació
4 fitxes pròpies +100 (victòria)
3 fitxes pròpies + 1 buida +5
2 fitxes pròpies + 2 buides +2
3 fitxes de l'adversari + 1 buida −4 (cal blocar-ho com a prioritat)
Fitxa pròpia a la columna central +3 (bonificació: la columna central participa en més línies guanyadores possibles) 
def puntuar_finestra(finestra, peça):
    puntuacio = 0
    adversari = JUGADOR if peça == IA else IA

    if finestra.count(peça) == 4:
        puntuacio += 100
    elif finestra.count(peça) == 3 and finestra.count(0) == 1:
        puntuacio += 5
    elif finestra.count(peça) == 2 and finestra.count(0) == 2:
        puntuacio += 2

    if finestra.count(adversari) == 3 and finestra.count(0) == 1:
        puntuacio -= 4  # Bloquejar l'amenaça de l'adversari és prioritari

    return puntuacio

def avaluar_posicio(tauler, peça):
    puntuacio = 0

    # Bonificació per fitxes a la columna central (columna 3)
    columna_central = [tauler[fila][COLUMNES // 2] for fila in range(FILES)]
    puntuacio += columna_central.count(peça) * 3

    # Totes les finestres horitzontals, verticals i diagonals
    for fila in range(FILES):
        for col in range(COLUMNES - 3):
            puntuacio += puntuar_finestra(
                [tauler[fila][col + i] for i in range(4)], peça
            )
    for col in range(COLUMNES):
        for fila in range(FILES - 3):
            puntuacio += puntuar_finestra(
                [tauler[fila + i][col] for i in range(4)], peça
            )
    for fila in range(FILES - 3):
        for col in range(COLUMNES - 3):
            puntuacio += puntuar_finestra(
                [tauler[fila + i][col + i] for i in range(4)], peça
            )
            puntuacio += puntuar_finestra(
                [tauler[fila + 3 - i][col + i] for i in range(4)], peça
            )

    return puntuacio

Minimax amb poda alfa-beta i ordenació de moviments

L'últim ingredient clau és explorar primer les columnes centrals: com que solen ser les millors jugades, examinar-les abans permet que la poda alfa-beta descarti moltes més branques que si s'exploressin les columnes en ordre 0,1,2...6.

import math

ORDRE_COLUMNES = [3, 2, 4, 1, 5, 0, 6]  # Centre primer: millora molt la poda

def minimax_connecta4(tauler, profunditat, alfa, beta, es_torn_ia):
    columnes_valides = [c for c in ORDRE_COLUMNES if columna_valida(tauler, c)]
    es_terminal = (
        hi_ha_victoria(tauler, JUGADOR)
        or hi_ha_victoria(tauler, IA)
        or len(columnes_valides) == 0
    )

    if profunditat == 0 or es_terminal:
        if es_terminal:
            if hi_ha_victoria(tauler, IA):
                return None, math.inf
            elif hi_ha_victoria(tauler, JUGADOR):
                return None, -math.inf
            else:
                return None, 0  # Empat: tauler ple
        return None, avaluar_posicio(tauler, IA)  # Profunditat maxima: heuristica

    if es_torn_ia:
        millor_valor = -math.inf
        millor_columna = columnes_valides[0]
        for col in columnes_valides:
            fila = fila_disponible(tauler, col)
            copia = [f[:] for f in tauler]
            posar_fitxa(copia, fila, col, IA)
            _, valor = minimax_connecta4(copia, profunditat - 1, alfa, beta, False)
            if valor > millor_valor:
                millor_valor = valor
                millor_columna = col
            alfa = max(alfa, millor_valor)
            if alfa >= beta:
                break  # Poda: MIN mai deixaria arribar aquí
        return millor_columna, millor_valor
    else:
        millor_valor = math.inf
        millor_columna = columnes_valides[0]
        for col in columnes_valides:
            fila = fila_disponible(tauler, col)
            copia = [f[:] for f in tauler]
            posar_fitxa(copia, fila, col, JUGADOR)
            _, valor = minimax_connecta4(copia, profunditat - 1, alfa, beta, True)
            if valor < millor_valor:
                millor_valor = valor
                millor_columna = col
            beta = min(beta, millor_valor)
            if alfa >= beta:
                break  # Poda: MAX mai deixaria arribar aquí
        return millor_columna, millor_valor

# Ús: la IA calcula la seva jugada explorant 6 torns (3 seus + 3 de l'adversari) endavant
columna_escollida, valor = minimax_connecta4(
    tauler, profunditat=6, alfa=-math.inf, beta=math.inf, es_torn_ia=True
)

Amb aquesta implementació, augmentar la profunditat fa que la IA jugui millor però trigui més a decidir; la poda alfa-beta combinada amb l'ordenació centre-primer és el que fa que, a la pràctica, es puguin explorar 6-8 torns endavant en temps real en lloc dels 2-3 que permetria un Minimax sense optimitzar.

Miniactivitat — AC5071/01/06 — Minimax al tres en ratlla (o al Connecta 4)

Implementa el tres en ratlla (tic-tac-toe) complet amb un motor Minimax que mai perdi (com a màxim empata). Compara el nombre de nodes explorats amb i sense poda alfa-beta per al mateix tauler inicial, i explica per quin motiu la poda no canvia mai la jugada escollida per l'algorisme.

Ampliació opcional: adapta el codi de Connecta 4 d'aquesta pàgina perquè es pugui jugar (per consola) contra la IA. Prova diferents profunditats d'exploració (2, 4, 6) i mesura el temps que triga a decidir cada jugada. Explica per què cal limitar la profunditat en aquest joc i no en el tres en ratlla.