h1.

h1. Teoria jocurilor

 

(Categoria _Teoria jocurilor_, Autori _Filip Cristian Buruiana, Vlad Tudose, Victor Rusu_)

p{font-size:32px;}=. Teoria jocurilor

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.
Se spune ca un jucator are strategie _sigura de castig_ daca acesta va castiga, indifierent de modul in care ar incerca adversarul sa ii impiedice victoria. Daca un joc respecta toate cele cinci conditii de mai jos si unul dintre jucatori alege intotdeauna strategia cea mai buna, atunci rezultatul este predeterminat:

p{margin-right:8em;}>. _Filip Cristian Buruiana_

* 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

 
 

Majoritatea jocurilor impartiale se pot reduce la urmatorul joc: "Se considera un graf orientat aciclic care contine pioni in anumite noduri. Cei doi jucatori muta alternativ. Prin mutare se intelege miscarea unui pion aflat in nodul $x$ intr-un nod {$y$}, astfel incat sa existe un arc care iese din nodul $x$ si intra in nodul {$y$}. Jucatorul care nu mai poate muta pierde."

'!teoria-jocurilor?dice.jpg!':teoria-jocurilor/notiuni

!teoria-jocurilor?img001.jpg!

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
 

De exemplu, pentru graful din figura de mai sus, daca exista doi pioni, unul in nodul $1$ si celalalt in nodul {$2$}, primul jucator aflat la mutare are strategie sigura de castig.
 
Cum graful este aciclic, jocul este finit si are intotdeauna un castigator. Daca in graf exista un singur pion, castigatorul poate fi determinat prin metoda programarii dinamice. Astfel, {$win{~x~}$} va fi _true_ daca si numai daca primul jucator aflat la mutare are strategie de castig atunci cand pionul se afla in nodul {$x$}. Astfel, {$win{~x~}$} = _true_ daca si numai daca exista un nod $y$ astfel incat sa existe arc intre $x$ si $y$ si {$win{~y~}$} = _false_. In caz contrar, {$win{~x~}$} = _false_. Pentru exemplul de mai sus, atunci cand avem un singur pion, {$win{~2~}$} = _true_, iar {$win{~1~}$} si {$win{~4~}$} vor fi _false_. Valorile vectorului $win$ se vor calcula in ordinea din sortarea topologica a nodurilor, in complexitate {$O(N + M)$}, unde $N$ este numarul de noduri iar $M$ numarul de muchii din graful dat.
 
Folosind teoria dezvoltata independent de Roland Percival Sprague (1936) si Patrick Michael Grundy (1939), putem reduce complexitatea jocului cu mai multi pioni la complexitatea analizei jocului cu un pion. Ca in algoritmul de programare dinamica de mai sus, se incearca determinarea pozitiilor castigatoare si a celor necastigatoare pentru un singur pion.