# Three-player impartial games

## 0 Introduction

Let us begin with a very specific problem: Assume $`G`$ is an impartial (positional) game played by three people who alternate moves in cyclic fashion (Natalie, Oliver, Percival, Natalie, Oliver, Percival, …), under the convention that the player who makes the last move wins. Let $`H`$ be another such game. Suppose that the second player, Oliver, has a winning strategy for $`G`$. Suppose also that Oliver has a winning strategy for $`H`$. Is it possible for Oliver to have a winning strategy for the disjunctive sum $`G+H`$ as well?

Recall that an impartial positional game is specified by (i) an initial position, (ii) the set of all positions that can arise during play, and (iii) the set of all legal moves from one position to another. The winner is the last player to make a move. To avoid the possibility of a game going on forever, we require that from no position may there be an infinite chain of legal moves. The disjunctive sum of two such games $`G,H`$ is the game in which a legal move consists of making a move in $`G`$ (leaving $`H`$ alone) or making a move in $`H`$ (leaving $`G`$ alone). Readers unfamiliar with the theory of two-player impartial games should consult  or .

It is important to notice that in a three-player game, it is possible that none of the players has a winning strategy. The simplest example is the Nim game that starts from the position $`1+2`$, where 1 and 2 denote Nim-heaps of size one and two respectively. As usual, a legal move consists of taking a number of counters from a single heap. In this example, the first player has no winning move, but his actions determine whether the second or third player will win the game. None of the players has a winning strategy. That is, any two players can cooperate to prevent the remaining player from winning. It is in a player’s interest to join such a coalition of size two if he can count on his partner to share the prize with him – unless the third player counters by offering an even bigger share of the prize. This kind of situation is well known in the theory of “economic” (as opposed to positional) games. In such games, however, play is usually simultaneous rather than sequential.

Bob Li  has worked out a theory of multi-player positional games by decreeing that a player’s winnings depend on how recently he has moved when the game ends (the last player to move wins the most, the player who moved before him wins the next most, and so on), and by assuming that each player will play rationally so as to get the highest winnings possible. Li’s theory, when applied to games like Nim, leads to quite pretty results, and this is perhaps sufficient justification for it; but it is worth pointing out that, to the extent that game theory is supposed to be applicable to the actual playing of games, it is a bit odd to assume that one’s adversaries are going to play perfectly. Indeed, the only kind of adversaries a sensible person would play with, at least when money is involved, are those who do not know the winning strategy. Only in the case of two-player games is it the case that a player has a winning strategy against an arbitrary adversary if and only if he has a winning strategy against a perfectly rational adversary.

Phil Straffin  has his own approach to three-player games. He adopts a policy (“McCarthy’s revenge rule”) governing how a player should act in a situation where he himself cannot win but where he can choose which of his opponents will win. Straffin analyzes Nim under such a revenge rule, and his results are satisfying if taken on their own terms, but the approach is open to the same practical objections as Li’s. Specifically, if a player’s winning strategy depends on the assumption that his adversaries will be able to recognize when they can’t win, then the player’s strategy is guaranteed to work only when his opponents can see all the way to the leaves of the game tree. In this case, at least one of them (and perhaps each of them) believes he can’t win; so why is he playing?

The proper response to such objections, from the point of view of someone who wishes to understand real-world games, is that theories like Li’s and Straffin’s are prototypes of more sophisticated theories, not yet developed, that take into account the fact that players of real-life games are partly rational and partly emotional creatures, capable of such things as stupidity and duplicity.

It would be good to have a framework into which the theories of Li and Straffin, along with three-player game-theories of the future, can be fitted. This neutral framework would make no special assumptions about how the players behave. Here, we develop such a theory. It is a theory designed to answer the single question “Can I win?,” asked by a single player playing against two adversaries of unknown characteristics. Not surprisingly, the typical answer given by the theory is “No”; in most positions, any two players can gang up on the third. But it turns out that there is a great deal to be said about those games in which one of the players does have a winning strategy.

In addition to the coarse classification of three-player games according to who (if anyone) has the winning strategy, one can also carry out a fine classification of games analogous to, but much messier than, the classification of two-player games according to Grundy-value. The beginnings of such a classification permit one to answer the riddle with which this article opened; the later stages lead to many interesting complications which have so far resisted all attempts at comprehensive analysis.

## 1 Notation and Preliminaries

Games will be denoted by the capital letters $`G`$, $`H`$, $`X`$, and $`Y`$. As in the two-player theory, we can assume that every position carries along with it the rules of play to be applied, so that each game may be identified with its initial position. The game $`G^{}`$ is an option of $`G`$ if it is legal to move from $`G`$ to $`G^{}`$. To build up all the finite games, we start from the null-game $`0`$ (the unique game with no options) and recursively define $`G=\{G_1^{},G_2^{},\mathrm{}\}`$ as the game with options $`G_1^{},G_2^{},\mathrm{}`$. The game $`\{0\}`$ will be denoted by 1, the game $`\{0,1\}`$ will be denoted by 2, and so on. (It should always be clear from context whether a given numeral denotes a number or a Nim game.)

