Nella scorsa puntata della serie sulla simulazione abbiamo preso in esame la differenza tra gioco ingiusto e gioco a somma zero, presentando un esempio elementare di codice che ne mostrasse le caratteristiche quando eseguito su di un computer. Abbiamo notato come un computer, quando programmato correttamente, può presentare un comportamento apparentemente intelligente, assimilabile a quello di un essere umano. Infine è stata descritta una struttura dati classica per lo sviluppo di algoritmi decisionali: occorre un sistema di archiviazione in grado di “ricordare” o “calcolare” lo stato delle mosse nel tempo, ed un meccanismo probabilistico, in genere basato su etichette con pesi differenti da applicare alle decisioni.

Oggi approfondiremo ulteriormente questi concetti, prendendo in esame la strategia alla base della maggior parte delle simulazioni effettuate in Teoria dei Giochi.

La strategia Minimax

Innanzi tutto occorre contestualizzare l’argomento.

L’analisi si applica a giochi deterministici (vale a dire giochi di pura abilità in cui il caso non gioca alcun ruolo). Considereremo solo giochi:

• a due giocatori, nei quali cioè si affrontano solo due contendenti, indicaticon0 e 1;
• a mosse alternate, nei quali cioè i giocatori muovono a turno, alternandosi (se una certa mossa spetta al giocatore x, la mossa successiva spetta al giocatore 1-x)

In qualunque gioco, si può definire il concetto di stato: per esempio, nel caso degli scacchi lo stato è rappresentato dalla disposizione dei pezzi sulla scacchiera. Una configurazione di gioco è data dallo stato in cui il gioco si trova e dal giocatore cui tocca muovere (detto il “giocatore di turno”).

Il minimax è un metodo per minimizzare la massima (minimax) perdita possibile; in alternativa, per massimizzare il minimo guadagno (maximin). Fu scoperto nella teoria dei giochi in caso di gioco a somma zero con due giocatori, sia nel caso di mosse alternative (turni) sia di mosse simultanee, venendo successivamente esteso a giochi più complessi e al supporto decisionale in presenza di incertezza.

Una versione semplice dell’algoritmo si può vedere in giochi come il tris, dove è possibile vincere, perdere o pareggiare.

• Se il giocatore A può vincere con una sola mossa, la mossa migliore è quella vincente.
• Se il giocatore B sa che una data mossa porterà A a poter vincere con la sua prossima mossa, mentre un’altra lo porterà a pareggiare, la migliore mossa del giocatore B è quella che lo porterà alla patta.

Verso la fine del gioco è facile capire quali sono le mosse migliori; l’algoritmo minimax trova la mossa migliore in un dato momento cercandola a partire dalla fine del gioco e risalendo verso la situazione corrente. Ad ogni passo l’algoritmo assume che il giocatore A cerchi di massimizzare le sue probabilità di vincere, mentre B cerchi di minimizzare le probabilità di vittoria di A, per esempio massimizzando le proprie chance di vittoria.

Come funziona il minimax

L’algoritmo analizza ricorsivamente l’albero a partire dagli ultimi nodi terminali ( foglie ), risalendo i vari percorsi di gioco ( rami ).
Esempio pratico
In una situazione di gioco partecipano due giocatori:

• Mini. E’ il giocatore che deve minimizzare il valore di gioco.
• Max. E’ il giocatore che deve massimizzare il valore di gioco.

I due giocatori hanno obiettivi opposti. Si tratta, pertanto, di un gioco a somma zero (non cooperativo) e sequenziale.

Algoritmo minimax

L’algoritmo minimax è un algoritmo ricorsivo per la ricerca della mossa migliore in un gioco a somma zero che si svolge tra due giocatori. L’algoritmo minimax è utilizzato nella teoria delle decisioni quando i giocatori si trovano in interazione strategica. L’interazione strategica è la situazione che si verifica quando due o più agenti decisionali (giocatori) sono influenzati dall’esito delle proprie scelte e da quelle degli altri agenti. In tali circostanze gli agenti devono formulare una strategia al fine di effettuare le scelte migliori per massimizzare la propria utilità (payoff) tenendo anche conto delle strategie adottate dagli altri agenti che partecipano al medesimo gioco.

L’algoritmo minimax consente di individuare le scelte migliori dei due giocatori nel corso del gioco, analizzando a ritroso l’albero di gioco a partire dai nodi terminali, ossia dalle possibili situazioni in cui può terminare il gioco (fine gioco), e risalendo progressivamente fino alla posizione corrente dei giocatori. Ad esempio nel seguente albero di gioco è rappresentato un gioco sequenziale tra due giocatori, il primo giocatore (MAX) deve massimizzare il valore del gioco mentre il secondo giocatore deve minimizzarlo.

Supponiamo di avere un gioco in cui i due giocatori hanno solo due mosse possibili ciascuno ogni turno. L’algoritmo genera l’albero di gioco, dove i cerchi rappresentano le mosse del giocatore che usa l’algoritmo (giocatore massimizzante) e i quadrati sono le mosse dell’avversario (giocatore minimizzante). Per le limitazioni del sistema di calcolo, limitiamo l’albero a una profondità di quattro turni.

Quale valore venga realmente assegnato dipende da come vengono valutate le posizioni finali di vittoria e di sconfitta: un metodo è assegnare 1 alle mosse che portano alla vittoria finale e -1 a quelle di sconfitta (il che porta a sviluppare la teoria combinatoria dei giochi formulata da John Conway), un altro è di adottare i valori infinito positivo e negativo. Il valore per il giocatore A di ogni mossa non immediatamente vincente è poi il valore minimo di tutte le possibili contromosse di B. Per questo A viene anche detto “giocatore massimizzante” e B “giocatore minimizzante”.

