El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Cerca amb Adversari: Jocs i Minimax

Següent ►
►

A les dues lliçons anteriors la furgoneta de NovaMarket cercava el seu camí en un món passiu: el mapa no canviava perquè ella es mogués. Però a 02-01 vam veure que molts entorns són multiagent, i alguns són competitius: hi ha un altre agent els objectius del qual s'oposen als nostres i que respon a cada decisió amb la seva. En aquesta situació no n'hi ha prou amb planificar un camí; cal preguntar-se "i què farà l'altre?" a cada pas. La branca de la IA que estudia això és la cerca amb adversari, i el seu algorisme fonamental és minimax. L'aprendrem on va néixer, als jocs: veurem què canvia respecte de la cerca de 03-02, com es representa una partida com a arbre de joc, com minimax tria la millor jugada suposant que el rival també juga perfectament, i com la poda alfa-beta obté la mateixa resposta explorant una fracció de l'arbre. L'implementarem per al tres en ratlla, comptant nodes per mesurar cada millora, i explicarem per què en escacs o go cal tallar la cerca i avaluar posicions amb heurístiques (l'enllaç amb Deep Blue i AlphaGo de 01-01). Finalment el portarem a NovaMarket amb una "guerra de preus" simplificada davant d'un competidor, i discutirem amb honestedat on acaba la utilitat de minimax quan la informació és imperfecta i el joc no és de suma zero.

Contingut

  1. Què canvia quan hi ha un adversari
  2. Jocs de suma zero amb informació perfecta
  3. L'arbre de joc: nivells MAX i MIN
  4. Minimax pas a pas sobre un arbre numèric
  5. Minimax per al tres en ratlla en Python, comptant nodes
  6. Poda alfa-beta: idea, exemple numèric i implementació
  7. Límit de profunditat i funció d'avaluació: de les dames a Deep Blue i AlphaGo
  8. Aterratge a NovaMarket: la guerra de preus i el defraudador adaptatiu
  9. Límits de minimax: informació imperfecta, suma no zero, incertesa

  1. Què canvia quan hi ha un adversari

A la cerca de 03-02 l'agent controlava totes les decisions: triava un tram, el món responia de manera determinista i el tram següent també el triava ell. Quan apareix un adversari, la meitat de les decisions les pren un altre, i les pren en contra nostra. Això té conseqüències directes:

Aspecte Cerca simple (03-02) Cerca amb adversari
Qui decideix Només l'agent L'agent i l'adversari, per torns
Què és una solució Un camí fix fins a l'objectiu Una estratègia: què fer davant de cada possible resposta del rival (un pla condicional, no una llista)
Què s'optimitza Cost mínim del camí La utilitat al final de la partida, suposant el millor joc del rival
Entorn (02-01) Monoagent, determinista Multiagent competitiu, determinista en les regles però impredictible en el rival
Mida del problema L'espai d'estats L'espai d'estats elevat a la profunditat de la partida: cada torn multiplica les branques

En Diego ho va entendre amb un exemple del seu dia a dia: "quan planifico una ruta, la ciutat no me la canvia ningú; quan fixo un preu, el del davant ho veu i reacciona en una hora". Aquesta reacció converteix la decisió en un joc.

  1. Jocs de suma zero amb informació perfecta

Minimax es formula per a una classe concreta de jocs, la més simple i alhora la més estudiada:

  • Dos jugadors que alternen torns. Els anomenarem MAX (nosaltres, que volem maximitzar la utilitat) i MIN (el rival, que la vol minimitzar).
  • Determinista: no hi ha daus ni cartes ocultes; el resultat d'una jugada és sempre el mateix.
  • Informació perfecta: tots dos veuen l'estat complet (el tauler) en tot moment.
  • Suma zero: el que guanya l'un ho perd l'altre. Si al final assignem +1 a la victòria de MAX, −1 a la de MIN i 0 a les taules, la utilitat de MIN és exactament l'oposada a la de MAX, i per això n'hi ha prou amb una sola funció d'utilitat: MAX la maximitza i MIN la minimitza.

Tres en ratlla, dames, escacs i go compleixen les quatre condicions. El pòquer no (informació imperfecta i atzar), i moltes situacions de negoci tampoc (ho veurem a la secció 9). La formulació d'un joc com a problema afegeix a la de 02-01 un element: la funció jugador(estat) que diu a qui li toca. En resum: estat inicial, jugador(s), accions(s), resultat(s, a), terminal(s) i utilitat(s).

  1. L'arbre de joc: nivells MAX i MIN

