Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G$ be an impartial combinatorial game. I claim that there is a game $G'$ such that $G$ (without terminal positions; see below) under the misère play rule is equivalent to $G'$ under the normal play rule. I wonder if this construction is already known and written down somewhere in the literature (so that I can cite it)? Any reference would be appreciated. Here is the construction of $G'$:

  • The positions of $G'$ are the non-terminal positions of $G$.
  • A move in $G'$ is a move in $G$ which does not lead to a terminal position of $G$.
  • Hence, the terminal positions of $G'$ are those non-terminal positions of $G$ which only move to terminal positions of $G$, i.e. which have nimber $1$ under the normal play rule.

Then I think that $G$ wins/loses under the misère play rule iff $G'$ wins/loses under the normal play rule. Basically this just captures the following philosophy behind misère games: Try to avoid the terminal positions!

I am interested in this because of the following: I have read at various places that there are no nimbers for misère games. However, with the replacement of $G$ by $G'$ above, we can just define the nimber of a non-terminal position of $G$ to be the nimber of the corresponding position of $G'$ under the normal play rule. Terminal positions are boring, they get no nimber. As soon as we know them, we can discard them from the analysis of our misère game $G$. What's wrong with that? This has been applied in the game of noetherian rings.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The misère Grundy number is defined almost exactly as you have defined the "nimber for misère games": terminal positions get misère Grundy number $1$, and all others get the mex (minimal excludant) of the options' misère Grundy numbers, as usual (so that positions that can only move to terminal positions have misère Grundy number $\mathrm{mex}(\{1\})=0$). This can be found in Meghan Rose Allen's MSc thesis at http://miseregames.org/docs/meghan.pdf , as well as in On Numbers and Games, and perhaps Winning Ways for your Mathematical Plays as well.

Why then, have you found the claim that there are "no nimbers for misère games"? Because unlike in the normal play case, these misère Grundy numbers don't tell you nearly enough information for how to play sums with all sorts of games under misère play. They don't even tell you enough to play misère Nim! Two heaps of size $2$ (call the position $G$) has misère Grundy number $0$, and so does a single heap of size $1$. But $G+G$ is a $\mathcal{P}$ position, whereas $1+1$ is a $\mathcal{N}$ position under misère play.

share|improve this answer
    
Thanks a lot, this is exactly what I was looking for. By "no nimbers for misère games" I actually meant that there is no Sprague-Grundy Theorem for misère games. –  Martin Brandenburg May 8 '13 at 14:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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