Minimax

Minimax, în teoria deciziei , este o metodă pentru minimizarea maxim (minimax) posibila pierdere ; alternativ, pentru a maximiza câștigul minim ( maximin ). A fost descoperit în teoria jocurilor în cazul unui joc cu sumă zero cu doi jucători, atât în cazul mișcărilor alternative (ture), cât și al mișcărilor simultane și a fost ulterior extins la jocuri mai complexe și la sprijinirea deciziilor în prezența incertitudinii.

O versiune simplă a algoritmului poate fi văzută în jocuri precum tic-tac-toe , unde este posibil să câștigi, să pierzi sau să tragi la egalitate.

Dacă jucătorul A poate câștiga într-o singură mutare, cea mai bună mișcare este cea câștigătoare.
Dacă Jucătorul B știe că o mișcare îl va conduce pe A să câștige cu următoarea sa mutare, în timp ce alta va duce la egalitate, cea mai bună mișcare a Jucătorului B este cea care îl va aduce la remiză.

Spre sfârșitul jocului este ușor de înțeles care sunt cele mai bune mișcări; algoritmul minimax găsește cea mai bună mișcare la un moment dat, căutând-o începând de la sfârșitul jocului și deplasându-se spre situația actuală. La fiecare pas, algoritmul presupune că jucătorul A încearcă să-și maximizeze șansele de câștig, în timp ce B încearcă să minimizeze șansele de câștig ale lui A, de exemplu prin maximizarea șanselor sale de a câștiga.

Criteriul Minimax în teoria deciziilor statistice

În teoria deciziilor statistice clasice, minimaxul este un estimator $\delta$ ${\ displaystyle \ delta}$ $\ delta$ pe care le folosim pentru a estima o anumită valoare $\theta \in \Theta$ ${\ displaystyle \ theta \ in \ Theta}$ ${\ displaystyle \ theta \ in \ Theta}$ , important pentru noi; printre toate posibile $\delta$ ${\ displaystyle \ delta}$ $\ delta$ , cel minimax trebuie să minimizeze pierderea maximă posibilă, adică trebuie să aibă următoarea proprietate:

\sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\sup _{\theta }R(\theta ,\delta )

{\ displaystyle \ sup _ {\ theta} R (\ theta, {\ tilde {\ delta}}) = \ inf _ {\ delta} \ sup _ {\ theta} R (\ theta, \ delta)}

{\ displaystyle \ sup _ {\ theta} R (\ theta, {\ tilde {\ delta}}) = \ inf _ {\ delta} \ sup _ {\ theta} R (\ theta, \ delta)}

.

unde este ${\tilde {\delta }}$ ${\ displaystyle {\ tilde {\ delta}}}$ ${\ displaystyle {\ tilde {\ delta}}}$ este estimatorul minimax și $R(\theta ,\delta )$ ${\ displaystyle R (\ theta, \ delta)}$ ${\ displaystyle R (\ theta, \ delta)}$ este o funcție de risc , care este definită ca integrală a unei funcții de pierdere corespunzătoare.

Algoritmi Minimax în jocuri pe rând

În jocurile pe rând (N jucătorii se mișcă sau se joacă alternativ), principiul minimax ia forma algoritmului minimax , adică un algoritm recursiv pentru a găsi cea mai bună mișcare într-o situație dată. Algoritmul minimax constă dintr-o funcție de evaluare pozițională care măsoară bunătatea unei poziții (sau a stării de joc) și indică cât de dorit este ca jucătorul dat să atingă acea poziție; jucătorul face apoi mișcarea care minimizează valoarea celei mai bune poziții atinse de celălalt jucător. Prin urmare, algoritmul minimax atribuie o valoare fiecărei mișcări legale, proporțională cu cât scade valoarea poziției pentru celălalt jucător.

Care valoare este de fapt atribuită depinde de modul în care sunt evaluate pozițiile finale de victorie și înfrângere: o metodă este de a atribui 1 mișcărilor care conduc la victoria finală și -1 celor înfrângere (ceea ce duce la dezvoltarea teoriei jocului combinatoriu formulată de John Conway ), alta este să adopte valorile infinitului pozitiv și negativ. Valoarea pentru jucătorul A a fiecărei mișcări care nu câștigă imediat este apoi valoarea minimă a tuturor contramutărilor posibile de B. Acesta este motivul pentru care A este numit și „jucător maximizant” și B „jucător minimizant”.

Acest lucru presupune că este posibil pentru cei care calculează (nu vorbim încă despre aplicații de calculator) să evalueze întregul arbore al mișcărilor posibile din joc; în realitate acest lucru se poate face doar pentru jocuri foarte simple, în timp ce pentru altele, cum ar fi șahul sau go, acest lucru nu este posibil sau este posibil doar în etapele finale și, în general, se poate calcula doar o estimare a probabilității ca o anumită mișcare la victoria unuia dintre jucători.

