Quotient semigroup presentations in misere impartial combinatorial games Thane Plambeck http://www.plambeck.org/ 15 Aug 2004 INTRODUCTION In these notes, we describe a natural quotient semigroup structure on the positions of an impartial game with fixed rules. The basic construction is the same for both normal and misere play impartial games. The theory is an algebraic one that is motivated by the effort to generalize the well-known normal-play Sprague Grundy theory to misere play. For such misere games, we've been able to write down semigroup presentations that succinctly capture information about how to play particular wild misere games. Previously unsolved games have now been resolved (see reference [2]) using such techniques. This note just presents the basic idea. We'll be assuming that the rules of such a misere game are fixed in advance. This viewpoint contrasts with the typical one in normal play: there, the Sprague-Grundy theorem says that even when we're playing a sum of games with *different* rules, this is no harder than finding their respective nim heap equivalents, and imagining that we're playing Nim on each of them, instead. In misere play, this viewpoint does not turn out to be very useful. Instead, we prefer the viewpoint that fixes a particularly nasty game on the operating table at the onset, such as Dawson's chess, Guiles, or Grundy's game. Only after the doctor has selected his victim does he begin to subject it to analysis. POSITIONS We imagine a general game to be played with several heaps of beans. Two players take turns removing beans from some selected heap according to some set of rules that govern how many beans may be taken, whether the remaining beans are allowed to be split into new heaps, etc. The game ends when no legal move is available. In normal play, the last player to make a legal move is the *winner*; in misere play, he is the *loser*. So taking the rules as fixed, a general position is a multiset of heap sizes. For example, the multiset {1,1,5,6} would represent two heaps of size 1 and one each 5 and 6. The rules will say what moves are available from such a position; what the rules are exactly doesn't concern us yet. We can think of a general position as a member of the set P = P_\infty, ie set of all all partitions of all finite integers. The rules tell us what moves are available from each position. Adding game positions corresponds to combining multisets. This is a commutative operation. It's just set unions in the multiset notation. For example {1,1,5,6} + {2,5,6,6} = {1,1,5,5,6,6}. THE SEMIGROUP Thinking of positions as multisets as described above, we define a relation q ~ r on positions in P. Specifically, q~r iff for every position in p in P, q+p has the same outcome as r+p. Ie, it has to be that both q+p and r+p are N positions, or are both P positions, no matter what game p we choose to add to both. It should be observed that the p's to be considered in this definition are only those *that arise as sums in the game under analysis*. We specifically exclude general misere game positions that do not actually arise in the game under analysis. Of course, when we begin an analysis, it's not apriori clear what misere games will arise as such sums, but that turns out not to be so important. The relation ~ an equivalence relation on P. (Simple check). Do the elements of a particular congruence class all have the same outcome? Yes, by definition---just take p to be the empty position (ie, zero) in the definition. So each class can be thought of as carrying a big stamp labelled "P" (previous player wins in best play for all positions in this class) or "N" (next player wins). Since we're interested in finding strategies, regardless of what fancy semigroup notation or language we bring to bear on this problem, we want to preserve such information about how to play the game. Q: Is there a useful notion of a quotient with respect to this equivalence relation? A: Yes. It's an equivalence relation. The set of all classes is our quotient set. Q: Does it make sense to think of a semigroup on the quotient? A: Yes. The Lallement book (see References, [1], below) defines a "congruence" on a semigroup S as an equivalence relation ~ on S that is stable under left and right multiplication. Ie, need to have for all x,y,z in S, x ~ y implies xz ~ yz AND x ~ y implies zx ~ zy. Is that true in our example? Yes. Proof: x ~ y means that for all w, x+w and y+w have the same outcome. (*) Now consider xz and yz. Is it true that xz ~ yz? To show that, we need to prove that for all t, xzt and yzt have the same outcome. But that has to be true, just put let w = zt and apply (*). So our relation ~ is a congruence on the semigroup of all positions, and it induces a semigroup structure on the set of its congruence classes. This is called the quotient of S by ~, and it's the object of interest to us. So, for misere games---and also for normal play games, since we've never really used the fact that we're interested in misere games in the definition---we've got an interesting question here, what do these quotient semigroups look like? For a normal play game, the equivalence classes are in correspondence with the Sprague-Grundy nim values that occur in the game. The quotient semigroup is isomorphic to a direct product of Z_2's. If the game is known to have a bounded nim sequence, a finite number of Z_2's appear in the direct product. For example, suppose I'm playing a sum of nim heaps of size one or two in normal play. The quotient semigroup is presented by {a,b | a^2=b^2=1 }. This is a four element semigroup (in fact it is more than that---a group, not just a semigroup). It's Z_2 \cross Z_2, and the elements are just are old friends {*0, *1, *2, *3}. In passing from additive notation used in CGT to multiplicative notation that is more convenient in semigroups the 'identity' of the game (ie *0, or zero) becomes a multiplicative 1. We haven't really learned anything that we didn't know already from the Sprague Grundy theory. But now let's do the same thing for a misere quotient semigroup. Let's write down the presentation for misere Nim played with heaps of size 1 and 2 only. How many equivalence classes are there? Remember, two elements are in the same equivalence class only if there's nothing that can distinguish between them. We can divide up the different types of position like this {1, 1.1.1, 1.1.1.1.1, ... } = D(1) = odd # of heaps of size 1 only = 2nd player win. {-, 1.1, 1.1.1.1, ... } = E(1) = 1st player win. {2.2, 2.2.2.2, ... } = 2.2 E(2) = 2nd player win. {2, 2.2.2, 2.2.2.2.2, ...} = D(2) = 1st player win. Are these exactly the congruence classes? No, since they don't even exhaust all positions. We've ignored the ones that have both 1's and 2's in them. There are really 3x3 = 9 raw classes, corresponding to each of these choices zero, odd, or even+ number of 1's zero, odd, or even+ number of 2's. ["even+" means 2 or 4 or 6 ... ] The question is, which of these are truly distinguishable? Draw up a table. #1's #2's genus ====================== 0 0 {0, {1, 2, 0}} D 0 {1, {0, 3, 1}} E+ 0 {0, {1, 2, 0}} 0 D {2, {2, 0}} D D {3, {3, 1}} E+ D {2, {2, 0}} 0 E+ {0, {0, 2}} D E+ {1, {1, 3}} E+ E+ {0, {0, 2}} There are six possible genera: {0, {1, 2, 0}} {1, {0, 3, 1}} {2, {2, 0}} {3, {3, 1}} {0, {0, 2}} {1, {1, 3}} And we can write out a multiplication table. (Exercise) The genus values suggest that we can perhaps identify two classes from each of the three groups in the table. In the top group, E(1) and the empty position are identified. In the next group, the two position types of genus {2, {2, 0}} are identified. Similarly, we can identify the {0, {0, 2}} genus positions in the final group of three. In fact this is correct. We haven't really said enough to prove that our claims are valid (Exercise), but they are. The resulting presentation of the quotient semigroup is {a,b | ab= ba, a^2=1, b^3 = b}. This is a six element semigroup. The correspondence is a <-> nim heap of size 1 b <-> nim heap of size 2 In other words, in passing from normal play to misere play, we had to replace the equation b^2=1 with b^3=b in order to present the quotient semigroup. The elements of the misere quotient semigroup are 1 (ie, the empty position), a, b, b^2, ab, and ab^2. References [1] Gerard Lallement, "Semigroups and Combinatorial Applications", Wiley Interscience 1979. [2] Misere Games. (Web site with many misere game solutions and more references) http://www.plambeck.org/oldhtml/mathematics/games/misere