We recursively define the relation of identity by the rule that $`G`$ and $`H`$ are identical if and only if for every option $`G^{}`$ of $`G`$ there exists an option $`H^{}`$ of $`H`$ identical to it, and vice versa. We define (disjunctive) addition, represented by $`+`$, by the rule that $`G+H`$ is the game whose options are precisely the games of the form $`G^{}+H`$ and $`G+H^{}`$. It is easy to show that identity is an equivalence relation that respects the “bracketing” and addition operations, that addition is associative and commutative, and that $`0`$ is an additive identity.

The following abbreviations will prove convenient:

$$\begin{array}{ccc}\hfill GH& \text{means}\hfill & G+H\hfill \\ \hfill G^n& \text{means}\hfill & G+G+\mathrm{}+G\text{(}n\text{ times)}\hfill \\ \hfill m_n& \text{means}\hfill & \{\{\mathrm{}\{m\}\mathrm{}\}\}\text{(}n\text{ layers deep)}\hfill \end{array}$$

Thus, $`\{12\}^34_5`$ denotes

$$\{1+2\}+\{1+2\}+\{1+2\}+\{\{\{\{\{4\}\}\}\}\}.$$

(We’ll never need to talk about Nim-heaps of size $`>9`$, so our juxtaposition convention won’t cause trouble.) Note that for all $`G`$, the games $`G0`$, $`G^1`$, $`G_0`$, and $`G`$ are identical.

Relative to any non-initial position in the course of play, one of the players has just moved (the Previous player) and one is about to move (the Next player); the remaining player is the Other player. At the start of the game, players Next, Other, and Previous correspond to the first, second, and third players (even though, strictly speaking, there was no “previous” move). We call $`G`$ a Next-game ($`𝒩`$-game) if there is a winning strategy for Next, and we let $`𝒩`$ be the set of $`𝒩`$-games; $`𝒩`$ is the type of $`G`$, and $`G`$ belongs to $`𝒩`$. We define $`𝒪`$-games and $`𝒫`$-games in a similar way.

If none of the players has a winning strategy, we say that $`G`$ is a Queer game ($`𝒬`$-game). In a slight abuse of notation, I will often use “$`=`$” to mean “belongs to”, and use the letters $`N,O,P,Q`$ to stand for unknown games belonging to these respective types. Thus I will write $`1=N`$, $`11=O`$, $`111=P`$, etc.; and the problem posed in the Introduction can be formulated succinctly as: solve $`O+O=O`$ or prove that no solution exists. (At this point I invite the reader to tackle $`Q+Q=O`$. There is a simple and elegant solution.)

The following four rules provide a recursive method for classifying a game:

* $`G`$ is an $`𝒩`$-game exactly if it has some $`𝒫`$-game as an option.
* $`G`$ is an $`𝒪`$-game exactly if all of its options are $`𝒩`$-games, and it has at least one option (this proviso prevents us from mistakenly classifying $`0`$ as an $`𝒪`$-game).
* $`G`$ is a $`𝒫`$-game exactly if all of its options are $`𝒪`$-games.
* $`G`$ is a $`𝒬`$-game exactly if none of the above conditions is satisfied.

Using these rules, it is possible to analyze a game completely by classifying all the positions in its game-tree, from leaves to root.

## 2 Some Sample Games

Let us first establish the types of the simpler Nim games. It’s easy to see that

$`0`$ $`=P,`$   
$`1`$ $`=\{0\}=\{P\}=N,`$   
$`11`$ $`=\{1\}=\{N\}=O,`$   
$`111`$ $`=\{11\}=\{O\}=P,`$   
and so on; in general, the type of $`1^n`$ is $`𝒫`$, $`𝒩`$, or $`𝒪`$ according as the residue of $`n`$ mod 3 is 0, 1, or 2. Also

$`2`$ $`=N,`$   
$`3`$ $`=N,`$   
and so on, because in each case Next can win by taking the whole heap.

$`12`$ $`=\{1,2,11\}=\{N,N,O\}=Q,`$   
$`112`$ $`=\{11,12,111\}=\{O,Q,P\}=N,`$   
$`1112`$ $`=\{111,112,1111\}=\{P,N,N\}=N,`$   
$`11112`$ $`=\{1111,1112,11111\}=\{N,N,O\}=Q,`$   
and so on; in general, the type of $`1^n2`$ is $`𝒩`$, $`𝒬`$, or $`𝒩`$ according as the residue of $`n`$ mod 3 is 0, 1, or 2. The winning strategy for these $`𝒩`$-games is simple: reduce the game to one of the $`𝒫`$-positions $`1^{3k}`$.

$`1+1=11`$ is a solution of the equation $`N+N=O`$. Does $`G=N`$ imply that $`G+G=O`$ in general? We can easily see that the answer is “No”:

$$2+2=22=\{12,2\}=\{Q,N\}=Q.$$

($`12`$ is identical to $`21`$, so they can be treated as a single option.)

Here are some more calculations which will be useful later.

$`\{2\}`$ $`=\{N\}=O`$   
$`\{\{2\}\}`$ $`=\{O\}=P`$   
$`\{1,11\}`$ $`=\{N,O\}=Q`$   
$`\{2,11\}`$ $`=\{N,O\}=Q`$   
## 3 Adding Games

