Invertibility modulo dead-ending no-$\mathcal {P}$-universes

Abstract

In combinatorial game theory, under normal play convention, all games are invertible, whereas only the empty game is invertible in misère play. For this reason, several restricted universes of games were studied, in which more games are invertible. Here, we study combinatorial games under misère play, in particular universes where no player would like to pass their turn. In these universes, we prove that having one extra condition makes all games become invertible. We then focus our attention on a specific quotient, called ${\mathcal {Q}_{\mathbb {Z}}}$, and show that all sums of universes whose quotient is ${\mathcal {Q}_{\mathbb {Z}}}$ also have ${\mathcal {Q}_{\mathbb {Z}}}$ as their quotient.

1 Introduction

A combinatorial game is a two-player game with no chance and perfect information. The players, called Left and Right,¹ alternate moves until one player is unable to move. The last player to move loses the game under the misère play convention, while that same player would win under normal play convention. In this paper, we are only studying finite combinatorial games.

The conditions that make a game combinatorial ensure that one of the players has a winning strategy. The main objective of combinatorial game theory is to determine which player has a winning strategy and what this strategy is. A basic way would be to look at all possible moves for both players all the way until the game ends in all branches and backtrack the winning player up to the original position. Unfortunately, this method is usually quite time-consuming and often space-consuming as well. Hence other approaches were developed, some specific to particular games and some more general. One general approach is to decompose the position into a sum of smaller positions, study them separately and conclude on their sum. It is thus interesting to be able to simplify the smaller positions before looking at the larger picture, including intermediate sums.

Finding invertibility of games is one of the most efficient ways to simplify sums of games. A game G is said to be invertible if there is a game H such that the sum $G+H$ is equivalent to the zero game, that is, the game with no move. Under normal convention, all games are invertible (one actually just needs to reverse the role of the players in a game to find its inverse), whereas in the misère version, the only invertible game is the empty game (Mesdal and Ottaway 2007). Misère games were thus studied in a more restrictive context (Allen 2009; Dorbec et al. 2014; McKay et al. 2014; Milley 2015; Milley et al. 2012; Milley and Renault 2013; Plambeck 2005; Plambeck and Siegel 2008; Renault 2013), where more games are invertible. In some cases, all games are invertible (McKay et al. 2014; Milley 2015; Milley and Renault 2013; Renault 2013). This happens specifically in all contexts studied so far where no player would ever want to pass their turn (Milley and Renault 2013; Renault 2013). Hence it is natural to wonder if it is always the case.

1.1 Preliminaries

A game can be defined recursively by its sets of options $G = \{G^{\varvec{L}}|G^{\varvec{R}}\}$, where $G^{\varvec{L}}$ is the set of games Left can reach in one move (called Left options), and $G^{\varvec{R}}$ the set of games Right can reach in one move (called Right options). A typical Left option of G is denoted $G^L$, and a typical Right option of G is denoted $G^R$. A follower of a game G is a game that can be reached from G after a succession of (not necessarily alternating) Left and Right moves. Note that a game G is considered one of its own followers. The zero game $0=\{\cdot |\cdot \}$, is the game with no options (a dot indicates an empty set of options). A Left end (resp. Right end) is a game where Left (resp. Right) cannot move.

The disjunctive sum $G + H$ of two games G and H is defined recursively as $G+H = \{G^{\varvec{L}}+H,G+H^{\varvec{L}}\mid G^{\varvec{R}}+H,G+H^{\varvec{R}}\}$, where $G^{\varvec{L}}+H$ is understood to range over all sums of H with an element of $G^{\varvec{L}}$, thus $G+H$ is the game where each player can, on their turn, play one of their legal moves in one (but not both) of the components. The conjugate $\overline{G}$ of a game G is recursively defined as $\overline{G} = \{\overline{G^{\varvec{R}}}|\overline{G^{\varvec{L}}}\}$, where again $\overline{G^{\varvec{R}}}$ is understood to range over all conjugates of elements of $G^{\varvec{R}}$, thus $\overline{G}$ is the game where Left’s and Right’s roles are reversed.

A game can also be depicted by its game tree, where the game tree for each option is linked to the root by downward edges, Left-slanted for Left options and Right-slanted for Right options. It can be more readable than the bracket notation. For instance, the game trees of a few games are depicted in Fig. 1 with their bracket notations below each tree, respectively.

Fig. 1

Some game trees

Fig. 2

Partial ordering of outcomes

Under both conventions, we can sort all games into four sets according to their outcomes. When Left has a winning strategy on a game G no matter which player starts, we say G has outcome $\mathcal {L}$, and G is an $\mathcal {L}$-position. Similarly, $\mathcal {N}$, $\mathcal {P}$ and $\mathcal {R}$ (for next, previous and Right) denote respectively the outcomes of games on which the first player, the second player and Right has a winning strategy regardless of who starts the game. The misère outcome of a game G is denoted $o^-(G)$. $\mathcal {P}$-positions are games in which players would rather have their opponent start, that they would like to pass if it was their turn. Outcomes are partially ordered according to Fig. 2, with Left preferring greater games (by convention, and thus Right preferring smaller games).

