h1. Teoria jocurilor
h1.
(Categoria _Teoria jocurilor_, Autor _Filip Cristian Buruiana_)
(toc)*{text-align:center} *Capitole*
* '*Notiuni de baza*':teoria-jocurilor
* 'Jocul NIM':teoria-jocurilor/jocul-nim
* 'Numere Sprague-Grundy':teoria-jocurilor/numere-SG
* 'Adunarea jocurilor':teoria-jocurilor/adunarea-jocurilor
* 'w-numere':teoria-jocurilor/w-numere
* 'Aplicatii si probleme':teoria-jocurilor/probleme
p{font-size:32px;}=. Teoria jocurilor
h2. Notiuni de baza
p{margin-right:8em;}>. _Filip Cristian Buruiana_
Prin _joc_ se intelege un sir de decizii (actiuni, mutari), luate de parti ale caror interese se ciocnesc. Jocurile studiate in acest articol sunt cele care au doi parteneri. De asemenea, toate jocurile analizate sunt jocuri cu _mutari libere_: la fiecare pas, jucatorul aflat la mutare poate alege sa efectueze una in mod constient, in functie de regulament si de situatia jocului la momentul respectiv. Decizia nu este constransa de niciun factor aleator, precum zaruri, carti de joc sau monede.
!<teoria-jocurilor?dice.jpg 30%! Pentru un joc dat, un jucator are strategie _sigura de castig_ daca acesta va castiga, prin mutari alese pe baza unui anumit criteriu in functie de starea de joc, indifierent de modul in care ar incerca adversarul sa ii impiedice victoria. In aceasta situatie, spunem ca jocul respectiv are _rezultatul predeterminat_. Mai jos sunt prezentate cele cinci conditii necesare si suficiente pentru ca un joc sa aiba rezultatul predeterminat:
'!teoria-jocurilor?dice.jpg!':teoria-jocurilor/notiuni
* Se termina dupa un numar finit de pasi
* Nu contine un element intamplator introdus de zaruri, carti de joc, etc.
* Este un joc cu informatie completa, in care un jucator inainte de a executa o mutare cunoaste rezultatele tuturor mutarilor precedente
* Un jucator poate vedea toate mutarile adversarului
* Jucatorii muta alternativ
<br>
h4. Pozitii castigatoare, pozitii pierzatoare
!>teoria-jocurilor?winlose.jpg 48%!
Fie un joc in care rezultatul este predeterminat, deci unul dintre jucatori are strategie sigura de castig. Intr-un astfel de joc, multimea tuturor starilor (situatiilor) care pot aparea la un moment dat poate fi separata in doua submultimi $P$ si $N$ cu proprietatile:
* intersectia dintre $P$ si $N$ este multimea vida
* reuniunea multimilor $P$ si $N$ este multimea tuturor starilor de joc
* din orice stare din $P$, putem ajunge, efectuand o mutare convenabila, intr-o stare din $N$
* starile din care nu se mai poate efectua nicio mutare ({_terminale_}) sunt in multimea $N$
* din orice stare neterminala din $N$, oricum am efectua o mutare, vom ajunge intr-o stare din $P$
O stare din multimea $P$ se va numi castigatoare sau $P$-pozitie, iar o stare din $N$ se va numi pierzatoare sau $N$-pozitie. Jucatorul aflat la mutare care este intr-o $P$-pozitie are strategie sigura de castig, in timp ce jucatorul care se afla intr-o $N$-pozitie va pierde, indiferent de mutarile pe care le va face, in situatia in care adversarul sau joaca optim.
Demonstratia acestei afirmatii se bazeaza pe proprietatile de mai sus. Se observa urmatorul invariant: jucatorul cu strategie de castig se va afla mereu intr-o pozitie castigatoare in cazul unui joc perfect, in timp ce adversarul sau se va afla mereu intr-o pozitie de pierdere. Prin joc perfect se intelege ca jucatorul cu strategie de castig, aflat evident intr-o $P$-pozitie, isi va aduce adversarul intr-o pozitie de pierdere. Mai mult, adversarul, aflat acum intr-o pozitie de pierdere, nu poate lasa jocul decat intr-o pozitie de castig, si procedeul se reia, urmand alternanta starilor castig-pierdere, pana cand s-a ajuns intr-o stare terminala ({$N$}-pozitie), si nu se mai poate muta.
p{margin:1em; padding: 0.5em; height: 45px; border-top: 1px solid silver;}=.
'Notiuni de baza':teoria-jocurilor/notiuni | 'Jocul NIM':teoria-jocurilor/jocul-nim | 'Numere Sprague-Grundy':teoria-jocurilor/numere-SG |
'Adunarea jocurilor':teoria-jocurilor/adunarea-jocurilor | 'w-numere':teoria-jocurilor/w-numere | 'Aplicatii si probleme':teoria-jocurilor/probleme
