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 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."
Notiuni de baza | Jocul NIM | Numere Sprague-Grundy |
Adunarea jocurilor | w-numere | Aplicatii si probleme
