|
      Varianta de NIM implementata de mine se poate scrie si sub forma N( n1 , n2 , n3 , n4 , n5 ). Este un joc NIM cu 5 gramezi si n1 obiecte in gramada 1, n2 obiecte in gramada 2, etc. Se poate considera ca jocul este compus de fapt din 5 jocuri simple, cu o singura gramada, care se vor juca simultan. Considerand jocurile simple N(n1), N(n2), N(n3), N(n4), N(n5), jocul compus va fi obtinut prin relatia:
            N(n1,n2,n3,n4,n5)=N(n1) N(n2) N(n3) N(n4) N(n5)
      Pentru a juca jocul compus, cei doi jucatori aleg pe rand unul din jocurile alcatuitoare si efectueaza o mutare in el. Atunci cand unul din jocuri ajunge pe pozitie terminala, jucatorii vor face mutari in jocurile neterminate pana cand si acestea ajung intr-o pozitie terminala. La fel ca la jocurile simple, cel care va face ultima mutare va castiga.
      Mutarile efectuate pot fi impartite in doua submultimi :
1. S = multimea mutarilor sigure
2. P = multimea mutarilor periculoase
      Cele 2 multimi au urmatoarele proprietati:
1. 0 apartine lui S
2. Din orice element din P exista o mutare catre un element din S
3. Toate mutarile dintr-o pozitie din S rezulta intr-un element din P
      Strategia de castig este sa muti intotdeauna spre un element din S, adversarul fiind astfel obligat sa mute catre o pozitie din P.
      Prezentarea algoritmului
- se construieste o matrice binara astfel: se ia numarul de obiecte din fiecare gramada si se trece in binar.
- atata timp cat mai am cel putin o gramada nevida se efectueaza
(XOR) pe fiecare coloana si se analizeaza rezultatele:
- daca exista cel putin o coloana pe care se obtine 1 inseamna ca suntem pe o pozitie din P, dar putem muta spre o pozitie din S.
Aleg urmatoarea mutare astfel: pentru ca am un joc compus trebuie sa aleg un joc simplu din jocurile care il alcatuiesc si sa efectuez mutarea in acest joc simplu. Un joc simplu inseamna de fapt o gramada.
- aleg prima coloana din cele pe care am obtinut 1 prin XOR
- aleg prima linie de pe aceasta coloana care are 1
- parcurg aceasta linie:
- daca elementul apartine unei coloane pe care am obtinut 1 prin XOR il inversez (daca e 0 va deveni 1, daca e 1 va deveni 0)
- altfel, daca nu apartine unei coloane de acest tip il las neschimbat
- am modificat linia din matrice si trebuie sa modific numarul de obiecte din gramada aleasa.
- altfel daca pe toate coloanele se obtine 0 suntem pe o pozitie din S dar putem muta doar spre o pozitie din P. In acest caz pot lua din orice gramada, oricate obiecte doresc, deoarece singura sansa sa ajung iar pe o pozitie din S ar fi sa iau obiecte din doua gramezi diferite si asta nu este posibil.
- in momentul in care toate gramezile sunt vide verific cine a facut mutarea castigatoare: jucatorul uman sau calculatorul.
|