Calculul acestei estimări poate fi îmbunătățit dacă este posibil să se furnizeze o funcție euristică de evaluare care să evalueze pozițiile non-terminale ale jocului fără a fi nevoie să cunoască toate mutările următoare: în acest caz poate fi luat în considerare doar un anumit număr de mutări viitoare. . Acest număr se numește „adâncimea” algoritmului și este măsurat în mișcări: Deep Blue are o adâncime de 12 mișcări ^{[ fără sursă ]} .

În practică, algoritmul minimax este de a explora toate nodurile posibile ale arborelui de joc: numărul mediu de noduri copil pentru fiecare nod luat în considerare se numește factor de ramură și este egal cu numărul mediu de mișcări posibile într-un una generică.poziția jocului. Prin urmare, numărul de noduri care urmează să fie evaluate crește exponențial cu adâncimea de căutare și este egal cu factorul de ramură ridicat la adâncimea de căutare. Complexitatea de calcul a algoritmului minimax este deci NP completă, ceea ce îl face impracticabil pentru obținerea unei soluții definitive la jocuri mai puțin decât banale și util numai pentru obținerea unui comportament de joc „nu prea rău”. Cu toate acestea, performanța minimax poate fi îmbunătățită drastic, menținând corectitudinea rezultatelor, adoptând tăierea alfa-beta : există alte metode euristice de tăiere a arborelui de joc, dar aceasta este singura care nu afectează rezultatul final. a căutării minimax.

Pseudo cod

Iată un pseudocod al algoritmului minimax, cu o adâncime euristică specificată:

 funcție minimax (nod, adâncime)
    IF nod este un nod terminal SAU adâncime = 0
        returnează valoarea euristică a nodului
    DACĂ adversarul trebuie să joace
        α: = + ∞
        PENTRU FIECARE copil de nod
            α: = min (α, minimax (fiul, adâncimea-1))
    Altfel trebuie să jucăm
        α: = -∞
        PENTRU FIECARE copil de nod
            α: = max (α, minimax (copil, adâncime-1))
    întoarce α

Exemplu

Să presupunem că avem un joc în care cei doi jucători au doar două mișcări posibile în fiecare rând. Algoritmul generează arborele de joc din dreapta, unde cercurile reprezintă mișcările jucătorului folosind algoritmul (maximizarea jucătorului), iar pătratele sunt mișcările adversarului (minimizarea jucătorului). Datorită limitărilor sistemului de calcul, așa cum s-a explicat mai sus, limităm arborele la o adâncime de patru spire.

Algoritmul evaluează fiecare nod frunză cu o funcție euristică de evaluare și obține valorile prezentate. Miscările care fac câștigarea maximă a jucătorului au o valoare infinită pozitivă, în timp ce mișcările care dau câștigător jucătorului minimizator au o valoare negativă infinită. La al treilea nivel, algoritmul va alege, pentru fiecare nod, nodul copil cu cea mai mică valoare și va atribui această valoare nodului examinat; de exemplu nodul din stânga va asuma valoarea minimă între „10” și „+ ∞”, adică „10”. Pasul următor, la nivelul 2, alege valoarea maximă dintre toate nodurile copil (nodurile de nivelul 3) și o atribuie nodului părinte respectiv al celui de-al doilea nivel. Algoritmul continuă să evalueze valorile maxime și minime ale nodurilor copil și le atribuie nodurilor părinte, alternativ, până când ajunge la nodul rădăcină al arborelui, pentru care alege nodul copil cu valoarea maximă (reprezentată cu o săgeată albastră în figură). Această mișcare este ceea ce jucătorul ar trebui să facă pentru a minimiza funcția de pierdere maximă posibilă.

Teorema Minimax în cazul mișcărilor simultane

Următorul este un exemplu de joc cu sumă zero, în care A și B se mișcă simultan, ilustrând algoritmul minimax . Să presupunem că fiecare jucător poate alege între trei mișcări posibile, iar matricea de recompensă pentru A este:

	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

în timp ce B are aceeași matrice de recompensă, dar cu semnele inversate (de exemplu, dacă alegerile sunt A1 și B1, atunci B plătește 3 până la A ) atunci alegerea minimax simplă pentru A este A2, deoarece astfel cel mai rău rezultat posibil ar fi să plătească 1, în timp ce cel pentru B este B2, deoarece cel mai rău rezultat ar fi să nu plătiți nimic. Cu toate acestea, această soluție nu este stabilă, deoarece dacă B crede că A va alege A2, atunci B va juca B1 pentru a câștiga 1; deci, dacă A crede că B alege B1, A va juca A1 pentru a câștiga 3, ceea ce îl va duce pe B să joace B2, ducându-i pe ambii jucători să-și dea seama de dificultatea de a face o alegere. Pentru aceasta este nevoie de o strategie mai puternică.