Given two games G and H, we say that G is greater than or equal to H in misère play whenever Left always prefers the game G rather than the game H, that is $G\geqslant ^- H$ if for every game X, $o^-(G+X) \geqslant o^-(H+X)$. We say that G and H are equivalent in misère play, denoted $G\equiv ^- H$, when we have both $G \geqslant ^- H$ and $H \geqslant ^- G$.

General equivalence and comparison are very limited in general misère play (see Mesdal and Ottaway 2007; Siegel 2007), this is why Plambeck and Siegel defined (in Plambeck 2005; Plambeck and Siegel 2008) an equivalence relationship under restricted sets of games, which lead to a breakthrough in the study of misère play games.

Definition 1

(Plambeck 2005; Plambeck and Siegel 2008) Let $\mathcal {U}$ be a set of games, G and H two games. We say G is greater than or equal to H modulo $\mathcal {U}$ in misère play and write $G \geqslant ^-_\mathcal {U}H$ if $o^-(G+X) \geqslant o^-(H+X)$ for every $X \in \mathcal {U}$. We say G is equivalent to H modulo $\mathcal {U}$ in misère play and write $G \equiv ^-_\mathcal {U}H$ if $G \geqslant ^-_\mathcal {U}H$ and $H \geqslant ^-_\mathcal {U}G$.

Whenever $\mathcal {U}$ is closed under sum, $\equiv ^-_\mathcal {U}$ is a congruence relation between elements of $\mathcal {U}$. Thus the disjunctive sum modulo $\mathcal {U}$ defines a monoid $\mathcal {M}_\mathcal {U}= \mathcal {U}/\equiv ^-_\mathcal {U}$. We also consider the tetrapartition of $\mathcal {M}_\mathcal {U}$ according to outcomes: given an outcome $\mathcal {O}$, we denote $\mathcal {O}_\mathcal {U}$ the set of equivalence classes of $\mathcal {U}$ with outcome $\mathcal {O}$ so that $\mathcal {M}_\mathcal {U}$ is the disjoint union of $\mathcal {P}_\mathcal {U}$, $\mathcal {L}_\mathcal {U}$, $\mathcal {R}_\mathcal {U}$ and $\mathcal {N}_\mathcal {U}$. The structure $\mathcal {Q}_\mathcal {U}= (\mathcal {M}_\mathcal {U}, \mathcal {P}_\mathcal {U}, \mathcal {L}_\mathcal {U}, \mathcal {R}_\mathcal {U})$ is the misère quotient of $\mathcal {U}$, as defined by Plambeck and Siegel in Plambeck (2005), Plambeck and Siegel (2008), with the addition of $\mathcal {L}$ and $\mathcal {R}$ outcomes since we consider partizan games.

This approach gave several results. For instance, Plambeck (2005) and Plambeck and Siegel (2008) considered and solved the sets of all positions of given games, octal games in particular. Other sets have been considered, including the sets of alternating games $\mathcal {A}$ (Milley et al. 2012), impartial games $\mathcal {I}$ (Berlekamp and Conway 2001; Conway 2001), dicot games $\mathcal {D}$ (Allen 2009; Dorbec et al. 2014; McKay et al. 2014), dead-ending games $\mathcal {E}$ (Milley 2015; Milley and Renault 2013), and all games $\mathcal {G}$ Mesdal and Ottaway (2007).

We believe that some properties, namely being closed under disjunctive sum, conjugation and followers, make a set of games more relevant to be studied. We hence define a universe to be a set of games closed under disjunctive sum, conjugation and followers.

Another interesting property for a game is to be dead-ending. We say a Left (resp. Right) end is a dead end if all its followers are Left (resp. Right) ends. A game is said to be dead-ending if all its end followers are dead ends.

In Sect. 2, we look at universes with no $\mathcal {P}$-positions, establish the invertibility of all elements when they are all dead-ending, and give an example of a universe with almost no invertible element when this last condition is dropped. In Sect. 3, we focus on a particular quotient, ${\mathcal {Q}_{\mathbb {Z}}}$, and prove that if several universes share this quotient, then their sum shares this quotient as well.

2 Invertibility modulo universes without $\mathcal {P}$-positions

This section is dedicated to universes with no $\mathcal {P}$-position. We first consider dead-ending games.

We recall the following lemma from Milley and Renault (2013), which we use to prove invertibility of games.

Lemma 2

(Milley and Renault 2013) Let $\mathcal {U}$ be a set of games closed under conjugation and followers, and S a set of games closed under followers. If $G + \overline{G} + X \in \mathcal {L}^- \cup \mathcal {N}^-$ for every game $G \in S$ and every Left end $X \in \mathcal {U}$, then $G + \overline{G} \equiv ^-_\mathcal {U}0$ for every $G \in S$.

We can now prove that all games are invertible in dead-ending universes containing no misère $\mathcal {P}$-position.

Theorem 3

Let $\mathcal {U}$ be a set of games closed under conjugation, sum, and followers, such that every game in $\mathcal {U}$ is dead-ending and no game in $\mathcal {U}$ has misère outcome $\mathcal {P}$. For any game G in $\mathcal {U}$, we have $G + \overline{G} \equiv ^-_\mathcal {U}0$.

