h1. Teoria jocurilor
h2(#nim). Jocul NIM
(Categoria _Teoria jocurilor_, Autor _Filip Cristian Buruiana_)
Probabil cel mai cunoscut joc impartial este jocul de {$NIM$}. In acest joc, se considera $N$ gramezi, fiecare gramada avand un numar de pietre. La fiecare pas, jucatorul aflat la mutare elimina un numar nenul de pietre (eventual toate) dintr-o singura gramada. Jucatorii muta alternativ. Castigatorul este cel care ia ultimele pietre.
(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. Jocul NIM
!>teoria-jocurilor/jocul-nim?nim.jpg 90%!
Probabil cel mai cunoscut joc impartial este jocul {$NIM$}. In acest joc, se considera $N$ gramezi, fiecare gramada avand un numar de pietre. La fiecare pas, jucatorul aflat la mutare elimina un numar nenul de pietre (eventual toate) dintr-o singura gramada. Jucatorii muta alternativ. Castigatorul este cel care ia ultimele pietre. De obicei, jocul $NIM$ se joaca cu $3$ gramezi de pietre, insa strategia de castig este aceeasi indiferent de numarul gramezilor.
h4. Operatia _exclusive-or_
!<teoria-jocurilor/jocul-nim?tabel.jpg 80%!
Pentru a determina strategia de castig ne vom folosi de operatia _xor_ ({_exclusive or_}) si proprietatile ei. Aceasta operatie se realizeaza prin operatorul $^$ in C/C++, si prin $xor$ in Pascal. Ca operatie pe biti, ea poate fi interpretata ca adunare in baza $2$ fara transport, dupa cum reiese din tabelul alaturat.
Atunci cand facem _xor_ intre numere naturale trebuie mai intai sa transformam aceste numere in baza $2$, si apoi sa adunam fara transport bitii de pe fiecare pozitie. De exemplu, $1 xor 7 xor 5 = 3$, deoarece avem:
{$1 = (001){~2~}$} {$xor$}
{$7 = (111){~2~}$}
{$5 = (101){~2~}$}
______________
{${@(011)@}{~2~} = 3$}
h4. Strategia de castig
Pe baza operatiei _xor_, strategia de castig pentru $NIM$ poate fi formulata conform urmatoarei teoreme:
De obicei, jocul NIM se joaca cu $3$ gramezi de pietre, insa strategia de castig este aceeasi indiferent de numarul gramezilor. Pentru a determina aceasta strategie vom folosi urmatoarea teorema:
_Teorema_: Fie $N$ gramezi. Prima gramada are {$x{~1~}$} pietre, cea de a doua {$x{~2~}$}, si asa mai departe, pana la ultima care are {$x{~N~}$} pietre. O astfel de pozitie este pierzatoare in jocul de $NIM$ daca si numai daca _suma-xor_ a numerelor de pietre din gramezi este {$0$}, adica daca {$x{~1~} xor x{~2~} ... xor x{~N~} = 0$}.
Pentru a demonstra aceasta teorema, trebuie sa aratam ca dintr-o stare cu suma-xor egala cu $0$ (pierzatoare), oricum am muta, nu putem ajunge decat intr-o stare cu suma-xor nenula (castigatoare), si ca dintr-o stare castigatoare putem efectua o mutare in mod convenabil astfel incat sa ajungem intr-o stare de pierdere.
Sa presupunem prin reducere la absurd ca dintr-o stare cu suma-xor $0$ putem ajunge in alta stare care are suma-xor tot $0$. Selectam o gramada oarecare cu $y$ pietre si dorim sa eliminam un numar de pietre din aceasta gramada. Daca notam cu $S$ suma-xor a numerelor de pietre din celelalte $N-1$ gramezi neselectate, atunci avem {$S xor y = 0$}. Dar {$a xor b = 0$} daca si numai daca {$a = b$}, deci {$S = y$}. Daca din gramada selectata eliminam $x$ pietre, {$0 < x ≤ y$}, pentru a ajunge intr-o stare tot cu suma-xor $0$ trebuie sa avem {$S xor (y-x) = 0$}, echivalent cu {$S = y-x$}. De aici si din {$S = y$} rezulta ca {$x = 0$}, fals, deoarece nu putem elimina $0$ pietre. Deci oricum am efectua o mutare dintr-o stare de pierdere vom ajunge intr-o stare castigatoare.
Ramane de demonstrat ca din orice stare de castig putem sa aducem adversarul intr-o stare pierzatoare. Fie $S$ suma-xor a marimilor celor $N$ gramezi. Daca exista o gramada cu $y$ pietre astfel incat {$y > y xor S$}, atunci putem elimina {$y - y xor S$} pietre din aceasta gramada, ramanand cu {$y - (y - y xor S) = y xor S$} pietre. Din gramada cu $y$ pietre am obtinut o gramada cu {$y xor S$} pietre, deci noua suma-xor va fi obtinuta din cea veche ({$S$}) xorata cu ea insasi: {$(... xor y) xor S = S xor S = 0$}. In consecinta, daca exista o gramada cu proprietatea de mai sus, atunci putem ajunge din orice stare de castig in una de pierdere. Fie $p$ pozitia celui mai semnificativ bit din reprezentarea binara a lui {$S$}. Printre cele $N$ gramezi, va exista cel putin una care are bitul de pe pozitia $p$ egal cu $1$ (altfel bitul $p$ din $S$ ar fi fost {$0$}). Fie $y$ numarul de pietre dintr-o astfel de gramada. Bitii de $1$ din $y$ si $S$ de pe pozitia $p$ se vor anula pentru ca {$1 xor 1 = 0$}. Astfel, vom avea {$y > y xor S$}.
!teoria-jocurilor/jocul-nim?xor.jpg 90%!
In consecinta, putem ajunge din orice stare de castig intr-o stare de pierdere. Teorema este astfel demonstrata.
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
Pentru a demonstra aceasta teorema, trebuie sa aratam ca dintr-o stare cu _suma-xor_ egala cu $0$, prin orice mutare am face, nu putem ajunge decat intr-o stare cu suma-xor nenula, si ca dintr-o stare cu suma-xor nenula putem efectua o mutare in mod convenabil astfel incat sa ajungem intr-o stare cu suma-xor 0.
