03. Adversary search

Introduzione e definizioni

L'adversary search è la ricerca di soluzioni in un problema con avversari.
Giochi ad informazione completa: ogni giocatore conosce l'intera configurazione del gioco ad ogni mossa
Giochi ad informazione incompleta: non tutti (o nessuno) i giocatori conoscono l'intera configurazione di gioco ad ogni mossa.
Giochi estensivi: giochi che permettono più mosse e non solo una.

Strategia: non è unica, dipende dall'obiettivo. Ad esempio in alcuni giochi la strategia di un giocatore è quella di resistere il più possibile, mentre la strategia dell'altro giocatore è quella di attaccare eliminando l'avversario.
Stategia del probing: si usa quando il gioco è ad informazione incompleta. Si sacrificano dei pezzi per scoprire la configurazione di gioco dell'avversario.

Mossa in italiano: il movimento dei pezzi di un giocatore. Equivale ad una semimossa (ply) in inglese.
Mossa in inglese (move): il movimento dei pezzi di tutti i giocatori (praticamente la conclusione effettiva di un turno).

MinMax

E' l'algoritmo di riferimento per gli spazi di ricerca generati da situazioni con avversari. I raffinamenti di questi sono il pruning (evitare di esplorare rami dell'albero dello spazio di ricerca che non sono produttivi secondo la funzione euristica) e lo storing dell'end game. Ovvero sappiamo a priori quali configurazioni di gioco portano alla soluzione e quali no, ovviamente in fase avanzata del gioco.

Minmax per due giocatori

Ci sono due giocatori, Mr. Max e Mr. Min. Si parte da una configurazione di gioco e deve muovere Mr.max portando la configurazione di gioco in altri stati, poi muove Min e così via. Ovviamente si può costruire l'albero di ricerca duale MaxMin dove muove prima Min.

d6.jpg

Se l'algoritmo di ricerca lavora su uno spazio relativo a chi massimizza, cioè Max, la prima mossa sarà fatta sempre da Mr.Max, altrimenti come si è scritto c'è il duale.
La configurazione di gioco iniziale è a , con la mossa di Max ci si sposta nelle configurazioni b o c o d.

Supponiamo che le foglie dell'albero siano configurazion di gioco dove il gioco è terminato. Valutiamo con 1 la configurazione dove vince Max e con -1 quella in cui vince Min. Alcuni nodi non li classifichiamo perchè ci sarà un ragionamento in seguito.

d7.jpg

Supponiamo di essere in configurazione k e deve muovere Min. In questa configurazione Min perderà, poichè se muove in w perde, se muove in o poi Max sceglierà una mossa vincente (che lo porta in q).
Se siamo in configurazione i, Min muoverà in m per vincere.
Qui è facile valutare le mosse da intraprendere perchè siamo vicini alle foglie, ma Max da a come muove?
Dobbiamo riportare il valore della configurazione che verrà scelta al padre di quella configurazione. Per i nodi max si riporta il valore massimo tra i figli, per i nodi min si riporta il valore minimo tra i figli.
Ad esempio il nodo o avrà valore 1, poichè esiste ilf iglio q con valore 1 e Max sceglierà la mossa verso q. Il nodo k avrà valore 1 poichè o è stato valutato, mentre w avrà valore 1. Allo stesso modo g avrà valore 1, indipendentement dal valore di j, poichè lo eredita da k.

d8.jpg

Quindi per Max una combinazione di mosse vincente è $\left \{ c,g,k,o,q \right \}$.

Pruning primitivo

Supponiamo che l'alg abbia espanso, magari casualmente, i nodi sotto c. Sapendo che esiste una strategia vincente sotto c allora l'algoritmo si disinteressa della ricerca in altri rami. Questo è il pruning (taglio) più immediato.

Pruning base per Mr. Max (per Mr. Min cambia poco)

1. espandi l'albero sotto la configurazione corrente n.
2. valuta i nodi terminali del sottoalbero ottenuto con +1 e -1 a seconda se vince Max o Min
3. seleziona un nodo non valutato i cui figli sono stati valutati. Se non ci sono nodi non valutati, restituisci il valore di n.
4. Se il nodo selezionato appartiene a Min (cioè min deve fare la mossa) etichettalo con il valore v=min{valori dei figli}, 
   altrimenti se appartiene a Max usa il valore v=max{valori dei figli}
5. goto 3

Dallo pseudocodice non appare evidente, ma sostanzialmente man mano che si "sale" etichettando i nodi non foglia, se il sottoalbero contiene un nodo vincente per chi ha giocato inizialmente (cioè chi ha fatto la mossa nel nodo radice) allora verrà espanso solo quel sottoalbero (nel caso l'espansione dell'albero venga fatta sostanzialmente in modo depth first) ed una volta tornato il path vincente l'algoritmo si fermerà.

Versione depth first del minmax

Sia n la configurazione iniziale del gioco da cui parte la valutazione.
1. L={n} //insieme dei nodi non espansi
2. x=first(L). Se x=n and x è etichettato : return x and stop.
3. Se x ha un'etichetta v(x), sia p il genitore di x con etichetta corrente v(p) . 
   Se p appartiene a Min allora -> update v(p) = min (v(p), v(x) )
   Se p appartiene a Max allora -> update v(p) = max (v(p), v(x) )
   update L = L-{x}
   goto 2
4. Se x non ha etichetta ed è un nodo foglia, assegna ad x il valore +1 (vince Max) o 0 (pari) o -1 (vince Min),
   lascialo in L, goto 2.
5. Se x non ha etichetta e non è una foglia, poni v(x) = -inf se x appartiene a Max, 
   altrimenti v(x) = +inf se x appartiene a Min.
   Insert figli(x) in cima ad L.
   goto 2.

Una versione più specifica è la seguente

//Stato s : oggetto che definisce la situazione della partita, che sia una situazione attuale (ovvero effettivamente in atto)
//nel gioco, oppure una situazione prevista ma non ancora in atto (le situazioni previste si hanno quando si esplora lo
//stato del gioco.
//Il calcolo in un dato stato è visibile come il calcolo in un dato nodo nell'albero di ricerca.
 
inf : infinito
--
 
int minMaxvalue(Stato s){
  if (s.turnoMax()){
    return maxValue(s);
  }
  else {
    return minValue(s);
  }
}
 
int maxValue(Stato s){
  if (s.nodoTerminale()){
    return s.value();
      //funzione che valuta lo stato del gioco assegnando +1 o -1 (o 0) a seconda di chi ha vinto (o se han)
      //pareggiato.
  }
  //se non siamo in un nodo terminale
  Mossa[] mosse = s.mosseVelagli(); 
    //ritorna tutte le mosse fattibili dal giocatore
    //rispetto allo stato corrente
  int v = - inf; 
    //valore del nodo in assenza di informazioni, è un valore fortemente pessimistico.
  for (int i=0; i <= mosse.length; i++){
    s.effettuaMossa(mosse[i]); //applica temporanamente la mossa allo stato
    v = max (v, minValue(s));
      //come valore per questo stato, visto che non è terminale
      //scegli il valore massimo tra il valore precedentemente memorizzato e quello
      //ritornato dal giocatore avversario (che ricordiamo usa valori negativi)
    s.undoMossa();
      //perchè era applicata temporaneamente
      //osservare che nell'esecuzione dell'algoritmo
      //allo stato vengono applicate diverse mosse
      //che deve memorizzare per poi rimuoverle.
      //l'alternativa è crearsi uno stato per ogni nodo dell'albero
  }
  return v; //ritorniamo il valore di qusto nodo, che è il massimo dei nodi figli.
}
 
int minValue(Stato s){
  if (s.nodoTerminale()){
    return s.value();
  }
  Mossa[] mosse = s.mosseVelagli(); 
  int v = + inf; 
    //valutiamo secondo l'ottica di mr min quindi cerchiamo il valore più prossimo a -1
  for (int i=0; i <= mosse.length; i++){
    s.effettuaMossa(mosse[i]);
    v = min (v, maxValue(s));
      //notare min
    s.undoMossa();
  }
  return v; 
}

Giochi con pareggio

Esistono giochi in cui è possibile pareggiare, l'algoritmo visto sopra è identico e si assegna ai nodi terminali anche il valore 0 (pareggio)

Stima dei valori di un nodo (euristica)

La versione depth first del minmax può andar bene su spazi di ricerca limitati, ma se questi sono troppo grandi? Allora conviene stimare il valore dei nodi (scritto meglio: stimare il valore delle configurazioni di gioco) fermandoci ad un dato livello di profondità (cioè considero i nodi ad un dato livello di profondità come nodi foglia). Il valore stimato dei nodi sarà $e(x) \in \left [ -1,1 \right ]$ . I due estremi indicano: vince di certo mr min (cioè il nodo avrebbe valore reale -1) e vince di certo mr max. I valori intermedi indicano "c'è più probabilità che vinca Max/Min". L'euristica stima, come è stato scritto, la distanza della configurazione attuale dallo stato di vittoria.

d9.jpg

Esempio con gli scacchi

Si usa questa funzione euristica di stima: $e(x) = \frac{W-B}{W+B}$.
Dove Max è il bianco che possiede tot pezzi (W) e Min è il nero (B). In pratica questa stima (primitiva) conta il vantaggio dei pezzi di Max su quelli di Min rispetto al totale. E' facile vedere che e(x) varia tra -1 ed 1.
Ovviamente questa stima è limitata, poichè non tiene conto delle posizioni ma solo del valore dei pezzi. Quindi a parità di scelte si sceglie casualmente.

Tradeoff

Si ripresenta il problema del tradeoff. Quanto conviene investire in una stima accurata piuttosto che espandere l'albero. Il solito discorso del ragionamento sul livello o sul metalivello (pag11r nozione 6)

Versione del minmax depth first con stima del valore

Sia n la configurazione iniziale del gioco da cui parte la valutazione.
1. L={n} //insieme dei nodi non espansi
2. x=first(L). Se x=n and x è etichettato : return x and stop.
3. Se x ha un'etichetta v(x), sia p il genitore di x con etichetta corrente v(p) . 
   Se p appartiene a Min allora -> update v(p) = min (v(p), v(x) )
   Se p appartiene a Max allora -> update v(p) = max (v(p), v(x) )
   update L = L-{x}
   goto 2
4. Se x non ha etichetta ed è un nodo foglia oppure è un nodo che non espanderemo poichè abbastanza profondo, 
   assegna ad x il valore e(x) [nota. e(x) è esattamente il valore reale nel caso che x sia effettivamente una foglia],
   lascialo in L, goto 2.
5. Se x non ha etichetta e non è una foglia, poni v(x) = -inf se x appartiene a Max, 
   altrimenti v(x) = +inf se x appartiene a Min.
   Insert figli(x) in cima ad L.
   goto 2.

Come decidiamo quando fermare l'espansione dell'albero nel minmax con stima?

Possiamo basarci sulla profondità dei nodi (cioè stabiliamo un limite di profondità massimo da esplorare rispetto alla configurazione corrente), o sul tempo da spendere nella ricerca. Di solito questo non va bene, ci sono delle zone dove e(x) cambia molto da padre in figlio. Le mosse p->x dove il valore di e(x) è abbastanza diverso rispetto ad e(p) sono dette mosse tattiche. Invece quando e(x) cambia poco rispetto a e(p) le mosse sono dette quiete (o il nodo x è detto quieto). Dunque, se esploriamo rami con una lunga sequenza di mosse quiete, possiamo fermarci poichè possiamo assumere che con quelle mosse il gioco rimane stabile. Invece è meglio esplorare più a fondo i rami con mosse tattiche finchè non si trovano sequenze di mosse quiete per capire come evolve il gioco seguendo quelle mosse quiete.
Oppure ancora troviamo una mossa che dà un drastico vantaggio all'avversario (sempre secondo l'euristica che stiamo usando), dunque non conviene spender tempo su altri rami perchè l'avversario farà quella mossa e dobbiamo vedere se abbiamo la possibilità di controbatterla espandendo il sottoalbero che deriva da quella mossa.
Questa espansione è detta espansione singolare.