Unele mișcări sunt dominate de celelalte și pot fi eliminate: A nu va juca niciodată A3 deoarece rezultatul ar fi mai rău decât celelalte cazuri, indiferent de ce joacă B ; B oricum nu va juca B3, deoarece B2 va oferi un rezultat mai bun indiferent de alegerea lui A.

A poate evita să plătească mai mult de 1/3 în viitor jucând A1 cu probabilitatea 1/6 și A2 cu probabilitatea 5/6, indiferent de jocul lui B. B poate asigura un anumit câștig de cel puțin 1/3 cu o strategie aleatorie, jucând B1 cu probabilitatea 1/3 și B2 cu probabilitatea 2/3, indiferent de mișcările lui A. Aceste două strategii mixte de minimax sunt stabile și nu pot fi îmbunătățite în continuare.

John von Neumann a dovedit teorema minimaxului în 1928 , stabilind că astfel de strategii există întotdeauna în jocurile cu doi jucători cu sumă zero și pot fi găsite rezolvând un sistem adecvat de ecuații.

Minimax în situații de incertitudine

Teoria minimax a fost, de asemenea, extinsă la decizii: adică situații în care nu există oponenți, dar rezultatul final al unei alegeri depinde de factori necunoscuți și / sau imprevizibili, de exemplu alegerea locului în care se efectuează prospectarea geologică în căutarea mineralelor: fiecare cercetare are un cost, care se pierde dacă nu se găsește nimic, dar este rambursat de mai multe ori dacă se găsește un fir exploatabil. O posibilă abordare este tratarea acestor cazuri ca un joc împotriva naturii și utilizarea unei atitudini similare Legii lui Murphy și încercarea de a minimiza costul total maxim, cu aceleași tehnici ca în jocurile cu doi jucători cu sumă zero. Pentru aceste situații (jocuri cu doi jucători în care intervine și întâmplarea) au fost proiectați arbori expectiminimax .

Principiul minimax în jocurile non-zero

Dacă schimburile dintre jucători nu sunt sumă zero, aplicarea principiului minimax pare să ducă la strategii suboptimale. De exemplu, în jocul de dilemă al prizonierului , strategia minimax pentru fiecare prizonier este să trădeze întotdeauna, în timp ce strategia optimă este să nu trădăm niciodată. Prin urmare, în această categorie de jocuri, cea mai bună strategie nu este neapărat minimax.

Aplicații

Etică

Filosoful John Rawls a susținut în cartea sa A Theory of Justice că, dacă un individ este plasat în spatele unui „voal al ignoranței” (așa-numita poziție originală ) despre propria sa situație existențială, el va formula conceptul de societate dreaptă folosind minimaxul principiu. Conform acestui principiu, indivizii ar trebui să aleagă tipul de societate care oferă „cel mai rău caz”, adică în care cei mai nefericiți indivizi se află în starea cel mai puțin disperată.

Bibliografie

John von Neumann [1928]: Zur Theorie der Gesellschaftsspiele , Matematische Annalen, 100, 295-320; Traducere în limba engleză: Despre teoria jocurilor de strategie , în „Contribuții la teoria jocurilor”, n. IV, 13-42, 1959; vezi și „Lucrări colecționate”, vol. TU.

Elemente conexe

linkuri externe

( RO ) Teorema Minimax , la cut-the-knot.org .
( RO ) Minimax Analysis for Zero Sum Games , pe geocities.com . urlarchivio2 pe 5 mai 2007 (arhivat din adresa URL originală la 11 noiembrie 2007; a doua copie arhivată ) .
( EN ) „Principiul Maximin” din Un dicționar de termeni și nume filozofice. , pe swif.uniba.it . Adus la 5 mai 2007 (arhivat din original la 7 martie 2006) .
( RO ) Jucați un joc de pariuri și bluffuri împotriva unei strategii mixte de minimax , pe bewersdorff-online.de .
( RO ) Dicționarul algoritmilor și intrarea structurilor de date pentru minimax , la nist.gov .

Portalul Economiei

Portalul de matematică

V ·D · M Teoria jocului
Definiții	În formă normală joc · joc în formă extinsă · Joc cooperativ · Set de informații · Preferință · Recompensă · Credință · Cel mai bun răspuns · Joc corect
Soluții de echilibru	Nash Equilibrium · Bayesian Equilibrium · Balance perfect Bayesian (EBP) · Great Pareto
Strategii	Strategiile dominante · strategie pură · strategie mixtă · strategie de declanșare · Complotarea tacită · inducție înapoi · Dinte pentru dinte
Cursuri de joc	Full-Informații de joc · statice joc · dinamic sau joc secventiala · joc repetată · Signaling joc · joc cu sumă zero
Jocuri	Prizonierul dilema · Dilemma călător · pui joc · Dilemma voluntar · Egalitatea luptă · Deer Hunt · bănuți de potrivire · ultimatum joc · Chineză Morra · concurență Cournot · Stackelberg concurenței · Bertrand concurenței · Joc de miriapod
Teoreme	Teorema minimax · Teorema imposibilității săgeții