2
$\begingroup$

I am really confused about something in the Sprague-Grundy theorem for combinatorial games. I define $G(n)$ to be the Sprague-Grundy number for a single game of size $n$.

Is this correct:

  1. The Sprague-Grundy value of a more complex game (e.g. something with $k$ games at the same time, such as a game of $k$ piles) is equal to $G(a_1) \oplus G(a_2) \oplus ... \oplus G(a_k)$. No need to use the "mex" function here.

  2. The Sprague-Grundy value of a single game is equal to the minimal excluded value (the "mex" function) of the set of Sprague-Grundy values of all the positions you can reach. So $G(a_k) = \text{mex}(\{G(b_1) , G(b_2) , ... , G(b_m)\})$. where the $b$'s are just other positions reachable from $a$.

Because I am also confused when we start talking about regular Nim, where the answer doesn't seem to depend on Sprague-Grundy at all; the answer is the xor of all the pile sizes.

So my questions are:

-Are my earlier 2 points correct?

-Why does it seem like some Nim games don't involve Sprague-Grundy at all and you can just take the straight xor of everything without involving things like mex()?

$\endgroup$
2
$\begingroup$

Both are correct.

Nim with $p$ piles is a complex game: each pile is a simple game, and at each move you choose one of the $p$ piles and make your move in that simple game. Thus, your first point applies. However, that leaves the problem of determining the Sprague-Grundy value of a single pile of $n$ stones, and it’s here that you apply your second point: this is calculated using the minimum excluded value. For $n=0$ the set of moves is empty, and $\operatorname{mex}(\varnothing)=0$, If $n=1$, the only possible move is to $0$, so the set of values of possible outcomes is $\{0\}$, and clearly $\operatorname{mex}(\{0\})=1$. It’s straightforward in this way to show by induction that the Sprague-Grundy value of a pile of $n$ stones is

$$\operatorname{mex}(\{0,\ldots,n-1\})=n\;.$$

Thus, calculating the Sprague-Grundy value of a single pile turns out to be trivial. These values are in fact the basis of Sprague-Grundy theory.

$\endgroup$
  • $\begingroup$ @user401925: Correct: in Nim you actually are taking the XOR of the S-G values of the component games, and they just happen to be the sizes of the piles. $\endgroup$ – Brian M. Scott Dec 25 '16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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