Rys. 1 Graf, który określamy mianem „łańcucha”. W tym przypadku jest to łańcuch długości 8.

W Grimie dwaj uczestnicy naprzemiennie wykonują ruchy. Na początku rozgrywki mają oni do dyspozycji pewien graf. W tym artykule będziemy rozważać jedynie grafy początkowe, które są „łańcuchami”, tzn. takie grafy spójne, w których dwa wierzchołki mają stopień 1, a reszta wierzchołków ma stopień 2 (taki graf pokazany jest na rysunku 1).

W każdym ruchu gracz wybiera dowolny nieizolowany wierzchołek grafu i usuwa go wraz ze wszystkimi krawędziami z niego wychodzącymi. Przegrywa gracz, który jako pierwszy nie może wykonać ruchu.

Rys. 2 Przykładowa rozgrywka dla nieparzystej liczby wierzchołków przy założeniu, że gracz pierwszy gra zgodnie z opisaną w artykule strategią wygrywającą.

Jeśli liczba wierzchołków grafu jest nieparzysta (oczywiście, większa od 1), to istnieje strategia wygrywająca dla gracza pierwszego – wystarczy jako pierwszy wierzchołek wybrać wierzchołek będący środkiem symetrii, a następnie odbijać ruchy przeciwnika względem środka (Rys. 2). Po każdym ruchu pierwszego gracza, postępującego zgodnie z opisanym tu algorytmem, pozostałe wierzchołki są ponownie symetryczne względem środka. Dopóki drugi gracz jest w stanie wykonać ruch, dopóty pierwszy gracz może rozpocząć następną kolejkę. Zatem drugi gracz nie może wykonać dozwolonego ruchu jako ostatni. Ponieważ wierzchołków jest skończenie wiele, gra musi zakończyć się jego przegraną.

Trudniejszy do rozważenia jest przypadek, gdy liczba wierzchołków jest parzysta. Gdy wynosi ona 2, to strategię wygrywającą ma gracz pierwszy – niezależnie od wykonanego ruchu, drugiemu graczowi pozostanie jedynie izolowany wierzchołek. Dla czterech wierzchołków strategię wygrywającą ma gracz drugi. Dla łańcucha długości 6, 8 lub 10 znów wygrywa gracz pierwszy, ale dla długości 12 – drugi. Można tego dowieść, rozrysowując drzewo gry, niestety, o wykładniczej zależności liczby węzłów od długości łańcucha. Co dalej? Z pomocą przychodzi nam komputer i twierdzenie Sprague’a–Grundy’ego. Żeby je przedstawić, wprowadzimy najpierw kilka pojęć.

Grę nazwiemy normalną, jeśli przegrywa w niej ten z graczy, który jako pierwszy nie jest w stanie wykonać ruchu. Będziemy mówić, że gra jest bezstronna, jeśli obaj gracze mogą wykonać te same ruchy, mając do dyspozycji daną planszę. Przykładowo gra w kółko i krzyżyk bezstronna nie jest, gdyż gracz stawiający kółko nie może postawić krzyżyka. Grim i Nim zaliczają się do gier bezstronnych.

Funkcja mex (ang. minimum excludant) przyporządkowuje podzbiorowi zbioru liczb naturalnych najmniejszą liczbę naturalną do niego nienależącą. Na przykład,

Funkcja Sprague’a–Grundy’ego   określona jest rekurencyjnie dla poszczególnych pozycji w grze. Dla konfiguracji   w której gracz nie jest w stanie wykonać ruchu, definiujemy  Dla innych pozycji funkcja ta zwraca  zbioru wartości   dla wszystkich pozycji   do których możemy dojść w jednym ruchu z   Do poprawności definicji   wystarczy acykliczność gry, czyli brak możliwości powtórzenia konfiguracji w czasie rozgrywki, oraz założenie, że dla każdej konfiguracji początkowej gra może potrwać co najwyżej skończenie wiele tur.

W grze Grim dla pozycji składającej się z jednego bądź kilku izolowanych wierzchołków nie ma możliwości wykonania ruchu, więc  przyjmuje wartość  Łańcuchowi długości 2 funkcja   przyporządkowuje  równe  z wartości   dla wierzchołka izolowanego, który uzyskujemy niezależnie od tego, na który z dwóch możliwych ruchów się zdecydujemy. Zatem  Wartość  równa jest natomiast wartości funkcji  dla zbioru zawierającego: wartość   dla dwóch izolowanych wierzchołków  oraz dla łańcucha długości 2,  a zatem

