Revizia anterioară Revizia următoare
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 G1, G2, ..., GP. 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 Gi, 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."
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 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.
Notiuni de baza | Jocul NIM | Numere Sprague-Grundy |
Adunarea jocurilor | w-numere | Aplicatii si probleme
