h2(#adunare). Adunarea jocurilor
h1. Teoria jocurilor
(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
h2. Adunarea jocurilor
Valorile Sprague-Grundy reprezinta o generalizare fata de algoritmul de programare dinamica in cazul jocului cu un singur pion, deoarece cu ajutorul acestor valori pot fi combinate mai multe jocuri. De exemplu, putem presupune ca in graful orientat sunt mai multi pioni in loc de unul singur si ca o mutare consta in deplasarea unui pion din nodul in care se afla intr-un nod adiacent. La fel ca mai sus, cine nu mai poate muta pierde. In acest caz, castigatorul in cazul unui joc perfect nu se poate determina pe baza programarii dinamice in timp polinomial. Mai mult, determinarea castigatorului nu este deloc triviala, asa cum era in cazul jocului cu un pion. Atunci cand combinam (adunam) mai multe jocuri elementare, rezultatul poate fi determinat in mod eficient cu ajutorul valorilor Sprague-Grundy.
In cazul jocului cu mai multi pioni, in loc sa consideram un singur graf, putem considera (conceptual) mai multe grafuri de joc identice, in fiecare dintre acestea aflandu-se cate un pion. Acum, o mutare inseamna alegerea unui graf si deplasarea pionului din graful ales conform regulilor pentru un singur pion. In acest fel, am separat jocul initial in mai multe jocuri _independente_. Stim rezultatul pentru fiecare joc _independent_ in parte si dorim sa determinam castigatorul pentru jocul cu mai multe grafuri. Aceasta inseamna ca dorim sa combinam rezultatele partiale pentru a determina rezultatul general. Pentru aceasta vom folosi _adunarea grafurilor de joc_.
Sa presupunem ca avem $P$ jocuri notate {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$}, pe care dorim sa le adunam. Fiecare din cele $P$ 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 $P$ jocuri obtinem un nou joc {$G$} pentru care o stare (nod in graful asociat) este un {$P$}-uplu {$(v{~1~},v{~2~}, ...,v{~P~})$} 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 de programare dinamica (prezentat mai sus) pentru graful asociat jocului {$G$}. Se observa insa ca acest graf are {$|V{~1~}|*|V{~2~}|* ...*|V{~P~}|$} noduri, deci algoritmul nu este eficient.
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).
(vmenu)*(section) '*Adunarea xor*':teoria-jocurilor/adunarea-xor#xor
* 'Adunarea or':teoria-jocurilor/adunarea-or#or
* 'Adunarea almost or':teoria-jocurilor/adunarea-almost#almost
* 'Adunarea and':teoria-jocurilor/adunarea-and
* 'Adunarea also':teoria-jocurilor/adunarea-also
h3(#xor). Adunarea xor
_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$}.
Vom aduna jocurile {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$} astfel incat la fiecare pas jucatorul care urmeaza trebuie sa isi aleaga exact un joc si sa faca o mutare in jocul respectiv. Jucatorul care nu mai poate muta pierde. Un astfel de joc este generalizarea jocului cu un pion din capitolul precedent si se intalneste in problema 'Pawns':problema/pawns, data la concursul national Bursele Agora. Pentru a determina castigatorul in cazul acestui joc, ne vom folosi de urmatoarea teorema:
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)
_Teorema_: Fie jocurile independente {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$} si fie {$G$} suma acestor jocuri. Daca la fiecare pas alegem un singur joc si efectuam o mutare in jocul ales, atunci o stare {$(v{~1~},v{~2~}, ...,v{~P~})$} din jocul {$G$} este pierzatoare daca si numai daca {$mex(v{~1~}) xor mex(v{~2~}) xor ... xor mex(v{~P~}) = 0$}, unde {$v{~i~}$} reprezinta starea din jocul {$G{~i~}$}.
h3. Adunarea or
_Demonstratie_: Demonstratia este similara cu cea a jocului {$NIM$}, cele doua jocuri fiind asemanatoare. Starile care au suma-xor {$0$} sunt pierzatoare, celelalte stari fiind castigatoare.
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.
Dintr-o stare pierzatoare putem ajunge numai in stari castigatoare. Prin reducere la absurd putem presupune ca mutam dintr-o valoare {$x = mex(v{~i~})$} intr-o valoare {$x' = mex(v'{~i~})$}. Daca notam cu $S$ suma xor a starilor din jocurile diferite de {$i$}, atunci avem {$S xor x = 0$}, deci {$S = x$}. Dar trebuie sa avem si {$S xor x' = 0$}, deci $S$ este egal si cu {$x'$}, ceea ce implica {$x = x'$}. Aceasta egalitate nu poate avea loc, deoarece dintr-o stare nu putem ajunge intr-o stare adiacenta care sa aiba aceeasi valoarea Sprague-Grundy (conform definitiei functiei {$mex$}).
_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$}.
Din orice stare castigatoare putem ajunge intr-o stare pierzatoare.
_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.
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 {$mex(x{~i~})$} 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)
p{margin:1em; padding: 0.5em; height: 45px; border-top: 1px solid silver;}=.
'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
