Teoria jocurilor

(Categoria Teoria jocurilor, Autor Filip Cristian Buruiana)

w-numere

In capitolul precedent am observat diferite modalitati de a aduna jocuri. Jucatorul care efectua ultima mutare in aceste jocuri compuse castiga. Putem extinde insa complexitatea jocurilor analizate, considerand ca pentru un joc compus G castigatorul este cel care castiga primul unul dintre jocurile independente care compun jocul G. Acest tip de joc este numit sugestiv "The Winner takes it all" (WTIA).

Definitie: Fie G suma jocurilor G₁, G₂, ..., G_P. Jucatorul aflat la mutare alege unul din jocurile care il compun pe G si efectueaza o mutare in jocul ales. Intr-un joc de tip WTIA, daca unul din jucatori pierde un joc independent G_i, atunci el pierde intreg jocul G.

Jocul NIM pe nivele

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.

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.

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.

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.

Teorema: Fie un joc G definit ca adunarea de tip WTIA a jocurilor G₁, G₂, ... G_p. Pozitia x din jocul G, care este un p-uplu de forma (x₁, x₂, ... 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₁) xor w(x₂) xor ... xor w(x_p) = 0.

Demonstratie: Vom verifica daca pentru aceasta impartire sunt indeplinite conditiile pentru P-pozitii si N-pozitii, prezentate aici. 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₁) xor w(x₂) 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.

Aplicatie pe jocul NIM pe nivele

infoarena informatica de performanta