h2(#adunare). Adunarea jocurilor

Sa presupunem ca avem $N$ jocuri notate {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} pe care vrem sa le adunam. Fiecare din cele $N$ jocuri poate fi reprezentat ca un graf orientat fara circuite in care multimea nodurilor (notata {$V{~i~}$} pentru jocul {$i$}) este data de multimea starilor iar multimea arcelor (notata {$E{~i~}$} pentru jocul {$i$}) este data de perechile ordonate de stari adiacente (exista arc de la $x$ la $y$ daca se poate ajunge printr-o mutare din starea $x$ in starea $y$). Adunand cele $N$ jocuri obtinem un nou joc {$G$} pentru care o stare (nod in graful asociat) este un N-uplu {$(v{~1~},v{~2~}, ..., v{~N~})$} care ne precizeaza starea curenta pentru fiecare joc individual ({$v{~i~}$} este starea curenta in jocul $i$). Pentru a afla daca pentru o anumita stare din jocul $G$ exista sau nu strategie sigura de castig am putea aplica algoritmul simplu de programare dinamica (prezentat mai sus) pentru graful asociat jocului {$G$}. Se observa insa ca acest graf are {$|V{~1~}|*|V{~2~}|* ...*|V{~N~}|$} noduri, deci algoritmul nu este eficient.

Valorile Sprague-Grundy reprezinta o generalizare fata de algoritmul de programare dinamica in cazul jocului cu un singur pion, deoarece cu ajutorul acestor valori pot fi combinate mai multe jocuri. De exemplu, putem presupune ca in graful orientat sunt mai multi pioni in loc de unul singur si ca o mutare consta in deplasarea unui pion din nodul in care se afla intr-un nod adiacent. La fel ca mai sus, cine nu mai poate muta pierde. In acest caz, castigatorul in cazul unui joc perfect nu se poate determina pe baza programarii dinamice. Mai mult, determinarea castigatorului nu este deloc triviala, asa cum era in cazul jocului cu un pion. Atunci cand combinam (adunam) mai multe jocuri elementare, rezultatul poate fi determinat in mod eficient cu ajutorul valorile Sprague-Grundy.
 
In cazul jocului cu mai multi pioni, in loc sa consideram un singur graf, putem considera (conceptual) mai multe grafuri de joc identice, in fiecare dintre acestea aflandu-se cate un pion. Acum, o mutare inseamna alegerea unui graf si deplasarea pionului din graful ales conform regulilor pentru un singur pion. In acest fel, am separat jocul initial in mai multe jocuri _independente_. Dupa cum s-a demonstrat mai sus, stim rezultatul pentru fiecare joc _independent_ in parte si dorim sa determinam castigatorul pentru jocul cu mai multe grafuri.
 
Sa presupunem ca avem $P$ jocuri notate {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$}, pe care dorim sa le adunam. Fiecare din cele $P$ jocuri poate fi reprezentat ca un graf orientat fara circuite in care multimea nodurilor (notata {$V{~i~}$} pentru jocul {$i$}) este data de multimea starilor iar multimea arcelor (notata {$E{~i~}$} pentru jocul {$i$}) este data de perechile ordonate de stari adiacente (exista arc de la $x$ la $y$ daca se poate ajunge printr-o mutare din starea $x$ in starea $y$). Adunand cele $P$ jocuri obtinem un nou joc {$G$} pentru care o stare (nod in graful asociat) este un {$P$}-uplu {$(v{~1~},v{~2~}, ..., v{~P~})$} care ne precizeaza starea curenta pentru fiecare joc individual ({$v{~i~}$} este starea curenta in jocul $i$). Pentru a afla daca pentru o anumita stare din jocul $G$ exista sau nu strategie sigura de castig am putea aplica algoritmul simplu de programare dinamica (prezentat mai sus) pentru graful asociat jocului {$G$}. Se observa insa ca acest graf are {$|V{~1~}|*|V{~2~}|* ...*|V{~P~}|$} noduri, deci algoritmul nu este eficient.

In continuare vom arata cum putem sa determinam eficient daca o stare este castigatoare sau nu pentru un joc compus folosindu-ne de informatiile preprocesate pentru fiecare joc individual.
h3. Adunarea xor