The type of $`G+H`$ is not in general determined by the types of $`G`$ and $`H`$. (For example, 1 and 2 are both of type $`𝒩`$, but $`1+1=O`$ while $`2+2=Q`$.) That is, addition does not respect the relation “belongs to the same type as”. To remedy this situation we define equivalence ($``$) by the condition that $`GH`$ if and only if for all games $`X`$, $`G+X`$ and $`H+X`$ belong to the same type. It is easy to show that “equivalence” is an equivalence relation, that it respects bracketing and addition, and that if $`G^{}H^{}`$ then $`\{G^{},H^{},\mathrm{}\}\{H^{},\mathrm{}\}`$ (that is, equivalence options of a game may be conflated).

We are now in a position to undertake the main task of this section: determining the addition table. Recall that in the two-player theory, there are only two types ($`𝒩`$ and $`𝒫`$) and their addition table is as shown in Table 1.

Here, the entry $`PN`$ denotes the fact that the sum of two $`𝒩`$-games can be either a $`𝒫`$-game or an $`𝒩`$-game.

The analogous addition table for three-player games is given by Table 2.

Notice that in one particular case (namely $`G=P`$ and $`H=Q`$, or vice versa), knowing the types of $`G`$ and $`H`$ does tell one which type $`G+H`$ belongs to, namely $`Q`$. A corollary of this is that $`P+P+\mathrm{}+P+Q=Q`$.

To prove that Table 1 applies, one simply finds solutions of the allowed “equations” $`P+P=P`$, $`P+N=N`$ (from which $`N+P=N`$ follows), $`N+N=P`$, and $`N+N=N`$, and proves that the forbidden equations $`P+P=N`$ and $`P+N=P`$ have no solutions. To demonstrate the validity of Table 2, we must find solutions to twenty-two such equations, and prove that the remaining eighteen have no solutions.

Table 3 shows the twenty-two satisfiable equations and their solutions.

And now, the proofs of impossibility for the eighteen impossible cases.

###### Claim 1.

None of the following is possible.

$`O+P`$ $`=N`$ (1)   
$`N+P`$ $`=P`$ (2)   
$`O+O`$ $`=P`$ (3)   
$`P+P`$ $`=O`$ (4)   
$`O+N`$ $`=O`$ (5)   
###### Proof 3.1.

By (joint) infinite descent. Here, as in subsequent proofs, the infinite-descent “boilerplating” is omitted.

Note that none of the hypothetical $`𝒫`$-games in equations (1)-(4) can be the $`0`$-game, so all of these games $`X,Y`$ have options.

Suppose (1) holds; say $`X=O`$, $`Y=P`$, $`X+Y=N`$. Some option $`X^{}+Y`$ or $`X+Y^{}`$ must be a $`𝒫`$-game. But then we have either $`N+P=P`$ (every option $`X^{}`$ must be an $`𝒩`$-game), which is (2), or $`O+O=P`$ (every option $`Y^{}`$ must be an $`𝒪`$-game), which is (3).

Suppose (2) holds; say $`X=N`$, $`Y=P`$, $`X+Y=P`$. Then there exists $`X^{}=P`$, which must satisfy $`X^{}+Y=P+P=O`$ (equation (4)).

Suppose (3) holds; say $`X=O`$, $`Y=O`$, $`X+Y=P`$. Then there exists $`Y^{}=N`$, which must satisfy $`X+Y^{}=O+N=O`$ (equation (5)).

Suppose (4) holds; say $`X=P`$, $`Y=P`$, $`X+Y=O`$. Then there exists $`X^{}=O`$, which must satisfy $`X^{}+Y=O+P=N`$ (equation (1)).

Finally, suppose (5) holds; say $`X=O`$, $`Y=N`$, $`X+Y=O`$. Then there exists $`Y^{}=P`$, which must satisfy $`X+Y^{}=O+P=N`$ (equation (1)).

###### Claim 1.

None of the following is possible.

$`P+P`$ $`=N`$ (6)   
$`O+P`$ $`=P`$ (7)   
$`N+P`$ $`=O`$ (8)   
###### Proof 3.2.

By infinite descent. A solution to (6) yields an (earlier-created) solution to (7), which yields a solution to (8), which yields a solution to (6).

###### Claim 2.

It is impossible that

$$N+N=P$$
(9)   
###### Proof 3.3.

By contradiction. A solution to (9) would yield a solution to (8).

###### Claim 3.

None of the following is possible.

$`Q+P`$ $`=N`$ (10)   
$`Q+P`$ $`=P`$ (11)   
$`Q+O`$ $`=P`$ (12)   
$`Q+P`$ $`=O`$ (13)   
$`Q+N`$ $`=O`$ (14)   
###### Proof 3.4.

By infinite descent (making use of earlier results as well).

Suppose (10) holds with $`X,Y`$. Some option $`X^{}+Y`$ or $`X+Y^{}`$ must be a $`𝒫`$-game. In the former event, we have $`X^{}P`$ (since $`X=Q`$), so that either $`N+P=P`$ (equation (2)), $`O+P=P`$ (equation (7)), or $`Q+P=P`$ (equation (11)); in the latter event we have $`Q+O=P`$ (equation (12)).

