h1. Teoria jocurilor

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

(Categoria _Teoria jocurilor_, Autori _Filip Cristian Buruiana, Vlad Andrei Tudose, Victor Rusu_)
 
(toc)*{text-align:center} *Capitole*
* 'Notiuni de baza':teoria-jocurilor#baza
* 'Jocul NIM':teoria-jocurilor#nim
* 'Numere Sprague-Grundy':teoria-jocurilor#SG
* 'Adunarea jocurilor':teoria-jocurilor#adunare
* 'w-numere':teoria-jocurilor#wnumere
* 'Aplicatii si probleme':teoria-jocurilor#probleme

h2. Notiuni de baza

Se observa ca daca {$mex(x) = 0$}, in jocul cu un singur pion situat in nodul $x$ jucatorul care muta primul nu are strategie sigura de castig, iar daca {$mex(x)$} este diferit de $0$ atunci jucatorul care muta primul va castiga intotdeauna, in cazul in care joaca optim. Aceasta afirmatie este usor de demonstrat: daca {$mex(x)$} este diferit de $0$ atunci exista un nod {$y$}, vecin al lui {$x$}, astfel incat {$mex(y)$} sa fie egal cu $0$. In consecinta, primul jucator il va aduce intotdeauna pe adversarul sau in noduri care au valoarea Sprague-Grundy egala cu $0$. Mai mult, primul jucator va ramane intotdeauna in noduri cu valoare diferita de $0$, deoarece al doilea jucator nu il poate forta sa ajunga in aceste noduri: din nodurile cu valoarea $0$ se poate ajunge doar in noduri cu valoarea nenula. In consecinta, jucatorul al doilea va pierde, deoarece va fi adus intr-un nod final (fara urmasi).

Valorile Sprague-Grundy se pot calcula si pentru jocuri in care nu apar precizate explicit grafuri. Fiecare stare posibila a jocului va fi un nod in graf, iar un arc va indica o posibila mutare: o trecere de la o stare la alta, conform regulilor existente.

Valorile Sprague-Grundy se pot calcula si pentru jocuri in care nu apar precizate explicit grafuri. Fiecare stare posibila a jocului va fi un nod in graf, iar un arc va indica o posibila mutare: o trecere de la o stare la alta, conform regulilor existente.
 
h2. Adunarea jocurilor
 
Sa presupunem ca avem $N$ jocuri notate {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} pe care vrem sa le adunam. Fiecare din cele $N$ jocuri poate fi reprezentat ca un graf orientat fara circuite in care multimea nodurilor (notata {$V{~i~}$} pentru jocul {$i$}) este data de multimea starilor iar multimea arcelor (notata {$E{~i~}$} pentru jocul {$i$}) este data de perechile ordonate de stari adiacente (exista arc de la $x$ la $y$ daca se poate ajunge printr-o mutare din starea $x$ in starea $y$). Adunand cele $N$ jocuri obtinem un nou joc {$G$} pentru care o stare (nod in graful asociat) este un N-uplu {$(v{~1~},v{~2~}, ..., v{~N~})$} care ne precizeaza starea curenta pentru fiecare joc individual ({$v{~i~}$} este starea curenta in jocul $i$). Pentru a afla daca pentru o anumita stare din jocul $G$ exista sau nu strategie sigura de castig am putea aplica algoritmul simplu de programare dinamica (prezentat mai sus) pentru graful asociat jocului {$G$}. Se observa insa ca acest graf are {$|V{~1~}|*|V{~2~}|* ...*|V{~N~}|$} noduri, deci algoritmul nu este eficient.
In continuare vom arata cum putem sa determinam eficient daca o stare este castigatoare sau nu pentru un joc compus folosindu-ne de informatiile preprocesate pentru fiecare joc individual.
 
h3. Adunarea xor
 
Vom aduna jocurile {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} astfel incat la fiecare pas jucatorul care urmeaza trebuie sa isi aleaga exact un joc si sa faca o mutare in jocul respectiv. Ultimul jucator care muta castiga. Un astfel de joc este si jocul NIM: atunci cand este la mutare, un jucator alege doar una din gramezile existente si efectueaza o mutare doar in aceasta gramada (ia un numar de pietre).
 
_Teorema_: Pentru un anumit joc $G$ care este suma jocurilor {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} dupa cum a fost definita mai sus o stare {$v = (v{~1~},v{~2~}, ..., v{~N~})$} este pierzatoare daca si numai daca {$mex(x1) xor mex(x2) xor ... xor mex(xn) = 0$}.
 
h4. _Demonstratie_: Vom arata ca jocul $G$ este echivalent cu un joc $NIM$ cu $N$ gramezi in care gramada $i$ are {$mex(v{~i~})$} pietre. In jocul NIM putem alege o gramada cu g(xi) pietre si sa luam cateva astfel incat in gramada sa ramana a<g(xi) pietre. Acestei mutari in jocul NIM ii corespunde o mutare in jocul compus G in care se alege jocul individual Gi si se muta din stare curenta xi intr-o stare y cu g(y)=a. Deoarece a<g(xi) va exista mereu o astfel de stare y. Nu vom lua in considerare mutarile cand dintr-o stare xi se muta intr-o stare y cu g(y)>g(xi) deoarece urmatorul jucator poate muta din starea y intr-o stare z cu g(z)=g(xi) si anuleaza practic mutarea precedentului. (de editat)
 
h3. Adunarea or
 
Sa presupunem ca dorim sa adunam jocurile {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} in asa fel incat la fiecare pas jucatorul care urmeaza poate sa isi aleaga oricate jocuri si sa faca o mutare in fiecare din jocurile alese. Ultimul jucator care muta castiga. Un astfel de caz se intalneste in problema 'Pioni':problema/pioni.
 
_Teorema_: Pentru un anumit joc $G$ care este suma jocurilor {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} dupa cum a fost definita mai sus o stare {$v = (v{~1~},v{~2~}, ..., v{~N~})$} este pierzatoare daca si numai daca {$mex(v{~1~}) = mex(v{~2~}) = ... = mex(v{~N~}) = 0$}.
 
_Demonstratie_: Daca toate starile {$v{~1~}$}, {$v{~2~}$}, ..., {$v{~n~}$} sunt terminale atunci starea $v$ este pierzatoare si {$mex(v{~1~}) = mex(v{~2~}) = ... = mex(v{~N~}) = 0$}, deci teorema este adevarata. Daca starea $x$ contine cel putin un joc cu valoarea Sprague-Grundy nenula se fac mutari in toate aceste jocuri astfel incat sa lase adversarul intr-o stare in care toate jocurile au valoarea SG egala cu {$0$}. Dintr-o astfel de stare, orice mutare ar face adversarul va exista cel putin un joc cu valoarea SG nenula.