Proof

By Lemma 2, we just need to prove that Left wins $G + \overline{G} + X$ playing first for every Left end $X \in \mathcal {U}$ and every $G \in \mathcal {U}$. We actually prove that if $X = 0$, then $o^-(G + \overline{G} + X) = \mathcal {N}$, and otherwise $o^-(G + \overline{G} + X) = \mathcal {L}$ by induction on G and X. If $X=0$, then as $G + \overline{G} + X = \overline{G + \overline{G} + X}$, the outcome of the game is $\mathcal {N}$ or $\mathcal {P}$, but as no game in $\mathcal {U}$ has outcome $\mathcal {P}$, its outcome is $\mathcal {N}$.

Assume now $X \ne 0$ and Right is the first to move in this game. If he plays in X, he ends up in a position with outcome $\mathcal {N}$ or $\mathcal {L}$ by induction, where Left wins playing first. If he plays in $G + \overline{G}$, Left can answer with the symmetric move and leave her opponent a position $G' + \overline{G'} + X$, with $G'$ an option of G, which has outcome $\mathcal {L}$ by induction. Hence Left wins $G + \overline{G} + X$ playing second. As no game in $\mathcal {U}$ has outcome $\mathcal {P}$, we have $o^-(G + \overline{G} + X) = \mathcal {L}$.

We thus have the hypothesis of Lemma 2 and can conclude that every game of $\mathcal {U}$ is invertible with its conjugate as inverse. $\square$

Unfortunately, that property is not true for all universes, as we now give a counterexample in the general case. We define a game $a = \{\cdot |2\}$, and we look at the closure ${{c\ell }(a, \overline{a})}$ of a and its conjugate under sum and followers, that is, ${{c\ell }(a, \overline{a})}$ is the smallest set closed under sum and followers that contains a and $\overline{a}$. Since $1+1=2$, an element of ${{c\ell }(a, \overline{a})}$ can be written under the form $k_1 1 + k_2 a + k_3 \overline{a} + k_4 \overline{1}$ (see Fig. 3). Note that neither a nor $\overline{a}$ is dead-ending.

Fig. 3

The four generators of ${{c\ell }(a, \overline{a})}$

We first fully determine the outcomes of games in ${{c\ell }(a, \overline{a})}$.

Theorem 4

Let G be a game in ${{c\ell }(a, \overline{a})}$ and write $G = k_1 1 + k_2 a + k_3 \overline{a} + k_4 \overline{1}$. We have