Suppose (11) holds with $`X,Y`$. Since $`X=Q`$, it has an option $`X^{}`$ of type $`𝒩`$ or type $`𝒬`$ (for if all options of $`X`$ were $`𝒪`$-games and $`𝒫`$-games, $`X`$ would be of type $`𝒫`$ or $`𝒩`$). If $`X^{}=N`$, then we have $`X^{}+Y=N+P=O`$ (equation (8)), and if $`X^{}=Q`$, then we have $`X^{}+Y=Q+P=O`$ (equation (13)).

Suppose (12) holds with $`X,Y`$. Then $`X+Y^{}=Q+N=O`$ (equation (14)).

Suppose (13) holds with $`X,Y`$. Since $`X=Q`$, it has an option $`X^{}`$ of type $`𝒪`$ or of type $`𝒬`$ (for if all options of $`X`$ were $`𝒩`$-games and $`𝒫`$-games, $`X`$ would be of type $`𝒪`$ or $`𝒩`$). $`X^{}=O`$ yields $`X^{}+Y=O+P=N`$ (equation (1)), and $`X^{}=Q`$ yields $`X^{}+Y=Q+P=N`$ (equation (10)).

Finally, suppose (14) holds with $`X,Y`$. Then there exists $`Y^{}=P`$, which must satisfy $`X+Y^{}=Q+P=N`$ (equation (10)).

###### Claim 4.

It is impossible that

$$Q+N=P$$
(15)   
###### Proof 3.5.

By contradiction. A solution to (15) would yield a solution to (13).

###### Claim 5.

Neither of the following is possible:

$`Q+Q`$ $`=N`$ (16)   
$`Q+Q`$ $`=P`$ (17)   
###### Proof 3.6.

By infinite descent.

Suppose (16) holds with $`X,Y`$. Then some option of $`X+Y`$ must be a $`𝒫`$-game; without loss of generality, we assume $`X+Y^{}=P`$. But $`X=Q`$, and we have already ruled out $`Q+P=P`$ (equation (11)), $`Q+N=P`$ (equation (5)), and $`Q+O=P`$ (equation (12)), so we have $`X+Y^{}=Q+Q=P`$ (equation (17)).

Suppose (17) holds with $`X,Y`$. $`X`$ must have an $`𝒩`$-option or $`𝒬`$-option $`X^{}`$, but if $`X^{}=N`$ then $`X^{}+Y=N+Q=O`$ (equation (14)), which can’t happen; so $`X^{}=Q`$. Similarly, $`Y`$ has a $`𝒬`$-option $`Y^{}`$. $`X^{}+Y=O`$, so $`X^{}+Y^{}=Q+Q=N`$ (equation (16)).

(Note that the second half of this proof requires us to look two moves ahead, rather than just one move ahead as in the preceding proofs.)

The remaining case is surprisingly hard to dispose of; the proof requires us to look five moves ahead.

###### Claim 6.

It is impossible that

$$O+O=O$$
(18)   
###### Proof 3.7.

By infinite descent. Suppose (18) holds with $`X,Y`$. For all $`X^{}`$ we have $`X^{}+Y=N`$, so that $`X^{}+Y`$ must have some $`𝒫`$-option; but this $`𝒫`$-option cannot be of the form $`X^{}+Y^{}`$, since $`N+NP`$ (equation (9)). Hence there must exist an option $`X^{\prime \prime }`$ of $`X^{}`$ such that $`X^{\prime \prime }+Y=P`$. This implies that $`X^{\prime \prime }=N`$, since none of the cases $`O+O=P`$ (equation (3)), $`P+O=P`$ (equation (7)), $`Q+O=P`$ (equation (12)) can occur. Similarly, every $`Y^{}`$ has an option $`Y^{\prime \prime }`$ such that $`X+Y^{\prime \prime }=P`$, $`Y^{\prime \prime }=N`$. Since $`X^{\prime \prime }+Y`$ is a $`𝒫`$-game, $`X^{\prime \prime }+Y^{}`$ and $`X^{}+Y^{\prime \prime }`$ are $`𝒪`$-games and $`X^{\prime \prime }+Y^{\prime \prime }`$ is an $`𝒩`$-game. One of the options of $`X^{\prime \prime }+Y^{\prime \prime }`$ must be a $`𝒫`$-game; without loss of generality, say $`X^{\prime \prime \prime }+Y^{\prime \prime }=P`$. Since $`Y^{\prime \prime }=N`$ and since none of the cases $`N+N=P`$ (equation (9)), $`P+N=P`$ (equation (2)), $`Q+N=P`$ (equation (15)) can occur, $`X^{\prime \prime \prime }`$ must be an $`𝒪`$-game. But recall that $`X^{\prime \prime }+Y`$ is a $`𝒫`$-game, so that its option $`X^{\prime \prime \prime }+Y`$ is an $`𝒪`$-game. This gives us $`X^{\prime \prime \prime }+Y=O+O=O`$, which is an earlier-created solution to (18).

The proof of Claim 18 completes the proof of the validity of Table 2. Observe that this final clinching claim, which answers the article’s opening riddle in the negative, depends on five of the preceding six claims. Our straightforward question thus seems to lack a straightforward solution. In particular, one would like to know of a winning strategy for the Natalie-and-Percival coalition in the game $`G+H`$ that makes use of Oliver’s winning strategies for $`G`$ and $`H`$. Indeed, it would be desirable to have strategic ways of understanding all the facts in this section.

