Visualizza wikitesto di Minimax

[[File:JohnvonNeumann-LosAlamos.jpg|thumb|[[John von Neumann]]]]
Il '''minimax''', nella [[teoria delle decisioni]], è un metodo per minimizzare la massima ('''minimax''') [[Funzione di perdita|perdita]] possibile; in alternativa, per massimizzare il minimo guadagno ('''maximin'''). Fu introdotto 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 (gioco)|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.

== Il criterio Minimax nella teoria statistica delle decisioni ==
Nella classica [[teoria delle decisioni]] statistica, il '''minimax''' è uno [[stimatore]] <math>\delta</math> che usiamo per stimare un certo valore <math>\theta \in \Theta</math>, per noi importante; fra tutti i possibili <math>\delta</math>, quello minimax deve minimizzare la massima perdita possibile, cioè deve godere della seguente proprietà:

: <Math>\sup_\theta R(\theta,\tilde{\delta}) = \inf_\delta \sup_\theta R(\theta,\delta)</math>.

dove <Math>\tilde{\delta}</Math> è lo stimatore minimax e <math>R(\theta,\delta)</math> è una [[funzione di rischio]], che è definita come l'integrale di una corrispondente [[funzione di perdita]].

== Algoritmi minimax in giochi a turni ==
Nei [[Teoria dei giochi|giochi]] a turni (N giocatori muovono o giocano alternativamente), il principio del minimax assume la forma di '''algoritmo minimax''', cioè un [[algoritmo ricorsivo]] per la ricerca della mossa migliore in una determinata situazione. L'algoritmo minimax è costituito da una [[Logica proposizionale|funzione di valutazione posizionale]] che misura la bontà di una posizione (o stato del gioco) e indica quanto è desiderabile per il dato giocatore raggiungere quella posizione; il giocatore fa poi la mossa che minimizza il valore della migliore posizione raggiungibile dall'altro giocatore. Quindi l'algoritmo minimax assegna un valore ad ogni mossa legale, proporzionale a quanto essa diminuisce il valore della posizione per l'altro giocatore.

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 Horton Conway|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 (gioco)|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: [[IBM Deep Blue|Deep Blue]] ha una profondità di 12 mosse{{Senza fonte}}.

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, 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.

=== Pseudocodice ===
Ecco uno [[pseudocodice]] di algoritmo minimax, con una profondità euristica specificata:

 '''function''' minimax(nodo, profondità)
     '''SE''' nodo è un nodo terminale '''OPPURE''' profondità = 0
         '''return''' il valore euristico del nodo
     '''SE''' l'avversario deve giocare
         α := +∞
         '''PER OGNI''' figlio di nodo
             α := min(α, minimax(figlio, profondità-1))
     '''ALTRIMENTI''' dobbiamo giocare noi
         α := -∞
         '''PER OGNI''' figlio di nodo
             α := max(α, minimax(figlio, profondità-1))
     '''return''' α

=== Esempio ===
[[File:Minimax.svg|right|300px]]
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 a destra, 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, come spiegato sopra, limitiamo l'albero a una profondità di quattro turni.

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]].

== Teorema minimax nel caso di mosse simultanee ==

