Teoria jocurilor

(Categoria Teoria jocurilor, Autor Filip Cristian Buruiana)

• Capitole
• Notiuni de baza
• Jocul NIM
• Numere Sprague-Grundy
• Adunarea jocurilor
• w-numere
• Aplicatii si probleme

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, 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 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.

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.

Functia w

Notiuni de baza | Jocul NIM | Numere Sprague-Grundy |
Adunarea jocurilor | w-numere | Aplicatii si probleme