At this point it is a good idea to switch to a notation that is more mnemonically helpful than $`N`$, $`O`$, and $`P`$, vis-à-vis addition. Let $`\mathrm{𝟎}`$, $`\mathrm{𝟏}`$, and $`\mathrm{𝟐}`$ denote the Nim-positions $`0`$, $`1`$, $`11`$, respectively. Also, let $`\mathbf{}`$ be the Nim-position $`22`$. (Actually, we’ll want these symbols to represent the equivalence classes of these respective games, but that distinction is unimportant right now.) We will say that two games $`G`$, $`H`$ are similar if they have the same type; in symbols, $`GH`$. Every game is thus similar to exactly one of $`\mathrm{𝟎}`$, $`\mathrm{𝟏}`$, $`\mathrm{𝟐}`$, and $`\mathbf{}`$. We can thus use these four symbols to classify our games by type; for instance, instead of writing $`G=N`$, we can write $`G\mathrm{𝟏}`$.

Here is the rule for recursively determining the type of a game in terms of the types of its options, restated in the new notation:

* $`G`$ is of type $`\mathrm{𝟏}`$ exactly if it has some option of type $`\mathrm{𝟎}`$.
* $`G`$ is of type $`\mathrm{𝟐}`$ exactly if all of its options are of type $`\mathrm{𝟏}`$, and it has at least one option.
* $`G`$ is of type $`\mathrm{𝟎}`$ exactly if all of its options are of type $`\mathrm{𝟐}`$.
* $`G`$ is of type $`\mathbf{}`$ exactly if none of the above conditions is satisfied.

Here is the new addition table for 3-player game types; it resembles a faulty version of the modulo 3 addition table.

It is also worthwhile to present the “subtraction table” as an object of study in its own right. To this end define $`\mathrm{𝟑}=111`$ as an alternative to $`\mathrm{𝟎}`$.

The minuend is indicated by the row and the subtrahend by the column. Note that subtraction is not a true operation on games; rather, the assertion “$`\mathrm{𝟏}\mathrm{𝟐}`$ is $`\mathrm{𝟏𝟐}\mathbf{}`$” means that if $`G,H`$ are games such that $`G+H\mathrm{𝟏}`$ and $`G\mathrm{𝟐}`$ then $`H`$ $`\mathrm{𝟏}`$, $`\mathrm{𝟐}`$, or $`\mathbf{}`$.

The six entries in the upper left corner of the subtraction table (the only entries that are single types) correspond to assertions that can be proved by joint induction without any reference to earlier tables. In fact, a good alternative way to prove that addition satisfies Table 4 would be to prove that addition satisfies the properties implied by the six upper-left entries in Table 5 (by joint induction) and then to prove three extra claims: (i) if $`G\mathrm{𝟐}`$ and $`H\mathrm{𝟐}`$ then $`G+H\sim ̸\mathrm{𝟐}`$; (ii) if $`G\mathbf{}`$ and $`H\mathbf{}`$ then $`G+H\sim ̸\mathrm{𝟎}`$; and (iii) if $`G\mathbf{}`$ and $`H\mathbf{}`$ then $`G+H\sim ̸\mathrm{𝟏}`$.

## 4 Adding Games to Themselves

Another sort of question related to addition concerns the disjunctive sum of a game with itself. Recall that in two-player game theory, a strategy-stealing argument can be used to show that the sum of a game of type $`𝒩`$ with itself must be of type $`𝒫`$ (even though a sum of two distinct games of type $`𝒩`$ can be of either type $`𝒫`$ or type $`𝒩`$).

We seek a similar understanding of what happens when we add a three-player game to itself. Table 6 shows the possible types $`G+G`$ can have in our three-player theory, given the type of $`G`$.

To verify that all the possibilities listed here can occur, one can simply look at the examples given at the beginning of Section 3. To verify that none of the omitted possibilities can occur, it almost suffices to consult Table 4. The only possibility that is not ruled out by the addition table is that there might be a game $`X`$ with $`X\mathrm{𝟏}`$, $`X+X\mathrm{𝟏}`$.

Suppose $`X`$ were such a game. Then $`X`$ would have to have a $`𝒫`$-option $`X_1^{}`$ (now we call it a $`\mathrm{𝟎}`$-option) along with another option $`X_2^{}`$ such that $`X+X_2^{}\mathrm{𝟎}`$. This implies that $`X_1^{}+X_2^{}\mathrm{𝟐}`$ and $`X_2^{}+X_2^{}\mathrm{𝟐}`$. Since $`X_1^{}\mathrm{𝟎}`$, the condition $`X_1^{}+X_2^{}\mathrm{𝟐}`$ implies (by way of Table 4) that $`X_2^{}\mathrm{𝟐}`$. But $`X_2^{}+X_2^{}\mathrm{𝟐}`$ implies (by way of Table 4) that $`X_2^{}\mathrm{𝟏}\text{ or}\mathbf{}`$. This contradiction shows that no such game $`X`$ exists, and completes the verification of Table 6.

In the same spirit, we present a trebling table (Table 7), showing the possible types $`G+G+G`$ can have given the type of $`G`$.

