Twierdzenie Sprague-Grundy'ego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Twierdzenie Sprague–Grundy - twierdzenie, według którego zbiór gier, które są

  • typu impartial (gracze mogą wykonywać dokładnie te same ruchy w danym momencie)
  • typu normal game (przegrywa ten, kto nie może zrobić ruchu)
  • gracz może zrobić ruch w dowolnej grze podczas swojej kolejki

można rozpatrywać łącznie pod kątem zwycięskiej strategii, tak jak w grze NIM. Wartość nimliczby ją określającej, jest równa Mex zbioru nimliczb danych gier.

Gracz rozpoczynający grę posiada zwycięską strategię wtedy i tylko wtedy, gdy powyższa wartość jest większa od 0

Uwagi[edytuj | edytuj kod]

Warto zauważyć, iż wartość nimliczby określającej zwycięską strategię jednej gry jest równa nimliczbie tej gry, a nie wartości Mex zbioru jednoelementowego.


Twierdzenie zostało odkryte niezależnie przez R. P. Sprague (1935) oraz P. M. Grundy (1939).

Bibliografia[edytuj | edytuj kod]

  • Game Teory, Thomas S. Ferguson