$$\begin{aligned} o^-(G)= {\left\{ \begin{array}{ll} \mathcal {N}&{} \text {if }\, k_1+k_2 = k_3+k_4 \text { or } (k_1=k_3=0 \text { and } k_2 \geqslant k_4) \text { or }\\ &{}\quad (k_2=k_4=0 \text { and } k_3 \geqslant k_1) \\ \mathcal {L}&{} \text {if }\, k_2+k_4> 0 \text { and } k_3+k_4> k_1+k_2 \\ \mathcal {R}&{} \text {if }\, k_1+k_3> 0 \text { and } k_1+k_2 > k_3+k_4 \end{array}\right. } \end{aligned}$$

Proof

We prove the result by induction on G. If $k_1=k_3=0$, then G is a Left end and $o^-(G) \geqslant \mathcal {N}$. Similarly, if $k_2=k_4=0$, then G is a Right end and $o^-(G) \leqslant \mathcal {N}$.

Assume first $k_1=k_3=0$ and $k_2 \geqslant k_4$. If Right moves first, either there is no move and he wins immediately, or he can play in one of the $k_2$ a, moving from G to $2 \cdot 1 + (k_2-1)a + k_4 \overline{1}$ which has outcome $\mathcal {R}$ by induction since $2+k_2-1 > k_2 \geqslant k_4$. If we have $k_4 > k_2$ instead, Right moving in an a would result in a similar game with $k_4 \geqslant 2+k_2-1$ and Right moving in a $\overline{1}$ would result in $k_2 a + (k_4-1) \overline{1}$ with $k_4-1 \geqslant k_2$, both having outcome $\mathcal {N}$ or $\mathcal {L}$ by induction. Similarly, if $k_2=k_4=0$ and $k_3 \geqslant k_1$, Left wins playing first, and loses playing first if $k_1 > k_3$.

Assume now both $k_2+k_4$ and $k_1+k_3$ are positive. Playing first, Left can either play on an $\overline{a}$ or a 1, both increasing the difference $(k_3+k_4)-(k_1+k_2)$ by 1 while not changing the fact that $k_2+k_4$ is positive. By induction, if that difference was non-negative, she moved to an $\mathcal {L}$-position, and otherwise, she moved either to an $\mathcal {N}$-position or an $\mathcal {R}$-position, both of which she loses playing second. The symmetric result when Right plays first concludes the proof. $\square$

Note that no game has outcome $\mathcal {P}$. Using this characterisation, we can now prove that there are games in ${{c\ell }(a, \overline{a})}$ that are not invertible. Worse, actually, only one of them is.

Proposition 5

Let G be a game in ${{c\ell }(a, \overline{a})}$. If $G \equiv ^-_{{{c\ell }(a, \overline{a})}} 0$, then $G = 0$.

Proof

We write $G = k_1 1 + k_2 a + k_3 \overline{a} + k_4 \overline{1}$. Assume $k_1+k_2+k_3+k_4$ is positive. Then at least one player has a move. Without loss of generality, we can assume Left has a move. Now consider the game $X=(k_1+k_2+k_3+k_4+1)a$. By Theorem 4, we have $o^-(0+X) = \mathcal {N}$, while $o^-(G+X) = \mathcal {R}$. Hence $G \not \equiv ^-_{{{c\ell }(a, \overline{a})}} 0$. $\square$

This proves that 0 is the only invertible game in ${{c\ell }(a, \overline{a})}$ since any sum of two games in ${{c\ell }(a, \overline{a})}$ stays in ${{c\ell }(a, \overline{a})}$ and would thus need to be 0 to be equivalent to 0 modulo ${{c\ell }(a, \overline{a})}$. Actually, the situation is even worse. These games are not even cancellative.²

Proposition 6

The only cancellative game in ${{c\ell }(a, \overline{a})}$ is 0.

Proof

First note that $1+1+\overline{1}$ and 1 are not equivalent modulo ${{c\ell }(a, \overline{a})}$ since $o^-(1+1+\overline{1}+\overline{a}+\overline{a}) = \mathcal {L}$ while $o^-(1+\overline{a}+\overline{a}) = \mathcal {N}$. Similarly, $1+\overline{1}+\overline{1}$ and $\overline{1}$ are not equivalent modulo ${{c\ell }(a, \overline{a})}$.

Now let G be any non-zero game in ${{c\ell }(a, \overline{a})}$. G has either a Left or a Right option (or both). Without loss of generality, we may assume it has a Right option. We claim that $G + 1$ and $G + 1+1+\overline{1}$ are equivalent modulo ${{c\ell }(a, \overline{a})}$. Indeed, consider any game X in ${{c\ell }(a, \overline{a})}$ and write $G+X+1 = k_1 1 + k_2 a + k_3 \overline{a} + k_4 \overline{1}$. As G is not a Right end, we have $k_2+k_4 > 0$. We ensured $k_3+k_1 > 0$ by having 1 in the sum. Hence the outcome of $G+X+1$ is fully determined by $(k_2+k_1) - (k_3+k_4)$. Similarly, the outcome of $G+X+1+1+\overline{1}$ is fully determined by $(k_2+(k_1+1) - (k_3+(k_4+1))$. Since the two numbers are equal, the two games have the same outcome. Hence we have $G + 1 \equiv ^-_{{{c\ell }(a, \overline{a})}} G + 1+1+\overline{1}$ but $1 \not \equiv ^-_{{{c\ell }(a, \overline{a})}} 1+1+\overline{1}$, thus completing the proof that G is not cancellative in ${{c\ell }(a, \overline{a})}$. $\square$

Nevertheless, there exist universes with non-dead-ending positions but without $\mathcal {P}$-positions where all games are invertible. It could thus be interesting to characterise which ones among them share this property.

3 The quotient ${\mathcal {Q}_{\mathbb {Z}}}$

The simplest non-trivial universe with no $\mathcal {P}$-position is ${\mathcal {U}_{\mathbb {Z}}}= \{k_1 1 + k_2 \overline{1}|k_1,k_2 \in \mathbb {N}\}$. As $1+\overline{1} \equiv ^-_{\mathcal {U}_{\mathbb {Z}}}0$ (see Milley and Renault 2013), each equivalence class has a representative of which at most one of $k_1$ and $k_2$ is positive.

Definition 7

We note ${\mathcal {Q}_{\mathbb {Z}}}$ the quotient of ${\mathcal {U}_{\mathbb {Z}}}$, that is, we abuse notation by using $\mathbb {Z}$ as index instead of ${\mathcal {U}_{\mathbb {Z}}}$, ${\mathcal {M}_{\mathbb {Z}}}$ is the monoid generated by 1 and $\overline{1}$ where $1 + \overline{1}$ simplifies to 0, $\mathcal {P}_{\mathbb {Z}}$ is empty, $\mathcal {L}_{\mathbb {Z}}$ is the set of positions with a positive number of 1s, $\mathcal {R}_{\mathbb {Z}}$ is the set of positions with a positive number of $\overline{1}$s, and $\mathcal {N}_{\mathbb {Z}}$ is $\{0\}$.

The set of equivalence classes of ${\mathcal {Q}_{\mathbb {Z}}}$ is isomorphic to $\mathbb {Z}$, with positive integers representing games with outcome $\mathcal {L}$, negative integers representing games with outcome $\mathcal {R}$, and 0 representing games with outcome $\mathcal {N}$. Actually, several other universes, such that the universe of dead ends, the universe of canonical numbers (Milley and Renault 2013), and the universe of black and white Toppling Dominoes positions (Renault 2013), seemingly more complex, share this same quotient.

Proposition 8

A universe $\mathcal {U}$ has quotient ${\mathcal {Q}_{\mathbb {Z}}}$ if and only if there exists a surjective function $f: \mathcal {U}\rightarrow \mathbb {Z}$ such that:

• (i) $\forall G,H \in \mathcal {U}, f(G+H) = f(G) + f(H)$,

• (ii) $o^-(G) = \left\{ \begin{array}{ll} \mathcal {N}&{} \text { if }\, f(G) = 0, \\ \mathcal {L}&{} \text { if }\, f(G) < 0, \\ \mathcal {R}&{} \text { if }\, f(G) > 0. \end{array}\right.$

In this case, we say that f is a quotient map from $\mathcal {U}$ to $\mathbb {Z}$. We will see after Lemma 14 that such a quotient map is actually unique.

Note that universes with positions that are not dead-ending can still have quotient ${\mathcal {Q}_{\mathbb {Z}}}$. Still, all the positions are invertible.

We also define the sum of two sets of games as follows:

Definition 9

Let $S_1$ and $S_2$ be two sets of games. We define $S_1+S_2$, the sum of these sets, as follows:

$$\begin{aligned} S_1+S_2 = \{s_1+s_2 \mid s_1 \in S_1 \wedge s_2 \in S_2\}. \end{aligned}$$

In Renault (2013), the author considered sums of universes having quotient ${\mathcal {Q}_{\mathbb {Z}}}$, namely dead ends, canonical numbers and black and white Toppling Dominoes positions, and these sums were sharing the same quotient ${\mathcal {Q}_{\mathbb {Z}}}$. Here we prove that this is always the case.

First, we give another characterisation for a universe to have quotient ${\mathcal {Q}_{\mathbb {Z}}}$. The main point of this characterisation is that it only considers the value of f through options of a game to determine the value of f through that game. This is the major tool to prove Theorem 17, which says that the sum of two universes with quotient ${\mathcal {Q}_{\mathbb {Z}}}$ is a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$. The next lemma shows one way of the equivalence.

Lemma 10

Let $\mathcal {U}$ be a universe and $f: \mathcal {U}\rightarrow \mathbb {Z}$ a surjective function such that:

• a) $\forall G \in \mathcal {U}, n>0, (f(G) = n) \Rightarrow ((\exists G^L \in G^{\varvec{L}}, f(G^L) = n-1) \wedge (\forall G^L \in G^{\varvec{L}}, f(G^L) \geqslant n-1))$,

• b) $\forall G \in \mathcal {U}, n \geqslant 0, (f(G) = n) \Rightarrow \left\{ \begin{array}{ll} ( &{} ((G^{\varvec{R}}\ne \emptyset ) \Rightarrow (\exists G^R \in G^{\varvec{R}}, \\ &{}\qquad 1 \leqslant f(G^R) \leqslant n+1)) \\ \wedge &{} (\forall G^R \in G^{\varvec{R}}, f(G^R) \leqslant n+1)) \end{array}\right. ,$

• c) $\forall G \in \mathcal {U}, n<0, (f(G) = n) \Rightarrow ((\exists G^R \in G^{\varvec{R}}, f(G^R) = n+1) \wedge (\forall G^R \in G^{\varvec{R}}, f(G^R) \leqslant n+1))$,

• d) $\forall G \in \mathcal {U}, n \leqslant 0, (f(G) = n) \Rightarrow$