To prove that all the possibilities listed in the first three rows can actually occur, one need only check that $`0+0+0\mathrm{𝟎}`$, $`\{\{2\}\}+\{\{2\}\}+\{\{2\}\}\mathbf{}`$, $`1+1+1\mathrm{𝟎}`$, $`2+2+2\mathbf{}`$, $`11+11+11\mathrm{𝟎}`$, and $`\{2\}+\{2\}+\{2\}\mathbf{}`$. To prove that the nine cases not listed cannot occur takes more work.

Four of the cases are eliminated by the observation that $`G+G+G`$ can never be of type $`\mathrm{𝟏}`$ (the second and third players can always make the Next player lose by using a copy-cat strategy). Tables 3 and 5 allow one to eliminate three more cases. The next two claims take care of the final two cases.

###### Claim 7.

If $`G\mathbf{}`$, then $`G+G+G\sim ̸\mathrm{𝟐}`$.

###### Proof 4.1.

Suppose $`X\mathbf{}`$ with $`X+X+X\mathrm{𝟐}`$. Let $`X^\alpha `$ be an option of $`X`$. Since $`X^\alpha +X+X\mathrm{𝟏}`$, $`X^\alpha +X+X`$ must have a $`\mathrm{𝟎}`$-option of the form $`X^\alpha +X^\beta +X`$ (for $`X^\beta `$ some option of $`X`$) or of the form $`X^{\alpha \gamma }+X+X`$ (for $`X^{\alpha \gamma }`$ some option of $`X^\alpha `$). In either case, we find that the $`\mathbf{}`$-game $`X`$, when added to some other game ($`X^\alpha +X^\beta `$ or $`X^{\alpha \gamma }+X`$), yields a game of type $`\mathrm{𝟎}`$; this is impossible, by Table 4.

###### Claim 8.

If $`G\mathrm{𝟐}`$, then $`G+G+G\sim ̸\mathrm{𝟐}`$.

###### Proof 4.2.

Suppose $`X\mathrm{𝟐}`$ with $`X+X+X\mathrm{𝟐}`$. Notice that $`X^{}+X+X\mathrm{𝟏}`$ for every option $`X^{}`$ of $`X`$.

Case I: There exist options $`X^\alpha `$, $`X^\beta `$ of $`X`$ (possibly the same option) for which $`X^\alpha +X^\beta +X\mathrm{𝟎}`$. Then its option $`X^\alpha +(X^\beta +X^\beta )\mathrm{𝟐}`$. Since $`X^\alpha \mathrm{𝟏}`$, Table 5 gives $`X^\beta +X^\beta \mathrm{𝟏}`$. But this contradicts Table 6, since $`X^\beta \mathrm{𝟏}`$.

Case II: There do not exist two such options of $`X`$. Let $`X^\alpha `$ be an option of $`X`$. Since $`X^\alpha +X+X\mathrm{𝟏}`$, and since there exists no $`X^\beta `$ for which $`X^\alpha +X^\beta +X\mathrm{𝟎}`$, there must exist an option $`X^{\alpha \gamma }`$ of $`X^\alpha `$ such that $`X^{\alpha \gamma }+X+X\mathrm{𝟎}`$. $`X+X\mathrm{𝟏}\text{ or }\mathbf{}`$, by Table 6, but $`X+X`$ cannot be of type $`\mathbf{}`$, since adding $`X^{\alpha \gamma }`$ yields a $`\mathrm{𝟎}`$-position. Hence $`X+X\mathrm{𝟏}`$, and Table 5 implies $`X^{\alpha \gamma }\mathrm{𝟐}`$. Since $`X+X\mathrm{𝟏}`$, there must exist an option $`X^\delta `$ with $`X^\delta +X\mathrm{𝟎}`$. Everything we’ve proved so far about $`X^\alpha `$ applies equally well to $`X^\delta `$ (since all we assumed about $`X^\alpha `$ was that it be some option of $`X`$). In particular, $`X^\delta `$ must have an option $`X^{\delta ϵ}`$ such that $`X^{\delta ϵ}\mathrm{𝟐}`$. However, since $`X^{\delta ϵ}+X`$ is an option of the $`\mathrm{𝟎}`$-position $`X^\delta +X`$, $`X^{\delta ϵ}+X\mathrm{𝟐}`$. Hence $`X^{\delta ϵ}`$ and $`X`$ are two $`\mathrm{𝟐}`$-positions whose sum is a $`\mathrm{𝟐}`$-position, contradicting Table 4.

## 5 Nim for Three

We wish to classify all Nim-positions as belonging to $`𝒩`$, $`𝒪`$, $`𝒫`$, or $`𝒬`$ — or rather, as we now put it, as being similar to $`\mathrm{𝟎}`$, $`\mathrm{𝟏}`$, $`\mathrm{𝟐}`$, or $`\mathbf{}`$. We will actually do more, and determine the equivalence classes of Nim games. Table 8 shows the games we have classified so far (on the left) and their respective types (on the right).

We will soon see that every Nim-game is equivalent to one of the Nim-games in Table 8. We call these reduced Nim-positions. The last paragraph of this section gives a procedure for converting a three-player Nim-position into its reduced form.

Throughout this section (and the rest of this article), the reader should keep in mind the difference between the notations 2 and $`\mathrm{𝟐}`$. The former is a single Nim-heap of size 2; the latter is the game-type that corresponds to a second-player win. Note in particular that 2 is not of type $`\mathrm{𝟐}`$ but rather of type $`\mathrm{𝟏}`$.

