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

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

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.

!teoria-jocurilor?img002.jpg!

!teoria-jocurilor?img002.jpg!
 
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.