Then $\mathcal {U}$ has quotient ${\mathcal {Q}_{\mathbb {Z}}}$, having f as a quotient map to $\mathbb {Z}$.

Proof

We prove that f satisfies the two conditions of Proposition 8 by induction on the games in $\mathcal {U}$. First consider a game G in $\mathcal {U}$. If G has no option, then it cannot satisfy the right part of the implications a) and c). Hence $f(G) = 0$ which corresponds to condition (ii) of Proposition 8 since $o^-(G) = \mathcal {N}$.

Assume G is a game such that $f(G) > 0$. From a), it has a Left option, and all its Left options have misère outcome $\mathcal {N}$ or $\mathcal {R}$ by induction. Hence Right has a winning strategy playing second in G. From b), Right can move to a misère $\mathcal {R}$-position by induction if he has any move. Hence Right has a winning strategy playing first in G, which proves G has misère outcome $\mathcal {R}$.

We can prove similarly that if $f(G) < 0$, G has misère outcome $\mathcal {L}$.

Now assume $f(G) = 0$. From b), Right can move to a misère $\mathcal {R}$-position by induction if he has any move. Hence Right has a winning strategy playing first in G. Similarly, from d), Left has a winning strategy playing first in G. Hence G has misère outcome $\mathcal {N}$.