L'arbre de joc és l'arbre de cerca de 03-02 amb una diferència: els nivells s'alternen entre decisions de MAX i de MIN. L'arrel és l'estat actual amb MAX al torn; els seus fills són les posicions després de cada jugada de MAX, en què li toca a MIN; els nets, les posicions després de cada resposta de MIN, i així fins a les fulles, que són estats terminals amb la seva utilitat. Per al tres en ratlla, des del tauler buit l'arbre complet té 9 branques al primer nivell, 8 al segon, 7 al tercer… fins a un total de 549.946 nodes, dels quals 255.168 són fulles (partides acabades). Són menys fulles que les 9! = 362.880 maneres d'omplir el tauler perquè moltes partides acaben abans d'omplir-lo, i hi ha més nodes que fulles perquè comptem també totes les posicions intermèdies. És prou gran perquè valgui la pena ser intel·ligent i prou petit perquè Python el recorri sencer en segons: el vehicle didàctic perfecte.

  1. Minimax pas a pas sobre un arbre numèric

Abans del tres en ratlla, un arbre abstracte de dos nivells amb les utilitats ja posades a les fulles. MAX mou a l'arrel A triant entre B, C i D; MIN respon a cadascuna d'elles triant entre tres fulles.

graph TD
    A[MAX: A = 3] --> B[MIN: B = 3]
    A --> C[MIN: C = 2]
    A --> D[MIN: D = 2]
    B --> B1[3]
    B --> B2[12]
    B --> B3[8]
    C --> C1[2]
    C --> C2[4]
    C --> C3[6]
    D --> D1[14]
    D --> D2[5]
    D --> D3[2]

El raonament de minimax va de baix a dalt:

  1. A B li toca a MIN. De les fulles 3, 12 i 8 triarà la menor: B val 3. Encara que B2 = 12 sigui temptador per a MAX, mai no l'obtindrà perquè MIN no ho permetrà.
  2. A C, MIN tria el mínim de 2, 4, 6: C val 2.
  3. A D, MIN tria el mínim de 14, 5, 2: D val 2. Fixa't en la trampa de D1 = 14: la millor fulla de l'arbre és allà, però MIN s'encarregarà que no s'hi arribi.
  4. A A li toca a MAX, que tria el màxim entre 3, 2 i 2: A val 3, i la jugada correcta és anar a B.

Aquest "3" és el valor minimax de la posició: la utilitat que MAX pot garantir-se si MIN juga perfectament. Si MIN s'equivoca, MAX obtindrà més; si MIN juga bé, MAX no obtindrà menys. En codi, la recursió és d'una transparència total:

ARBRE = {"A": ["B", "C", "D"], "B": ["B1", "B2", "B3"],
         "C": ["C1", "C2", "C3"], "D": ["D1", "D2", "D3"]}
VALORS = {"B1": 3, "B2": 12, "B3": 8, "C1": 2, "C2": 4, "C3": 6, "D1": 14, "D2": 5, "D3": 2}

def minimax_arbre(node, es_max):
    if node in VALORS:                        # fulla: retornem la seva utilitat
        return VALORS[node]
    valors = [minimax_arbre(fill, not es_max) for fill in ARBRE[node]]     # el torn s'alterna
    return max(valors) if es_max else min(valors)

print([minimax_arbre(f, False) for f in ARBRE["A"]])   # [3, 2, 2]
print(minimax_arbre("A", True))                          # 3

Observa que minimax és una cerca en profunditat (03-02): la recursió baixa per la primera branca fins a les fulles abans de mirar la segona, i només necessita memòria per al camí actual. El seu cost temporal és O(bᵐ), amb b jugades possibles per torn i m nivells de profunditat: per als escacs (b ≈ 35, m ≈ 80) és un nombre amb més de 120 xifres. D'aquí les seccions 6 i 7.

  1. Minimax per al tres en ratlla en Python, comptant nodes

Ara un joc real. Decisions de representació (recorda 03-01: la representació és mitja solució):

  • El tauler és una llista de 9 caselles, índexs 0-8 d'esquerra a dreta i de dalt a baix, amb "X", "O" o " " (buida).
  • Les línies guanyadores són 8 tripletes d'índexs: 3 files, 3 columnes i 2 diagonals.
  • X és MAX i sempre comença; O és MIN. Utilitat: +1 si guanya X, −1 si guanya O, 0 en taules.
import math

LINIES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),      # files
          (0, 3, 6), (1, 4, 7), (2, 5, 8),      # columnes
          (0, 4, 8), (2, 4, 6)]                 # diagonals

