Motivation for the Sprague-Grundy theorem - MathOverflow

Motivation for the Sprague-Grundy theorem

2012-04-21T19:48:59Z

The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber.

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)?

Answer by Michael Albert for Motivation for the Sprague-Grundy theorem

2012-04-22T01:55:54Z

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.

As for applications, the hope generally is that it may be easier 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!

For taking and breaking 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 octal games.

Answer by Martin Brandenburg for Motivation for the Sprague-Grundy theorem

2012-04-24T12:38:01Z

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 Game Theory.

Answer by Lorenzo Lami for Motivation for the Sprague-Grundy theorem

2012-05-21T23:39:42Z

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).

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:

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 < n_i.$$

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$.