Now consider two games G and H in $\mathcal {U}$. Assume first $f(G) + f(H) > 0$. Then at least one among f(G) and f(H) is positive. Without loss of generality, we may assume f(G) is positive. By a), there exists a Left option $G^{L_1}$ of G such that $f(G^{L_1}) = f(G)-1$. Hence we have a Left option $G^{L_1} + H$ of $G+H$ such that $f(G^{L_1} + H) = f(G^{L_1}) + f(H) = f(G) - 1 + f(H)$ by induction. By a), we have $f(G+H)$ is at most $f(G) + f(H)$. Similarly, as all Left options of $G+H$ are of the form $G^L + H$ or $G + H^L$, using a) and d) and induction, we can say that they are all mapped to integers greater than or equal to $f(G)+f(H)-1$. By d), as $G+H$ has a Left option and all Left options mapped to non-negative integers, $f(G+H)$ is positive. For any positive integer k less than $f(G)+f(H)$, there is no Left move from $G+H$ to a position mapped to $k-1$, so by a), $f(G+H)$ cannot be k. Hence $f(G+H) = f(G) + f(H)$.

Similarly, we have that if $f(G) + f(H) < 0$, then $f(G+H) = f(G) + f(H)$.

Now assume $f(G) + f(H) = 0$. First assume $f(G) = f(H) = 0$. If $G+H$ has no Left option, it cannot satisfy the right part of the implication a), hence it is mapped to a non-positive integer. Assume now $G+H$ has a Left option, it means G or H has a Left option. Without loss of generality, we may assume G has a Left option. From d), we know there exists a Left option $G^{L_1}$ of G such that $f(G^{L_1}) = -1$. Hence the Left option $G^{L_1} + H$ of $G+H$ is such that $f(G^{L_1} + H) = f(G^L_1) + f(H) = -1$ by induction, which implies that $f(G+H)$ is non-positive, as the opposite would contradict a). Similarly, we prove that $f(G+H)$ is non-negative. Hence we have $f(G+H) = 0$. Assume now without loss of generality that $f(G)> 0 > f(H)$. From a), we get a Left option $G^{L_1}$ of G such that $f(G^{L_1}) = f(G)-1$. Similarly as above, this implies $f(G+H)$ is non-positive. We prove that $f(G+H)$ is non-negative in a similar way. Hence we have $f(G+H) = 0$, which concludes the proof. $\square$

We now prove the other way in four steps. First we show that players cannot alter the image of the game through f more than one to their advantage in one move.

Lemma 11

Let $\mathcal {U}$ be a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$ and f a quotient map from $\mathcal {U}$ to $\mathbb {Z}$. Then for any game G in $\mathcal {U}$, for any Left option $G^L$ of G, we have $f(G^L) \geqslant f(G) - 1$.

Proof

Let G be a game in $\mathcal {U}$ and n the image of G through f. As f is surjective, we can find a game H in $\mathcal {U}$ such that $f(H) = 1-n$. We have $f(G+H) = 1$, so $G+H$ has misère outcome $\mathcal {R}$. Hence any first move of Left is losing, which means the image through f of each Left option of G should be at least $n-1$, concluding the proof. $\square$

We now show that when Left has a winning move under optimal play, she has a move to a position where she wins whoever plays first.

Lemma 12

Let $\mathcal {U}$ be a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$ and f a quotient map from $\mathcal {U}$ to $\mathbb {Z}$. Let G be a game in $\mathcal {U}$ such that f(G) is non-positive and G has a Left option. Then G has a Left option $G^L$ such that $-1 \geqslant f(G^L) \geqslant f(G)-1$.

Proof

As f(G) is non-positive, G has misère outcome $\mathcal {N}$ or $\mathcal {L}$. Hence Left wins playing first in G, either because G has no Left option or because she has a winning move. G having a Left option puts us in the second case and there is a winning Left move from G to some $G^L$. By Lemma 11, we have $f(G^L) \geqslant f(G)-1$. Since $G^L$ is a winning move, it has outcome $\mathcal {P}$ or $\mathcal {L}$. Hence $f(G^L)$ is negative by Proposition 8. Therefore, we have $-1 \geqslant f(G^L) \geqslant f(G)-1$. $\square$

For the next part, we need to ensure we can find Right ends in $\mathcal {U}$ whose images through the quotient map cover all positive integers. Hence we consider the game $\{0|\cdot \}$.

Lemma 13

Let $\mathcal {U}$ be a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$ and f a quotient map from $\mathcal {U}$ to $\mathbb {Z}$. Then $\{0|\cdot \} \in \mathcal {U}$ and $f(\{0|\cdot \})=1$.

Proof

As f is surjective, there is an infinite number of games in $\mathcal {U}$. As $\mathcal {U}$ is closed under followers, there exists some game in $\mathcal {U}$ with birthday 1. The three games with birthday 1 are $\{0|\cdot \}$, $\{0|0\}$ and $\{\cdot |0\}$. As $\{0|0\}$ has misère outcome $\mathcal {P}$, it cannot be in $\mathcal {U}$. As $\mathcal {U}$ is closed under conjugation and $\{0|\cdot \}$ and $\{\cdot |0\}$ are each other’s conjugates, both are in $\mathcal {U}$. $\{0|\cdot \}$ has misère outcome $\mathcal {R}$, hence its image through f must be positive. Similarly, 0 has misère outcome $\mathcal {N}$ and its image through f is 0. Having a Left option to 0, whose image through f is 0, $\{0|\cdot \}$’s image through f must be at most 1 by Lemma 11. Hence $f(\{0|\cdot \})=1$. $\square$

We can now prove that when Right loses playing first, he has a move whose image through f is closer to 0 than the original game.

Lemma 14

Let $\mathcal {U}$ be a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$ and f a quotient map from $\mathcal {U}$ to $\mathbb {Z}$. Let G be a game in $\mathcal {U}$ such that f(G) is negative. Then G has a Right option $G^R$ such that $f(G^R) = f(G)+1$.

Proof

As f(G) is negative, G has misère outcome $\mathcal {L}$, and Right has a move in G.

By Lemma 13, we have $\{0|\cdot \}$ in $\mathcal {U}$ and $f(\{0|\cdot \}) = 1$. As $\mathcal {U}$ is closed under sum, we have $(-f(G)) \cdot \{0|\cdot \}$ in $\mathcal {U}$. We have $f(G + ((-f(G)) \cdot \{0|\cdot \})) = 0$ so $G + ((-f(G)) \cdot \{0|\cdot \})$ has misère outcome $\mathcal {N}$. Hence Right has a winning move in $G + ((-f(G)) \cdot \{0|\cdot \})$, which has to be in G since he has no move in $(-f(G)) \cdot \{0|\cdot \}$. Therefore, there is a Right move from G to some $G^R$ such that $f(G^R) > f(G)$. By the conjugate version of Lemma 11, no Right option of G may have an image through f more than $f(G)+1$. Hence $G^R$ is such that $f(G^R) = f(G)+1$. $\square$

Note that this proof implies that the quotient map to $\mathbb {Z}$ from a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$ is unique.

Corollary 15

Let $\mathcal {U}$ be a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$ and $f,f'$ two quotient maps from $\mathcal {U}$ to $\mathbb {Z}$. Then $f = f'$.

Proof

We get $f(\{0|\cdot \}) = 1 = f'(\{0|\cdot \})$ from Lemma 13. For any G in $\mathcal {U}$, if f(G) is negative, $G + ((-f(G)) \cdot \{0|\cdot \})$ has outcome $\mathcal {N}$ so $f'(G) + (-f(G)) \cdot f'(\{0|\cdot \}) = f'(G + ((-f(G)) \cdot \{0|\cdot \}))=0$ and $f'(G) = f(G)$; similarly when f(G) is positive; when f(G) is 0, G has outcome $\mathcal {N}$ so $f'(G)$ is 0 as well. $\square$

We can now state the other way of the characterisation.

Theorem 16

Let $\mathcal {U}$ be a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$. Then the quotient map f from $\mathcal {U}$ to $\mathbb {Z}$ is such that:

• a) $\forall G \in \mathcal {U}, n>0, (f(G) = n) \Rightarrow ((\exists G^L \in G^{\varvec{L}}, f(G^L) = n-1) \wedge (\forall G^L \in G^{\varvec{L}}, f(G^L) \geqslant n-1))$,

• b) $\forall G \in \mathcal {U}, n \geqslant 0, (f(G) = n) \Rightarrow \left\{ \begin{array}{ll} ( &{} ((G^{\varvec{R}}\ne \emptyset ) \Rightarrow (\exists G^R \in G^{\varvec{R}}, 1\\ &{}\qquad \leqslant f(G^R) \leqslant n+1)) \\ \wedge &{} (\forall G^R \in G^{\varvec{R}}, f(G^R) \leqslant n+1)) \end{array}\right. ,$

• c) $\forall G \in \mathcal {U}, n<0, (f(G) = n) \Rightarrow ((\exists G^R \in G^{\varvec{R}}, f(G^R) = n+1) \wedge (\forall G^R \in G^{\varvec{R}}, f(G^R) \leqslant n+1))$,

• d) $\forall G \in \mathcal {U}, n \leqslant 0, (f(G) = n) \Rightarrow$

Proof

The result is a combination of Lemmas 11, 12, 14 and their conjugate versions. $\square$

With this characterisation, which says that the value of f through a game only depends on the value of f through its options, we can now prove the main theorem of this section.

Theorem 17

Let $\mathcal {U}_1$ and $\mathcal {U}_2$ be two universes with quotient ${\mathcal {Q}_{\mathbb {Z}}}$. Then ${\mathcal {U}_1+\mathcal {U}_2}$ is a universe having quotient ${\mathcal {Q}_{\mathbb {Z}}}$.

Fig. 4

Game trees of $2_\#0$ and $2_\#20$

Proof

Let G and H be two games in ${\mathcal {U}_1+\mathcal {U}_2}$. We can write $G = G_1 + G_2$ and $H = H_1 + H_2$ such that $G_1,H_1 \in \mathcal {U}_1$ and $G_2,H_2 \in \mathcal {U}_2$. Then $\overline{G} = \overline{G_1} + \overline{G_2} \in {\mathcal {U}_1+\mathcal {U}_2}$. Hence ${\mathcal {U}_1+\mathcal {U}_2}$ is closed under conjugation. $G+H = (G_1+H_1) + (G_2+H_2) \in {\mathcal {U}_1+\mathcal {U}_2}$. Hence ${\mathcal {U}_1+\mathcal {U}_2}$ is closed under disjunctive sum. A follower of G is the sum of a follower of $G_1$ with a follower of $G_2$. Hence ${\mathcal {U}_1+\mathcal {U}_2}$ is closed under followers. Therefore ${\mathcal {U}_1+\mathcal {U}_2}$ is a universe.