def guanyador(t):
    """Retorna 'X' o 'O' si hi ha tres en ratlla, o None."""
    for a, b, c in LINIES:
        if t[a] != " " and t[a] == t[b] == t[c]:
            return t[a]
    return None

def moviments(t):
    """Indexs de les caselles buides: les jugades legals."""
    return [i for i, casella in enumerate(t) if casella == " "]

def terminal(t):
    return guanyador(t) is not None or not moviments(t)

def utilitat(t):
    g = guanyador(t)
    return 1 if g == "X" else -1 if g == "O" else 0

def mostrar(t):
    files = [" " + " | ".join(t[i:i + 3]) for i in (0, 3, 6)]
    print("\n---+---+---\n".join(files))

I l'algorisme. Per poder comparar més tard amb alfa-beta, comptem a la variable global nodes quantes vegades es crida minimax, és a dir, quantes posicions s'examinen:

nodes = 0

def minimax(t, torn):
    """Valor minimax del tauler t quan li toca moure a `torn` ('X' o 'O')."""
    global nodes
    nodes += 1
    if terminal(t):
        return utilitat(t)
    if torn == "X":                        # MAX
        millor = -math.inf
        for m in moviments(t):
            t[m] = "X"                     # fer la jugada...
            valor = minimax(t, "O")        # ...veure que passa si O respon tan be com pot...
            t[m] = " "                     # ...i desfer-la (backtracking) per provar la seguent
            millor = max(millor, valor)
        return millor
    else:                                  # MIN
        millor = math.inf
        for m in moviments(t):
            t[m] = "O"
            valor = minimax(t, "X")
            t[m] = " "
            millor = min(millor, valor)
        return millor

def millor_jugada(t, torn):
    """Retorna (casella, valor, nodes_explorats) de la millor jugada per a `torn`."""
    global nodes
    nodes = 0
    millor_m = None
    millor_v = -math.inf if torn == "X" else math.inf
    for m in moviments(t):
        t[m] = torn
        v = minimax(t, "O" if torn == "X" else "X")
        t[m] = " "
        if (torn == "X" and v > millor_v) or (torn == "O" and v < millor_v):
            millor_m, millor_v = m, v
    return millor_m, millor_v, nodes

Punts importants del codi:

  • Fer i desfer la jugada sobre la mateixa llista (t[m] = "X" … t[m] = " ") evita copiar el tauler a cada crida. És el patró de backtracking típic de la cerca en profunditat; funciona perquè, en tornar de la recursió, restaurem exactament l'estat anterior.
  • millor_jugada és l'"arrel" de l'arbre: aplica el mateix criteri que minimax, però recordant quina jugada dona el millor valor, que és el que de debò necessitem.
  • Cada crida a minimax recorre LINIES a terminal; ho podríem optimitzar, però per a 550.000 posicions Python triga uns segons, suficient.

Provem-ho en tres situacions:

# 1) Tauler buit: quina es la millor obertura i quant val el joc?
print(millor_jugada([" "] * 9, "X"))

# 2) O amenaca guanyar a la columna central: X ha de bloquejar a la casella 7
t = ["X", "O", "X",
     " ", "O", " ",
     " ", " ", " "]
print(millor_jugada(t, "X"))

# 3) X pot crear una doble amenaca: la casella 3 obre dues linies alhora
t3 = ["X", "O", " ",
      " ", "X", " ",
      " ", " ", "O"]
print(millor_jugada(t3, "X"))
(0, 0, 549945)
(7, 0, 205)
(3, 1, 237)

Lectura de resultats:

  1. Des del tauler buit el valor és 0: amb joc perfecte per totes dues bandes el tres en ratlla acaba en taules, cosa que qualsevol nen descobreix jugant i que minimax demostra explorant 549.945 posicions (totes les de l'arbre llevat de l'arrel). Retorna la casella 0 perquè és la primera amb valor 0; en realitat les nou obertures valen 0. Si imprimeixes el valor de cadascuna veuràs que totes empaten i que la més "barata" d'analitzar és el centre (55.505 nodes davant de 59.705 de les cantonades i 63.905 dels laterals), perquè la simetria del centre escurça més partides.
  2. Amb O amenaçant la columna central, X bloqueja a 7; el valor continua sent 0 (taules amb bon joc), i només calen 205 nodes perquè queden poques caselles.
  3. A la tercera posició, X juga a la casella 3 i el valor passa a +1: minimax ha trobat la doble amenaça (columna esquerra i fila central) contra la qual O no té defensa. Aquest és el tipus de "visió" que un jugador humà necessita entrenar i que la cerca obté per pura enumeració.

Si deixes jugar millor_jugada contra si mateixa des del tauler buit obtindràs sempre taules: minimax mai no perd i mai no deixa escapar una victòria forçada.

  1. Poda alfa-beta: idea, exemple numèric i implementació

Minimax examina l'arbre sencer, però gran part de la feina és inútil: hi ha branques el resultat de les quals no pot canviar la decisió, i podem deixar d'explorar-les tan bon punt ho sapiguem. Aquesta és la poda alfa-beta, que retorna exactament el mateix valor i la mateixa jugada que minimax, però visitant molts menys nodes.

Tornem a l'arbre numèric de la secció 4 i seguim l'ordre en què la cerca en profunditat el recorre:

  1. S'explora B sencer: B1 = 3, B2 = 12, B3 = 8, així que B = 3. MAX ja sap que a A pot garantir-se almenys 3. Aquest "almenys" és alfa (α): la millor opció trobada fins ara per a MAX en el camí des de l'arrel.
  2. Es comença C. La primera fulla és C1 = 2. Com que MIN tria el mínim, C valdrà 2 o menys. Però MAX ja té garantit 3 a B; una branca que val com a molt 2 mai no serà triada. No cal mirar C2 ni C3: es poden.
  3. Es comença D. D1 = 14: D val com a molt 14, encara podria superar 3, seguim. D2 = 5: D val com a molt 5, encara podria superar 3, seguim. D3 = 2: D val com a molt 2, ja no pot superar 3. Aquí no hem estalviat res perquè la fulla dolenta era l'última.

Resultat: mateix valor (3, anar a B) explorant 11 nodes en lloc de 13. Al pas 3 es veu la clau del rendiment: l'ordre importa. Si D3 hagués estat primer, D s'hauria podat després d'una sola fulla. Amb un ordre perfecte (provar primer les millors jugades), alfa-beta explora de l'ordre de b^(m/2) nodes en lloc de bᵐ: pot mirar el doble de profunditat amb el mateix esforç. Amb ordre aleatori el guany és menor però continua sent gran.

Formalment es mantenen dos valors durant la recursió: α = la millor utilitat que MAX pot assegurar-se fins ara (comença en −∞ i només creix), i β = la millor utilitat que MIN pot assegurar-se fins ara (comença en +∞ i només baixa). Tan bon punt α ≥ β en algun node, la resta dels seus fills es descarta: MAX ja té alguna cosa millor en un altre lloc (o MIN ja té alguna cosa pitjor per a nosaltres en un altre lloc) i aquesta branca mai no es jugarà.

def alfabeta(t, torn, alfa, beta):
    global nodes
    nodes += 1
    if terminal(t):
        return utilitat(t)
    if torn == "X":                                    # MAX
        millor = -math.inf
        for m in moviments(t):
            t[m] = "X"
            millor = max(millor, alfabeta(t, "O", alfa, beta))
            t[m] = " "
            alfa = max(alfa, millor)                   # MAX millora la seva garantia
            if alfa >= beta:                           # MIN mai no permetra arribar aqui
                break                                  # PODA
        return millor
    else:                                              # MIN
        millor = math.inf
        for m in moviments(t):
            t[m] = "O"
            millor = min(millor, alfabeta(t, "X", alfa, beta))
            t[m] = " "
            beta = min(beta, millor)                   # MIN millora la seva garantia
            if alfa >= beta:                           # MAX mai no triara venir aqui
                break                                  # PODA
        return millor

def millor_jugada_ab(t, torn):
    global nodes
    nodes = 0
    millor_m = None
    millor_v = -math.inf if torn == "X" else math.inf
    alfa, beta = -math.inf, math.inf
    for m in moviments(t):
        t[m] = torn
        v = alfabeta(t, "O" if torn == "X" else "X", alfa, beta)
        t[m] = " "
        if torn == "X" and v > millor_v:
            millor_m, millor_v = m, v
            alfa = max(alfa, v)                        # tambe a l'arrel s'aprofita la cota
        elif torn == "O" and v < millor_v:
            millor_m, millor_v = m, v
            beta = min(beta, v)
    return millor_m, millor_v, nodes

print(millor_jugada_ab([" "] * 9, "X"))
print(millor_jugada_ab(t, "X"))
print(millor_jugada_ab(t3, "X"))
(0, 0, 18296)
(7, 0, 100)
(3, 1, 92)

Comparació directa, mateixa jugada i mateix valor en els tres casos:

Posició Minimax (nodes) Alfa-beta (nodes) Reducció
Tauler buit 549.945 18.296 30×
Bloqueig a la casella 7 205 100 2×
Doble amenaça a la casella 3 237 92 2,6×

