Minimax
Minimax (numit uneori minmax) este o regulă de decizie utilizată în teoria jocurilor, statistică și filosofie și care constă în minimizarea pierderii maxime posibile. Alternativ, abordarea poate fi și cea a maximizării câștigului minim (maximin). A început din teoria jocului cu sumă zero cu doi jucători, acoperind atât cazurile în care jucătorii fac mutări alternativ și cele în care fac mutări simultan. Regula a fost extinsă și la jocuri mai complexe și la procese generale de luare a deciziilor în condiții de incertitudine.
Teoria jocurilor
[modificare | modificare sursă]În teoria jocurilor simultane, o strategie minimax este o strategie mixtă care face parte din soluția unui joc cu sumă zero. În jocurile cu sumă zero, soluția minimax este aceeași cu echilibrul Nash.
Teorema Minimax
[modificare | modificare sursă]Teorema minimax afirmă că:
- Oricare ar fi jocul cu sumă zero cu strategii finite și doi jucători, există o valoare V și o strategie mixtă pentru fiecare jucător, astfel încât (a) Dată fiind strategia lui 2, câștigul lui 1 este V, și (b) Dată fiind strategia lui 1, câștigul lui 2 este -V.
Echivalent, strategia jucătorului 1 îi garantează un câștig de V indiferent de strategia jucătorului 2, și în același timp jucătorul 2 își poate garanta un câștig de -V. Numele de minimax apare deoarece fiecare jucător încearcă, la fiecare pas, să minimizeze câștigul maxim al celuilalt — deoarece jocul este cu sumă zero, își maximizează astfel propriul câștig minim.
Această teoremă a fost enunțată de John von Neumann[1], care a afirmat: "Din câte pot vedea, nu poate să existe o teorie a jocurilor … fără acea teoremă … am considerat că nimic nu merita publicat până când nu a fost demonstrată teorema minimax".[2]
Exemplu
[modificare | modificare sursă]| B alege B1 | B alege B2 | B alege B3 | |
|---|---|---|---|
| A alege A1 | +3 | -2 | +2 |
| A alege A2 | -1 | 0 | +4 |
| A alege A3 | -4 | -3 | +1 |
Următorul exemplu de joc cu sumă zero, în care A și B mută simultan, ilustrează soluțiile minimax. Se presupune că fiecare jucător are la dispoziție trei variante, și se consideră matricea câștigurilor A afișată la dreapta. Se presupune că matricea câștigurilor lui B este aceeași matrice, cu semnele schimbate. Atunci, alegerea minimax pentru A este A2 deoarece cel mai prost rezultat posibil este să piardă 1, în timp ce alegerea minimax pentru B este B2 deoarece cel mai slab rezultat pe care îl poate obține este 0. Totuși, această soluție nu este stabilă, deoarece dacă B crede că A va alege A2, atunci B va alege B1 pentru a câștiga 1; apoi dacă A crede că B va alege B1 atunci A va alege A1 pentru a câștiga 3; apoi B va alege B2; și în cele din urmă ambii jucători vor realiza dificultatea deciziei, deci este necesară o strategie mai stabilă.
Unele variante sunt dominate de altele și pot fi eliminate: A nu va alege A3 deoarece și A1 și A2 produc rezultate mai bune, indiferent de ce alege B; B nu va alege B3 deoarece B2 va produce un rezultat mai bun, indiferent ce alege A.
A poate evita o pierdere așteptată de peste 1/3 alegând A1 cu probabilitatea 1/6 și A2 cu probabilitatea 5/6, indiferent ce alege B. B poate asigura un câștig așteptat de cel puțin 1/3 folosind o strategie aleatoare de alegere, cu B1 cu probabilitatea 1/3 și B2 cu probabilitatea 2/3, indiferent ce alege A. Aceste strategii minimax mixte sunt stabile și nu mai pot fi îmbunătățite.
Note
[modificare | modificare sursă]- ^ Von Neumann, J: Zur theorie der gesellschaftsspiele Math. Annalen. 100 (1928) 295-320
- ^ John L Casti (). Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience. p. p. 19. ISBN 0-471-00261-5.
 | Acest articol din domeniul informaticii este deocamdată un ciot. Puteți ajuta Wikipedia prin dezvoltarea lui. |