Let $f_1$ and $f_2$ be the quotient maps from $\mathcal {U}_1$ and $\mathcal {U}_2$ to $\mathbb {Z}$ respectively. We define $f:{\mathcal {U}_1+\mathcal {U}_2}\rightarrow \mathbb {Z}$ as $f(G_1+G_2) = f_1(G_1)+f_2(G_2)$ for any $G_1$ in $\mathcal {U}_1$ and $G_2$ in $\mathcal {U}_2$. Let $G = G_1 + G_2$ be a game in ${\mathcal {U}_1+\mathcal {U}_2}$ such that $G_1 \in \mathcal {U}_1$ and $G_2 \in \mathcal {U}_2$. We prove by induction on G that f satisfies the hypothesis of Lemma 10, using the fact that both $f_1$ and $f_2$ satisfy these hypothesis by Theorem 16. Any Left option of G is of the form $G_1+G_2^L$ or $G_1^L+G_2$. As any $G_1^L$ and $G_2^L$ are such that $f_1(G_1^L) \geqslant f_1(G_1) - 1$ and $f_2(G_2^L) \geqslant f_2(G_2) - 1$, we have $f(G^L) \geqslant f(G) - 1$ for any Left option $G^L$ of G. Similarly, we have $f(G^R) \leqslant f(G) + 1$ for any Right option $G^R$ of G.

Assume first f(G) is positive. Then $f_1(G_1)$ or $f_2(G_2)$ is positive. Without loss of generality, we may assume $f_1(G_1)$ to be positive. Then there exists a Left option $G_1^L$ of $G_1$ such that $f_1(G_1^L) = f_1(G_1) - 1$. Hence the Left option $G_1^L + G_2$ of $G_1 + G_2$ has an image through f with value $f(G)-1$. Similarly, if f(G) is negative, there exists a Right option $G^R$ of G such that $f(G^R) = f(G)+1$.

Assume now f(G) is non-negative. If there is no Right option from G, there is nothing to prove. Assume then Right has a move from G. If $f_1(G_1)$ is negative, there is a Right option $G_1^R$ of $G_1$ such that $f_1(G_1^R) = f_1(G_1) + 1$, hence the Right option $G_1^R + G_2$ of $G_1+G_2$ has an image through f with value $f(G)+1$. Similarly, there is a Right option $G_1 + G_2^R$ of $G_1+G_2$ having an image through f with value $f(G)+1$ whenever $f_2(G_2)$ is negative. Assume both $f_1(G_1)$ and $f_2(G_2)$ are non-negative. Without loss of generality, since Right has an option from $G_1+G_2$, we may assume $G_1$ has a Right option. As $f_1(G_1)$ is non-negative, there exists a Right option $G_1^R$ of $G_1$ such that $1 \leqslant f_1(G_1^R) \leqslant f_1(G_1) + 1$. Then the Right option $G_1^R + G_2$ of $G_1 + G_2$ is such that $1 \leqslant 1 + f_2(G_2) \leqslant f(G_1^R + G_2) \leqslant f(G) + 1$. Similarly, if f(G) is non-positive, either Left has no move from G or there exists a Left option $G^L$ of G such that $-1 \geqslant f(G^L) \geqslant f(G) - 1$.

Therefore ${\mathcal {U}_1+\mathcal {U}_2}$ is a universe with quotient ${\mathcal {Q}_{\mathbb {Z}}}$. $\square$

This result does not seem to generalise easily to other quotients since we had to look at the possible moves of all positions in every equivalence class. Actually, the result is not true for any quotient. Call $*$ the game $\{0|0\}$, $*2$ the game $\{0,*|0,*\}$, $2_\#$ the game $\{*2|*2\}$, $2_\#0$ the game $\{0,2_\#|0,2_\#\}$ and $2_\#20$ the game $\{0,*2,2_\#|0,*2,2_\#\}$ (see Fig. 4 for some game trees). Plambeck found that the closures ${c\ell }(2_\#0)$ and ${c\ell }(2_\#20)$ by sum and followers of the last two games share the same quotient, but their sum does not. Their common quotient can be seen as the following:

$$\begin{aligned} (\langle a,b,c|a^2=1,b^3=b,b^2c=c,c^3=ac^2\rangle ,\{a,b^2,bc,c^2\},\emptyset ,\emptyset ) \end{aligned}$$

with fourteen elements. What is surprising, and might explain why the sum gets a bigger quotient, is that the common elements of these two universes are not always mapped to the same element of the quotient. For example, $*2$ is mapped to b from ${c\ell }(2_\#0)$ but to ab from ${c\ell }(2_\#20)$. This situation cannot happen with ${\mathcal {Q}_{\mathbb {Z}}}$ because of Lemma 13.