Il minimax, nella teoria dei giochi, è un metodo che mira a minimizzare la perdita attesa. Per fare ciò, il giocatore presume che la decisione presa dal suo avversario sarà sfavorevole. Cioè, lo scenario peggiore è previsto prima del movimento dell'avversario.
Per dirla in altro modo, il metodo minimax consiste nel prendere la decisione migliore presumendo che l'altro giocatore scelga lo scenario peggiore per te.
Bisogna tener conto che questo metodo è applicabile in un gioco a due persone (due giocatori) e che non è cooperativo, ma un gioco a somma zero. Ciò significa che ciò che un giocatore vince viene perso dall'altro e viceversa. Di conseguenza, ogni agente sarà interessato a massimizzare la propria utilità, anche se ciò danneggia l'altro.
A questo punto, dobbiamo anche ricordare che la teoria dei giochi è una branca della matematica e dell'economia che studia la scelta che ottimizza la situazione di un individuo quando costi e benefici non sono fissati in anticipo, ma dipendono dalle decisioni degli altri.
Algoritmo Minimax in un albero decisionale
Possiamo vedere come il metodo minimax viene applicato in un albero decisionale con diversi nodi. Il gioco inizia dal basso e termina con un risultato al livello più alto.
Alla base dell'albero, l'avversario fa la prima mossa, quindi ci si aspetta il peggior risultato. Poi, nel secondo livello, spetta al giocatore x che cercherà di massimizzare il suo profitto, tenendo conto della decisione precedentemente presa dall'avversario.
Al terzo livello è di nuovo il turno dell'avversario e così via. Mostreremo un esempio di seguito.
Esempio di algoritmo Minimax
Nel seguente albero decisionale, mostriamo i risultati ottenuti dal giocatore x in ogni momento del gioco. Alla base, al primo livello, l'avversario prende la decisione. Per questo motivo, vengono forniti gli scenari in cui il giocatore può perdere -10 o vincere 5.
Al secondo livello, tocca al giocatore x, quindi massimizzerà il suo profitto. Tra perdere 10 o vincere 1, vincerai 1. Allo stesso modo, tra vincere 5 o 7, vincerai 7.
Quindi, è di nuovo il turno dell'avversario, quindi verranno presentati gli scenari in cui il giocatore x ha il risultato peggiore, -3 e 4, a seconda dei casi. Infine, tra la sconfitta di 3 o la vittoria di 4, il giocatore x prenderà la decisione che consentirà quest'ultima.
Dobbiamo tenere in considerazione che i valori di ciascun nodo dipenderanno da una funzione di utilità.
Per capire meglio l'albero, supponiamo che alla base la decisione riguardi la distribuzione del prodotto. Il concorrente (l'avversario) può esternalizzare la distribuzione (vedi lato sinistro dell'albero). In tal caso, deve scegliere, ad esempio, tra il mazziere A e B. Quindi, sceglie il primo, facendo perdere al giocatore x 10 (se scegliesse B, il giocatore x ne vincerebbe 12).
Tuttavia, forse l'avversario preferisce distribuire lui stesso la sua merce, potendo noleggiare automezzi o acquistare un camion. Di entrambi gli scenari, scegli il primo che è meno lusinghiero per il giocatore x perché vince 5 e non 10.