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$}, {$2$} 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
In figura alaturata exista doua supergramezi. Prima dintre ele contine gramezi de dimensiune {$4$}, {$2$} si {$3$}, de la baza inspre varf, iar a doua supergramada este compusa din doua gramezi de cate $2$ si respectiv $5$ pietre.
In acest joc exista urmatoarele pozitii speciale:
* _superpierzatoare_: daca exista vreo supergramada goala atunci jocul este incheiat
* _supercastigatoare_: in care jucatorul la rand va castiga dintr-o singura mutare. Toate pozitiile care nu sunt superpierzatoare si au cel putin o supergramada formata dintr-o singura gramada nevida sunt supercastigatoare deoarece un jucator poate goli aceasta supergramada la urmatoarea mutare.
* _superpierzatoare_, daca exista vreo supergramada goala atunci jocul este incheiat
* _supercastigatoare_, in care urmatorul jucator va castiga dintr-o singura mutare. Toate pozitiile care nu sunt superpierzatoare si au cel putin o supergramada cu o singura gramada nevida sunt supercastigatoare deoarece un jucator poate goli aceasta supergramada la urmatoarea mutare.
Toate celelalte pozitii sunt considerate normale.
Daca jucatorul la mutare este intr-o superpozitie stie cum trebuie sa joace. O mutare dintr-o pozitie normala poate duce in alta pozitie normala sau intr-o pozitie supercastigatoare. Dar cum mutarea intr-o pozitie supercastigatoare va duce la pierderea jocului putem considera numai mutarile care duc in alte pozitii normale. Asfel cand un jucator nu mai poate muta intr-o pozitie normala pierde jocul deoarece va trebui sa mute intr-o pozitie supercastigatoare.
h4. Functia w
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
