h2(#adunare). Adunarea jocurilor

h1. Teoria jocurilor
 
(Categoria _Teoria jocurilor_, Autor _Filip Cristian Buruiana_)
 
(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
 
h2. Adunarea jocurilor

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 in timp polinomial. 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 valorilor Sprague-Grundy.