Twierdzenie Sprague’a-Grundy’ego – twierdzenie dotyczące gier, które są: bezstronne (impartial), czyli gracze mogą wykonywać dokładnie te same ruchy w danej sytuacji normalne (normal game), czyli przegrywa ten, kto nie może zrobić ruchu w każdej pozycji można wykonać skończoną liczbę ruchów każda rozgrywka ma skończoną długość
Funkcja Sprague’a-Grundy’ego:
jest określona rekurencyjnie
F(p)=0 dla pozycji p, dla której nie można wykonać ruchu
F(k)= mex(A) gdzie A, to zbiór wartości funkcji F dla pozycji, do których możemy dojść w jednym ruchu z pozycji k, jeśli A nie jest pusty.
Twierdzenie Sprague’a-Grundy’ego:
Gracz ma strategię zwycięską wtedy i tylko wtedy, gdy wartość funkcji Sprague’a-Grundy’ego jest różna od 0. Wartość funkcji Sprague’a-Grundy’ego dla sumy gier (tzn. gra toczy się na kilku planszach, gracz w dowolnym ruchu wykonuje ruch na jednej planszy) wyraża się wzorem:
gdzie suma nimliczb po prawej stronie równości oznacza operację xor na liczbach F(P1), F(P2), ...F(Pn)
Przykłady 1) gra nim: Jest n żetonów.