Combinatorial Game Theory – Nimbers for Misère Games

combinatorial-game-theoryreference-request

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.

Best Answer

Nimbers

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.


References for "$G'$"

You also asked for a reference for something like your $G'$ construction. I think the closest standard object to what you are looking for is the "mate" of $G$, denoted by $G^-$. It is defined by: $$G^{-}=\begin{cases} \left\{ \emptyset\right\} & \text{ if }G\cong\emptyset\text{;}\\ \left\{ \left(G'\right)^{-}:G'\in G\right\} & \text{ otherwise}. \end{cases}$$

For references, you can find this as definition V.3.1 of Aaron N. Siegel's "Combinatorial Game Theory". It can also be found in "On Numbers and Games" (check the index for "mate").

Related Question