h4. Jocul NIM pe nivele

!<teoria-jocurilor/w-numere?leveled_nim.jpg 55%!

Jocul $NIM$ este un caz trivial daca se joaca dupa regulile {$WTIA$}, deoarece jucatorul care muta primul poate alege o gramada oarecare si sa ia toate pietrele din aceasta gramada, castigand astfel un joc independent (gramada din care s-a facut mutarea) si, implicit, tot jocul cu mai multe gramezi. Putem introduce insa urmatoarea variatie a jocului $NIM$, care nu este deloc triviala: "Fie $N$ supergramezi de monede, fiecare supergramada fiind formata dintr-un numar oarecare de gramezi asezate una peste cealalta. La fiecare mutare un jucator alege o supergramada si ia cel putin o moneda din cea mai de sus gramada nevida. Cand un jucator ia ultimile monede dintr-o supergramada jocul se termina si acesta este declarat castigator."

Sa consideram un exemplu cu doua supergramezi. Prima dintre acestea contine gramezi de dimensiune {$4$}, {$9$} si {$3$}, de la baza inspre varf, iar a doua supergramada este compusa din doua gramezi de cate $2$ si respectiv $5$ pietre. Primul jucator poate alege sa elimine pietre din prima supragramada sau din cea de a doua. In cazul in care alege sa faca mutarea din prima supragramada, atunci el poate lua intre una si trei pietre din gramada din varf. Daca ia trei pietre, gramada de sus se goleste, iar noua gramada de la varf din care se vor face mutari in prima supergramada va contine $9$ pietre.
 
h4. Clasificarea pozitiilor
 
In acest joc $NIM$ pe nivele identificam urmatoarele pozitii speciale (numite _superpozitii_):
 
* _superpierzatoare_, in care exista o supergramada care nu contine nicio gramada. In acest caz, jucatorul aflat la mutare este considerat pierzator.
* _supercastigatoare_, in care jucatorul la rand va castiga dintr-o singura mutare. Toate pozitiile care au cel putin o supergramada formata dintr-o singura gramada nevida sunt supercastigatoare deoarece un jucator poate goli aceasta supergramada la urmatoarea mutare, castigand jocul.
 
Toate celelalte pozitii (in care fiecare supergramada contine cel putin doua gramezi) sunt considerate normale.
 
Daca jucatorul aflat la mutare gaseste jocul intr-o pozitie superpierzatoare atunci a pierdut. Daca in schimb pozitia este una supercastigatoare, el va castiga dintr-o singura mutare. Daca jucatorul se afla intr-o pozitie normala, atunci el poate aduce jocul in alta pozitie normala sau intr-o pozitie supercastigatoare. Aducerea adversarului intr-o pozitie supercastigatoare va duce insa la pierderea jocului. In consecinta, jucatorul aflat in pozitii normale va muta doar in alte pozitii normale. Se observa ca atunci cand un jucator nu mai poate muta intr-o pozitie normala pierde jocul deoarece va fi obligat sa mute intr-o pozitie supercastigatoare.
 
h4. Functia w
 
Pentru a determina daca dintr-o pozitie jucatorul aflat la mutare are strategie de castig vom introduce o functie {$w$} astfel:
 
_Definitie_: Functia $w$ este o functie definita pe multimea starilor unui joc cu valori in multimea numerelor naturale reunita cu indicatorii speciali $SC$ (pentru o pozitie supercastigatoare) si $SP$ (pentru una superpierzatoare). Functia w se obtine astfel:
 
# {$w(x) = SP$}, daca $x$ este o pozitie superpierzatoare
# {$w(x) = SC$}, daca exista o stare $u$ astfel incat din $x$ sa se poata ajunge in $u$ printr-o mutare si {$w(u) = SP$}
# {$w(x) = minim(n ≥ 0 | n diferit de w(u), oricare ar fi u stare vecina a lui x pentru care w(u) este numar natural)$}. Prin stare vecina se intelege ca se poate ajunge dintr-o singura mutare din $x$ in {$u$}.
 