Questo presuppone che sia possibile per chi computa (non parliamo ancora di applicazioni al calcolatore) valutare tutto l’albero delle mosse possibili del gioco; in realtà questo si può fare solo per giochi molto semplici, mentre per altri, come gli scacchi o il go questo non è possibile o lo è solo nelle fasi finali, e in generale si può solo calcolare una stima della probabilità che una data mossa porti alla vittoria di uno dei giocatori.

Il calcolo di questa stima può essere migliorato se è possibile fornire una funzione di valutazione euristica che valuti le posizioni non terminali del gioco senza dover conoscere tutte le mosse successive: in questo caso si possono considerare solo un certo numero di mosse future. Questo numero è detto “profondità” dell’algoritmo ed è misurato in mosse:

L’algoritmo valuta ogni nodo foglia con una funzione di valutazione euristica e ottiene i valori mostrati. Le mosse che fanno vincere il giocatore massimizzante hanno un valore infinito positivo, mentre le mosse che danno la vittoria al giocatore minimizzante hanno un valore infinito negativo. Al terzo livello l’algoritmo sceglierà, per ogni nodo, il nodo figlio con il valore minore ed assegnerà tale valore al nodo in esame; per esempio il nodo a sinistra assumerà il valore minimo fra “10” e “+∞”, cioè “10”. Il prossimo passo, al livello 2, sceglie il massimo valore fra tutti i nodi figli (i nodi del livello 3) e lo assegna al rispettivo nodo genitore del secondo livello. L’algoritmo continua a valutare i valori massimi e minimi dei nodi figli e ad assegnarli ai nodi genitori, alternativamente, finché non raggiunge il nodo radice dell’albero, per il quale sceglie il nodo figlio con il valore massimo (rappresentato con una freccia blu in figura). Questa mossa è quella che il giocatore dovrebbe fare per minimizzare la massima possibile funzione di perdita.

In pratica il lavoro dell’algoritmo minimax è di esplorare tutti i possibili nodi dell’albero di gioco: il numero medio di nodi figlio per ogni nodo in esame è detto fattore di diramazione, ed è pari al numero medio di mosse possibili in una generica posizione del gioco. Pertanto il numero di nodi da valutare cresce esponenzialmente con la profondità di ricerca ed è pari al fattore di diramazione elevato alla profondità di ricerca. La complessità computazionale dell’algoritmo minimax quindi è NP completa, il che lo rende poco pratico per ottenere una soluzione definitiva di giochi meno che banali (Ad esempio, soltanto il semplice gioco del tris a nove caselle ha ben oltre 360 mila nodi terminali (9!) ossia combinazioni di gioco, gli scacchi hanno circa 10⁴⁰ nodi terminali), e utile solo per ottenere una condotta di gioco “non troppo cattiva”. Tuttavia le prestazioni del minimax possono essere migliorate drasticamente, mantenendo la correttezza dei risultati, adottando la potatura alfa-beta: esistono altri metodi euristici di potatura dell’albero di gioco, ma questo è l’unico che non influenza il risultato finale della ricerca minimax.

Potatura alfa-beta

La potatura alfa-beta è una variante dell’algoritmo minimax che consente di ridurre il numero dei nodi e delle ramificazioni da analizzare per giungere al risultato minimax ottimale. L’idea alla base della potatura alfa-beta è molto semplice e consiste nell’interrompere l’esplorazione in profondità dei nodi quando non sarebbero comunque selezionati dai giocatori perché peggiori rispetto alle alternative possibili. Ciò consente di effettuare una potatura logica dell’albero di gioco e ridurre la complessità dell’algoritmo.
A differenza dell’algoritmo minimax completo, l’algoritmo con potatura alfa-beta analizza soltanto una parte dell’albero di gioco, giungendo comunque alla medesima soluzione strategica ottimale.

L’efficienza della potatura alfa-beta è fortemente condizionata all’ordine di presentazione dei nodi foglia in una ramificazione.
Quando la potatura interrompe l’esplorazione, l’algoritmo potrebbe comunque aver scandagliato l’intera ramificazione del nodo B. Le possibili soluzioni al problema sono un ordinamento dei successori a partire dalla mossa corrente (potatura alfa-beta con ordinamento) oppure l’individuazione della mossa migliore mediante una funzione euristica (potatura alfa-beta euristica).

Considerazioni finali

1) Il minimax funziona soltanto nei giochi con numero finito di turni
L’algoritmo minimax è poco adatto a risolvere i giochi strategici con un numero indefinito di turni.
E’ importante sapere a chi spetta l’ultima mossa del gioco.
2) La complessità del minimax cresce in modo esponenziale
Se il gioco ha molti turni l’albero di ricerca, la ricerca in profondità richiede molto tempo e memoria.
Il numero dei nodi terminali potrebbe essere eccessivo.
3) Il minimax non è adatto nei giochi con più di due giocatori
Quando gli agenti decisionali sono più di due, le scelte strategiche diventano molto più complesse.
Il metodo minimax non riesce a interpretare le interazioni perché entrano in gioco altri fattori.
Esempio. Nei giochi a tre o più giocatori, alcuni agenti potrebbero coalizzarsi tra loro contro un altro agente: le scelte non sono individuali.
Inoltre, le stesse coalizioni sono sottoposte al rischio dei tradimenti.
È quindi importante la reputazione dei giocatori.

E così via.

Bibliografia

Minimax – Wikipedia

Algoritmo Minimax – OKpedia

Minimax ( teoria dei giochi ) – Andrea Minini

La strategia MiniMax e le sue varianti – Paolo Boldi