## Motivation for the Sprague-Grundy theorem

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

## 3 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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). – Fernando Martin Apr 25 2012 at 3:31
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 ... – Martin Brandenburg Apr 25 2012 at 7:34
Martin: Indeed, it's a very nice result. Thanks for your help anyway! – Fernando Martin Apr 25 2012 at 18:06

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9461444020271301, "perplexity_flag": "head"}