I una comprovació de l'efecte de l'ordre: si a moviments retornem primer el centre, després les cantonades i després els laterals (l'ordre que qualsevol jugador amb experiència provaria), la cerca des del tauler buit baixa de 18.296 a 7.274 nodes, 75 vegades menys que minimax pur. Als motors d'escacs, ordenar bé les jugades (captures primer, jugades que van ser bones en cerques anteriors…) és tan important com la poda mateixa.

  1. Límit de profunditat i funció d'avaluació

El tres en ratlla s'esgota sencer. Els escacs, amb unes 35 jugades legals per posició i partides de 80 mitges jugades, tenen un arbre de l'ordre de 35⁸⁰ ≈ 10¹²³ nodes; el go, amb 250 jugades per torn i partides de 150 moviments, de l'ordre de 10³⁶⁰. Ni alfa-beta ni cap ordinador concebible els recorren. La solució pràctica té dues parts:

  • Tallar la cerca a una profunditat màxima (per exemple, 6 mitges jugades) i tractar aquestes posicions com si fossin fulles.
  • Substituir la utilitat exacta (que només es coneix en posicions terminals) per una funció d'avaluació heurística que estimi com de bona és una posició per a MAX: en escacs, material (peó 1, cavall 3, torre 5…), mobilitat, seguretat del rei; en go, territori i influència. És la mateixa idea que l'heurística h d'A* a 03-02: una estimació barata que guia la cerca quan l'exacte és inabastable.

Per al tres en ratlla podem construir una avaluació senzilla: nombre de línies encara "obertes" per a X (sense cap O), ponderades per quantes X ja tenen, menys el mateix per a O. Amb profunditat 1 aquesta avaluació ja prefereix el centre (valor 4, perquè el centre és a quatre línies) sobre les cantonades (3) i els laterals (2). No demostra res, però orienta bé, i en jocs grans això és tot el que es pot demanar.

Aquesta combinació (alfa-beta + profunditat limitada + avaluació heurística + ordenació de jugades + taules de posicions ja vistes) és exactament l'arquitectura de Deep Blue, que el 1997 va vèncer Kaspàrov analitzant uns 200 milions de posicions per segon amb una funció d'avaluació dissenyada a mà per grans mestres i enginyers, com vam recordar a 01-01. És una IA simbòlica i de cerca pura (02-02): no va aprendre a jugar; va cercar més lluny i va avaluar millor que un humà. El go va resistir vint anys més perquè el seu factor de ramificació és massa gran fins i tot per a alfa-beta i perquè ningú no va saber escriure una funció d'avaluació bona a mà; AlphaGo (2016) va resoldre justament aquest punt substituint l'avaluació manual per una xarxa neuronal entrenada amb partides i amb joc contra si mateixa, i combinant-la amb una forma de cerca per mostreig. Com s'entrena aquesta xarxa és matèria d'aprenentatge per reforç (04-02) i de xarxes neuronals (mòdul 5); el que importa aquí és veure que la cerca amb adversari continua sent l'esquelet i que el que va evolucionar va ser d'on surt l'avaluació.

  1. Aterratge a NovaMarket: la guerra de preus i el defraudador adaptatiu

8.1 Una guerra de preus simplificada

En Diego i la Marta volen decidir el preu setmanal d'un televisor estrella sabent que el seu principal competidor reacciona als seus moviments. Modelem-ho com un joc de dos nivells: NovaMarket (MAX) tria entre mantenir el preu, baixar-lo un 5 % o baixar-lo un 10 %; el competidor (MIN) respon mantenint, igualant o baixant encara més. A les fulles hi posem el marge setmanal estimat de NovaMarket (en milers d'euros) per a cada combinació, obtingut de les seves dades històriques de vendes:

graph TD
    R[MAX NovaMarket] --> M[MIN: mantenir = 3]
    R --> B5[MIN: baixar 5% = 5]
    R --> B10[MIN: baixar 10% = 4]
    M --> M1[comp. manté: 12]
    M --> M2[comp. baixa 5%: 6]
    M --> M3[comp. baixa 10%: 3]
    B5 --> B51[comp. manté: 14]
    B5 --> B52[comp. iguala: 8]
    B5 --> B53[comp. baixa 10%: 5]
    B10 --> B101[comp. manté: 13]
    B10 --> B102[comp. iguala: 6]
    B10 --> B103[comp. baixa 15%: 4]

Reutilitzem la recursió genèrica de la secció 4 amb noms del negoci:

ARBRE_PREUS = {
    "inici":     ["mantenir", "baixar_5", "baixar_10"],
    "mantenir":  ["m_comp_mante", "m_comp_baixa5", "m_comp_baixa10"],
    "baixar_5":  ["b5_comp_mante", "b5_comp_iguala", "b5_comp_baixa10"],
    "baixar_10": ["b10_comp_mante", "b10_comp_iguala", "b10_comp_baixa15"],
}
MARGE_NOVA = {      # milers d'euros de marge setmanal per a NovaMarket
    "m_comp_mante": 12, "m_comp_baixa5": 6, "m_comp_baixa10": 3,
    "b5_comp_mante": 14, "b5_comp_iguala": 8, "b5_comp_baixa10": 5,
    "b10_comp_mante": 13, "b10_comp_iguala": 6, "b10_comp_baixa15": 4,
}

def minimax_generic(arbre, utilitats, node, es_max):
    if node in utilitats:
        return utilitats[node]
    valors = [minimax_generic(arbre, utilitats, fill, not es_max) for fill in arbre[node]]
    return max(valors) if es_max else min(valors)

for opcio in ARBRE_PREUS["inici"]:
    print(f"{opcio:9s} -> pitjor cas {minimax_generic(ARBRE_PREUS, MARGE_NOVA, opcio, False)}")
print("Valor minimax:", minimax_generic(ARBRE_PREUS, MARGE_NOVA, "inici", True))
mantenir  -> pitjor cas 3
baixar_5  -> pitjor cas 5
baixar_10 -> pitjor cas 4
Valor minimax: 5

Minimax recomana baixar un 5 %, no perquè sigui l'opció amb la millor fulla (la millor fulla, 14, també és en aquesta branca, però això és casualitat), sinó perquè és la que garanteix més en el pitjor cas: passi el que passi, el marge no baixarà de 5.000 €. Mantenir el preu té la pitjor garantia (3) perquè deixa la iniciativa al competidor. Aquest raonament d'"assegurar el terra" és el que aporta minimax a una decisió de negoci, i és especialment valuós quan el cost d'equivocar-se és alt.

8.2 El defraudador que s'adapta

El cas 3 (frau en devolucions) és un altre entorn amb adversari: quan NovaMarket endureix una regla ("bloquejar devolucions sense tiquet a partir de la tercera al mes"), els defraudadors l'aprenen i canvien de tàctica (reparteixen devolucions entre diversos comptes, baixen de tres). El detector que es dissenya pensant només en el comportament passat és com un jugador que no mira les respostes del rival. Pensar en mode minimax significa preguntar-se, per a cada regla candidata, "quina és la millor resposta del defraudador a aquesta regla i quant frau se'm cola llavors?", i triar la regla la pitjor resposta de la qual és la menys danyosa. A la pràctica no es construeix un arbre explícit, però l'hàbit mental és el mateix, i hi tornarem quan parlem de l'avaluació de models de frau al mòdul 4.

  1. Límits de minimax: quan el món no és un tauler

La guerra de preus de 8.1 és útil com a exercici de pensament, però convé ser honestos sobre en què s'allunya d'un joc de tauler. Cada diferència assenyala una eina diferent:

Supòsit de minimax En el tres en ratlla En la guerra de preus Què cal en el seu lloc
Suma zero Sí: el que guanya X ho perd O No: una guerra de preus pot perjudicar tots dos, i mantenir preus beneficiar tots dos Teoria de jocs general (equilibris, no minimax); modelar la utilitat del rival, no la nostra en negatiu
Informació perfecta Sí: tots dos veuen el tauler No: no coneixem els costos ni l'estoc del competidor, ni ell els nostres Models probabilístics i raonament amb incertesa (06-03)
Determinista Sí No: la demanda té atzar (clima, campanyes, moda) Utilitat esperada (02-01) en lloc d'utilitat fixa; nodes d'atzar a l'arbre ("expectiminimax")
Un sol rival, racional Sí Hi ha diversos competidors, i no sempre reaccionen de manera òptima Models del rival apresos de dades (mòdul 4)
Partida finita i aïllada Sí Es repeteix cada setmana: la reputació i les represàlies importen Jocs repetits; aprenentatge per reforç (04-02)

Un exemple concret de la primera fila: si a més del marge de NovaMarket estimem el marge del competidor a cada fulla i suposem que ell maximitza el seu en lloc de minimitzar el nostre, la resposta prevista a "baixar 5 %" passa de "baixar 10 %" (que a ell li deixa 6.000 €) a "igualar" (que li deixa 9.000 €), i el marge que hauríem d'esperar és 8, no 5. En aquest cas la decisió no canvia (baixar 5 % continua sent el millor), però la valoració sí, i en altres casos podria canviar també la decisió. Minimax dona el terra garantit; el model del rival dona l'expectativa realista. Un bon analista mira tots dos.

