3
$\begingroup$

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

$\endgroup$

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer! I was aware of this, since I'm reading Ferguson's book; I just wanted to know if the equivalence relation tells us something about each class (e.g. if all games in a class have something in common). $\endgroup$ Apr 25, 2012 at 3:31
  • $\begingroup$ Sorry. Actually I've only read Part I of his book and apart from that I have no background in game theory. I don't know a good answer to your question. But isn't it great that we can classify impartial combinatorial games by natural numbers? In Conway's theory these games embed into a larger class of "numbers", including surreal numbers ... $\endgroup$ Apr 25, 2012 at 7:34
  • $\begingroup$ Martin: Indeed, it's a very nice result. Thanks for your help anyway! $\endgroup$ Apr 25, 2012 at 18:06
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.