DOCUMENTACIÓ MINIMAX


Descripció

La funció d'avaluació ha de valer el valor màxim quan guanyo jo i el valor mínim quan guanya el contrincant. D'aquesta manera, jo voldré maximitzar aquesta funció mentre que el contrincant la voldrà minimitzar. Per això, l'algorisme s'anomena minimax. L'heurística d'un node fulla ve determinat per una funció definida segons l'estat. I l'heurística d'un node no fulla es calcula de la següent manera:

L'algorisme, donat un estat ha de decidir quin moviment (node fill) triarà. La decisió consisteix en generar un sub-arbre de profunditat "prof" per cada fill, amb tots els moviments possibles d'ambdós jugadors. Cada nivell de l'arbre minimax representa els moviments d'un dels dos jugadors. S'avaluen els nodes fulla dels subarbres segons una funció definida, i es propaguen les heurístiques cap als nodes superiors (maximitzant o minimitzant). Finalment, selecciona el fill amb millor valor de l'heurística.

Per a poder propagar les heurístiques cap als nivells superiors, sense haver de recórrer tot l'arbre una segona vegada, es genera l'arbre en profunditat. A més, esborrem els nodes de l'estructura "arbre_nodes" quan ja hem avaluat el seu corresponent pare. Així guanyem en eficiència.

Exemple d'ordre d'exploració i evolució de l'arbre per l'algorisme minimax:

Per a fer l'algorisme encara més eficient, es pot incloure la poda alfa/beta. Tenint en compte, que els nivells de l'arbre parells representen els meus moviments, els anomenem de maximització, i els nivells senars, de minimització. Obtenim així dos tipus de poda: l'alfa i la beta.

La poda beta es basa en el següent:

- Si (x>3) -> (y=3) -> (k=5)

- Si (x<=3) -> (y=x<=3) -> (k=5)

O sigui, podant la branca x, arribaré al mateix resultat (k=5) que si no la podés.

Però com ho reconeixo al meu algorisme ? Doncs definint la variable beta com el valor més gran fins al moment obtingut de minimitzar els seus successors. I podaré els germans dels nodes dels nivells de maximització amb valor menor que beta.

Començo inicialitzant beta amb el valor més petit possible (-100). Exploro el node A, el node B i el node D. Com que D és un node fulla l'avaluo (8), després exploro E que també és fulla i l'avaluo (5). Torno al node B i li dono com a valor d'heurística el mínim entre els seus fills (5). Com que 5 és més gran que -100 actualitzo beta amb el valor 5. Continuo explorant C i F. Aquest últim és fulla, l'avaluo (3) i com que la seva heurística és menor que beta, podo tots els seus germans (G).

Simètricament, la poda alfa consisteix en:

- Si (x>=9) -> (y=x>=9) -> (k=5)

- Si (x<9) -> (y=9) -> (k=5)

Definint alfa com el valor més petit fins al moment obtingut de maximitzar els seus successors, podo els germans dels nodes dels nivells de minimització amb valor més gran que alfa.

Començo inicialitzant alfa amb el valor més gran possible (100). Exploro el node A, el node B i el node D. Com que D és un node fulla l'avaluo (8), després exploro E que també és fulla i l'avaluo (5). Torno al node B i li dono com a valor d'heurística el màxim entre els seus fills (8). Com que 8 és més petit que 100 actualitzo alfa amb el valor 8. Continuo explorant C i F. Aquest últim és fulla, l'avaluo (9) i com que la seva heurística és major que alfa, podo tots els seus germans (G).

Pseudocodi

Algorisme minimax (node node_inicial, int prof, booleà poda)

FiAlgorisme

/* Arbre */

TAD arbre ()

/* Crea un nou arbre buit */

Funcio arbre_buit (): arbre

FiFuncio

/* Afegeix un node a l'arbre */

Funcio afegir_elem (arbre a, node n): arbre

FiFuncio

/* Afegeix a l'arbre els fills del node i-èssim de l'arbre */

Funcio generar_fills (arbre a, int i): arbre

FiFuncio

/* Assigna l'avaluació del node i-èssim (fulla) de l'arbre */

Funcio avaluar_fulla (arbre a, int i): arbre

FiFuncio

/* Assigna l'avaluació del node i-èssim (no fulla) de l'arbre */

Funcio avaluar_no_fulla (arbre a, int i): arbre

FiFuncio

/* Treu de l'arbre els fills del node i-èssim */

Funcio borrar_fills (arbre a, int i): arbre

FiFuncio

/* Treu de l'arbre el node i-èssim */

Funcio borrar_elem (arbre a, int i): arbre

FiFuncio

FiTAD

Inici Anterior