Un problema è comparare mosse analizzate a livelli differenti (magari perchè abbiamo esplorato un ramo pieno di mosse tattiche piuttosto che un altro con mosse tattiche ma meno tattiche dell'altro ramo), poichè più è profondo il livello più la valutazione è precisa quindi la mossa a livello di profondità inferiore (sul ramo esplorato meno) è solo una stima meno accurata rispetto alla mossa a livello di profondità maggiore, quindi compararle non è immediato.

Iterative deepening per esplorare lo spazio di ricerca con limite di tempo

Una possibile implementazione per esplorare l'albero di ricerca è quella di sfruttare l'iterative deepening. Partendo da una data profondità ci si spinge sempre più in basso (usando techine di pruning o meno) finchè non scade il tempo. L'idea è quella che la profondità di partenza rientra sicuramente nel tempo a disposizione mentre le profondità successive non sono certe. Quando il tempo scde si ritorna la mossa migliore esplorata fino a quel momento sull'ultima iterazione completata.
Siccome l'albero di ricerca cresce in modo esponenziale gran parte del tempo lo spenderemo sempre sull'ultima iterazione. Infatti date delle iterazioni, quella di partenza a profondità i ed quella finale a profondità i+k con un branching factor medio all'incirca identico B per ogni terazione e dogni iterazione aumenta la profondità di 1, si avrà che nell'iterazione finale si visiteranno $O \left ( \frac{B^{i+k+1}-1}{B-1} \right ) = O \left ( B^{i+k} \right )$ mentre nelle altre iterazioni avremo (per lo stesso ragionamento): $\sum_{j=0}^{k-1} O \left ( B^{i+j} \right ) = O \left ( B^{k-1} \right )$ perchè è una somma di valori ed asintoticamente conta quello con esponente maggiore che ha un esponente comunque minore dell'ultima iterazione.
Inoltre potremmo migliorare la ricerca con l'uso di cache in caso di raggiungimento di uguali stati di gioco in diversi rami (cosa che vedremo in futuro).

Espansione singolare

d10.jpg

E' chiaro che Min sceglierà e, quindi si espande il sottoalbero che ha radice e tralasciando gli altri sottoalberi. Probabilisticamente (come scelte) è come se sotto w ci fosse solo e.

Effetto orizzonte dato dall'espansione singolare

Supponiamo di espandere i nodi fino al settimo livello di profondità, e troviamo una mossa molto vantaggiosa per l'avversario. Dunque espandiamo fino al nono livello per trovare una contromossa e la troviamo. Chi ci assicura che la nostra contromossa porti ad una sconfitta totale entro la 12esima mossa? Sostanzialmente noi siamo limitati nella stima perchè non riusciamo a valutare tutte le mosse possibili, ovvero vediamo fino "all'orizzonte".

Strategie per limitare l'effetto orizzonte

Si può considerare l'espansione in profondità (espansione singolare) non solo della migliore combinazione di mosse, ma anche della seconda migliore combinazione di mosse, per vedere in quale dei due path è possibile evitare mosse estremamente vantaggiose per l'avversario.

Un'altra alternativa è quella di cambiare strategia quando sono in netto svantaggio cambiando la funzione di valutazione euristica (ad esempio la funzione di valutazione base cerca di non essere troppo difensiva, mentre la nuova funzione euristica vede meglio posizioni molto difensive in gioco).

Ovviamente queste strategie si applicano poichè non possiamo permetterci, in tempi ragionevoli (o con uso ragionevole di risorse), l'espansione di tutto l'albero di ricerca. Altrimenti con tutto l'albero espanso potremmo dire certamente "vinco/perdo/pareggio".

Alpha beta pruning sul minmax

Varie tecniche che servono per risparmiare risorse di calcolo evitando la valutazione di nodi (o meglio rami) dello spazio di ricerca trascurabili, in quanto non così utili nella giocata, rispetto ad altri.

d11.jpg

Conviene espandere il nodo e? No poichè Min sceglierà la configurazione d. Dunque non conviene proprio portare il gioco in configurazione c e bisogna provare a trovare una soluzione migliore espandendo b. Quindi purge(e) Nota: comunque c è necessario espanderlo altrimenti non si trova d ed il ragionamento cade.

d12.jpg

Qui abbiamo valori stimati di alcune configurazioni di gioco. Possiamo evitare di espandere g? Si. Perchè in d la mossa migliore mi dà un -0.05 e quindi Min in c ha due possibilità: scegliere d o scegliere g nel caso in cui questo abbia ha un valore ancora più negativo di d. Ma siccome a noi interessa il vantaggio del massimizzatore, vuol dire che sceglieremo b e quindi espandere g è inutile, purge(g).
Come prima è comunque necessario aver espanso un certo numero di nodi per dire quali nodi conviene espandere e quali no.

d13.jpg

Ancora ci chiediamo se convenga espandere g.
Come prima, quale sia il valore di b il valore di e non potrà ssere maggiore di -0.1. Qual è il valore (stimato, ricordiamo che stiam stimando) in d? Non lo sappiamo con certezza ma se h avesse un valore minore di e si sceglierebbe quest'ultimo per limitare la stima a solo -0.1. Allo stesso modo vale per c, se i avesse un valore superiore a d min sceglierebbe d. Tutto questo per dire che anche se si scegliesse i o h il valore di e è definito come negativo minore o uguale di -0.1 e ciò ci basta per la valutazione, in quanto cerchiamo valori positivi poichè deve muovere Max. Dunque purge(g).

Algoritmo che modella il ragionamento appena esposto (cioè il pruning)

Sia n un nodo da cui muove Max.
1. Prendiamo s fratello di n con valore v(s) [nell'esempio f fratello di g]
2. Consideriamo il path dalla radice dell'albero di ricerca al nodo n (quindi n non è la radice!!), ovvero (root, ... , n).
   In questo path i nodi in posizione dispari (considerando che la root è in posizione 0) sono i nodi di Min.
3. Se un nodo di Min nel path ha un fratello n' tale che v(n')>v(s) [nell'esempio v(b)>v(f)], allora prune(n)

d23

Questo perchè siccome Max deve assicurarsi il valore maggiore, se trova un valore migliore di v(s) (in questo caso v(n') ) allora cercherà di muoversi verso n' e può farlo perchè n' è raggiungibile da un nodo dello stesso ramo che arriva ad s, ma precedente ad s come livello, ed è un nodo che viene dopo una mossa che deve fare Max. Questo sulla base del fatto che se i fratelli di s sono a valore maggiore, comunque Min non li sceglierà e sceglierà s che è il nodo a valore minore. L'altro caso è che i nodi fratelli di s siano a valore minore di s, comunque per Max la scelta di Min gli assicurerà un valore minore o uguale di s. Quindi lui evita questa conseguenza scegliendo prima un'altra mossa che lo porta ad n' che ha un valore più buono.

Dubbio Solved?: nel passo 1 il fratello di n deve essere un nodo allo stesso livello di n o, come pare più logico, deve essere un nodo allo stesso livello di n ma che condivide il genitore con n? Perchè nell'esempio abbiamo prunato g fratello di e.
Ovviamente bisogna far attenzione al testo. In un albero un nodo fratello è in generale un nodo allo stesso livello del nodo dato. In altri casi potrebbe essere un nodo allo stesso livello del nodo dato ma con lo stesso genitore. Credo che questo caso intenda proprio nodi fratelli con lo stesso genitore.

Alpha beta search

Un algoritmo min max con Alpha beta search.

Dato un nodo n
1. lista di nodi L={n}
2. sia x=first(L). Se x=n ed x ha un valore, return x, path(x)
3. se x ha un valore v(x), indichiamo con p il genitore di x. Altrimenti se x non ha valore goto 5.
   //Determiniamo ora se è può essere tagliato/pruned se non siamo saltati al passo 5
   Se p è di Min, sia 
   alpha=max(valori dei nodi allo stesso livello di p, valori dei soli nodi antenati di p che appartengono a Min) 
   OR
   alpha = -inf 
   se non c'è un valore per nessuno di questi nodi.
   Se v(x)<= alpha , prune(p) //eliminiamo p ed i suoi discendenti dalla lista L.
   [1]
   Se invece p è di Max facciamo l'operazione duale considerando 
   beta=min(valori dei nodi allo stesso livello di p, valori dei soli nodi antenati di p che appartengono a Max) 
   OR 
   beta = +inf se
   non ci sono valori per i nodi prima citati.
   Se v(x)>= beta , prune(p).
   //vedi [1] ma duale.
4. Se p non è stato tagliato sia v(p) il suo valore. Se p è di Min, allora v(p)= min{v(x), v(p) } ; 
   se p è di Max allora v(p)= max{v(x), v(p) }. Rimuoviamo x da L e goto 2.
5. Se x non ha un valore ed è una foglia oppure non è ulteriormente espandibile (abbiamo raggiunto il limite di profondità
   o di tempo) assegna ad x il valore stimato e(x) (che è pari a quello reale se x è una foglia) e goto2.
   Se x è un nodo espandibile, assegniamo e(x)= -inf se x è di Max altrimenti e(x) = +inf se x è di Min, 
   aggiungiamo tutti i figli di x ad L in cima e goto 2.

[1] Se il valore di x è minore del valore che Min può ottenere nei nodi precedenti a p in nodi allo stesso livello di p (ricordiamo che il valore di un nodo è assegnato in salita dal minMax quindi non ha senso pensare di trovare qualcosa di meglio in avanti perchè è stato già valutato), cioè x <= alpha, allora per Max è svantaggioso arrivare a p perchè Min potrebbe scegliere uno stato che aumenta il suo vantaggio scegliendo x o ecventuali nodi figli di p con valore ancora più piccolo di x. Max, come segnalato da alpha, può indirizzare il gioco su stati dove Min si deve accontentare di valori superiori ad x e dunque espandere ulteriormente il sottoalbero sotto p è inutile per Min (o per chi sta simulando la giocata di Min). Quindi prune(p).

d24

Dall'algoritmo appena esposto si evince che:

  • alpha è il valore che Max si può garantire spostando il gioco sull'opportuno nodo da cui poi min deve muovere. (ovvero è il valore più alto ottenibile da un nodo di Min che si può raggiungere senza che Min possa evitarlo)
  • beta, vicerversa, è la versione di alpha per Min.

Complessità: nel caso peggiore non si migliora niente (dobbiamo espandere comunque tutti i nodi dell'albero senza poter evitare il prune), cioè
ho $O \left ( B^{D} \right )$ nodi da espandere (in realtà avrei D+1 come esponente vedi pag15r, ma diciamo che l'aggiunta di un valore costante non cambia molto il concetto). Nel caso ideale (cioè che dove posso fare un prune lo faccio) lo spazio di ricerca si riduce a $O \left ( 2 \cdot B^{\frac{D}{2}} \right )$ cioè è come se avessi un in ${B}'=\sqrt{B}$ ovvero a parità di tempo raddoppio lo spazio di ricerca utile espanso.
Nota: i giochi su scacchiera in generale sono PSPACE complete se la scacchiera fosse di dimensioni variabili e non fisse.

Versione più specifica:

Stato s, vedi primi pezzi di codice sul minmax.
 
int AB(Stato s){
  if (s.turnoMax()){
    return maxValueAB(s, -inf, +inf);
      //i valori -inf e +inf sono i valori iniziali di alpha e beta nel caso in cui
      //non ci sia nessun valore di riferimento
  }
  else {
    return maxValueAB(s, -inf, +inf);
  }
}
 
int maxvalueAB(Stato s, int alpha, int beta){
  if (s.nodoFoglia()){
    return s.valore();
  }
  int v = -inf;
  mossa mosse[] = s.mosseLegali();
  for (int i=0; i<mosse.length; i++){
    s.effettuaMossa(mosse[i]);
    v = max (v, minValueAB(s, alpha, beta) );
    s.undoMossa();
    if (v >= beta){
      //andrebbe troppo bene a Max, Min non glielo permetterebbe
      //quindi tagliamo il sottoalbero rispetto a questo stato
      return v;
        //si evita di valutare ulteriori figli
        //[1]
    }
    alpha = max (alpha, v);
      //se Max può garantirsi qualcosa di meglio di alpha, è meglio tenerlo in conto
  }
  return v;
}
 
int minValueAB(Stato s, int alpha, int beta){
  if (s.nodoFoglia()){
    return s.valore();
  }
  int v = +inf;
  mossa mosse[] = s.mosseLegali();
  for (int i=0; i<mosse.length; i++){
    s.effettuaMossa(mosse[i]);
    v = min (v, maxValueAB(s, alpha, beta) );
    s.undoMossa();
    if (v <= alpha){
      return v;
        //andrebbe troppo bene a Min, Max non glielo permetterebbe
    }
    beta = min (beta, v);
  }
  return v;
}

[1]: si osserva che in caso di pruning il valore v è una stima del valore che si sarebbe potuto ottenere da quello stato, siccome è uno stato di Max si poteva anche andare oltre v (discorso più che valido quando c'è di mezzo l'euristica). Analogamente per Min si ha che v sarebbe potuto essere ancora minore come valore.

Problematiche

Si vede che l'apha-beta pruning aiuta molto ad evitare di valutare rami "inutili" solo se i figli di un nodo sono valutati in ordine di importanza. Cioè se i figli di un nodo di Max sono valutati in ordine di utilità per max, dal più primettente al meno promettente, così se quello più promettente lo è troppo viene tagliato l'intero sottoalbero, che altrimenti verrebbe valutato.
Ad esempio:

Beta = 4

Valore di figli del nodo corrente
{1,2,3,4,5}
Se riesco ad ordinarli in qualche modo e quindi faccio la ricerca espandendo in questa sequenza:
{5,4,3,2,1}
So già che il primo figlio rende questo nodo troppo promettente (max sceglierebbe il figlio con valore 5) 
e dunque lo taglio

Se invece espandessi i figli nell'ordine iniziale mi accorgerei di 5 troppo tardi (dopo aver valutato tutti gli altri)
quindi il taglio sarebbe inutile.

Forward pruning

E' un pruning che consiste in tagli in avanti ed è combinabile con le altre strategie viste (depth first ed alpha-beta pruning).
Si basa sul fatto che l'efficienza del pruning alpha-beta aumenta se i figli sono esplorati in ordine di importanza per chi deve muovere in un dato nodo. In questo modo verranno valutate prima le mosse che non si devono tagliare e poi la prima mossa che si taglia indicherà che anche le mosse rimanenti possono essere tagliate.
La funzione di ordinamento deve essere veloce e deve dare una buona stima, e normalmente è meno complessa della funzione euristica che valuta un dato stato. Questo perchè se fosse una funzione più complessa della funzione euristica stessa converrebbe esplorare direttamente i nodi visto che computazionalmente ci costerebbe allo stesso modo. Ancora, se fosse una funzione di ordinamento esatta allora troveremmo subito il path migliore, ma basta sostituirla alla funzione euristica per rendere inutile l'ordinamento in quanto si troverebbe comunque il path migliore.

Ora, oltre all'ordinamento, il forward pruning sostanzialmente dice "date le mosse ordinate, dalla i-esima in poi non considerarle proprio", quindi si assume che la funzione di ordinamento sia abbastanza buona da non lasciare, nell'insieme delle mosse che verranno tagliate in ogni nodo, mosse buone.

Algoritmo MinMax visto da un unico punto di vista, NegaMax

Invece di avere due giocatori, uno Min e l'altro Max, uno che minimizza il valore di utilità e l'altro che massimizza, entrambi massimizzano. Questo concetto è applicabile a giochi a somma zero ovvero a giochi dove se uno vince l'altro perde o al limite si pareggia, non è possibile che entrambi vincano ed entrambi perdano. Questo significa che nell'intervallo di valori prima utilizzato ( ovvero [-1,1]) ogni giocatore tende a portare la somma dei valori dal punto di vista dei due giocatori a 0, ma vediamo meglio come.
Sia f(x) la funzione di valutazione di Bianco e g(x) la funzione di valutazione di Nero. Se Bianco è in vantaggio f(x) sarà positiva verso 1 e sarà negativa verso -1, stessa cosa per Nero, ovvero se nero è in vantaggio g(x) tende ad 1 altrimenti a -1.
Si vede che in ogni caso la somma f(x)+g(x) applicata ad un dato istante del gioco sarà 0 posto di analizzare lo stato del gioco con "gli stessi occhi" cioè con la stessa funzione di valutazione sia per Bianco che per Nero, soltanto che questa funzione tiene conto per chi sta valutando (altrimenti per uno potremmo stare a +0.22 e per l'altro a -0.40 ed i conti non tornano), cioè se valuto uno stato dove il Bianco è in vantaggio assegno un valore al gioco e poi fisso il segno + per il Bianco ed il segno - per il nero. I casi banali sono:

  • Vince il Bianco: f(x) = 1 e g(x)=-1 .
  • Vince il Nero: f(x) = -1 e g(x)=1 .
  • Pareggio: f(x) = 0 e g(x)=0 .

Quindi f(x)+g(x)=0 per ogni configurazione di gioco.
Visto che ogni stato del gioco è valutato con la stessa funzione di valutazione (che poi assegna opportunamente i segni + e -), si osserva in sostanza che f(x)=-g(x) da cui g(x)=-f(x) . Quindi il bianco gioca per massimizzare f(x), il nero giocherebbe per massimizzare g(x). Visto che g(x) è opposta ad f(x) (vedi disegno successivo che vuole dare un'idea non è preciso al 100%), si ha che $max \ g(x) = max -f(x)$ ma il massimo di una funzione ribaltata rispetto all'asse delle ascisse è il minimo della funzione originale cambiato di segno, quindi $max -f(x) = - min \ f(x) \rightarrow min \ f(x) = - max -f(x) = - max \ g(x)$. Quindi se chi giocava come Mr Max cercava $max \ f(x)$ continuerà ad usare questo approccio, invece mr Min cercava $min \ f(x)$ ed invece massimizzerà sempre usando $- max -f(x)$. (Questa frase, per quanto sia costruita con deduzioni corrette, non lega benissimo con l'idea dell'algoritmo che invece usa la più semplice idea delle funzioni opposte. Quindi è trascurabile in caso generi confusione)

d25

Dunque invece di massimizzare per un giocatore e minimizzare per un altro con due funzioni identiche nella forma ma opposte (vedi disegno), ne usiamo solo una ed il valore rispetto all'avversario che muove sarà sempre opposto per i ragionamenti precedenti.

Implementazione del Negamax con iterative deepening

int negamax(Stato s, int depth){
  if (depth <= 0 || s.nodoTerminale()){
      //siamo in un nodo terminale oppure abbiamo consumato tutta la profondità che potevamo esaminare
    return s.valore();
      //s.valore sarà la stima esatta se siamo nel nodo terminale, altrimenti è una stima della bontà della
      //config attuale secondo il giocatore che in questa chiamata ha il turno.
      //Quindi se per questo giocatore la stima è buona, per il giocatore che ha fatto la mossa precedente
      //(cioè l'avversario), la stima è cattiva (perchè la visione è opposta) e viceversa in caso la stima
      //per questo giocatore non sia granchè.
  }
  int best 0 - inf; 
    //abbiam detto che usiamo solo la massimizzazione (si veda nel for man mano che si trovano
    //valori migliori si salvano al posto di best), quindi il valore peggiore è - inf
    //(equivalente a -1 nei ragionamenti atti in precedenza)
  mossa mosse[] = s.mosseLegali();
  for (int i =0; i<mosse.length; i++){
    s.applicaMossa(mosse[i]);
    int val = -negaMax(s, depth -1 );
      //Siccome il gioco dell'avversario è opposto a quello del giocatore corrente (ragionamenti precedenti)
      //Se sta perdendo (valore negativo assegnato dall'euristica) io sto vincendo (cambio segno)
      //o viceversa.
    s. undoMossa();
    if (val> best){
      //se abbiamo trovato una mossa migliore tra quelle legali a partire da questo stato
      //quindi massimizziamo.
      best = val;
    }
  }
  return best;
}

Negamax con iterative deepening ed alpha beta pruning

Stavolta alpha e beta hanno un significato leggermente diverso rispetto a quello visto in precedenza.

  • alpha: valore che il giocatore che sta valutando le mosse è in grado di garantirsi in mosse precedentemente valutate.
  • beta: valore che l'avversario, del giocatore che sta valutando, riesce a garantirsi in mosse precedentemente valutate.

Ovviamente all'inizio si parte con dei dati valori di alpha e beta, in generale, visto che entrambi i giocatori massimizzano, si parte con entrambi i valori pari a meno infinito (o meno -1 nel solito intervallo di valori limitato).

int negamaxAB(Stato s, int a, int b, int depth){
  if (depth <= 0 || s.nodoTerminale()){
    return s.valore();
  }
  int best 0 - inf; 
  mossa mosse[] = s.mosseLegali();
  for (int i =0; i<mosse.length; i++){
    s.applicaMossa(mosse[i]);
    int val = -negaMaxAB(s, -b, -a, depth -1 );
      //Siccome il gioco dell'avversario è opposto a quello del giocatore corrente (ragionamenti precedenti)
      //Se sta perdendo (valore negativo assegnato dall'euristica) io sto vincendo (cambio segno)
      //o viceversa.
      //per quanto riguarda -b e -a la spiegazione è la seguente. L'avversario vede con gli occhi
      //"opposti" al giocatore corrente e sappiamo che il b attuale è quanto può garantirsi (quindi deve essere
      //passato come a), soltanto che per la sua valutazione il valore deve essere opposto a quello che abbiamo usato noi.
      //Stessa cosa per a che è quanto si può garantire questio giocatore (quindi è beta per
      //l'avversario, soltanto che visto con la valutazione opposta).
    s. undoMossa();
    if (val>= b){
      //Il valore ottenuto supera quello che può garantirsi l'avversario.
      //Cioè l'avversario può garantirsi, con i suoi occhi (quindi nel suo turno a=+5), +5.
      //Il giocatore corrente al più può arrivare a -4 (secondo i suoi occhi) perchè uno stato
      //migliore di -4 (-4 significa svantaggio) non sarebbe ottenibile perchè l'avversario sceglierebbe
      //un'altra mossa. Perchè -4 e non positivo? Perchè il gioco è a somma zero
      //quindi se lui può garantirsi un vantaggio il giocatore attuale meglio di un certo svantaggio non può fare.
      return val;
        //potremmo, forse, fare di più ma l'avversario ce lo impedirebbe quindi ritorniamo
        //un valore che rappresenta un'approssimazione superiore. 
    }
    if (val> best){
      //se abbiamo trovato una mossa migliore tra quelle legali a partire da questo stato
      best = val;
    }
    if (val > a){
      //abbiamo trovato una mossa che è migliore di tutte quelle precedenti che possiamo raggiungere
      //(senza che l'avversario ce lo impedisca)
      a = val;
    }
  }
  return best;
}

L'algoritmo migliora di efficienza se, come abbiam scritto per l'alpha beta base, si ordinano i figli per importanza.

Ricerca con negamax alpha beta e finestra limitata

Partendo con i valori base, ovvero alpha = beta = -inf si permette di cercare tutte le possibilità, perchè chi valuta di volta in volta può sicuramente migliorare questi valori. Man mano che i valori migliorano si genera una finestra delle possibilità ristretta tra alpha e beta, ovvero un giocatore tende a migliorare alpha ma non potrà mai superare il valore beta, quindi taglia sempre più possibilità (le possibilità sotto alpha non sono interessanti ma sono interessanti solo quelle tra alpha e beta).
Ovviamente ciò implica che se i valori di alpha e beta di partenza fossero vicini, allora l'algoritmo, sin da subito, taglierebbe molte possibilità.

Se l'esecuzione dell'algoritmo, rispetto al giocatore che sta muovendo, fornisce un valore minore di alpha, vuol dire che abbiamo un upper bound di un valore che in realtà potrebbe essere ancora più piccolo. Perchè potrebbe essere più piccolo? Perchè noi approssimiamo con alpha tutti i valori minori di alpha, ovvero non ci interessano valori minori se possiamo garantirci un valore maggiore (alpha, appunto). In realtà, con l'algoritmo prima visto, grazie a 'best' riusciamo a ritornare l'esatto valore (a distanza di una chiamata, cioè ritorniamo l'esatto valore dal chiamato al chiamante, altrimenti la frase non è più vera) nel caso non si raggiunga un valore superiore a beta. Cioè tutto ciò che è stoto beta viene tornato senza apporssimazioni. Questo perchè l'algortmo con best è detto fail-softAB, mentre l'algoritmo non fail soft approssima tutto con gli estremi alpha e beta.
Stessa cosa si ha per beta. Ovvero, nell'algoritmo non fail-soft, un valore superiore a beta sarebbe approssimato con beta, nell'algoritmo fail soft viene ritornato esattamente ma, a differenza dei valori inferiori ad alfa, stavolta questo valore genera un taglio quindi non si sa se potrebbero esistere mosse ancora migliori del valore ritornato.

Principal variation search

Detto anche minimal window search o negascout.

L'idea dell'algoritmo è la seguente: basandoci sul negamaxAB e sui ragionamenti esposti sulla finestra limitata , nel caso in cui abbiamo una buona fuznione di ordinamento dei figli possiamo ipotizzare di individuare velocemente il path migliore. Infatti si valuterà prima il figlio con ordine di importanza maggiore, poi il figlio di questo allo stesso modo e così via. Ovvero è come se per prima cosa esplorassi il path migliore. Il punto è che quasi mai abbiamo una perfetta funzione di ordinamento, quindi potremmo ottenere un path buono ma non ottimo, come ci muoviamo sui rimanenti rami?
Sui rimanenti rami, a differenza di quanto abbiamo fatto per il primo ramo esplorato (il path che assumiamo sia buono), utilizziamo una finestra limitata per la ricerca (costruita sulla base delle informazioni ottenute sul path buono). In questo modo sui rimanenti rami taglieremo molto e solo nel caso in cui esista un path ancora migliore ma ammissibile (ovvero il valore è $\alpha < val < \beta$) allora si cambia il path migliore. In questo modo ci assicuriamo una esecuzione più veloce nell'albero di ricerca, cosa che ci permette di trovare una funzione di ordinamento migliore che necessariamente costerà di più del solito.

int pvs(Stato s, int a, int b, int depth){
  if (depth < 0 || s.nodoFoglia() ){
    return s.valore();
  }
  mossa mosse[] = s.mosseLegali();
  ordina(mosse);
    //la funzione di ordinamento di solito è una sottospecializzazione della funzione euristica
  s.effettuaMossa(mosse[0]);
    //supponiamo che ordina mosse funzioni proprio bene quindi il primo figlio è sempre il migliore
  int best = -pvs(s, -b, -a, depth -1);
    //valutiamo il "ramo migliore"
  s.undoMossa();
  if (best >=  b){
    //mossa troppo buona, l'avversario ci fermerà prima
    return best;
  }
  if (best > a){
    //miglioriamo ciò che possiamo garantirci
    a = best;
  }
  for (int i=1; i<mosse.length; i++){
    //vediamo le altre mosse che dicono
    s.effettuaMossa(mosse[i] );
    int val = -pvs(s, -(a+1), -a, depth -1);
      //esploriamo la parte rimanente dell'albero con una finestra ristrettissima, ammette giusto un valore
      //(perchè usiamo interi) superiore ad alpha
    if (val > a && val < b){
      //se il valore tornato dall'esecuzione precedente supera a
      //(di uno o più punti, perchè ricordiamo che questo algoritmo grazie a best non approssima
      //(il valore con l'estremo superiore della finestra)
      //ma non è troppo buono (cioè è < di b) in modo tale che l'avversario ci bloccherebbe
      //allora esplora meglio quel path dando più possibilità
      val = -pvs(s, -(a+1), -val, depth -1);
        //passo -val al posto di a, poichè val sarà il nuovo a di sicuro
 
      //nel caso in cui val sia minore di alpha a noi non ci interessa
      //esplorare meglio la mossa perchè possiamo garantirci già di meglio.  
    }
    s.undoMossa();
    if (val>= b){
      return val;
    }
    if (val> best){
      best = val;
    }
    if (val > a){
      a = val;
    }
  }
  return best;
}

A fronte di un vantaggio molto alto (tagliare molti rami grazie all'ordinamento) l'unico svantaggio è che se ordiniamo male dobbiamo valutare molte volte gli stessi sottoalberi con finestre di valori diverse.

PVS simulato su iterazioni diverse dell'iterative deepening

Come abbiamo detto l'iterative deepening consuma la maggior parte del tempo sull'ultima iterazione ma comunque consuma buona parte del tempo (circa la metà) sulle itererazioni precedenti. Quindi l'idea è di massimizzare l'utilità delle iterazioni precedenti facendoci suggerire un path iniziale migliore. In questo modo possiamo simulare una sorta d pvs.

int pvs(Stato s, int a, int b, int depth, path l){
  if (depth < 0 || s.nodoFoglia() ){
    return s.valore();
      //in un nodo foglia non ha senso modificare il path perchè
      //lo stato non ha conseguenze
  }
  path newL = new path();
  mossa mosse[] = s.mosseLegali();
  for (int i=0; i<mosse.length; i++){
    s.effettuaMossa(mosse[i] );
    int val = -pvs(s, -b, -a, depth -1), newL;
    s.unodMossa();
    if (val>= b){
      return val;
    }
    if (val> best){
      best = val;
    }
    if (val > a){
      //è la mossa (path) migliore al momento
      a = val;
      l.empty(); //svuotiamo il path
      l.addhead(mosse[i]);
      l.addTail(newL);
        //si può osservare che il path che si ritorna grazie al riferimento
        //(perchè il chiamante del metodo ottiene il risultato in newL)
        //sarà formato dal path mossaMiglioreAttuale, mosseSuccessiveMigliori
        //dove mosse successive migliori sono le mosse scoperte nelle chiamate successive
        //che costruiscono di volta in volta il path
    }
  }
  return best;
}

In questo modo alla prima iterazione otteniamo il path migliore della prima iterazione e su questo restringiamo la finestra alpha-beta.

Psv simulato come predizione.

Similmente a quanto visto prima, se memorizziamo il path osservato e magari continuiamo a svilupparlo mentre l'avversario pensa, abbiamo un path migliore di riferimento. Se l'avversario esegue, effettiamente, una mossa prevista dal path che si ritiene migliore, allora questo stesso path può servire da punto di partenza per il nuovo iterative deepening fornendo una finestra alpha-beta.
Se invece l'avversario fa una mossa non prevista bisogna ricominciare da capo.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License