We start our proof of the validity of Table 8 by showing that no two games in the table are equivalent to each other. In this we will be assisted by Tables 9 and 10.

Table 9 gives the types for games of the form $`1^m+2_n`$. Each row of the chart gives what we shall call the signature of $`1^m`$, relative to the sequence $`2,\{2\},\{\{2\}\},\mathrm{}`$. Since no two games of the form $`1^m`$ have the same signature, no two are equivalent.

Similarly, Table 10 is the signature table for games of the form $`1^m2`$, relative to $`2_n`$.

We see that all the games $`1^m`$ and $`1^m2`$ are distinct.

What about $`22`$? It can’t be equivalent to $`1^{3k+1}2`$ for any $`k`$ (even though both are $`\mathbf{}`$-games), because $`22+1\mathbf{}`$ while $`1^{3k+1}2+1=1^{3k+2}2\mathrm{𝟏}`$.

What about 3? It can’t be equivalent to $`1^{3k+1}`$ for any $`k`$, because $`3+1\mathbf{}`$ while $`1^{3k+1}+1\mathrm{𝟐}`$; it can’t be equivalent to $`1^{3k}2`$ because $`3+2_2\mathrm{𝟏}`$ while $`1^{3k}2+2_2\mathbf{}`$; it can’t be equivalent to $`1^{3k+2}2`$ because $`3+1\mathbf{}`$ while $`1^{3k+2}2+1=1^{3k+3}2\mathrm{𝟏}`$; and it can’t be equivalent to $`2`$ because $`\{0,11\}+2\mathrm{𝟐}`$ while $`\{0,11\}+3\mathbf{}`$.

Now that we know that all of the Nim games in Table 8 are inequivalent, let us show that every Nim game is equivalent to one of these.

###### Claim 9.

$`mn\mathbf{}`$ for all $`m,n2`$.

###### Proof 5.1.

Any two players can gang up on the third, by depleting neither heap until the victim has made his move, and then removing both heaps.

###### Claim 10.

The following are true for all games $`G`$:

1. $`Gn\sim ̸\mathrm{𝟎}`$ for $`n2`$.
2. $`Gn\sim ̸\mathrm{𝟐}`$ for $`n3`$.
3. If $`Gm\mathrm{𝟏}`$ then $`Gn\mathrm{𝟏}`$, for $`m,n2`$.
4. $`G1n\sim ̸\mathrm{𝟐}`$ for $`n2`$.
5. $`Gmn\sim ̸\mathrm{𝟏}`$ for $`m,n2`$.
6. $`Gmn\sim ̸\mathrm{𝟐}`$ for $`m,n2`$.
7. $`Gmn\sim ̸\mathrm{𝟎}`$ for $`m,n2`$.

###### Proof 5.2.

(a) Suppose $`Gn\mathrm{𝟎}`$. Then its options $`G1`$ and $`G`$ are $`\mathrm{𝟐}`$-games. But since $`G`$ is also an option of $`G1`$, this is a contradiction.

(b) Suppose $`Gn\mathrm{𝟐}`$. Then $`G`$, $`G1`$, and $`G2`$ are all $`\mathrm{𝟏}`$-games, and in particular $`G2`$ must have a $`\mathrm{𝟎}`$-option. That $`\mathrm{𝟎}`$-option can be neither $`G`$ nor $`G1`$, so there must exist $`G^{}2\mathrm{𝟎}`$, contradicting (a).

(c) Assume $`Gm\mathrm{𝟏}`$. Then either $`G\mathrm{𝟎}`$ or $`G1\mathrm{𝟎}`$ (no other option of $`Gm`$ can be of type $`\mathrm{𝟎}`$, by (a)), and in either case $`Gn\mathrm{𝟏}`$.

(d) Suppose $`G1n\mathrm{𝟐}`$. Then $`G1`$, $`G11`$, and $`Gn`$ are all $`\mathrm{𝟏}`$-games. $`Gn`$ must have a $`\mathrm{𝟎}`$-option, but $`G1\mathrm{𝟏}`$ and no option $`G^{}n`$ or $`Gm`$ ($`2m<n`$) can be a $`\mathrm{𝟎}`$-game (by (a)), so $`G`$ itself must be a $`\mathrm{𝟎}`$-game. Also, since $`G11\mathrm{𝟏}`$ and $`G1\sim ̸\mathrm{𝟎}`$, there must exist $`G^{}`$ with $`G^{}11\mathrm{𝟎}`$. Then $`G^{}1\mathrm{𝟐}`$ and $`G^{}\mathrm{𝟏}`$, which is inconsistent with $`G\mathrm{𝟎}`$.

(e) Every option of $`Gmn`$ has a component heap of size 2 or more, so $`G+m+n`$ has no $`\mathrm{𝟎}`$-options, by (a).

(f) Suppose $`Gmn\mathrm{𝟐}`$. Then $`G`$ can’t be $`0`$ (by Claim 9), so it must have an option $`G^{}`$; $`G^{}mn\mathrm{𝟏}`$, contradicting (e).

(g) Suppose $`Gmn\mathrm{𝟎}`$. Then $`G`$ can’t be $`0`$ (by Claim 9), so it must have an option $`G^{}`$; $`G^{}mn\mathrm{𝟐}`$, contradicting (f).