Altfel spus, pozitiile superpierzatoare vor avea asociat indicatorul $SP$, iar cele supercastigatoare indicatorul $SC$. Eliminand toate aceste pozitii speciale vom obtine un graf in care toate pozitiile sunt normale. Daca aplicam algoritmul functiei $mex$ de determinare a valorilor Sprague-Grundy pe pozitiile ramase obtinem chiar valorile returnate de functia {$w$} pentru aceste pozitii.
 
p{padding:0.1em 0.5em 0.5em 0.5em; margin:0.5em; border: 1px solid #666666;background-color:#E2E2E2}.
_Teorema_: Asemanator cu functia {$mex$}, o pozitie $x$ este pierzatoare daca si numai daca {$w(x) = SP$} sau {$w(x) = 0$}.
 
_Demonstratie_: Daca {$w(x) = SP$}, atunci evident $x$ este o pozitie de pierdere. Daca {$w(x)$} este numar natural si {$w(x) > 0$}, atunci este posibil ca jucatorul la mutare sa mute intr-o pozitie $y$ cu {$w(y) = 0$} (conform definitiei). Dintr-o pozitie {$w(x) = 0$} se poate muta numai in pozitii supercastigatoare sau in pozitii cu {$w(x) > 0$} (intr-o stare superpierzatoare nu se poate muta, deoarece in aceste stari se poate ajunge doar din stari supercastigatoare). Dat fiind faptul ca jocul este finit, se va ajunge la situatia in care din pozitia {$w(x) = 0$} nu mai exista decat mutari in pozitii {$SC$}.
 
p{padding:0.1em 0.5em 0.5em 0.5em; margin:0.5em; border: 1px solid #666666;background-color:#E2E2E2}.
_Teorema_: Fie un joc $G$ definit ca adunarea de tip $WTIA$ a jocurilor {$G{~1~}$}, {$G{~2~}$}, ... {$G{~p~}$}. Pozitia {$x$} din jocul {$G$}, care este un {$p$}-uplu de forma {$(x{~1~}, x{~2~}, ... x{~p~})$}, unde {$x{~i~}$} este starea din jocul {$G{~i~}$}, este pierzatoare daca si numai daca cel putin una din urmatoarele conditii este indeplinita:
 
1. exista un joc $i$ astfel incat {$w(x{~i~}) = SP$}
2. pentru orice joc $i$, {$w(x{~i~})$} este numar natural. In plus, {$w(x{~1~}) xor w(x{~2~}) xor ... xor w(x{~p~}) = 0$}.
 
_Demonstratie_: Vom verifica daca pentru aceasta impartire sunt indeplinite conditiile pentru $P$-pozitii si $N$-pozitii, prezentate 'aici':teoria-jocurilor/notiuni#pozitii. Daca exista un joc $i$ astfel incat {$w(x{~i~}) = SP$}, atunci starea $x$ este una terminala si este de pierdere. Mai mult, din orice pozitie pierzatoare neterminala conform impartirii de mai sus, oricum am efectua o mutare, vom ajunge intr-o pozitie castigatoare.
 
Toate pozitiile terminale x au un subjoc xi care este SP, altfel s-ar mai putea efectua mutari. Daca un jucator este intr-o pozitie pierzatoare atunci w(x) = SP sau {$w(x{~1~}) xor w(x{~2~}) xor ... xor w(x{~p~}) = 0$}. Primul caz a fost analizat mai sus. Daca un jucator muta in orice subjoc k atunci fie va muta intr-o pozitie supercastigatoare in acel joc, fie va muta intr-o pozitie y cu w(y) � w(xk). In abele cazuri va muta in pozitii castigatoare.
Daca un jucator este intr-o pozitie castigatoare atunci w(x) = SC sau w(x1) xor w(x2) xor ... xor w(xp) diferit de {$0$}. In primul caz va exista un subjoc xk astfel incat w(xk) = SC. Un jucator va putea muta in acest subjoc intr-o pozitie superpierzatoare. Daca suma nim a w-numerelor subjocurilor este diferita de 0 atunci un jucator poate gasi cu usurinta o mutare care sa o modifice in 0, procedand similar jocului Nim.
 
h4. Aplicatie pe jocul NIM pe nivele
 

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 |