Motivation for the Sprague-Grundy theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:55:47Z http://mathoverflow.net/feeds/question/94769 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94769/motivation-for-the-sprague-grundy-theorem Motivation for the Sprague-Grundy theorem Fernando Martin 2012-04-21T19:48:59Z 2012-05-28T14:57:11Z <p>The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber.</p> <p>What does the equivalence relation thus defined tell us about a certain game? (e.g. does a high SG-number imply that the position is hard to compute?) What are some specific uses of the theorem (besides making the calculation of N and P positions considerably easier)?</p> http://mathoverflow.net/questions/94769/motivation-for-the-sprague-grundy-theorem/94797#94797 Answer by Michael Albert for Motivation for the Sprague-Grundy theorem Michael Albert 2012-04-22T01:55:54Z 2012-04-22T01:55:54Z <p>There is no direct link with difficulty of computation -- for example a single Nim heap of $n$ counters has nim-value $*n$. Of course, if a game is equivalent to $*n$ it must have at least $n$ options, so in that sense it is more complex.</p> <p>As for applications, the hope generally is that it may be <em>easier</em> to analyse a game in general by working out the exact nim-values rather than just seeking the partition into next player wins ($\mathcal{N}$) and previous player wins ($\mathcal{P}$). Unfortunately, this hope is not often realised!</p> <p>For <em>taking and breaking</em> games there has been considerable work done in trying to determine both the actual sequences of nim-values, and the types of behaviours these sequences can exhibit (various forms of periodicity most prominently). See for instance the wikipedia article on <a href="http://en.wikipedia.org/wiki/Octal_game" rel="nofollow">octal games</a>.</p> http://mathoverflow.net/questions/94769/motivation-for-the-sprague-grundy-theorem/95018#95018 Answer by Martin Brandenburg for Motivation for the Sprague-Grundy theorem Martin Brandenburg 2012-04-24T12:38:01Z 2012-04-24T12:38:01Z <p>It is quite typical that a game may be decomposed into a sum of rather easy games. The Sprague-Grundy theorem essentially tells us what the Sprague-Grundy function of this sum is just the nim-sum of the Sprage-Grundy functions of the summands, each being very easy to compute. Then one can determine the $\mathcal{N}$ and $\mathcal{P}$-positions of the sum by finding the zeros. This method is illustrated by some examples in section I.4 in Ferguson's <a href="http://www.math.ucla.edu/~tom/Game_Theory/Contents.html" rel="nofollow">Game Theory</a>.</p> http://mathoverflow.net/questions/94769/motivation-for-the-sprague-grundy-theorem/97610#97610 Answer by Lorenzo Lami for Motivation for the Sprague-Grundy theorem Lorenzo Lami 2012-05-21T23:39:42Z 2012-05-28T14:57:11Z <p>The Sprague-Grundy theorem provides a surjective homomorphism $\mathcal{G}$ from the commutative monoid of symmetric games onto the group $On_2$ (the ordinals with the nim sum). The point of this quotient is that $\ker \mathcal{G}$ is exactly the class of $\mathcal{P}$ games. So you can see how the Sprague-Grundy theorem defines a partition on all games, which are many. In fact, you can think of a symmetric game as a well founded set (formally a biset with equal side-sets, as presented in On Numbers and Games by J. H. Conway); in this light we are partitioning the whole Von Neumann hierarchy $\mathbb{V}$, where each class is indeed very well populated (it is a proper class).</p> <p>This bridge theorem, as already outlined, allows to compute the outcome of a game just by computing the nimber of each of its components; this is the main use and its original purpose. But it can also be useful the other way round:</p> <p>If $n_1 + \cdots + n_k = t \neq 0$, where $+$ is the nim sum, then $$\exists i \in \{ 1, \dots ,k \} \mbox{ such that } n_i + t &lt; n_i.$$</p> <p>A proof is as follows: since $t \neq 0$, $n_1 + \cdots + n_k$ is a $\mathcal{N}$-position in Nim so there must be a winning move from, say, $n_1$ to $\bar{n}_1$ such that $\bar{n}_1 + n_2 + \cdots + n_k =0$. Since in Nim the only legal moves are to decrease numbers it follows that $n_1 > \bar{n}_1$. But, since $On_2$ satisfies $\forall x\ x+x=0$, adding $n_2 + \cdots + n_k + t$ to each side of the previous equation yields (after cancellations) $\bar{n}_1 + t = n_2 + \cdots + n_k + t = n_1$.</p>