h2. Numere Sprague-Grundy
h1. Teoria jocurilor
(Categoria _Teoria jocurilor_, Autor _Filip Cristian Buruiana_)
Majoritatea jocurilor impartiale se pot reduce la urmatorul joc: "Se considera un graf orientat aciclic care contine pioni in anumite noduri. Cei doi jucatori muta alternativ. Prin mutare se intelege miscarea unui pion aflat in nodul $x$ intr-un nod {$y$}, astfel incat sa existe un arc care iese din nodul $x$ si intra in nodul {$y$}. Jucatorul care nu mai poate muta pierde."
(toc)*{text-align:center} *Capitole*
* 'Notiuni de baza':teoria-jocurilor
* 'Jocul NIM':teoria-jocurilor/jocul-nim
* '*Numere Sprague-Grundy*':teoria-jocurilor/numere-SG
* 'Adunarea jocurilor':teoria-jocurilor/adunarea-jocurilor
* 'w-numere':teoria-jocurilor/w-numere
* 'Aplicatii si probleme':teoria-jocurilor/probleme
!teoria-jocurilor?img001.jpg!
h2. Numere Sprague-Grundy
De exemplu, pentru graful din figura de mai sus, daca exista doi pioni, unul in nodul $1$ si celalalt in nodul {$2$}, primul jucator aflat la mutare are strategie sigura de castig.
Alaturi de jocul {$NIM$}, numerele Sprague-Grundy au o importanta deosebita in analiza jocurilor impartiale. Majoritatea acestora se poate reduce la urmatorul joc: "Se considera un graf orientat aciclic care contine un pion intr-un nod oarecare. Cei doi jucatori muta alternativ. Prin mutare se intelege miscarea pionului din nodul in care se afla intr-un nod adiacent. Jucatorul care nu mai poate muta pierde."
Cum graful este aciclic, jocul este finit si are intotdeauna un castigator. Daca in graf exista un singur pion, castigatorul poate fi determinat prin metoda programarii dinamice. Astfel, {$win{~x~}$} va fi _true_ daca si numai daca primul jucator aflat la mutare are strategie de castig atunci cand pionul se afla in nodul {$x$}. Astfel, {$win{~x~}$} = _true_ daca si numai daca exista un nod $y$ astfel incat sa existe arc intre $x$ si $y$ si {$win{~y~}$} = _false_. In caz contrar, {$win{~x~}$} = _false_. Pentru exemplul de mai sus, atunci cand avem un singur pion, {$win{~2~}$} = _true_, iar {$win{~1~}$} si {$win{~4~}$} vor fi _false_. Valorile vectorului $win$ se vor calcula in ordinea din sortarea topologica a nodurilor, in complexitate {$O(N + M)$}, unde $N$ este numarul de noduri iar $M$ numarul de muchii din graful dat.
!<teoria-jocurilor/numere-SG?img001.jpg 75%!
Folosind teoria dezvoltata independent de Roland Percival Sprague (1936) si Patrick Michael Grundy (1939), putem reduce complexitatea jocului cu mai multi pioni la complexitatea analizei jocului cu un pion. Ca in algoritmul de programare dinamica de mai sus, se incearca determinarea pozitiilor castigatoare si a celor necastigatoare pentru un singur pion.
De exemplu, pentru graful din figura alaturata, daca pionul se afla initial in nodul $1$, primul jucator aflat la mutare va pierde in cazul unui joc perfect.
Cum graful este aciclic, jocul este finit si are intotdeauna un castigator. Daca in graf exista un singur pion, castigatorul poate fi determinat prin metoda programarii dinamice. Astfel, {$win{~x~}$} va fi _true_ daca si numai daca primul jucator aflat la mutare are strategie de castig atunci cand pionul se afla in nodul {$x$}. Astfel, {$win{~x~}$} = _true_ daca si numai daca exista un nod $y$ astfel incat sa existe arc intre $x$ si $y$ si {$win{~y~}$} = _false_. In caz contrar, {$win{~x~}$} = _false_. Pentru exemplul de mai sus, {$win{~2~}$} = _true_, iar {$win{~1~}$} si {$win{~4~}$} vor fi _false_. Valorile vectorului $win$ se vor calcula in ordinea din sortarea topologica a nodurilor, in complexitate {$O(N + M)$}, unde $N$ este numarul de noduri iar $M$ numarul de muchii din graful dat.
_Definitie_: Functia Sprague-Grundy pentru un graf {$G = (V, E)$} este o functie {$mex$} ({_minimum excludant_}) definita pe $V$ cu valori in multimea numerelor naturale, unde {$mex(x) = minim(n ≥ 0 |n diferit de g(y), oricare ar fi y vecin al lui x)$}.
Totusi, daca in graf ar exista mai multi pioni, problema determinarii castigatorului nu mai poate fi rezolvata prin programare dinamica. Folosind teoria dezvoltata independent de Roland Percival Sprague (1936) si Patrick Michael Grundy (1939), putem reduce complexitatea jocului cu mai multi pioni la complexitatea analizei jocului cu un pion. Ca in algoritmul de programare dinamica de mai sus, se incearca determinarea pozitiilor castigatoare si a celor necastigatoare pentru un singur pion.
Altfel spus, valoarea Sprague-Grundy pentru un nod $x$ al grafului aciclic dat este cel mai mic numar natural care nu este atribuit niciunui vecin al nodului {$x$}. Valorile Sprague-Grundy pentru nodurile grafului de mai jos sunt scrise cu rosu in dreptul fiecarui nod.
_Definitie_: Functia Sprague-Grundy pentru un graf {$G = (V, E)$} este o functie {$mex$} ({_minimum excludant_}) definita pe $V$ cu valori in multimea numerelor naturale, unde {$mex(x) = minim(n ≥ 0 |n diferit de mex(y), oricare ar fi y vecin al lui x)$}.
!teoria-jocurilor?img002.jpg!
!>teoria-jocurilor/numere-SG?img002.jpg 75%!
Altfel spus, valoarea Sprague-Grundy pentru un nod $x$ al grafului aciclic dat este cel mai mic numar natural care nu este atribuit niciunui vecin al nodului {$x$}. Atribuirea valorilor se face incepand cu nodurile terminale, carora le este asociata valoarea {$0$}. Valorile Sprague-Grundy pentru nodurile grafului de mai jos sunt scrise cu rosu in dreptul fiecarui nod.
Se observa ca pozitiile care au valoarea Sprague-Grundy egala cu $0$ sunt _pierzatoare_, in timp ce restul pozitiilor sunt _castigatoare_. Aceasta inseamna ca daca {$mex(x) = 0$}, in jocul cu un singur pion situat in nodul $x$ jucatorul care muta primul nu are strategie sigura de castig, iar daca {$mex(x)$} este diferit de $0$ atunci jucatorul care muta primul va castiga intotdeauna, in cazul in care joaca optim. Aceasta afirmatie este usor de demonstrat: daca {$mex(x)$} este diferit de $0$ atunci exista un nod {$y$}, vecin al lui {$x$}, astfel incat {$mex(y)$} sa fie egal cu $0$. In consecinta, primul jucator il va aduce intotdeauna pe adversarul sau in noduri care au valoarea Sprague-Grundy egala cu $0$. Mai mult, primul jucator va ramane intotdeauna in noduri cu valoare diferita de $0$, deoarece al doilea jucator nu il poate forta sa ajunga in aceste noduri: din nodurile cu valoarea $0$ se poate ajunge doar in noduri cu valoarea nenula. In concluzie, jucatorul al doilea va pierde, deoarece va fi adus intr-un nod final (fara urmasi). La o analiza mai atenta se observa ca starile de joc respecta proprietatile pozitiilor castigatoare si pierzatoare, enuntate 'aici':teoria-jocurilor.
Se observa ca daca {$mex(x) = 0$}, in jocul cu un singur pion situat in nodul $x$ jucatorul care muta primul nu are strategie sigura de castig, iar daca {$mex(x)$} este diferit de $0$ atunci jucatorul care muta primul va castiga intotdeauna, in cazul in care joaca optim. Aceasta afirmatie este usor de demonstrat: daca {$mex(x)$} este diferit de $0$ atunci exista un nod {$y$}, vecin al lui {$x$}, astfel incat {$mex(y)$} sa fie egal cu $0$. In consecinta, primul jucator il va aduce intotdeauna pe adversarul sau in noduri care au valoarea Sprague-Grundy egala cu $0$. Mai mult, primul jucator va ramane intotdeauna in noduri cu valoare diferita de $0$, deoarece al doilea jucator nu il poate forta sa ajunga in aceste noduri: din nodurile cu valoarea $0$ se poate ajunge doar in noduri cu valoarea nenula. In consecinta, jucatorul al doilea va pierde, deoarece va fi adus intr-un nod final (fara urmasi).
Valorile Sprague-Grundy se pot calcula si pentru jocuri in care nu apar precizate explicit grafuri. Fiecare stare posibila a jocului va fi un nod in graf, iar un arc va indica o posibila mutare: o trecere de la o stare la alta, conform regulilor existente.
Valorile Sprague-Grundy se pot calcula si pentru jocuri in care nu apar precizate explicit grafuri. Fiecare stare posibila a jocului va fi un nod in graf, iar un arc va indica o posibila mutare: o trecere de la o stare la alta, conform regulilor existente.
p{margin:1em; padding: 0.5em; height: 45px; border-top: 1px solid silver;}=.
'Notiuni de baza':teoria-jocurilor | 'Jocul NIM':teoria-jocurilor/jocul-nim | '*Numere Sprague-Grundy*':teoria-jocurilor/numere-SG |
'Adunarea jocurilor':teoria-jocurilor/adunarea-jocurilor | 'w-numere':teoria-jocurilor/w-numere | 'Aplicatii si probleme':teoria-jocurilor/probleme
