JOURNAL OF COMBINATORIALTHEORY, Series A 37,205-230( 1984) Mist&-e Annihilation Games* THOMAS S. FERGUSON Department of Mathematics, University of California, Los Angeles, California 90024 Communicated by the Managing Editors Received April 20, 1982 Graph games with an annihilation rule, as introduced by Conway, Fraenkel and Yesha, are studied under the midre play rule for progressively finite graphs that satisfy a condition on the reversibility of non-terminal Sprague-Grundy zeros to Spragu+Grundy ones. Two general theorems on the Spragu+Grundy zeros and ones are given, followed by two theorems characterizing the set of P-positions under certain additional conditions. Application is made to solving many subtraction games, and solutions to two games not covered by the general theory are presented indicating a direction for future research. 0 1984 Academic PICSS, Inc. 1. INTRODUCTION This paper is concerned with games that are played on a directed graph, G, in the following manner. At the start of the game, a finite number of counters is placed on the vertices of the graph. A move consists of taking exactly one counter and moving it from its vertex along one of the directed edges to a new vertex. More than one counter may be at a vertex. Players alternate moves, and play continues until one of the players is unable to make a move because all counters are in terminal vertices of the graph, i.e., vertices from which no move is possible. If play continues forever, the game is declared a tie. If play stops, the player who moved last is declared the winner if the normal play rule is in force. Under the mis2re play rule, the player who moved last loses. Games of this sort in which the graph may have circuits or loops are called “loopy games” and have been studied by Fraenkel and Per1 [ 11, Fraenkel and Tassa [2], and Conway [3]. Some of the theory also appears in Chapter 11 of Conway’s book [4]. Such games are impartial in the sense that the moves available at any position do not depend on which player is to move. Partizan loopy graph games in which there are two graphs on the * Research was partially supported by NSF Grant No. MCS80-02732. 205 0097.31651$834. 00 Copyright Q 1984 by Academic Press, Inc. All rights of reproduction in any form reserved. 206 THOMAS S. FERGUSON same set of vertices, one graph for each player, have been studied by Flanigan [ 51. In this paper, we restrict attention to graphs that are progressively finite, that is, for every vertex v of G the game starting with a single counter on v must end in a finite number of moves. Games on such a graph are not loopy; there are no ties. In addition, we assume that the Sprague-Grundy function (SG-function) of the graph is finite. The SG-function, g, is defined on the vertices of the graph with values in the non-negative integers as follows. Call a vertex w, a follower of vertex v, if there is a directed edge from v to w, denoted by v + w. Then g(v) = min{ m E Z : m # g(w) for some follower w of v } (1) =mex{g(w): v-t w} where mex stands for minimal excludant (see Conway [4]), For terminal vertices v, g(v) = 0 by this definition. Then this definition may be applied inductively to determine the SG-values of other vertices. A position in which there are n counters on vertices v, ,..., v,, duplication allowed, may be described by the multi-set x = {v, ,..., v,}. A P-position is one in which the previous player, the one who has just moved, can insure himself a win with optimal play. An N-position is one in which the player next to move can force a win with optimal play. Each position is either a P- position or an N-position. A game may be said to be solved if a simple description is given of the P-positions, one such that for a given position it can be determined in “polynomial time” whether or not the position is a P- position. As an example, the well-known game Nim has a graph G whose vertices are the non-negative integers and whose directed edges are from any integer to any lesser integer. Thus, in the graph game Nim, any counter may be moved from its vertex, n, to any vertex m provided m < n. The only terminal vertex is 0, and it is easy to see that the SG-function takes values g(n) = n for n = 0, 1, 2 ,.... The solution to this game was given by Bouton [6] in terms of the operation of binary addition of integers without carry, known as nim-sum. If r and s are non-negative integers with binary expansions r = Cr r,2’ and s = 27 s,2’ for some m, where each ri and si are 0 or 1, then the nim-sum of randsist=rIs,wheret=Crti2’andti=r,+simod2andt,=Oor 1. Nim-sum is associative and commutative since addition mod 2 is. Bouton’s characterization of the P-positions for Nim with the normal play rule has been generalized into the basic theorem of the subject of impartial games with normal play by Sprague [7] and Grundy [8]. This theorem states that for progressively finite graphs with finite SG-function g, a position MISIhE ANNIHILATION GAMES 207 x= iv i,..., v,} is a P-position for normal play if, and only if, the nim-sum of the SG-values of the components is zero, that is, g(x) = g(vJ + * * - ? g(v,) = 0. (2) For misere play, the situation is much more complex. An excellent treatment of impartial games with midre play is found in Chapter 12 of Conway [4], in which one class of games called tame games are defined for which the solution can be easily found. A subclass of the tame games are the miske graph games whose graph satisfies the following condition. CONDITION A. Every non-terminal vertex of SG-value zero has a follower of SG-value one. It is easily seen that the game Nim satisfies this condition vacuously. Bouton [6] also solved the misere version of Nim and noted that it required only a small modification of the solution of the normal version of Nim. In Ferguson [9, Corollary of Theorem 21, it is noted that the natural generalization of Bouton’s solution is also a solution to a general mistre graph game if, and only if, the graph satisfies Condition A. (Note in that paper, a different definition of graph game is used, one that allows “splitting.“) This solution is the following. Let Q, = {x = {v~,..., v,}] g(x) = 1 and g(vi) < 1 for all i}, and Q, = {x = {I,+,..., v,}] g(x) = 0 and g(v,) > 1 for some i}. Then the set of P-positions is p=Q,uQ,- (3) The concept of annihilation games was proposed by Conway and studied by Fraenkel [lo] and Fraenkel and Yesha [ 111. See also Fraenkel, Tassa and Yesha (1978) [ 121. Such games are played on a directed graph with a finite number of counters on distinct vertices of the graph. Play proceeds as in ordinary graph games until some counter is moved to a new vertex which is already occupied by another counter, when the annihilation rule comes into play: both counters are annihilated, i.e., removed from play. The multiset x used to describe a position now becomes a set. For progressively finite graphs with finite SG-functions, the P-positions for normal play in annihilation games are exactly the same as those in games without the annihilation rule, namely, positions that satisfy (2). For loopy graphs, however, annihilation games are quite distinct and it is to these games that Fraenkel and Yesha devoted their study. 208 THOMAS S. FERGUSON It is the purpose of this paper to study annihilation games on progressively finite graphs with finite SG-functions under the midre play rule. It turns out that the theory is quite distinct from and more complex than that without the annihilation rule. Even misbre annihilation Nim is distinct from misere Nim. For immediate comparison we give the solution here; this follows immediately from Theorem 3 in Section 3. For misere annihilation Nim, the set of P-positions is P = Q, U Q,, where Q, = {x = {vl ,..., v,,}] g(x) = 1 and the vi > 2 can be grouped into pairs of the form { 2j, 2j + 1 } for various j > 1 }, Q, = {x = (v~,..., v, }I g(x) = 0 and the v1 > 2 cannot be so grouped}. Asanexample,ifx={10,21,20,11},theng(x)=10~11?20?21=O but x is not in Q, since there exists a grouping into pairs { 10, 1 1 } and { 20,2 1 }. This can be moved into Q, by using one of the annihilation moves, 21-120 or ll-+ 10. In Section 2, it is shown for mistre annihilation games on progressively finite graphs with finite SG-function satisfying Condition A, that there is only one kind of vertex of SG-value 0 and only one kind of vertex of SG- value 1. That is, a counter on one vertex of SG-value 0 or 1 may be transferred to another vertex of the same SG-value without changing the outcome of the game. That this is not true for vertices of SG-value 2 or greater may be seen by referring to the examples of Section 4. In Section 3, two general theorems are given that characterize the set of P- positions in an easily computable fashion, provided certain additional conditions are satisfied. The first theorem applies to unbounded SG-functions provided the graph satisfies an additional Condition B on the edges joining vertices of SG-values greater than one. In the special case of graphs with SG-functions having values no greater than 3, a considerably weaker Condition C is used in the next theorem. In Section 4, the theorems of Section 3 are applied to the analysis of various subtraction games. Such games are known to satisfy Condition A (Ferguson [9]). In particular, all subtraction games with subtraction sets a subset of (1,2,3,4,5,6, 7) are scanned to see how successful the theorems of Section 3 are. On this basis, one feels they are quite successful, and the variety of simpler statements one can give to the solutions show the strength and usefulness of the theorems. The failures are collected in Sections 4.10 and 4.11. The former section indicates a need to generalize Theorem 3, as none of the games there have been solved. The latter section contains the only two games with SG-values no greater than three found earlier that did not satisfy Condition C. Solutions to both games are given in this section MISBRE ANNII-IILATION GAMES 209 indicating that Condition C can be weakened, and holding out hope that a general solution to games with SG-values no greater than 3, satisfying Condition A, can be found. 2. UNIQUENESS OF SG-OS AND SG-1s It is assumed throughout the rest of this paper that G is a progressively finite graph with finite SG-function, g. It is also assumedt hroughout without further explicit mention that Condition A is satisfied. This is a fairly restrictive assumption. For example, it rules out the very simple graph . a b C d 0 1 2 0 The vertex d has SG-value 0 and its only follower is c of SG-value 2. No general theorems, not using Condition A, are presented here. We are concerned solely with annihilation games on G under the misbre play rule. Without the annihilation rule, the P-positions for all such games are described by (3), the analogue of Bouton’s solution. Henceforth, the word “game” will be short for midre annihilation game. In addition, we use the notation SG-k as short for vertex of SG-value k, where k is a non-negative integer. The first theorem implies that all SG-OS are equivalent in the sense that transferring a counter from one SG-0 to another does not change the outcome (i.e., a P-position stays P, and an N-position stays N). In particular, removing the counter from an SG-0 does not change the outcome, since it would be like transferring it to a terminal node. The second theorem shows that all SG-1s are equivalent. In addition, it shows that removing the counters simultaneously from two SG-1s does not change the outcome. These theorems are proved by contradiction and induction using the notion of the simplicity of a position. We say a position x is simpler than a position y if there is a sequence of moves that takes y into x. LEMMA 1. The game with only one counter on non-terminal vertex v is a P-position if, and only if, g(v) = 1. This follows from the Corollary to Theorem 2 of Ferguson [9] since annihilation plays no role. It can otherwise be easily seen by checking that moving to an SG-1 is a optimal strategy when Condition A is satisfied. It is interesting to note that the only place Condition A is explicitly used in the proofs contained in this paper is in this lemma. 210 THOMAS S.FERGUSON We note the following characterization of the P- and N-positions for mike graph games. (i) Every terminal position is in N. (ii) Every follower of a P-position is an N-position. (iii) Every non-terminal N-position has a P-position as a follower. THEOREM 1. If x= {Up,..., u,} md Y= {Vl,“‘, vn, v,+1}, where g(u,+,) = 0, then x and y have the same outcome (i.e., both are N or both are P). ProoJI: Suppose the theorem is false. Let x and y be a simplest counterex- ample in the sense that no counterexample has a simpler x and for that x no counterexample has a simpler v,+ i . Case 1. x E P and y E N. Since x is not terminal, neither is y and y+y’EP. la. If the move involves one of the components of X, say v, --) V; without annihilation, then x’ = {vi ,..., u;} E N and y’ E P gives a simpler counterexample. lb. If the move annihilates one of the components of x, say v, + u,, _ , , then x’ = {vi,..., o,-~} E N and y’ E P is simpler. lc. If the move annihilates v,+ i, say v, --f u,+ 1, then y’ = {u 1,*--, z),-~} EP and x’= {u, ,..., v,,-i,u,+i} EN is simpler. Id. If the move involves moving the new component without annihilation, say v,+ i --t u;+ i, then there exists a further move VA+, + u:+ i with g(vp+ ,) = 0. If there is no annihilation, this gives a counterexample with a simpler y. If there is annihilation, say u:,, = v,, then y” = IV l,“‘, 21,-l } E N and x is simpler. le. If the move involves the new component with annihilation, say V n+1+ U”, then since g(v,) cannot be zero, there is a move u, + VAs uch that g(v;) = 0. Whether or not this causes annihilation, the resulting y’ E P and x’ E N is simpler. Case2 . x e N and y E P. By Lemma 1, x is not terminal since then y would be in N. Hence there exists a move x + x’ E P. 2a. If the move causes annihilation, say u, + v,-i, then x’ E P and Y' = {q,..., 0,-z, u,+1 } E N is a simpler counterexample. 2b. If the move causes annihilation with v,+ i, u, --f v,+ i, then y’ = Iv 1,*-*, u,-i} EN and x’ = {ui,..., u,-~, u,+r} E P is simpler. 2c. If the move is without annihilation, u, + VA, then x’ E P and y’ = {v i ,..., VA, v,+ i } E N is simpler. MIShE ANNIHILATION GAMES 211 In proving the corresponding result about SG-Is, we prove both that any SG-1 may be exchanged for any other, and that two SG-1s may be removed without changing the outcome. These two statements are proved together. T~~XUM 2. If x= {ul ,..., ?I,-~, un} and y= {u ,,..., unpl, u:} with g(u,) = g(uA) = 1, then x and y have the same outcome, If x = (0, ,..., un} and Y= {ul,..., u,, u,+1, u,+2} with g(u,+l ) = g(u,+,) = 1, then x and y have the same outcome. Proof: Suppose the theorem is false. Find a counterexample with a simplest x and y with the smallest value of n. There are four cases to consider, whether x is a counterexample to the first or second statement, and whether x E P and y E N or vice versa. From Theorem I, assume without loss of generality that no component of x has SG-value 0. Case 1. x = {u, ,..., u,} E P with g(u,) = 1 and y = {u, ,..., u,-i, VA} EN with g(uA) = 1. There exists a move y+y’ E P. la. If the move is from a vertex also in x, say u,-, + u;-,, with- out annihilation, then x’ = {ul ,..., VA-, , un} E N and y’ E P is a simpler counterexample; with annihilation, say u;-~ = u,-*, then x’ = Iv , ,***, u,-3 9 un} EN is simpler; with annihilation of u;, say u:-i = u;, then y’ = {u, ,..., u,-~} E P and x’ = {u ,,..., un-*, VA, u,} EN with g(uL) = g(u,) = 1 gives a counterexample with a smaller n. lb. If the move is from u; and causes annihilation, say u; + u,- i, then since g(u,-,) # 0 or 1, there is a move u,-, + uk- i such that g(uAel) = 1. With no annihilation, this gives x’ = {u, ,..., unP2, VA-, , un} E N with g(uA-,) = g(u,) = 1; with annihilation of u,, this gives x’ = {VI )..., II,-,} E N; with annihilation of say u,-~, this gives x’ = {?I1 )..., u,- 3, u,} EN with g(u,-2)=g(u,) = 1. This gives a simpler counterexample with y’ = {u, ,..., u,-,} E P. lc. If the move is VA+ ui with no annihilation, g(u:) cannot be 0 without contradicting Theorem 1 (since u, can be moved to an SG-0), so that there is a further move u; + ur with g(uF) = 1; with or without annihilation, this gives a simpler counterexample. Case 2. x = {u I ,..., u,} EN with g(u,) = 1 and y = {vi ,..., u,-~, u;} E P with g(uA) = 1. This case is symmetrical to Case 1, with x and y interchanged. Cuse3. x= {u i ,..., u,}EP and V={U ,,..., z~,,u,,+~,u,+~}EN with g(u,+ ,) = g(u,+,) = 1. There exists a move y + y’ E P. 3a. If the move is from a vertex also in x, say u, + u;, then whether or not there is annihilation, x’ = {u I ,..., VA} E N and y’ E P is simpler. 212 THOMAS S.FERGUSON 3b. If the move is from one of the additional vertices of y with annihilation, say v, + I + v,, then since g(v,) # 0 or 1, there is a move v, + VA with g(vA) = 1 taking x into x’ = {vi,..., VA} E N. With or without annihilation this is simpler. 3c. If the move is v,+i + VA+, without annihilation, then since g(vA+ i) # 0 or 1, there is a move VA+i + v:+, with g(ui+i) = 1. With or without annihilation this gives a simpler y” E N. Case 4. x = {ul,..., v,}EN and y= {vi,...,v,, v,+i, v~+~}EP with g(v,+J = g(v,+,) = 1. x cannot be, terminal since y can be moved to y’ = {v ,,...,v,,v,+1,v~+*}EN with g(v; + J = 0, which contradicts Lemma 1, Theorem 1. Hence, there exists a move x --f x’ E P. The same move in y, say y + y’ E N, gives a simpler counterexample whether or not there is annihilation. As a corollary to Theorems 1 and 2, we have a characterization of the P- positions among these positions with counters only on vertices having SG- values 0 or 1. COROLLARY. Under Condition A, ifx = {vl ,..., v,,} with each g(vi) = 0 or 1, then x is a P-position if and only if g(vi) = 1 for an odd number of Vi. Of course, the optimal strategy and hence simple direct proof of this corollary is clear. If your opponent moves from a position of this form, you can always return it to a position of this form. Your opponent will never be left without a move. Theorem 1 implies that there is only one type of vertex with SG-value 0. We may as well assume that every vertex of SG-value 0 is terminal; that is, the outcome of the game is not changed if all edges leading out of vertices with SG-value 0 are deleted. Similarly by Theorem 2, there is only one type of vertex of SG-value 1. The outcome of the game is not changed if all edges leading out of each SG-1 are deleted except for one edge, that edge going to a terminal vertex. Together, these theorems imply that the whole structure of the game on the graph is determined by the connections between the other vertices, that is, those vertices of SG-value 2 or greater. We call the subgraph on the set V, of vertices of SG-value 2 or greater the reduced graph. 3. Two CHARACTERIZATION THEOREMS We shall now prove two general theorems characterizing the set, P, of P- positions in the game under conditions involving only the connections between vertices with SG-values 2 or greater. The proofs use the standard procedure of verifying statements (i), (ii), and (iii) of the previous section. MISkFU? ANNIHILATION GAMES 213 In Theorem 3, we find the P-positions provided the graph satisfies the following additional condition. For each even integer k, a vertex u of SG- value k is called a terminal k if it does not have a follower of SG-value k + 1. For each even k > 2, and for each terminal k, v, form the set W by starting with W = {v} and then recursively joining to W all vertices of SG- value k or k + 1 that have a follower in W. Label these sets W, , W, ,..., in some order. Every SG-J’ for j > 2 belongs to at least one of the sets Wi. CONDITION B. The sets W,, W, ,..., are disjoint, and for every vertex v of SG-value 2n or 2n + 1 for n > 1 and for every k, 1 < k < n, either Bl: there exist some W, and w, E W, and w1 E W, with v + w, , 2, -, w2, g(wl) = 2k and g(wJ = 2k + 1, or B2: for m = 2k and m = 2k + 1, there exist w, and w2 in distinct Wi with u+wl,v+w2 and g(wJ = gh> = m. For Nim, with vertices {0, 1, 2,...} and SG-function g(v) = ZJ, the sets WI 9 w, v..., me {2, 31, {4, 51, {6, 7},..., and so satisfy Condition B. The main part of Condition B is that the sets Wi be disjoint. If the Wi are disjoint, the rest of Condition B is also necessary for Theorem 3 in the sense that on such graphs positions x can be found for which the conclusion of Theorem 3 is not true. As a counterexample, consider the reduced graph The position x consisting of the vertex of SG-value 4 and the lower vertex of SG-value 2 is a P-position with SG-value 6. THEOREM 3. Under Condition B, P = Q, U Q, where Q, = {x: g(x) = 1 and each set W, contains an even number of components of x), Q, = {x: g(x) = 0 and some set W, contains an odd number of components of x}. ProoJ (i) Clearly no terminal x is in P. (ii) SupposexEQ,,x+y,andg(y)=O.AchangeO+lor l+Oin the SG-value occurs if and only if one of the components is moved from SG- 214 THOMAS S. FERGUSON value 2j to 2~‘+ 1, or from SG-value 2j + 1 to 2j for some j> 0 with or without annihilation. Since the sets IV, are disjoint, y also has an even number of components in each Wi, and so is not in Q, . On the other hand, if x E Q,, x -+y and g(y) = 1, the same argument works to show that y must have an odd number of components in some Wi and so is not in Q,. (iii) Suppose x 6??Q , U Q,, and x is not terminal. Case 1. g(x) > 2. There exists a move x + y with g(v) = 0 involving the moving of some component of x from one vertex to a follower u’ of lesser SG-value. If y E Q,, we are done. If not, y has an even number of components in each W,. Therefore, move the indicated component either to a vertex of the same SG-value as V’ in another Wj (case B2) or to a vertex of SG-value one greater or one less than V’ depending on whether g(v’) is even or odd (in the same Wj (case Bl) if its SG-value is greater than one). Case2 . g(x) = 1 and some Wi contains an odd number of componentso f x. Since g(x) is odd, there is at least one component with odd SG-value. Moving any such component to a vertex with SG-value 1 less does not disturb the parity in the Wi with or without annihilation and puts x into Q,. Case 3. g(x) = 0 and there is an even number of componentso f x in each Wi and x is not terminal. If there exists a component of x with odd SG- value, then any move from SG-value 2j + 1 to 2J (j > 0) changes the SG- value of x by 1 without disturbing the parity in the Wi, and puts x into Q,. If all components of x have SG-value 0 then x E N by the Corollary of Theorem 2. Otherwise, all components of x have even SG-values, at least one of SG-value 2 or greater, so for somej > 1 there are at least two components of x with SG-values 2j in the same W,. At least one of them has a follower of SG-value 2j + 1. This move would put x into Q,. We now assume that the graph has no SG-values greater than 3, and obtain in Theorem 4 a considerable improvement over the previous theorem. Let Vi denote the set of vertices of SG-value greater than 1. Every graph that has an SG-2 has a terminal 2. A terminal 2 is a terminal vertex of the reduced graph. For a given terminal 2, say v, we may construct a set, W, generated by v by first putting W = {v} and then adding vertices to W by the following rule until no more vertices are added. RULE. Add to W all vertices w E V, such that (1) w has at least one follower in W, and (2) if w’ E V, is a follower of w not in W, then there is a follower of w’ that is in W. Each set so constructed contains exactly one terminal 2. Let us denote the