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

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

public

protected