Il seguente è un esempio di gioco a somma zero, dove '''A''' e '''B''' muovono contemporaneamente, che illustra l{{'}}''algoritmo minimax''. Supponiamo che ogni giocatore possa scegliere fra tre mosse possibili e la [[matrice ricompensa]] per '''A''' sia:

{| class="wikitable" align=left
 !
 ! B sceglie B1
 ! B sceglie B2
 ! B sceglie B3
 |-
 ! A sceglie A1
 | &nbsp;&nbsp;&nbsp;&nbsp;+3
 | &nbsp;&nbsp;&nbsp;&nbsp;-2
 | &nbsp;&nbsp;&nbsp;&nbsp;+2
 |-
 ! A sceglie A2
 | &nbsp;&nbsp;&nbsp;&nbsp;-1
 | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0
 | &nbsp;&nbsp;&nbsp;&nbsp;+4
 |-
 ! A sceglie A3
 | &nbsp;&nbsp;&nbsp;&nbsp;-4
 | &nbsp;&nbsp;&nbsp;&nbsp;-3
 | &nbsp;&nbsp;&nbsp;&nbsp;+1
 |}

mentre '''B''' ha la stessa matrice ricompensa ma con i segni invertiti (cioè se le scelte sono A1 e B1 allora '''B''' paga 3 ad '''A''') allora la scelta minimax semplice per '''A''' è A2, perché così il peggior risultato possibile sarebbe di pagare 1, mentre quella per '''B''' è B2 perché il risultato peggiore sarebbe di non pagare nulla. Tuttavia questa soluzione non è stabile, perché se '''B''' pensa che '''A''' sceglierà A2 allora '''B''' giocherà B1 per guadagnare 1; perciò se '''A''' crede che '''B''' scelga B1, '''A''' giocherà A1 per guadagnare 3, che porterà '''B''' a giocare B2, portando entrambi i giocatori a rendersi conto della difficoltà di fare una scelta. Per questo è necessaria una strategia più solida.

Alcune mosse sono ''dominate'' dalle altre e possono essere eliminate: '''A''' non giocherà mai A3 perché il risultato sarebbe peggiore degli altri casi, a prescindere da cosa giocherà '''B'''; '''B''' non giocherà comunque B3, perché B2 darà un risultato migliore qualunque sarà la scelta di '''A'''.

'''A''' può evitare di dover pagare in futuro più di 1/3 giocando A1 con probabilità 1/6 e A2 con probabilità 5/6, senza considerare le giocate di '''B'''. '''B''' può assicurarsi un guadagno certo di almeno 1/3 con una strategia casuale, giocando B1 con probabilità 1/3 e B2 con probabilità 2/3, a prescindere dalle mosse di '''A'''. Queste due strategie minimax miste sono stabili e non ulteriormente migliorabili.

[[John von Neumann]] dimostrò il '''Teorema minimax''' nel [[1928]], stabilendo che tali strategie esistono sempre in giochi di due giocatori a somma zero, e possono essere trovate risolvendo un opportuno [[sistema di equazioni]].

== Minimax in situazioni di incertezza ==
La teoria del minimax è stata estesa anche alle decisioni: cioè situazioni in cui non ci sono avversari, ma l'esito finale di una scelta dipende da fattori sconosciuti e/o imprevedibili, per esempio scegliere dove fare prospezioni geologiche in cerca di minerali: ogni ricerca ha un costo, che viene perso se non si trova nulla ma viene ripagato di molte volte se si trova un filone sfruttabile. Un possibile approccio è trattare questi casi come un gioco contro la ''Natura'' e usare un atteggiamento simile alla [[Legge di Murphy]] e cercando di minimizzare il costo totale massimo, con le stesse tecniche dei giochi a due giocatori a somma zero. Per queste situazioni (giochi a due giocatori in cui interviene anche la casualità) sono stati ideati gli [[albero expectiminimax|alberi expectiminimax]].

== Il principio minimax nei giochi non a somma zero ==
Se gli scambi fra i giocatori non sono a somma zero, l'applicazione del principio del minimax sembra portare a strategie non ottimali. Per esempio nel gioco del [[dilemma del prigioniero]] la strategia minimax per ogni prigioniero è di tradire sempre, mentre la strategia ottimale è non tradire mai. Pertanto, in questa categoria di giochi la strategia migliore non è necessariamente minimax.

== Applicazioni ==
=== Etica ===
Il filosofo [[John Rawls]] ha argomentato nel suo libro [[Una teoria della giustizia|A Theory of Justice]] che se si pone un individuo dietro un "velo di ignoranza" (la cosiddetta [[posizione originale]]) sulla propria situazione esistenziale, egli formulerà il concetto di società giusta usando il principio del minimax.
Secondo questo principio, gli individui dovrebbero scegliere il tipo di società che offre "il miglior caso peggiore", cioè in cui gli individui più sfortunati siano nella condizione meno disperata.

== Bibliografia ==
* John von Neumann [1928]: ''Zur Theorie der Gesellschaftsspiele'', Matematische Annalen, 100, 295-320; traduzione inglese: ''On the Theory of Games of Strategy'', in "Contributions to the Theory of Games", n. IV, 13-42, 1959; vedi anche "Collected Works", vol. VI.

== Voci correlate ==
* [[John von Neumann]]
* [[Tabella di trasposizione]]
* [[Tabella di refutazione]]
* [[Effetto orizzonte]]
* [[Negamax]]
* [[Expectiminimax]]
* [[Potatura alfa-beta]]
* [[Claude Elwood Shannon]]

== Collegamenti esterni ==

* {{Collegamenti esterni}}
* {{FOLDOC||minimax}}
* {{Garzanti|minimassimo}}
* {{cita web|url=https://www.cut-the-knot.org/Curriculum/Games/MixedStrategies.shtml|titolo=The Minimax Theorem|lingua=en}}
* {{cita web|lingua=en|url=http://www.geocities.com/arufast/a03minimax.html|titolo=Minimax Analysis for Zero Sum Games|urlarchivio=https://web.archive.org/web/20071111115445/http://www.geocities.com/arufast/a03minimax.html|accesso=5 maggio 2007|urlmorto=sì}}
* {{cita web|url=http://www.swif.uniba.it/lei/foldop/foldoc.cgi?maximin+principle|titolo="Maximin principle" from A Dictionary of Philosophical Terms and Names.|lingua=en|accesso=5 maggio 2007|urlarchivio=https://web.archive.org/web/20060307183023/http://www.swif.uniba.it/lei/foldop/foldoc.cgi?maximin+principle|urlmorto=sì}}
* {{cita web|url=http://www.bewersdorff-online.de/quaak/rules.htm|titolo=Play a betting-and-bluffing game against a mixed minimax strategy|lingua=en}}
* {{cita web|url=http://www.nist.gov/dads/HTML/minimax.html|titolo=The Dictionary of Algorithms and Data Structures entry for minimax|lingua=en}}
* {{cita web|titolo=Strategy Game Programming|url=https://www.fierz.ch/strategy1.htm|sito=fierz.ch}} — Strategy Game Programming for board games such as [[Checkers]] and [[Chess]]

{{Teoria dei giochi}}
{{portale|economia|matematica|statistica}}

[[Categoria:Teoria dei giochi]]
[[Categoria:Algoritmi sui grafi]]