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$ Commented 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$ Commented Apr 25, 2012 at 7:34
  • $\begingroup$ Martin: Indeed, it's a very nice result. Thanks for your help anyway! $\endgroup$ Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .