h2(#SG). Numere Sprague-Grundy

Majoritatea jocurilor impartiale cu doi jucatori 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."

Majoritatea jocurilor impartiale cu doi jucatori se pot 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."

!teoria-jocurilor?img001.jpg!

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.

De exemplu, pentru graful din figura de mai sus, daca pionul se afla initial in nodul 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, 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.

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.

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.

_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)$}.