Help needed in understanding S-Grundy Number , any good tutorial.
I am trying to solve Mathalon Problem 146 S-Grundy Game (dead link).
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Look up "Sprague-Grundy" on google. What worked for me was attending a course with Aviezri Fraenkel, but your mileage may differ. $\endgroup$– Yuval FilmusJun 5, 2011 at 0:19
-
$\begingroup$ The page is long gone, but you can see there were some problems there at web.archive.org/web/20120322195729/http://www.mathalon.in/… and the first of which was referenced in math.stackexchange.com/questions/20989/finding-four-numbers $\endgroup$– Mark S.Apr 17, 2016 at 20:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I've included this in some other answers of mine, but figured it might be able to stand on its own as a community-wiki resource list.
Some resources describing the strategy for Nim and the Sprague-Grundy Theorem and how they can be applied to other impartial games can be found at one or more of the following:
- Tom Ferguson's class notes on the subject
- Jing Li and Melissa Gymrek's class notes on the subject (from week 5 of a Spring 2011 course)
- MJD's notes in their tidy blog post about using this theory to solve the game in the question for $n$ up through $23$.
- Lim Chu Wee's series of blog posts which are also class notes building up the relevant theory (posts I through V)
- The lecture notes Misère Games and Misère Quotients by Aaron N. Siegel through page 10.
- My own long-winded series of blog posts building up the relevant theory (posts I.1 through I.6).
- Chapter 7 of the undergraduate textbook "Lessons in Play: An Introduction to Combinatorial Game Theory" by Albert, Nowakowski, and Wolfe (although a bit of reading of other chapters may be needed first).
- Chapter 9 of the undergraduate textbook "An Introduction to Combinatorial Game Theory" by L. R. Haff & W. J. Garner (although a bit of reading of other chapters may be needed first).
If you learn about Nim and the Sprague-Grundy theorem and how they work together, then the next thing to learn is about octal games. Because of the strategy for Nim (how Grundy values combine), it suffices to know the Grundy/Nim values for a single "heap". If you calculate enough of these for many octal games, you often see a pattern. The sequence appears to be eventually periodic. There is a theorem attributed to Guy and Smith that says an apparent periodicity that goes on for long enough is guaranteed to continue forever. You can read about it on page 11 of Misère Games and Misère Quotients by Aaron N. Siegel, in this blog post of mine or as Theorem IV.2.7 in the graduate textbook "Combinatorial Game Theory" by Aaron N. Siegel.