Il metodo Minimax
Il metodo minimax è un algoritmo ricorsivo che minimizza la massima perdita possibile due agenti razionali.
Chi l'ha creato? E' stato ideato negli anni '20 dal matematico-informatico John von Neumann.
A cosa serve?
Nella teoria dei giochi il minimax è usato per trovare le decisioni migliori/ottimali dei giocatori nei giochi di interazione strategica.
In particolar modo, l'algoritmo mini-max è utilizzato nei giochi a somma costante e a somma zero.
Nota. Un'altra applicazione utile è nell'intelligenza artificiale e nella costruzione dei modelli decisionali degli agenti razionali.
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.
Le caratteristiche del gioco
I due giocatori hanno obiettivi opposti. Si tratta, pertanto, di un gioco a somma zero ( non cooperativo ).
Inoltre, è un gioco sequenziale.
I due giocatori prendono le loro decisioni a turno, l'uno dopo l'altro, fino alla fine del gioco.
Ogni giocatore decide in base alle decisioni dell'altro. Come in una partita a scacchi.
Quindi, posso costruire un albero di gioco.
Nota. I nodi più in alto ( radice ) sono le prime decisioni di gioco mentre i nodi terminali ( foglie ) sono le ultime decisioni di gioco. Le decisioni del giocatore Mini sono cerchi mentre quelle del giocatore Maxi sono triangoli. Il valore all'interno dei simbolo è il risultato parziale del gioco. Quello nelle foglie è il risultato finale del gioco.
L'algoritmo minimax risale l'albero logico a ritroso a partire dall'ultimo livello di gioco ( turno ) rispettando i turni di gioco dei giocatori.
Esempio. L'ultima mossa spetta a Mini che sceglie il nodo (1) perché è quello che ha il valore minore. La penultima mossa è di Maxi che sceglie il nodo (8) perché è quello più alto. Infine la mossa ripassa a Mini che sceglie (2). Poi si giunge al nodo radice.
E' così possibile individuare le migliori scelte strategiche dei giocatori per ogni turno.
Quando l'algoritmo raggiunge il nodo radice, quello più alto, verifica se esiste un percorso in grado di congiungere il vertice e la base dell'albero.
Nell'esempio precedente c'è soltanto un percorso in grado di collegare il nodo radice a uno dei nodi terminali ( 0 → 2 → 6 → 1 ).
Il percorso individuato dall'algoritmo minimax è quello che minimizza le perdite complessive dei due giocatori.
In questo modo l'algoritmo riduce il rischio di incappare nelle situazioni peggiori per entrambi i giocatori.
Limiti del minimax
L'algoritmo minimax ha diverse limitazioni da considerare:
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.
Esempio. Nell'esempio precedente si conosce già che l'ultima mossa spetta al giocatore Mini.
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.
Quindi, la complessità spaziale e temporale dell'algoritmo minimax cresce in modo esponenziale con la profondità dell'albero di ricerca ( numero dei turni di gioco ).
Esempio. Il gioco del tris è un gioco di interazione molto semplice. Tuttavia, l'albero di gioco del gioco ha 360 mila foglie ( combinazioni di gioco ).
Per queste ragioni non è sempre possibile usare l'algoritmo minimax in modo completo.
Spesso è necessario ricorrere a qualche forma di potatura logica dell'albero di gioco prima di eseguire il minimax.
Esempi di potatura logica. Alcuni metodi di potatura logica usati per ridurre la profondità degli alberi sono la potatura alfa-beta e la tabella delle trasposizioni.
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. E' quindi importante la reputazione dei giocatori. E così via.