Note that (e), (f), and (g) together imply that $`Gmn\mathbf{}`$ for all $`m,n2`$.

###### Claim 11.

The following are true for all games $`G`$:

1. $`mn`$ for $`m,n3`$.
2. $`1m1n`$ for $`m,n2`$.
3. $`Gmn22`$ for $`m,n2`$.

###### Proof 5.3.

(A) Take an arbitrary game $`X`$. We know that each of $`Xm`$, $`Xn`$ is either of type $`\mathrm{𝟏}`$ or type $`\mathbf{}`$ (by (a), (b) above). If either of them is a $`\mathrm{𝟏}`$-game, then so is the other (by (c)), and if neither of them is a $`\mathrm{𝟏}`$-game, then both are $`\mathbf{}`$-games. Either way, $`m+X`$ and $`n+X`$ have the same type.

(B) The proof is similar, except that one needs (d) instead of (b).

(C) For all $`X`$, $`Gmn+X=(GX)mn\mathbf{}`$ and $`22+X=(X)22\mathbf{}`$.

To reduce a given Nim-position $`G=n_1+n_2+\mathrm{}+n_r`$ to one of the previously tabulated forms, first replace every $`n_i>3`$ by 3. This puts $`G`$ in the form $`1^a2^b3^c`$. If $`b+c2`$, then we have $`G22`$. Otherwise, we have $`G`$ in the form $`1^a`$, $`1^a2`$, or $`1^a3`$. Since $`1312`$, the last of these cases can be reduced to $`1^a2`$ unless $`a=0`$.

## 6 Equivalence Classes

The Nim game $`22`$ has the property that if one adds to it any other Nim-position, one gets a game of type $`\mathbf{}`$. In fact, if one adds any game whatsoever to $`22`$, one still gets a game of type $`\mathbf{}`$. $`22`$ is thus an element of an important equivalence class, consisting of all games $`G`$ such that $`G+X\mathbf{}`$ for all games $`X`$. We call this class the equivalence class of infinity. This equivalence class is a sort of a black hole, metaphorically speaking; add any game to the black hole, and all you get is the black hole.

If you take a two-player game for which a nice theory exists and study the three-player version, then it is unfortunately nearly always the case that most of the positions in the game are in the equivalence class of infinity.

There are some games which are “close” to infinity. Paradoxically, such games can give us interesting information about games that are very far away from infinity. Consider, for instance, the $`\mathrm{𝟐}`$-game $`2_1=\{2\}`$ (the game whose sole option is a Nim-heap of size 2).

###### Claim 12.

The only game $`G`$ for which $`G+2_1\sim ̸\mathbf{}`$ is the game 0.

###### Proof 6.1.

Let $`X`$ be the simplest game not identical to 0 such that $`X+2_1\sim ̸\mathbf{}`$.

Case I: $`X+2_1\mathrm{𝟎}`$. Then $`X+2\mathrm{𝟐}`$. But Claim 10(b), together with the fact that $`2`$ is equivalent to every Nim-position $`n`$ with $`n3`$, tells us that this can’t happen.

Case II: $`X+2_1\mathrm{𝟏}`$. The winning option of $`X+2_1`$ can’t be $`X+2`$, by Claim 10(a), so it must be an option of the form $`X^{}+2_1`$. But then $`X^{}+2_1\mathrm{𝟎}`$, which contradicts the assumed minimality of $`X`$. ($`X^{}=0`$ won’t help us, since $`0+2_1\mathrm{𝟐}`$, not $`\mathrm{𝟎}`$.)

Case III: $`X+2_1\mathrm{𝟐}`$. Letting $`X^{}`$ be any option of $`X`$, we have $`X^{}+2_1\mathrm{𝟏}`$. This contradicts the assumed minimality of $`X`$.

This implies that no game is equivalent to 0.

## 7 Open Questions

###### Question 7.1.

How do the doubling and tripling tables (Tables 6 and 7) extend to higher compound sums of a game with itself?

###### Question 7.2.

Is there a decision procedure for determining when two impartial three-player games are equivalent to each other?

###### Question 7.3.

What does the “neighborhood of infinity” look like? The game $`2_1\mathrm{𝟐}`$ has the property that when you add it to any non-trivial game, you get $`\mathbf{}`$. Is there a game of type $`\mathrm{𝟏}`$ with this property? Is there one of type $`\mathrm{𝟎}`$ with this property?

###### Question 7.4.

How does the theory generalize to $`n`$ players, with $`n>3`$? It is not hard to show that the portion of Table 5 in the upper left corner generalizes to the case of more than three players in a straightforward way. However, carrying the theory beyond this point seems like a large job. Here are two particular questions that seem especially interesting: Can an $`n`$-fold sum of a game with itself be a win for any of the players other than the $`n`$th? Does there exist a “black hole” $`X`$ such that for all games $`Y`$, $`X+Y`$ is a win for any coalition with over half the players?

## 8 Acknowledgments

This research was supported by a Knox Fellowship from Harvard College. I express deep appreciation to John Conway for his encouragement and for stimulating conversations. I also thank Richard Guy and Phil Straffin for many helpful remarks on the manuscript.