El que sí que és universal és la lliçó de fons: quan hi ha un altre agent que reacciona, una decisió no es pot avaluar sola, cal avaluar-la juntament amb la millor resposta de l'altre. Aquest principi, amb arbre explícit o sense, és l'aportació d'aquesta lliçó a la resta del curs.

Errors Comuns i Consells

  • Oblidar desfer la jugada (t[m] = " ") després de la crida recursiva: el tauler queda corromput i els resultats són absurds. Si prefereixes evitar el risc, crea una còpia (nou = list(t)) a costa de més memòria i temps.
  • Confondre el valor d'una posició amb la jugada: minimax retorna un nombre; cal embolcallar-lo (millor_jugada) per saber quin moviment produeix aquest nombre.
  • Posar les condicions de poda a l'inrevés: MAX actualitza α i poda si α ≥ β; MIN actualitza β i poda amb la mateixa condició. Un error habitual és actualitzar β a MAX. Comprova-ho sempre amb l'arbre de la secció 4: has d'obtenir 3 podant C després de C1.
  • Creure que alfa-beta canvia el resultat: mai. Si obtens valors diferents entre minimax i alfabeta, hi ha un error a la implementació de la poda.
  • No inicialitzar alfa i beta a l'arrel a −∞ i +∞: qualsevol altre valor pot podar branques vàlides.
  • Aplicar minimax a un problema que no és de suma zero sense adonar-se'n: com a la guerra de preus, la resposta serà excessivament pessimista. Pregunta't sempre si "el que jo perdo ho guanya l'altre" és literalment cert.
  • Funció d'avaluació amb l'escala equivocada: si les posicions terminals valen ±1 i l'avaluació heurística retorna valors com 4 o −3, una posició "prometedora" pot semblar millor que una victòria segura. Escala la utilitat terminal (per exemple ±100) perquè domini.

Exercicis

Exercici 1: minimax i alfa-beta a mà

Donat l'arbre següent (MAX a l'arrel, MIN al segon nivell, fulles amb utilitats), calcula el valor minimax de l'arrel i la jugada triada. Després aplica alfa-beta recorrent els fills d'esquerra a dreta i indica quines fulles es poden.

Arrel (MAX)
├── E (MIN): 5, 9, 4
├── F (MIN): 2, 7, 8
└── G (MIN): 6, 11, 3

Exercici 2: comptar l'estalvi de l'ordenació

Modifica moviments perquè retorni les caselles en l'ordre centre, cantonades, laterals ([4, 0, 2, 6, 8, 1, 3, 5, 7] filtrant les ocupades) i compara els nodes explorats per millor_jugada_ab des del tauler buit amb l'ordre original. Comprova que el valor i la jugada recomanada (ara la casella 4) continuen valent 0. Canvia el nombre de nodes de millor_jugada (minimax sense poda) en reordenar? Per què?

Exercici 3: el competidor racional a la guerra de preus

Afegeix el diccionari MARGE_COMP amb el marge del competidor a cada fulla (fes servir aquests valors: mantenir → 10, 11, 9; baixar_5 → 7, 9, 6; baixar_10 → 5, 7, 4, en el mateix ordre que les fulles d'ARBRE_PREUS) i escriu una funció resposta_racional(opcio) que retorni la fulla on el competidor maximitza el seu marge. Per a cada opció de NovaMarket imprimeix la resposta prevista, el nostre marge i el seu, i compara la recomanació amb la de minimax.

Solucions

Solució 1. E = min(5, 9, 4) = 4; F = min(2, 7, 8) = 2; G = min(6, 11, 3) = 3. Arrel = max(4, 2, 3) = 4, jugada E. Amb alfa-beta: s'explora E sencer (α passa a 4). A F, la primera fulla és 2 ≤ α, així que F no pot superar 4: es poden 7 i 8. A G, la primera fulla és 6 > 4 (seguim), la segona 11 (seguim), la tercera 3 fa G = 3 < 4; no hi ha poda perquè la fulla dolenta ha arribat al final. Total: 7 fulles examinades de 9 (se n'estalvien 2), mateix resultat que minimax. Si l'ordre dins de G hagués estat 3, 6, 11, també s'haurien podat 6 i 11 i n'hi hauria prou amb 5 fulles.

Solució 2.

ORDRE = [4, 0, 2, 6, 8, 1, 3, 5, 7]