Nim-suma to pewne działanie   które dwóm liczbom naturalnym przyporządkowuje również liczbę naturalną. Aby obliczyć Nim-sumę, należy zapisać oba argumenty w systemie dwójkowym, dodać liczby stojące przy tych samych potęgach dwójki (a więc zera lub jedynki) modulo 2, a następnie wynik zinterpretować jako zapis dwójkowy szukanej liczby. Z powyższego przepisu wynika od razu, że 

Twierdzenie Sprague’a–Grundy’ego pozwala wyznaczyć wartości funkcji   w sytuacji, gdy gracze grają w kilka normalnych i bezstronnych gier jednocześnie: w każdym ruchu wybierają jedną z plansz i wykonują na niej ruch zgodnie z zasadami odpowiadającej jej gry. Tak powstałą „multigrę” nazywamy sumą gier.

W przypadku, gdy funkcja   dla pozycji gry   przyjmuje wartość  możliwy jest ruch do takiej pozycji   by  zgodnie z definicją funkcji  Pozycja   może kończyć grę (dla takich   z definicji ), choć nie musi. Jeżeli  to wówczas dla każdej pozycji   osiągalnej za pomocą jednego ruchu, mamy  Strategia wygrywająca polega na takim wykonywaniu ruchów, by po każdym z nich trafić do takiej pozycji   że 

Jako przykład zastosowania rozważmy sumę dwóch egzemplarzy pewnej gry bezstronnej i normalnej (gramy tymi samymi zasadami, rozpoczynamy z tą samą pozycją początkową   na obu planszach). Wygrywa ten z graczy, który jako ostatni jest w stanie wykonać ruch. Na mocy podanego twierdzenia wartość funkcji Sprague’a–Grundy’ego dla tak powstałej gry będzie równa

a zatem nie istnieje strategia wygrywająca dla pierwszego gracza. Do takiego wniosku możemy też dojść bezpośrednio. Wystarczy zauważyć, że gracz drugi może zapewnić sobie zwycięstwo przez kopiowanie ruchów gracza pierwszego na planszy, na której ostatnio nie wykonał ruchu gracz pierwszy.

Jaki związek ma twierdzenie Sprague’a–Grundy’ego z grą Grim? Jeśli startując z łańcucha, usuniemy jeden wierzchołek, to otrzymamy dwa krótsze łańcuchy (być może jeden pusty, czyli długości 0), z których każdy od tej pory można traktować jako osobną grę. Chcąc wyznaczyć wartość funkcji Sprague’a–Grundy’ego dla łańcucha długości   należy obliczyć  z wartości   dla gier będących sumami łańcuchów długości   oraz  dla  ze zbioru  Wartość tej funkcji dla każdej takiej sumy łańcuchów otrzymujemy z twierdzenia Sprague’a–Grundy’ego – jest to  Stąd otrzymujemy definicję rekurencyjną:

Powyższy przepis można bardzo efektywnie (w porównaniu z przeszukiwaniem pełnego drzewa gry) wykorzystać do obliczenia wartości   za pomocą komputera. Uproszczenie bierze się stąd, iż zamiast rozpatrywać wszystkie możliwe konfiguracje planszy, możemy, dzięki twierdzeniu, ograniczyć się do rozpatrywania konfiguracji będących łańcuchem lub sumą dwóch łańcuchów. Prosta implementacja ma pesymistyczną złożoność   przy założeniu, że operację xor liczymy w czasie stałym.

Wykorzystując tę technikę, można sprawdzić, że jedynymi liczbami wierzchołków mniejszymi od   przy których strategię wygrywającą ma gracz drugi, są dokładnie liczby ze zbioru:

Pytanie, czy to jedyne liczby o tej własności, pozostaje otwarte.

Podanie jawnego wzoru na wartości funkcji Sprague’a–Grundy’ego dla różnych dwuosobowych gier bezstronnych w ogólności uchodzi za zadanie trudne. Obliczanie wartości tej funkcji za pomocą komputera (a nawet, przy odrobinie wytrwałości, na kartce papieru) zazwyczaj jest dużo prostsze, a pozwala określać, który z graczy ma strategię wygrywającą, dla konkretnych, także nietrywialnych sytuacji. Tak otrzymane wyniki mogą prowadzić do ciekawych hipotez dotyczących postaci funkcji   Czytelnika Wnikliwego zachęcamy również do wyznaczenia jawnego wzoru funkcji Sprague’a–Grundy’ego dla gry Nim.