def moviments(t):
    return [i for i in ORDRE if t[i] == " "]

print(millor_jugada_ab([" "] * 9, "X"))    # (4, 0, 7274)
print(millor_jugada([" "] * 9, "X"))       # (4, 0, 549945)

Alfa-beta baixa de 18.296 a 7.274 nodes i recomana ara la casella 4 (el centre; continua valent 0 com totes). Minimax sense poda explora exactament els mateixos 549.945 nodes: sense poda, l'ordre només canvia quan es visita cada node, no si es visita. L'ordenació només té efecte quan hi ha alguna cosa a podar.

Solució 3.

MARGE_COMP = {
    "m_comp_mante": 10, "m_comp_baixa5": 11, "m_comp_baixa10": 9,
    "b5_comp_mante": 7, "b5_comp_iguala": 9, "b5_comp_baixa10": 6,
    "b10_comp_mante": 5, "b10_comp_iguala": 7, "b10_comp_baixa15": 4,
}

def resposta_racional(opcio):
    return max(ARBRE_PREUS[opcio], key=lambda fulla: MARGE_COMP[fulla])

for opcio in ARBRE_PREUS["inici"]:
    r = resposta_racional(opcio)
    print(f"{opcio:9s} -> {r:17s} el nostre marge {MARGE_NOVA[r]}, el seu {MARGE_COMP[r]}")
mantenir  -> m_comp_baixa5     el nostre marge 6, el seu 11
baixar_5  -> b5_comp_iguala    el nostre marge 8, el seu 9
baixar_10 -> b10_comp_iguala   el nostre marge 6, el seu 7

El competidor racional respon a "mantenir" baixant un 5 % (li dona 11), i a les nostres baixades igualant-les. La millor opció per a NovaMarket continua sent baixar un 5 %, amb un marge esperat de 8 davant del terra de 5 que garantia minimax. Les dues maneres de raonar coincideixen en la decisió, però no en la xifra: minimax és una assegurança contra el pitjor cas; el model del rival, una predicció del que és probable.

Conclusió

Hem afegit a la cerca un ingredient nou: un adversari que decideix en contra nostra. Hem vist que als jocs de suma zero amb informació perfecta una solució ja no és un camí sinó una estratègia, i que l'arbre de joc alterna nivells MAX i MIN. L'algorisme minimax recorre aquest arbre en profunditat i propaga cap amunt, des de les fulles, el valor que cada jugador pot garantir-se; l'hem seguit a mà en un arbre numèric i l'hem implementat per al tres en ratlla, comprovant que el joc és taules i que calen 549.945 nodes per demostrar-ho. La poda alfa-beta obté el mateix resultat explorant 18.296 nodes (7.274 amb una bona ordenació de jugades), i el límit de profunditat amb funció d'avaluació és el que permet jugar als escacs o al go, el camí que va de Deep Blue a AlphaGo. Amb la guerra de preus de NovaMarket hem vist que l'hàbit d'"avaluar cada decisió juntament amb la millor resposta del rival" és útil també al negoci, i hem delimitat amb claredat quan minimax deixa de ser el model adequat (suma no zero, informació imperfecta, atzar, repetició).

Ens queda el tercer gran problema anunciat en obrir el mòdul. Fins ara hem cercat camins (03-02) i jugades (03-03) explorant l'espai d'estats de manera sistemàtica. Però el problema complet de la furgoneta (triar l'ordre de tots els lliuraments del dia) té, com vam veure a 03-01, n! solucions candidates, i cap cerca sistemàtica no l'esgota. A l'última lliçó del mòdul, Algorismes d'Optimització, canviarem d'enfocament: en lloc de construir la solució pas a pas, partirem d'una solució completa qualsevol i l'anirem millorant amb ascens de turó, recuit simulat i algorismes genètics, per resoldre el problema del viatjant de la furgoneta i l'assignació de comandes als magatzems de Zaragoza i Getafe.

◄ Anterior
◄
Següent ►
►

Fonaments d'Intel·ligència Artificial (IA)

Mòdul 1: Introducció a la Intel·ligència Artificial

Mòdul 2: Principis Bàsics de la IA

Mòdul 3: Algorismes en IA

Mòdul 4: Aprenentatge Automàtic (Machine Learning)

Mòdul 5: Xarxes Neuronals i Deep Learning

Mòdul 6: Lògica i Sistemes Experts

Mòdul 7: Eines i Llenguatges de Programació en IA

Mòdul 8: Projectes i Casos d'Estudi

Mòdul 9: Exercicis i Pràctiques

Mòdul 10: Recursos Addicionals

El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats